Python — 螢火蟲演算法(Firefly Algorithm, FA)求解最佳化問題
螢火蟲演算法(Firefly Algorithm, FA)是由劍橋大學的楊新社教授提出的群體智能演算法。靈感主要來源自螢火蟲的閃爍行為，並將閃光做為一信號系統，以吸引其他螢火蟲。
螢火蟲演算法（以下通稱 FA）就像 PSO、GA、ABC 等等演算法，是模仿自然界中動物行為所設計的演算法。其優點為參數少、易理解和容易實現，缺點為容易陷入局部最佳解，尤其是在解決更高維度的多維問題時更容易發生。
本文除了針對 FA 本身進行參數、步驟的說明外，也會以 Rastrigin function 最佳化問題為例，使用 FA 進行演示。針對 FA 易陷入局部最佳解 (Local Optimum) 的問題，網路上有其他文章說明 FA 的優化或是混合型算法等可解決其問題，而本文文末只會針對參數的改動和加入騷擾因子等方法進行解說，其他部分就不會多做介紹。
在本文你將會學會以下技巧:
1.培養分析問題的能力。
3.以python實現簡單的演算法。
4.透過演算法解決最佳化問題。關於其他最佳化演算法，筆者也針對過 GA、ABC 等演算法進行撰寫，有興趣的讀者不妨可以查看一下。
以下正文開始～
最佳化問題
- 此次求解最佳化問題為 Rastrigin function，為最佳化常用的測試函數，其最佳解為 f(0,0,…,0) = 0，公式如下：
Firefly Algorithm 的三大假設
- 螢火蟲不分性別。在不考慮求偶的情況下，便可假設任何一隻螢火蟲都可被其他螢火蟲所吸引，反之也可吸引其他螢火蟲。
- 吸引力與螢火蟲的亮度成正比。以兩隻螢火蟲來說，亮度較差的螢火蟲會被吸引移動到更亮的一個螢火蟲。但亮度會隨著距離的增加而減少。
- 隨機移動。若沒有比一個給定的螢火蟲更亮 (吸引力更大) 的螢火蟲，該螢火蟲就會隨機移動。
演算法邏輯
以下說明及 pseudocode 是維基百科的內容，針對 FA 的假設及流程已表達得非常清楚，所以我想我只要輔助說明即可。
變數定義及介紹
- N：Initial population 的大小，此變數決定初始群集內螢火蟲的個數。
- D：Dimension 維度大小，欲求解目標問題之變數數量。
- max_iter：欲進行迭代之總次數。
- β ：螢火蟲最大吸引度，通常當成吸引力常數。
- γ：為光吸收係數。
- αt：為一步長因子。
任兩隻螢火蟲的位置更新公式為：
其中：
- β exp[-γr² ](Xj-Xi )：指的是兩隻螢火蟲間的吸引度。
- r：為兩隻螢火蟲之間的距離。
- ∈t： 為一矢向量。
步驟說明
(1) 優先生成一 Initial population ，其螢火蟲數量為 N 、維度為 D。
(2) 計算各個螢火蟲的 fitness ，且任一隻螢火蟲會往較亮(fitness 較低)的螢火蟲靠近。
(3) 所有螢火蟲會與其他螢火蟲比較，並且更新位置(position)和亮度(brightness)；其 position 之更新公式為上段提及之公式。
(4) 回到 Step 2，重覆上述步驟直到找到最佳解。
Python 實作開始
Initial Population
產生初始群集，並針對群集內每隻螢火蟲進行 fitness 的計算。
- 初始參數設定為，N（5）、D（10）、max_iter（20）、β（1.0）、γ（0.0001）、αt（0.97）。
Minimum: 38.6345
進入 Firefly Algorithm 運算
將初始群集帶入 FA 中迭代，依序針對每隻螢火蟲，其會與亮度最亮 (fitness 最小) 的螢火蟲進行位置和亮度的更新，直到達到終止條件為止。
- 主要代碼如下：
經過20次的迭代後，將更新後的群集和 fitness 列出如下：
最佳解為 [ 0, 0, 0, 0, 0 ] ，其 fitness 為 0。
圖表顯示 10 隻螢火蟲已有 5 隻已達到最佳解，實務上為螢火蟲聚集再一起；若將問題降至二維，在平面上的表示則為點重疊在一起。
將結果視覺化如下，綠線為歷代迭代的最佳解：
- 透過迭代結果可知，設定 Dimension 為 5 下的結果可到達最佳 fitness 0 ，且約在第 7 次就收斂完畢了。
- 上述均為正常情況下，解決問題產生的最佳化結果；在下一段則會針對局部最佳之情形進行介紹。
局部最佳解問題
針對文章一開始有介紹到 FA 易陷入局部最佳解 (Local Optimum) 的情形，以和上述結果相同的參數進行演算，並同上述迭代 20 次後的結果，在多次試驗的情況下出現此情形：
最佳解為 [ 0, 0, 3, 0, 0 ] ，其 fitness 為 9。
落在 0 和 3 是因爲初始參數設定時，上界設定為 3、下界設定為 0 的關係。
除了第六隻螢火蟲外，其他螢火蟲之最佳解都為 9，明顯就是落入局部最佳的一個情況。
- 歷代最佳結果顯示，此次試驗於第 2 次迭代就落入局部最佳，並持續到迭代結束。
FA演算法之優化
若想要防止結果落入 local optimum 的情況，讀者不妨從以下幾個方法下去調整：
- 增加一縮減常數給 αt，使其每次更新時，位置都會有些微變動。如：給予一常數 0.97，於每次更新時， αt 都必須乘上這一常數。
- 調整 ∈t，其實在上述程式碼分享時，αt 和 ∈t 相乘時，有加入一隨機擾動因子，其介於 [0~1]；藉由此擾動因子，使螢火蟲於更新位置時，不會只固定於上下界的極值。
- 關於 FA 的優化、混合算法網上其他高手也都有提供，感興趣的讀者不妨可以自行查詢。
結語
FA 相較其他仿生演算法算是簡單的一種，其呈現的動物行為在優化過程中也較易呈現，各位讀者不妨可以將 FA 當作是仿生演算法的入門進行學習，在熟悉邏輯架構後也方便日後更快理解其他演算法。最後也謝謝各位願意花時間看到這裡，之後有機會會再多寫一些有趣的演算法供大家參考。
