基於粒子群演算法最優選址問題總結

1. 粒子群演算法的優缺點

優點：PSO同遺傳演算法類似，是一種基於迭代的優化演算法。系統初始化為一組隨機解，通過迭代搜尋最優值。同遺傳演算法比較，PSO的優勢在於簡單容易實現，並且沒有許多參數需要調整。

缺點：在某些問題上性能並不是特別好。網路權重的編碼而且遺傳運算元的選擇有時比較麻煩。最近已經有一些利用PSO來代替反向傳播演算法來訓練神經網路的論文。

(1)基於粒子群演算法最優選址問題總結擴展閱讀：

注意事項：

基礎粒子群演算法步驟較為簡單。粒子群優化演算法是由一組粒子在搜索空間中運動，受其自身的最佳過去位置pbest和整個群或近鄰的最佳過去位置gbest的影響。

對於有些改進演算法，在速度更新公式最後一項會加入一個隨機項，來平衡收斂速度與避免早熟。並且根據位置更新公式的特點，粒子群演算法更適合求解連續優化問題。

2. 粒子群演算法的演算法介紹

如前所述，PSO模擬鳥群的捕食行為。設想這樣一個場景：一群鳥在隨機搜索食物。在這個區域里只有一塊食物。所有的鳥都不知道食物在那裡。但是他們知道當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢。最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。
PSO從這種模型中得到啟示並用於解決優化問題。PSO中，每個優化問題的解都是搜索空間中的一隻鳥。我們稱之為「粒子」。所有的粒子都有一個由被優化的函數決定的適應值(fitness value)，每個粒子還有一個速度決定他們飛翔的方向和距離。然後粒子們就追隨當前的最優粒子在解空間中搜索。
PSO 初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己。第一個就是粒子本身所找到的最優解，這個解叫做個體極值pBest。另一個極值是整個種群目前找到的最優解，這個極值是全局極值gBest。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那麼在所有鄰居中的極值就是局部極值。 在找到這兩個最優值時，粒子根據如下的公式來更新自己的速度和新的位置：
v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = present[] + v[] (b)
v[] 是粒子的速度, w是慣性權重,present[] 是當前粒子的位置. pbest[] and gbest[] 如前定義 rand () 是介於（0， 1）之間的隨機數. c1, c2 是學習因子. 通常 c1 = c2 = 2.
程序的偽代碼如下
For each particle
____Initialize particle
END
Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End
____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained
在每一維粒子的速度都會被限制在一個最大速度Vmax，如果某一維更新後的速度超過用戶設定的Vmax，那麼這一維的速度就被限定為Vmax

3. 標准粒子群優化演算法的速度和位置更新方式

1、需要更新速度以及位置速度更新公式：v(i)=v(i)w+c1rand*(pbest(i)-x(i))+c2*rand(gbest(i)-x(i))。
2、速飢磨度更新公式由三部分組成：之前的速度影響v(i)*w，個體最優影響（pbest(i)-x(i)）和全局最優的影響(gbest(i)-x(i))則位置更新公式為：x(i)=x(i)+v(i）。
3、其中爛運斗，i指的是種群中的第i個粒子x(i)：粒子i的位置，剛開始應該給粒子隨機初始化位置v(i)：粒子i的速度，剛開始應該給粒子隨機初始化速度c1是粒子個體的學習因子，c2是粒子的群體學習因子，表示個體最優和群體悄櫻最優的影響，w為慣性因子，代表了歷史成績的影響pbest和gbest分別代表粒子個體最優位置和群體最優位置。

4. 關於粒子群演算法的問題

粒子群的版本甚多，常用的是加有慣性權重w的
v[] = w * v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[])
一般選擇慣性權重在迭代過程中線性下降，目的是在迭代的初期，以比較大的權重分配給粒子的原速度，而防止粒子過早的傾向於其本身的局部最優與全局最優，此時的全局搜索能力是可以的。但粒子群是基於牛頓力學的，隨著w的減小，速度v的作用會在更新中弱化，對應的是，pbest和gbest的作用得到了加強，這也就意味著，粒子會更加趨向於pbest和gbest的方向移動。這個時候粒子就特別容易陷入局部最優了。

