細菌覓食算法

細菌覓食算法(Bacterial Foraging Algorithm,BFA)[亦有稱為細菌覓食最佳化算法(Bacterial Foraging Optimization algorithm,BFO||BFOA)]由K.M.Passino於2002年基於Ecoli大腸桿菌在人體腸道內吞噬食物的行為，提出的一種新型仿生類算法。該算法因具有群體智慧型算法並行搜尋、易跳出局部極小值等優點，成為生物啟發式計算研究領域的又一熱點。
細菌覓食算法模仿大腸桿菌在人體腸道內覓食行為，屬於仿生類最佳化算法。在BFA模型中，最佳化問題的解對應搜尋空間中細菌的狀態，即最佳化函式適應值。BFA算法包括趨化(chemotaxis)、複製(reproduction)和驅散(elimination-dispersal)3個步驟。
①細菌向富養區域聚集的行為稱為趨化。在趨化過程中，細菌運動模式包括翻轉(tumble)和前進(run||swim)。細菌向任意方向移動單位步長定義為翻轉。當細菌完成一次翻轉後，若適應值得到改善，將沿同一方向繼續移動若干步，直至適應值不再改善，或達到預定的移動步數臨界值。此過程定義為前進。
②一旦生命周期結束，即達到臨界趨化次數，細菌將進行繁殖。細菌的繁殖過程遵循自然界“優勝劣汰，適者生存”原則。以趨化過程中各細菌適應值累加和為標準，較差的半數細菌死亡，較好的半數細菌分裂成兩個子細菌。子細菌將繼承母細菌生物特性，具有與母細菌相同的位置及步長。為簡化計算，可以規定複製過程中細菌總數保持不變。
③趨化過程可確保細菌的局部搜尋能力，複製過程能加快細菌的搜尋速度，但對於複雜的最佳化問題，趨化和複製無法避免細菌陷人局部極小現象發生。BFA引人驅散過程以加強算法全局尋優能力。細菌在完成一定次數的複製後，將以一定機率被驅散到搜尋空間中任意位置。