群體智慧|以眾人的力量尋找更好的解|蔡崇煒 - 2

 

承接上篇...

11. 鯨魚 (Whale)

模仿座頭鯨『網狀氣泡』的獵食方法,會有圍攻獵物、網狀氣泡、搜尋的特性。網狀氣泡是結合螺旋演算法,以增強鯨魚local search的能力。

12. 人工蜂群 (Artificial Bee Colony)

模擬蜜蜂的社會階級,會有三蜜蜂分別為employed bees(僱傭蜂)、onlookers(跟隨蜂)、scouts(偵查蜂)。花蜜就是fitness value,fitness越高,onlookers會越多。Employ可能會帶著onlooker一起做搜尋,有點像是local search;scout會random的搜尋,有點像是global search

13. 帝國主義 (Imperialist)

大者恆大,小者恆小。帝國主義中,會有不同的國家,會有分帝國(fitness高)和殖民地(fitness低)。帝國與帝國之間會互間競爭,小帝國會越來越小直到此帝國沒有任何殖民地,就會被消滅,大帝國會越來強,最後只會剩下一個帝國。如果殖民地的fitness比帝國還更高,則帝國位置會和此殖民地互換,也就是帝國的值一定會比殖民地高。

14. 珊瑚礁 (Coral Reefs)

每個格子只能被一種珊瑚居住,如果有其他珊瑚想住同一個格子,珊瑚間會打架,最後贏者就佔有這個格子。基本概念,格子可以讓各個解的相似度不要太相似,但在實作中,格子數量只會限制群體總數,所以格子不是真的在解空間佔有某一區塊,所以沒有可以促進解相似度高的優點。

如果生長不好的珊瑚蟲(fitness很小),無法找到居所,他會死掉。不會全部的親代與子代都會活下去,只有能夠找到居所的珊瑚才會存活下來。有些珊瑚很幸運,都沒人跟他搶,他就會活下來。但如果他被趕走,他就要再找新的居所,或跟別人搶居所。

15. 獅群 (Lion)

模仿獅子的社會階級,會有不同家族的獅群,獅群中有公獅、母獅與幼獸。如果公幼獸成年了,會被家族趕出去,成為遊牧公獅。遊牧公獅會在草原中漫遊,並佔領其他家族,攻擊能力比較差的家族公獅,比較爛的獅子也有可能被殺死。

家族內,公獅子是不做事的,有些母獅子會去狩獵。母獅會在自己領土中狩獵,有些母獅會往內狩獵,有些母獅會往外狩獵,但還是會在自己的領土中。公獅子會在自己的領途中隨機閒晃,很像是local random walk。

母獅和公獅會有交配行為,但他們喜歡玩3P,一隻母獅會和兩隻公獅交配,這三隻獅子會為出一個三角形,而幼獅會在此三角形中誕生。有些定居的母獅,有機會改變自己的行為,有可能移居到其他家族,或變成漫遊母獅。但公獅不能自行改變自己的行為!

(三)差分進化演算法 (Differential evolution, DE)相關變形

1. 基本DE

基本DE有四個階段,分別為初始化、突變、交換、選擇,這和基因演化 (evolution)很像。每個個體可以想像成一條染色體,一條染色體上帶有D個基因,而每個染色體的基因都略有不同。這像是人由五個部位所組成(頭胸腹手腳),每個的部分都會有所差異。

突變、交換、選擇這三個階段為一個世代交替,在DE中會不同進行世代交替。突變策略有很多種,最簡單的是DE/rand/1,r1、r2、r3是隨機的個體,因此DE/rand/1會隨機挑一個個體當作基準點,再隨機挑兩個個體相減取差分。這種相減的動作,即為DE為什麼叫差分 (Differential)的原因。

親代 -- 突變 --> 突變體  -- 交換 --> 子代,親代會透過突變而產生突變體,突變體會與親代互相部分交換基因,而產生最後的子代。交換 (crossover, 又稱交聯),可以將親代和突變體融合出介於兩者的子代,這樣的機制能確保子代帶有部分親代的性質,又帶有和親代不一樣的特色。

最後選擇階段,會比較親代與子代,將較好者留下,較差者淘汰。

2. APTDE

APTDE是DE的變型體,多加入自適應群體數的概念,也就是說它的群體數會因為個體的表現而所變化。APTDE認為如果群體表現好,則代表有冗員的個體存在,必須減少差的個體;如果群體表現停滯,則需要多新增個體,以突破搜尋逆境。

因此APTDE會有一組狀態監控器,會去監控群體的表現。在減少差的個體策略中,不是單純減少最差的個體,而是會將排名轉成機率。越好的解,越不容易被淘汰,但如果菁英個體真的太衰,也是會被淘汰的喔!畢竟人品也是一種實力?

3. EPSDE

EPSDE也是DE的變型體,多加入自適應參數的概念。在DE中,會有兩個重要的參數,分別為Scaling factor (F)和Crossover rate (CR)。F為突變的比例,CR為交換的比例。EPSDE選擇突變策略、F、CR的方法只有兩種,第一、從162種組合中挑選,第二、從親代精英組合中挑選。

4. MPEDE


MPEDE也是DE的變型體,多加入多群與自適應參數的概念。多群機制中,會有獎勵機制,以擴大菁英子群的影響力。而自適應參數機制和EPSDE不同,MPEDE每群會紀錄親代菁英個體的值,並更新子群的平均值,最後用新平均值去建構高斯分佈或柯西分佈。值得注意的是MPEDE,子群的概念,除了建立在不同的突變機制外,不同子群也會有不同偏好的參數值,這是和EPSDE最大的不同。

關於DE, APTDE, EPSDE, MPEDE更詳細的細節、實驗與實作,請參考 五、相關文章3~7項

五、相關文章

  1. 群體智慧|以眾人的力量尋找更好的解|蔡崇煒 - 1
  2. 群體智慧|以眾人的力量尋找更好的解|蔡崇煒 - 2
  3. 差分進化演算法 Differential evolution - 1
  4. 差分進化演算法 Differential evolution - 2|APTDE|自適應群體
  5. 差分進化演算法 Differential evolution - 3|EPSDE、MPEDE|自適應參數、多群
  6. 差分進化演算法 Differential evolution - 4|APTDE, EPSDE, MPEDE比較結果
  7. DE, APTDE, EPSDE, MDEDE source code

留言