其實陷入局部最優不只是粒子群的問題，進化類的演算法都存在這個問題，只不過有些演算法隨機性強一些，收斂速度慢一些，所以更加容易跳出局部最優（但不是絕對避免）

5. 粒子群演算法簡單介紹

粒子群演算法（也稱粒子群優化演算法（particle swarm optimization, PSO）），模擬鳥群隨機搜索食物的行為。粒子群演算法中，每個優化問題的潛在解都是搜穗穗索空間中的一隻鳥，叫做「粒子」。所有的粒子都有一個由被優化的函數決定的適應值（fitness value），每個粒子還有一個速度決定它們「飛行」的方向和距離。

粒子群演算法初始化為一群隨機的粒子（隨機解），然後根據迭代找到最優解。每一次迭代中，粒子通過跟蹤兩個極敏擾值來更新自己：第1個是粒子本身所找到的最優解，這個稱為個體極值；第2個是整個種群目前找到的最優解，這個稱為全局極值。也可以不用整個種群，而是用其中的一部分作為粒子的鄰居猜拿卜，稱為局部極值。

假設在一個D維搜索空間中，有N個粒子組成一個群落，其中第i個粒子表示為一個D維的向量：

第i個粒子的速度表示為：

還要保存每個個體的已經找到的最優解 ，和一個整個群落找到的最優解 。

第i個粒子根據下面的公式更新自己的速度和位置：

其中， 是個體已知最優解， 是種群已知最優解， 為慣性權重， , 為學習因子（或加速常數 acceleration constant)， , 是[0,1]范圍內的隨機數。

式(1)由三部分組成：

6. 粒子群優化演算法

         粒子群演算法 的思想源於對鳥/魚群捕食行為的研究，模擬鳥集群飛行覓食的行為，鳥之間通過集體的協作使群體達到最優目的，是一種基於Swarm Intelligence的優化方法。它沒有遺傳演算法的「交叉」(Crossover) 和「變異」(Mutation) 操作，它通過追隨當前搜索到的最優值來尋找全局最優。粒子群演算法與其他現代優化方法相比的一個明顯特色就是所 需要調整的參數很少、簡單易行 ，收斂速度快，已成為現代優化方法領域研究的熱點。

         設想這樣一個場景：一群鳥在隨機搜索食物。已知在這塊區域里只有一塊食物；所有的鳥都不知道食物在哪裡；但它們能感受到當前的位置離食物還有多遠。那麼找到食物的最優策略是什麼呢？

        1. 搜尋目前離食物最近的鳥的周圍區域

        2. 根據自己飛行的經驗判斷食物的所在。

        PSO正是從這種模型中得到了啟發，PSO的基礎是 信息的社會共享

        每個尋優的問題解都被想像成一隻鳥，稱為「粒子」。所有粒子都在一個D維空間進行搜索。

        所有的粒子都由一個fitness function 確定適應值以判斷目前的位置好壞。

        每一個粒子必須賦予記憶功能，能記住所搜尋到的最佳位置。

        每一個粒子還有一個速度以決定飛行的距離和方向。這個速度根據它本身的飛行經驗以及同伴的飛行經驗進行動態調整。

        粒子速度更新公式包含三部分： 第一部分為「慣性部分」，即對粒子先前速度的記憶；第二部分為「自我認知」部分，可理解為粒子i當前位置與自己最好位置之間的距離；第三部分為「社會經驗」部分，表示粒子間的信息共享與合作，可理解為粒子i當前位置與群體最好位置之間的距離。

        第1步   在初始化范圍內，對粒子群進行隨機初始化，包括隨機位置和速度

        第2步   根據fitness function，計算每個粒子的適應值

        第3步   對每個粒子，將其當前適應值與其個體歷史最佳位置（pbest）對應的適應值作比較，如果當前的適應值更高，則用當前位置更新粒子個體的歷史最優位置pbest

        第4步   對每個粒子，將其當前適應值與全局最佳位置（gbest）對應的適應值作比較，如果當前的適應值更高，則用當前位置更新粒子群體的歷史最優位置gbest

        第5步   更新粒子的速度和位置

        第6步   若未達到終止條件，則轉第2步

        【通常演算法達到最大迭代次數或者最佳適應度值得增量小於某個給定的閾值時演算法停止】

