群優化演算法

『壹』 粒子群優化演算法

姓名：楊晶晶  學號：21011210420  學院：通信工程學院

【嵌牛導讀】

傳統的多目標優化方法是將多目標問題通過加權求和轉化為單目標問題來處理的,而粒子演算法主要是解決一些多目標優化問題的（例如機械零件的多目標設計優化）,其優點是容易實現,精度高,收斂速度快。

【嵌牛鼻子】粒子群演算法的概念、公式、調參以及與遺傳演算法的比較。

【嵌牛提問】什麼是粒子群演算法？它的計算流程是什麼？與遺傳演算法相比呢？

【嵌牛正文】

1. 概念

        粒子群優化演算法(PSO：Particle swarm optimization) 是一種進化計算技術（evolutionary computation），源於對鳥群捕食的行為研究。

        粒子群優化演算法的基本思想：是通過群體中個體之間的協作和信息共享來尋找最優解。

        PSO的優勢：在於簡單容易實現並且沒有許多參數的調節。目前已被廣泛應用於函數優化、神經網路訓練、模糊系統控制以及其他遺傳演算法的應用領域。

2. 演算法

2.1 問題抽象

        鳥被抽象為沒有質量和體積的微粒(點)，並延伸到N維空間，粒子i在N維空間的位置表示為矢量Xi＝(x1，x2，…，xN)，飛行速度表示為矢量Vi＝(v1，v2，…，vN)。每個粒子都有一個由目標函數決定的適應值(fitness value)，並且知道自己到目前為止發現的最好位置(pbest)和現在的位置Xi。這個可以看作是粒子自己的飛行經驗。除此之外，每個粒子還知道到目前為止整個群體中所有粒子發現的最好位置(gbest)(gbest是pbest中的最好值)，這個可以看作是粒子同伴的經驗。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。

2.2 更新規則

      PSO初始化為一群隨機粒子(隨機解)。然後通過迭代找到最優解。在每一次的迭代中，粒子通過跟蹤兩個「極值」(pbest，gbest)來更新自己。在找到這兩個最優值後，粒子通過下面的公式來更新自己的速度和位置。

      公式(1)的第一部分稱為【記憶項】，表示上次速度大小和方向的影響；公式(1)的第二部分稱為【自身認知項】，是從當前點指向粒子自身最好點的一個矢量，表示粒子的動作來源於自己經驗的部分；公式(1)的第三部分稱為【群體認知項】，是一個從當前點指向種群最好點的矢量，反映了粒子間的協同合作和知識共享。粒子就是通過自己的經驗和同伴中最好的經驗來決定下一步的運動。

      以上面兩個公式為基礎，形成了PSO的標准形式。

      公式(2)和 公式(3)被視為標准PSO演算法。

2.3 標准PSO演算法流程

    標准PSO演算法的流程：

    1）初始化一群微粒(群體規模為N)，包括隨機位置和速度；

    2）評價每個微粒的適應度；

    3）對每個微粒，將其適應值與其經過的最好位置pbest作比較，如果較好，則將其作為當前的最好位置pbest；

    4）對每個微粒，將其適應值與其經過的最好位置gbest作比較，如果較好，則將其作為當前的最好位置gbest；

    5）根據公式(2)、(3)調整微粒速度和位置；

    6）未達到結束條件則轉第2）步。

        迭代終止條件根據具體問題一般選為最大迭代次數Gk或(和)微粒群迄今為止搜索到的最優位置滿足預定最小適應閾值。

      公式(2)和(3)中pbest和gbest分別表示微粒群的局部和全局最優位置。

    當C1＝0時，則粒子沒有了認知能力，變為只有社會的模型(social-only)：

被稱為全局PSO演算法。粒子有擴展搜索空間的能力，具有較快的收斂速度，但由於缺少局部搜索，對於復雜問題

比標准PSO 更易陷入局部最優。

    當C2＝0時，則粒子之間沒有社會信息，模型變為只有認知(cognition-only)模型：

      被稱為局部PSO演算法。由於個體之間沒有信息的交流，整個群體相當於多個粒子進行盲目的隨機搜索，收斂速度慢，因而得到最優解的可能性小。

