初探進化計算--群體智能

萬物之初，天地伊始。一定程度上來說，所有物種都是從簡單至複雜進化而來。就拿我們最熟悉的自己而言，我們從兩個肉眼都看不清的細胞結合，經由偉大的母親懷胎十月，成長為一個正常的人（僅僅從生物學上來講），再經由歲月的洗禮和經歷的摩擦，被塑造成一個個具有個性的人（社會學上來講）但從學術上來看這隻能說是個人的成長，不能被稱之為進化。

達爾文將進化（evolution）建立在自然選擇的基礎上，也就是我們常說的物競天擇適者生存，以基因為基本單位發表了《物種起源》。進化，就是指種群里的遺傳性狀在世代之間的變化。就好比原本我們都是猩猩，四隻腳走路，慢慢地有一些直起腰用兩隻腳，也許他們顏值高，生存能力強健，無論如何，他們更能適應環境。

最終，兩隻腳的人類遍地都是了，我們就說發生了進化。所以實質上進化就是種群基因頻率的改變。

那現在我們把這種自下而上的進化方式現在被搬上計算機的舞台，那我今天就說一說進化計算中一個比較活躍的分支：群體智能。這是什麼鬼呢？

目前群體智能演算法一般分為兩塊：以生物進行模擬的群體智能和非生物（煙花、磁鐵、頭腦風暴等）進行模擬的群體智能。

群體智能(swarm intelligence，SI) 是指由許多簡單個體組成的群體呈現出的湧現(emergence) 行為所表現出的集體智能。

如生物群體系統有蟻群、鳥群、蜂群等。雖然他們個體的力量很小，組成方式也較為簡單，但是作為一個群體所表現出的群體行為卻有很大的智能性。

鳥群的遷徙和覓食啊，蟻群搬運食物，滾過火海等。

有人說這種行為是自組織，沒有中心控制。事實是這樣沒錯，但是在我看來

自組織是指一類現象：即設定好了系統中局域的相互作用規則，一個初始狀態混亂的系統就可以自動演化成有序的形態。所以說在局部上是有控制的，從結果上來看，群體的狀態是既定的話，個體之間互不干涉，產生交互，也就是局部個體的多個集合促成的整體，最終求解。

---------------------------------------------------優雅的分割線---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

以螞蟻群為例

初始模型，我們給每隻螞蟻定義幾條規定

1.嗅探感知：群體有合攏性，緩緩移動，但互不碰撞，每隻螞蟻都能夠通過感官去感知周邊環境。

2.合作分工：在面對大規模的食物時，它們會呼喚其他同伴來合作。此外，還會有具體分工，如尋路，分班搬運等。

3.信息交流：通過個體的信息交互，可以告知各個同伴自己乃至整個環境的狀態。

4.突變應變：有敵人或者對自身群體產生威脅的東西時，會急速分散以躲避（有障礙會分路再集合）或者集簇（成團），方向朝向排斥。

這樣模擬下來，我們會發現群體湧現出來的結果彷彿就是真實的蟻群情況。

我們拿搜尋食物具體討論。

其步驟為:

(1) 隨機初始螞蟻群體位置。

Init X_ant

Init Y_ant

(2) 個體利用嗅覺搜尋食物的隨機方向與距離。

Xi= X_ant + Random

Yi= Y_ant + Random

(3) 由於無法得知食物位置，因此先估計與原點的距離(Distance)，再計算

味道濃度判定值(S)，此值為距離的倒數。

Distance=sqrt(X_i^2+Y_i^2 )；

Si=1/Distance

(4) 味道濃度判定值(S)代入味道濃度判定函數以求出個體位置的味道濃度(Smell)。

Smell = F(S)

(5) 找出此群體的中味道濃度最高的螞蟻(求極大值)

[bestSmell bestIndex] = max(Smell)

(6) 保留最佳味道濃度值與x、y 坐標，此時群體利用規定一移動過去。

Smellbest = bestSmell

X_ant = X(bestIndex)

Y_ant = Y(bestIndex)

(7) 進入迭代尋優，重複執行2-5，並判斷味道濃度是否優於前一迭代味道濃度，若是則執行6。

最後再給大家貼一下進化演算法的一般步驟，詳情可以參照博客：[Evolutionary Algorithm] 進化演算法簡介

Step 1 種群初始化：根據問題特性設計合適的初始化操作（初始化操作應盡量簡單，時間複雜度不易過高）對種群中的N個個體進行初始化操作；

Step 2 個體評價：根據優化的目標函數計算種群中個體的適應值（fitness value）；

Step 3 迭代設置：設置種群最大迭代次數gmax，並令當前迭代次數g=1；

Step 4 個體選擇：設計合適的選擇運算元來對種群P(g)個體進行選擇，被選擇的個體將進入交配池中組成父代種群FP(g)，用於交叉變換以產生新的個體。選擇策略要基於個體適應值來進行，假如要優化的問題為最小化問題，那麼具有較小適應值的個體被選擇的概率相應應該大一些。常用的選擇策略有輪盤賭選擇，錦標賽選擇等。

Step 5 交叉運算元：根據交叉概率pm（預先指定，一般為0.9）來判斷父代個體是否需要進行交叉操作。交叉運算元要根據被優化問題的特性來設計，它是整個遺傳演算法的核心，它被設計的好壞將直接決定整個演算法性能的優劣。

Step 6 變異運算元：根據變異概率pc（預先指定，一般為0.1）來判斷父代個體是否需要進行變異操作。變異運算元的主要作用是保持種群的多樣性，防止種群陷入局部最優，所以其一般被設計為一種隨機變換。

通過交叉變異操作以後父代種群FP(g)生成了新的子代種群P(g+1)，令種群迭代次數g=g+1，進行下一輪的迭代操作（跳轉到Step 4），直至迭代次數達到最大的迭代次數。

可以說這種自下而上，甚至脫離了一般數學的普遍態的研究方法還是很有趣的。大家有什麼想法可以隨意cue我哦~~