粒子群演算法流程圖如下：

以Ras函數（Rastrigin's Function）為目標函數，求其在x1,x2∈[-5,5]上的最小值。這個函數對模擬退火、進化計算等演算法具有很強的欺騙性，因為它有非常多的局部最小值點和局部最大值點，很容易使演算法陷入局部最優，而不能得到全局最優解。如下圖所示，該函數只在(0,0)處存在全局最小值0。

7. 分析標准粒子群演算法的不足及改進的方法

一個以上的目標，以優化
相對傳統的多目標優化方法在解決多目標問題，PSO具有很大的優勢。首先，PSO演算法和高效的搜索功能，有利於在這個意義上，多目標的最優解;其次，PSO代表了整個解決方案的人口集固有的並行性，同時搜索多個非劣解，所以容易搜索多個Pareto最佳的解決方案;此外，PSO通用的適合處理所有類型的目標函數和約束條件，PSO容易與傳統相結合的方法，和然後提出了有效的方法來解決一個具體的問題。 PSO本身，為了更好地解決多目標優化問題，必須解決的問題的全局最優粒子和個人選擇的最優粒子。為全局最優粒子的選擇，一方面，該演算法具有更好的收斂速度，另一方面帕累托邊界分散體的溶液中。如果在最佳的單個顆粒的選擇，需要較少的計算復雜性，並且是僅由較少數量的比較非
劣解更新。迄今為止，基於PSO的多目標優化，主要有以下
思路：
（1）向量法和加權方法。文獻[20]的固定權重法，自適應權重法和向量評估方法的第一次，PSO解決MO問題。然而，對於一個給定的優化問題，權重的方法通常是很難獲得一組合適的權重向量評價方法MO的問題是，往往無法得到滿意的解決方案。
（2）基於Pareto方法。 [21]帕累托排序機制和PSO相結合，處理的問題，多目標優化，Pareto排序方法來選擇一組的精英，和輪盤賭選擇全局最優粒子。雖然輪盤賭選擇機制，使所有的帕累托個人選擇的概率是一樣的，但實際上只有少數人的選擇的概率就越大，因此不利於保持種群多樣性;文獻[22]通過引入在PSO帕累托競爭機制，選擇全局最優粒子的顆粒知識基礎。候選個人隨機選自人口比較集進行比較，以確定非劣解，該演算法的成功取決於比較集的大小的參數設置。如果這個參數是太小了，選擇的過程，從人口的非劣效性個人可能是太小了，如果這個參數是太大，它可能會出現過早收斂。
（3）距離的方法。 [23]，被分配的各個的當前的解決方案之間的距離的基礎上Pa2reto的解決方案，其適應值，以便選擇全局最優粒子。隨著距離的方法需要被初始化潛在的解決方案，如果初始電位值太大，不同的解決方案，以適應不同的值並不顯著。這將導致在選擇壓力太小或個別均勻分布，導致在PSO演算法收斂速度非常慢。
（4）附近的「。文獻[24]提出了動態鄰域的選擇策略，為優化目標的定義，目標，和其他所有的目標定義的目標附近，然後選擇全局最優粒子的動態鄰域的策略，但該方法更敏感的目標函數的優化目標選擇和附近的排序。
（5）多組法。文獻[25]的人口劃分成多個子群，以及每個子群PSO演算法，通過搜索Pareto最優解的各種子群之間的信息交流。然而，由於需要增加的粒子的數量增加的計算量。
（6）非排名的方法。 [26]使用非主導的排序選擇全局最優的粒子。整個人口，粒子的個人最好成績粒子和它的後代，有利於提供一個適當的選擇壓力，小生境技術，以增加種群多樣性。比較所有粒子的個人最好成績顆粒在整個人群遺傳給後代，但是，由於其本身的性質是不利於人口的多樣性，容易形成早熟。此外，文獻[27]最大最小策略，博弈論引入PSO解決多MO。最大最小策略，以確定粒子的適應值，可以判斷帕累托最優的解決方案，而不需要集群和小生境技術。
2約束優化
在最近幾年也取得了一些進展，PSO演算法在約束最優化。基於PSO-的約束優化工作分為兩種類型：①罰函數法;②設計特定的進化操作或約束修正系數。 [28]採用罰函數法，採用非固定多段映射罰函數將約束的優化問題，然後利用PSO解決問題的轉換後，模擬結果表明，該演算法相對進化策略和遺傳演算法的優勢，但罰函數的設計過於復雜，不利於解決;文獻[29]，一個可行的解決方案，保留策略處理約束，即，一方面要更新所有的顆粒的存儲區域中到只保留可行的解決方案，在另一方面在初始化階段的所有的顆粒從一個可行的解決方案的空間值？初始的可行的解決方案空間，然而，是難以確定的很多問題，文獻[30 ]提出的多層信息共享策略粒子群與約束原則來處理，根據約束矩陣多層Pareto排序機制的微粒，從而一些微粒，以確定個人的搜索方向的其餘。
3離散優化為離散優化解決方案空間是離散點的集合，而不是連續PSO解決離散優化問題，必須予以糾??正的速度和位置更新公式，或變形。基於PSO的離散優化可分為以下三類：
速度（1）的位置變化的概率。 [31]首先提出了離散二進制PSO。二進制粒子的位置編碼器，Sigmoid函數，速度約束在[0，1]，代表粒子的概率立場;法[32] [31]在文獻
提高的地址更換安排。安排更換顆粒，速度是指根據兩個粒子的相似性，以確定粒子的位置變化也引入突變操作，以防止陷入局部極小的最優粒子的概率。
（2）重新定義的PSO的操作。 [33]通過重新定義粒子的位置，速度，和他們的加法和減法乘法運算，提出了一種新的離散粒子群，並為解決旅行商問題。雖然該演算法是有效的，但它提供了一種新的思維方式求解組合優化問題。
（3）連續PSO離散的情況下。 [34]採用連續PSO，解決分布式計算機任務的分配問題。於實數被轉換為一個正整數，和符號的實數部分和小數部分的
分除去。結果表明，在溶液中的質量和速度的方法的演算法是優於遺傳演算法。
4動態優化
在許多實際工程問題，優化環境是不確定的，或動態。因此，優化演算法必須有能力與環境的動態變化做出相應的調整，以最佳的解決方案，該演算法具有一定的魯棒性。 [35]首次提出了PSO跟蹤動態系統[36]提出了自適應PSO自動跟蹤動態系統的變化，種群粒子檢測方法和粒子重新初始化PSO系統變化的跟蹤能力增強;文獻[37]迅速變化的動態環境中，在粒子速度更新公式的變化條目的增加，消除了需要在環境中的變化來檢測，可以跟蹤環境處理。雖然該研究少得多，但不容質疑的，是一個重要的研究內容。

粒子群演算法的MATLAB程序

初始化粒子群;

對於每個粒子
計算他們的身體健康;
如果（健身優於粒子的歷史最好值）
歷史最好的個人裨錫更新;

如果選擇當前粒子群粒子;（當前的最優粒子比歷史最好粒子組）
與目前最好的粒子更新PG組;對於每個粒子

更新粒子類型①速度;
更新的位置粒子類型②;
完
雖然還沒有達到最大迭代次數，或不符合的最小誤差。