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


一、簡介

  • 學校:國立中山大學
  • 課程:群體智慧 (Swarm Intelligence)
  • 教授:蔡崇煒
  • 系所:資訊工程所
  • 學分:3學分
  • 學期:109-2
  • 宗宗的學期總成績:A+ (90~100)


二、評分

  • 出席狀況:10%
  • 期中報告:40%
  • 期末報告:50% 

群體智慧只有兩個報告,期中報告為實作至少一個超啟發式演算法應用在函數最佳化的問題,期末報告則是針對期中的演算法做改進。改進方法至少需用到(1) 自適應 (self-adaptive)和(2)減少群體 (population reduction)。

實作語言不限,不能直接呼叫現有的超啟發式演算法API,必須要自己手刻。報告時間大約10分鐘左右,除了PPT,須附上自己的書面資料與程式碼。嚴禁抄襲,評分重點主要是演算法的想法,最佳化的結果只是參考依據。

三、老師評價

蔡崇煒
從PPT的內容,可以看出蔡老師很用心在準備課程的內容。因為課堂教的內容是以2000-2020年間所發展的超啟發式演算法為主,裡面的內容也都是出自於多篇論文,像是研討會一樣,介紹近年的論文新知。

老師的興趣是畫畫,實驗室網站的畫是他自己畫的,映入眼簾的是莎士比亞書店 (shakespeare and company),他會將他的畫放入PPT中,有出現過重機、籃球鞋、中山大學。從老師給學生的評價,可知他講話蠻客氣的,點到為止的那種,尷尬又不失禮貌的。

老師的音調我覺得還可以,音調就平穩平穩的,我是沒睡著過。下課時,老師經常會和自己實驗室的學生互動,我覺得蠻好的。至於講解上,我覺得老師的規劃與速度蠻可以的,前半學期會著重在重要的三個演算法,後期就會講比較多。由於是演算法的課程,所以PPT內會出現一些噁心的數學公式,但通常老師會在用畫圖的方式,去示意這公式的用意與演算法的核心。

題外話,今年為了因應Covid-19,後半學期的部分都採線上上課,老師使用google meet。聽他說,他的麥克風是美國雪怪牌的,真的是下重本。然後我還推坑給物件導向程設的江老師,說蔡老師的錄音品質很棒。XD

四、課程分析

(一)簡介

群體智慧簡單來說,就是依靠眾人的力量,去找到較好的解,這很像是一個民主社會。在群體智慧中,菁英的意見固然重要,但多人的意見更為重要,每個人的意見都有可能是社會進步的來源。

因此在群體智慧的演算法中樂於製造多樣的個體,個體之間會彼此學習,有的個體負責在既有成果上精進,有的個體在未知的領域中拓荒。

(二)課綱

前半學期:

Ant Colony Optimization (老方法)、Particle Swarm Optimization (老方法)、Differential Evolution (當紅炸子雞)

1. 螞蟻群演算法 (ACO)

螞蟻會透過費洛蒙來溝通,螞蟻有定量的費洛蒙,可以定時灑在路徑上 。當費洛蒙量固定,路徑越短,則費洛蒙含量越高;反之,則越低。如果螞蟻遇到叉路,會先隨機選擇,然後會得到一些資訊(費洛蒙),再利用這些資訊做出決策。雖然費洛蒙濃度高的路徑,選擇機率比較大,但不代表每隻螞蟻都會去選它,它只是大家做決策的整體機率。

2. 粒子群演算法 (PSO)

粒子群是模擬鳥類的飛行,每顆粒子都有自己的飛行速度 (v),自己會知道自己之前搜尋的最好結位置(pBest),也會知道大家之前搜尋的最好位置 (gBest)。故每次粒子的位置,會依照v, pBest, gBest三者的向量,而有所調整。也就是說粒子的移動位置,除了會受到自己的原有的速度v外,也會受到自己和大家最好的搜尋經驗影響。

3. 差分進化演算法 (DE)

模仿基因演化的概念。有限的個體,在無限的領地中,不斷世代繁衍。每個世代都會突變 (mutation)與交聯 (crossover),而產生新子代,最後較好的個體會因天擇而存活在這土地之中。

後半學期:

Firefly, Cuckoo, BAT and Flower Pollination Algorithms、Spiral, Gravitational, big bang big crunch, grey wolf、Big Bang Big CrunchOptimization, Grey Wolf Optimizer, and Whale  Optimization、Artificial Bee Colony、Coral Reefs Optimization、Intelligent Water Drops Algorithm and Hydrological Cycle Algorithm、Lion Optimization Algorithm、Imperialist Competitive Algorithm ......

4. 螢火蟲 (Firefly)

每一隻螢火蟲會和每一隻螢火蟲比較亮度(fitness),如果自己亮度較差,則會被亮度較高的螢火蟲被吸引並靠近,並更新自己的亮度。所以每一隻亮度較好的螢火蟲都會對個別螢火蟲有影響。

5. 布穀鳥 (Cuckoo )

布穀鳥是一隻很壞的鳥,他會把別人的蛋推下去,並放自己的蛋於別人的巢中,給別的鳥孵化與餵養。如果鳥發現有外來的蛋,鳥就會放棄整窩的蛋。剛出生的布穀鳥寶寶會將其他尚未孵化的蛋推出去,布穀鳥從小就開始壞XD。

6. 蝙蝠 (BAT)

初始化蝙蝠的位置和飛行速度,有一定機率在比較好的解附近做loacl search,有會有一定機率在隨機走。

7. 螺旋 (Spiral)

利用旋轉矩陣,達到有系統的區域性搜尋 (local search)。在解空間撒下一群解,各自做旋轉,然後選擇最好的。越多點,做越多local search,找到最佳解的可能越高。

8. 萬有引力 (Gravitational)

以萬有引力的概念作搜尋,不過有些更改。萬有引力演算法(GS)的概念很像是PSO。PSO只參考global and local best,而GS參考更多的點,而且越好的點影響力越好。

萬有引力常數(G)會隨著宇宙的年紀下降,G(t0)是初始的萬有引力,G(t)是現在的萬有引力,簡單來說,就是G會隨著代數下降。因此一開始大家互相牽引的力會比較大,而牽引的力量會隨著代數下降,到了後期牽引力就會下降。

每個粒子的影響力除了萬有引力F(質量與距離)外,還會乘上隨機機率randj,所以影響力還帶有隨機性。

9. 大霹靂大擠壓 (Big Bang Big Crunch)

模仿不斷爆炸與收縮的過程,一開始會隨機初始化數點,並以較好的點當作中心點往內壓縮與減少,再以中心點附近產生新點(爆炸),再以較好的點當作中心點往內壓縮與減少,不斷重複爆炸與收縮。

10. 灰狼 (Grey Wolf)

模擬灰狼的社會階級,且有圍攻獵物、攻擊、搜尋的特性。alpha, beta, delta是三隻重要的灰狼,每隻灰狼都會受這三隻最好的灰狼受到引響。

下篇連結....會繼續介紹鯨魚、人工蜂群、帝國主義、珊瑚礁、獅群、DE的三個變型體。

五、相關文章

  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

留言