早期細菌趨藥性算法是一種模擬生物行為的最佳化算法,是基於Berg、Brown和Dahlquist提出的細菌趨藥性微觀模型,並且結合最新的生物學研究成果提出的。
基本介紹
- 中文名:細菌群體趨藥性算法
- 外文名:Bacterial colony chemotaxis
- 類型:細菌趨藥性微觀模型
- 基於:Berg、Brown和Dahlquist
發展過程,算法簡介,算法步驟,
發展過程
早期細菌趨藥性算法的研究是基於Berg、Brown和Dahlquist提出的細菌趨藥性微觀模型,前者分析了大腸埃希氏菌在胺基酸環境下的趨藥性,並且給出了模型參數的實驗測量值。後者研究了鼠傷寒沙門氏菌在胺基酸環境下的趨藥性,他們都給出了一個數學模型和實驗結果來證實他們的模型。Sibvue D.Muller及其同事們在此基礎上進步綜合,並且結合最新的生物學研究成果提出了細菌趨藥性算法(Bacterial Chemotaxis,BC),從國內公開發表的論文看,最先研究該算法的是浙江人學的李威武等人。作為一種新的模擬生物行為的最佳化算法,它的實現思想及進化機制和傳統的進化算法如:遺傳算法、模擬退火算法、進化策略、免疫算法等有所不同,Muller的BC算法只依賴於單個細菌的運動行為,它不斷地感受它周圍的環境變化並且只利用它過去的經驗來尋找最優點,BC算法具有較強的簡單性、魯棒性,但基本BC算法的性能只和基本的遺傳算法相當,甚至在某些情況下性能還要比一些改進的遺傳算法差。然而這種算法包含了細菌趨藥性的基本概念,最近的生物發現也提供了更多的細節和模型。 儘管已經發現細菌相互之間存在一種信息共享機制,但對於交流的方式並不是很清楚,所以,在最初的細菌趨藥性算法(BC)里一般地把細菌看作單獨的個體,不考慮他們之間的相互作用,這種細菌模型與那些群居昆蟲的相互作用模型不同(如螞蟻,蜜蜂,黃蜂或者白蟻),他們的模型被被看作是具有群體智慧型的系統,具有很強的解決問題的能力。於是,一種新的基於細菌趨藥性的擴展生物模型的最佳化方法被提出,即浙江大學李威武等人研究模擬了細菌個體間的信息傳遞與共享機制,並在基本BC算法的基礎上引入了群體互動概念,從而提出了細菌群體趨藥性算法。
算法簡介
細菌是一種單細胞生物體,是構成地球上各種高級生命體的最簡單最基本的形體,儘管簡單,但是他們可獲知周圍環境的信息,並有效的利用這些信息使自己生存下去,朝著對自己有利的環境移動,如營養豐富的區域,而逃避有毒的環境。所謂“趨向性”是指一個細胞對它周圍環境的運動反應,它會改變下一步運動的方向和持續時間,細菌通過比較兩步不同的環境屬性來得到所需要的方向信息,如果這種反應與化學物質的濃度(可以是引誘劑或驅除劑)有關,就叫做趨藥性。
細菌趨藥性算法就是從以上過程獲得靈感的而得到研究提煉出來的最佳化方法,最早由Bremermann及其同事進行,旨在利用細菌在化學引誘劑環境中的運動行為來進行函式最佳化,他們的研究表明了細菌在引誘劑環境下的應激機制和梯度下降相類似。這種算法分析了三維環境中的趨藥性,並被用於神經網路的訓練。另一種與之相類似的方法是引導加速隨機搜尋技術,這種方法被運用於飛行控制系統的最佳化和感知器最佳化。
算法步驟
1.單個細菌的描述
簡單來說,細菌對引誘劑的反應運動遵守如下的假設:
①細菌的運動軌跡是由一系列連續的直線組成,並且由運動方向和移動距離2 個參數決定。
②細菌在進行下一步運動要改變運動方向時,向左轉和向右轉的機率相同。
③細菌在各段相鄰軌跡間的夾角由機率分布來決定。
則單個細菌對應的算法步驟為:
①設定系統參數。
②選擇移動方向。
③確定移動距離。
在整個最佳化過程中,細菌僅利用它上一步或上幾步的位置信息來確定下一步的移動。一般認為這是一種隨機梯度近似的搜尋方法。
2.細菌群體信息互動模式
①尋找更優點坐標的位置。
②細菌向中心坐標移動。
③比較個體與群體移動的結果。
④改進策略。
⑤參數更新。