追蹤

宗宗大學

喜歡關注科學、哲學、社會、政治、教育,未來想當一位抱著理想的科學家,期許社會能夠進步。

群體智慧|以眾人的力量尋找更好的解|蔡崇煒 - 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

本文章發表於:課程

加入85

宗宗大學

國立中山大學 生物科學系

追蹤 384 鼓勵作者

喜歡關注科學、哲學、社會、政治、教育,未來想當一位抱著理想的科學家,期許社會能夠進步。

鼓勵作者

目前持有 Blink Coin: Loading..

選擇禮物


愛心

(Coin 10)

幫高調

(Coin 20)

咖啡

(Coin 30)

掌聲鼓勵

(Coin 40)

崇拜眼神

(Coin 50)

驚呆了

(Coin 60)

神人4ni

(Coin 70)

花束

(Coin 100)

鑽石

(Coin 300)

紅寶石

(Coin 500)

藍寶石

(Coin 1000)

黃寶石

(Coin 3000)


送出鼓勵



發表匿名文章不會出現你的大頭圖與名稱,你可暢所欲言,但文章內容務必遵守「佈告欄使用規範」!


回應

送出回應


想回應這篇文章嗎?也想發表文章嗎?
馬上登入來發表文章、追蹤作者、收藏文章或回應文章吧!

註冊 登入