2.4 參數分析

        參數：群體規模N，慣性因子 ，學習因子c1和c2，最大速度Vmax，最大迭代次數Gk。

        群體規模N：一般取20～40，對較難或特定類別的問題可以取到100～200。

        最大速度Vmax：決定當前位置與最好位置之間的區域的解析度(或精度)。如果太快，則粒子有可能越過極小點；如果太慢，則粒子不能在局部極小點之外進行足夠的探索，會陷入到局部極值區域內。這種限制可以達到防止計算溢出、決定問題空間搜索的粒度的目的。

        權重因子：包括慣性因子和學習因子c1和c2。使粒子保持著運動慣性，使其具有擴展搜索空間的趨勢，有能力探索新的區域。c1和c2代表將每個粒子推向pbest和gbest位置的統計加速項的權值。較低的值允許粒子在被拉回之前可以在目標區域外徘徊，較高的值導致粒子突然地沖向或越過目標區域。

        參數設置：

        1)如果令c1＝c2＝0，粒子將一直以當前速度的飛行，直到邊界。很難找到最優解。

        2)如果＝0，則速度只取決於當前位置和歷史最好位置，速度本身沒有記憶性。假設一個粒子處在全局最好位置，它將保持靜止，其他粒子則飛向它的最好位置和全局最好位置的加權中心。粒子將收縮到當前全局最好位置。在加上第一部分後，粒子有擴展搜索空間的趨勢，這也使得的作用表現為針對不同的搜索問題，調整演算法的全局和局部搜索能力的平衡。較大時，具有較強的全局搜索能力；較小時，具有較強的局部搜索能力。

        3)通常設c1＝c2＝2。Suganthan的實驗表明：c1和c2為常數時可以得到較好的解，但不一定必須等於2。Clerc引入收斂因子(constriction factor) K來保證收斂性。

      通常取為4.1,則K＝0.729.實驗表明，與使用慣性權重的PSO演算法相比，使用收斂因子的PSO有更快的收斂速度。其實只要恰當的選取和c1、c2，兩種演算法是一樣的。因此使用收斂因子的PSO可以看作使用慣性權重PSO的特例。

        恰當的選取演算法的參數值可以改善演算法的性能。

3. PSO與其它演算法的比較

3.1 遺傳演算法和PSO的比較

  1)共性：

  (1)都屬於仿生演算法。

  (2)都屬於全局優化方法。

  (3)都屬於隨機搜索演算法。

  (4)都隱含並行性。

  (5)根據個體的適配信息進行搜索，因此不受函數約束條件的限制，如連續性、可導性等。

  (6)對高維復雜問題，往往會遇到早熟收斂和收斂 性能差的缺點，都無法保證收斂到最優點。

    2)差異：   

    (1)PSO有記憶，好的解的知識所有粒子都保 存，而GA（Genetic Algorithm），以前的知識隨著種群的改變被改變。

    (2)PSO中的粒子僅僅通過當前搜索到最優點進行共享信息，所以很大程度上這是一種單共享項信息機制。而GA中，染色體之間相互共享信息，使得整個種群都向最優區域移動。

    (3)GA的編碼技術和遺傳操作比較簡單，而PSO相對於GA，沒有交叉和變異操作，粒子只是通過內部速度進行更新，因此原理更簡單、參數更少、實現更容易。

    (4)應用於人工神經網路(ANN)

    GA可以用來研究NN的三個方面：網路連接權重、網路結構、學習演算法。優勢在於可處理傳統方法不能處理的問題，例如不可導的節點傳遞函數或沒有梯度信息。

    GA缺點:在某些問題上性能不是特別好；網路權重的編碼和遺傳運算元的選擇有時較麻煩。

    已有利用PSO來進行神經網路訓練。研究表明PSO是一種很有潛力的神經網路演算法。速度較快且有較好的結果。且沒有遺傳演算法碰到的問題。

『貳』 粒子群優化的演算法參數

PSO參數包括：群體規模m，慣性權重w，加速常數c1和c2，最大速度Vmax，最大代數Gmax，解空間[Xmin Xmax]。
Vmax決定在當前位置與最好位置之間的區域的解析度（或精度）。如果Vmax太高，微粒可能會飛過好解，如果Vmax太小，微粒不能進行足夠的探索，導致陷入局部優值。該限制有三個目的：防止計算溢出；實現人工學習和態度轉變；決定問題空間搜索的粒度。
慣性權重w使微粒保持運動的慣性，使其有擴展搜索空間的趨勢，有能力探索新的區域。
加速常數c1和c2代表將每個微粒推向pbest和gbest位置的統計加速項的權重。低的值允許微粒在被拉回來之前可以在目標區域外徘徊，而高的值導致微粒突然的沖向或者越過目標區域。
如果沒有後兩部分，即c1 = c2 = 0，微粒將一直以當前的速度飛行，直到到達邊界。由於它只能搜索有限的區域，將很難找到好的解。
如果沒有第一部分，即w = 0，則速度只取決於微粒當前的位置和它們歷史最好位置pbest和gbest，速度本身沒有記憶性。假設一個微粒位於全局最好位置，它將保持靜止。而其它微粒則飛向它本身最好位置pbest和全局最好位置gbest的加權中心。在這種條件下，微粒群將統計的收縮到當前的全局最好位置，更象一個局部演算法。
在加上第一部分後，微粒有擴展搜索空間的趨勢，即第一部分有全局搜索的能力。這也使得w的作用為針對不同的搜索問題，調整演算法全局和局部搜索能力的平衡。
如果沒有第二部分，即c1 = 0，則微粒沒有認知能力，也就是「只有社會(social-only)」的模型。在微粒的相互作用下，有能力到達新的搜索空間。它的收斂速度比標准版本更快，但是對復雜問題，比標准版本更容易陷入局部優值點。
如果沒有第三部分，即c2 = 0，則微粒之間沒有社會信息共享，也就是「只有認知(cognition-only)」的模型。因為個體間沒有交互，一個規模為m的群體等價於m個單個微粒的運行。因而得到解的幾率非常小。

『叄』 粒子群優化演算法

         粒子群演算法 的思想源於對鳥/魚群捕食行為的研究，模擬鳥集群飛行覓食的行為，鳥之間通過集體的協作使群體達到最優目的，是一種基於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。

『肆』 人工螢火蟲群優化演算法的流程是什麼

人工螢火蟲群優化演算法流程如下：
1.初始化演算法基本參數。
2.隨機初始化螢火蟲的位置，計算螢火蟲的目標函數值作為各自最大螢光亮度。
3.計算群體中螢火蟲的相對亮度I和吸引度β，根據相對亮度決定螢火蟲的移動方向。
4.更新螢火蟲的空間位置，對處在最佳位置的螢火蟲進行隨機擾動。
5.根據更新後螢火蟲的位置，重新計算螢火蟲的亮度。
6.當滿足搜索精度或達到最大搜索次數時則轉7.否則，搜索次數增加1，轉3，進行下一次搜索。
7.輸出全局最優值和個體最優值。

『伍』 pso什麼意思

PSO是粒子群優化演算法（——Particle Swarm Optimization）的英文縮寫，是一種基於種群的隨機優化技術，由Eberhart和Kennedy於1995年提出。粒子群演算法模仿昆蟲、獸群、鳥群和魚群等的群集行為，這些群體按照一種合作的方式尋找食物，群體中的每個成員通過學習它自身的經驗和其他成員的經驗來不斷改變其搜索模式。

『陸』 群智能演算法的基本思想

群智能演算法的基本思想

基本思想

群演算法的核心含義就是模擬各種動物或者事物群體的一種尋優過程，群優化演算法通過設計一種無質量的粒子來模擬消陸各種動物群中的個體，個體僅具有兩個屬性：速度和位置，速度代表移動的快慢，位置代表移動的方向。每個單體在搜索空間中單獨的搜尋最優解，並將其記為當前個體極值，並將個體極值與整個群里的其他個體共享，找到最優的那個單體極值作為整個群的當前全局最優解，群中的所有單體根據自己找到的當前個體極值和整個群共享的當前全局最優解來調整自己的速度和位置，該類方法一般用拿賣頃於優化問題。

很多研究生的在寫論文的時候都會用到各種優化演算法，例如粒子群演算法、蟻群演算法、遺傳演算法等。但由於這些演算法都太配鬧老，所以往往導致論文的創新度不夠，達不到期刊的發表要求，於是就衍生出了大量的新改進演算法以提高創新度。演算法改進就是一種創新，只要你改的是合理且有效的。可以引用這些優秀的改進演算法來研究自己的題目。

群智能演算法是一種新興的演化計算技術，已成為越來越多研究者的關注焦點，它與人工生命，特別是進化策略以及遺傳演算法有著極為特殊的聯系。 群智能理論研究領域主要有兩種演算法：蟻群演算法和粒子群演算法。

『柒』 粒子群演算法簡單介紹

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

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

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

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

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

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

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

式(1)由三部分組成：

『捌』 智能優化演算法：雞群優化演算法

@[toc]
摘要：雞群演算法 (Chicken Swarm Optimization，CSO) 是一種新穎的仿生學演算法，充分繼承群智能優化特點，創新採用個體分類、協作優化，最大程度挖掘最優解，又能很好避免早熟現象。具有收斂快，尋優能力強的特點。

新型的仿生學演算法—雞群優化演算法，它模擬群的等級制度和雞群的群體活動行為。 在特殊的等級制度下雞群中不同雞種搜尋食物時存在著競爭。公雞搜索食物能力強，適應值小；母雞其次；小雞搜索食物能力最弱，適應值最大。

為了簡化，文中通過下列規則理想化雞群演算法：

因為不同的雞種有不同的運動規律， 因此，以下 3 種個體的位置更新策略各不相同。

適應度好的公雞能夠在更大的范圍內搜索食物，而且比適應度差的公雞能夠優先獲得食物實現全局搜索，它的位置更新受隨機選取的其他公雞位置的影響，則更新策略見式（1）-（2）

式 (1)-(2) 中：第 只公雞位置的第 j 維的值表示為， 表示當前的迭代次數，表示服從期望值為0 ，方差值為 2 的正態分布隨機數， 第 只公雞的適應度為 ，隨機選取公雞 的適應度為 ， 分母中加上無窮小數 ，避免除數為零。

母雞跟隨夥伴公雞搜索食物，位置更新受夥伴公雞位置影響。由於母雞的偷食行為，位置更新又與其它公雞和母雞有關系，則更新策略見式 (3)-(5) 。

式 (3)-(5) 中： Rand 是一個服從 [0,1] 均勻分布的隨機數，該母雞的夥伴公雞 的適應度值為 ， 表示其夥伴公雞對其的影響因子，其他公雞和母雞中隨機選取個體 的適應度值為 ， 為其他雞對其的影響因子。

小雞在其母親周圍搜尋食物，它的搜索能力最差，位置受到母親公雞的影響，則更新策略見式 (6) 。

式 (6) 中：母親母雞 位置的第 維數值為 ， ，母親母雞的位置對小雞位置的影響因子為 ， 其為隨機函數隨機生成，取值范圍一般為 (0,2) 。

步驟如下：

[1] MENG X ， LIU Y ， GAO X Z ， et al. A new bio-inspired algorithm: chicken swarm optimization[J]. Lecture Notes in Computer Science ,2014 ,8794(1):86-94.

[2] 胡漢梅,李靜雅,黃景光.基於雞群演算法的微網經濟運行優化[J].高壓電器,2017,53(01):119-125.

https://mianbaoo.com/o/bread/aJWbmZk=

文獻復現：基於模擬退火的改進雞群優化演算法(SAICSO)
[1]李振璧,王康,姜媛媛.基於模擬退火的改進雞群優化演算法[J].微電子學與計算機,2017,34(02):30-33+38.

文獻復現：一種改進的雞群演算法(ICSO)
[1]孔飛,吳定會.一種改進的雞群演算法[J].江南大學學報(自然科學版),2015,14(06):681-688.

文獻復現:全局優化的改進雞群演算法（ECSO)
[1]韓斐斐,趙齊輝,杜兆宏,劉升.全局優化的改進雞群演算法[J].計算機應用研究,2019,36(08):2317-2319+2327.