智能算法|有哪些以動物命名的算法?

黃梅時節家家雨,青草池塘處處蛙。
有約不來過夜半,閑敲棋子落燈花。


魚群算法?鳥群算法?蝙蝠算法?蟻群算法?病毒算法?。。。what?這些是什么沙雕算法?

別看這些算法名字挺接地氣的,實際上確實很接地氣。。。

以動物命名的算法可遠不止這些,俗話說得好,只要腦洞大,就能玩出新花樣,這句話在啟發式算法界絕對名副其實!然鵝什么是啟發式算法呢?

啟發式算法:一個基于直觀或經驗構造的算法,在可接受的花費(指計算時間和空間)下給出待解決組合優化問題每一個實例的一個可行解,該可行解與最優解的偏離程度一般不能被預計。通俗點講就是該類算法來源于生活,用這些算法求出來的解可能不是最好的,只能說是相對較好的,但是這個相對程度就不敢保證,只要能符合工程需要就行。

實際上啟發式策略又分為啟發式和元啟發式,啟發式策略是一類在求解某個具體問題時,在可以接受的時間和空間內能給出其可行解,但又不保證求得最優解(以及可行解與最優解的偏離)的策略的總稱。許多啟發式算法是相當特殊的,依賴于某個特定問題。元啟發式通常是一個通用的啟發式策略,他們通常不借助于某種問題的特有條件,從而能夠運用于更廣泛的方面。許多元啟發式算法都從自然界的一些隨機現象取得靈感,如模擬退火、遺傳算法、粒子群算法、蜂群算法、狼群算法等。

天牛須搜索算法(BAS)

天牛須搜索(Beetle Antennae Search-BAS),也叫甲殼蟲須搜索,是2017年提出的一種高效的智能優化算法。類似于遺傳算法、粒子群算法、模擬退火等智能優化算法,天牛須搜索不需要知道函數的具體形式,不需要梯度信息,就可以實現高效尋優。相比于粒子群算法,天牛須搜索只需要一個個體,即一只天牛,運算量大大降低。

當天牛覓食時,天牛并不知道實物在哪里,而是根據食物氣味的強弱來覓食。天牛有兩只長觸角,如果左邊觸角收到的氣味強度比右邊大,那下一步天牛就往左飛,否則就往右飛。依據這一簡單原理天牛就可以有效找到食物。

天牛須算法
### 蟻群算法(ant colony optimization, ACO)

蟻群算法(Ant Colony Algorithm)最初于1992年由意大利學者M.Dorigo等人提出,它是一種模擬自然界中真實蟻群覓食行為的仿生優化算法。研究發現:每只螞蟻覓食時在走過的路線上會留下一種稱為信息素的物質,螞蟻之間靠感知這種物質的濃度進行信息傳遞。螞蟻在選擇路徑時總是傾向于朝信息索濃度高的方向移動,而距離短的路徑上走過的螞蟻多,留下的信息素也多,后續螞蟻選擇它的概率也會越大;其他路徑上的信息素會隨著時間的推移不斷揮發,這樣就形成了一種正反饋機制,最后整個蟻群聚集到最短路徑上。

人工蟻群算法模擬了這一過程,每只螞蟻在解空間獨立地搜索可行解,解越好留下的信息素越多,隨著算法推進,較優解路徑上的信息素增多,選擇它的螞蟻也隨之增多,最終收斂到最優或近似最優的解上。

天牛須算法

魚群算法

人工魚群算法為山東大學副教授李曉磊2002年從魚找尋食物的現象中表現的種種移動尋覓特點中得到啟發而闡述的仿生學優化方案。

在一片水域中,魚往往能自行或尾隨其他魚找到營養物質多的地方,因而魚生存數目最多的地方一般就是本水域中營養物質最多的地方,人工魚群算法就是根據這一特點,通過構造人工魚來模仿魚群的覓食、聚群及追尾行為,從而實現尋優。

人工魚擁有以下幾種典型行為:

(1)覓食行為:一般情況下魚在水中隨機地自由游動,當發現食物時,則會向食物逐漸增多的方向快速游去。

(2)聚群行為: 魚在游動過程中為了保證自身的生存和躲避危害會自然地聚集成群,魚聚群時所遵守的規則有三條:

分隔規則:盡量避免與臨近伙伴過于擁擠;

對準規則:盡量與臨近伙伴的平均方向一致;

內聚規則:盡量朝臨近伙伴的中心移動。

(3)追尾行為:當魚群中的一條或幾條魚發現食物時,其臨近的伙伴會尾隨其快速到達食物點。

(4)隨機行為:單獨的魚在水中通常都是隨機游動的,這是為了更大范圍地尋找食物點或身邊的伙伴。

天牛須算法

鳥群算法

2016年,Meng等人收到鳥類群智能的啟發,提出了一種全新的群智能優化算法——鳥群算法(Bird Swarm Algorithm, BSA),鳥群算法是在基于鳥類社會行為和社交互動的基礎上,模擬其三種社會行為:覓食行為、警戒行為與飛行行為而來。相比于粒子群算法和差分進化算法等傳統優化算法,鳥群算法不僅遺傳了尋優速度塊、變異性強等優點,更具有自身獨特的優勢,由于鳥群算法存在四條靈活的搜索路線,并且可以自由調整,其在尋優的過程中能更好地平衡高效能與準確性。

天牛須算法
### 人工蜂群算法

自然界中的蜜蜂總能在任何環境下以極高的效率找到優質蜜源,且能適應環境的改變。蜜蜂群的采蜜系統由蜜源、雇傭蜂、非雇傭蜂三部分組成,其中一個蜜源的優劣有很多要素,如蜜源花蜜量的大小、離蜂巢距離的遠近、提取的難易程度等;雇傭蜂和特定的蜜源聯系并將蜜源信息以一定概率形式告訴同伴;非雇傭蜂的職責是尋找待開采的蜜源,分為跟隨蜂和偵查蜂兩類,跟隨峰是在蜂巢等待而偵查蜂是探測蜂巢周圍的新蜜源。蜜蜂采蜜時,蜂巢中的一部分蜜蜂作為偵查蜂,不斷并隨機地在蜂巢附近尋找蜜源,如果發現了花蜜量超過某個閾值的蜜源,則此偵査蜂變為雇傭蜂開始釆蜜,采蜜完成后飛回蜂巢跳搖擺舞告知跟隨峰。搖擺舞是蜜蜂之間交流信息的一種基本形式,它傳達了有關蜂巢周圍蜜源的重要信息如蜜源方向及離巢距離等,跟隨峰利用這些信息準確評價蜂巢周圍的蜜源質量。當雇傭蜂跳完搖擺舞之后,就與蜂巢中的一些跟隨蜂一起返回原蜜源采蜜,跟隨蜂數量取決于蜜源質量。以這種方式,蜂群能快速且有效地找到花蜜量最高的蜜源。

蜂群算法(Bee Colony Algorithm)是建立在蜜蜂自組織模型和群體智能基礎上提出的一種非數值優化計算方法。于1995年第一個提出了蜂群的自組織模擬模型。在模型中,盡管每個社會階層中的蜜蜂只完成單一任務,但蜜蜂相互間通過搖擺舞、氣味等多種信息方式,使得整個蜂群能協同完成諸如構建蜂巢、收獲花粉等多項任務。于2005年成功地把蜂群算法應用在函數的數值優化問題上,提出了比較系統且新穎的群體智能優化算法——ABCA算法(Artificial Bee Colony Algorithm,簡稱ABCA),算法主要模擬了蜂群的智能采蜜行為,蜜蜂根據各自分工進行各自的采蜜活動,并且通過蜜源信息的共享和交流,從而找到問題的最優解。Basturk于2006年又進一步將人工蜂群算法理論應用到解決限制性數值優化的問題上,并取得了較好的測試效果。人工蜂群在尋優等方面具有收斂速度快、求解質量高、魯棒性好、通用性強等優點,但也可能有早熟收斂和后期容易陷入局部極值等不足。

天牛須算法

螢火蟲算法

2005年,印度學者K.N.Krishnanand和D.Ghose在IEEE群體智能會議上提出一種新的群智能優化算法,人工螢火蟲群優化(Glowworm Swarm Optimization, GSO)算法。2009年,劍橋學者Xin-She Yang根據自然界中螢火蟲的發光行為提出螢火蟲算法(Firefly Algorithm, FA)。這2種算法均是受螢火蟲的發光特性和集聚行為的啟發。

GSO算法思想源于模擬自然界中螢火蟲在晚上群聚活動的自然現象而提出,在螢火蟲的群聚活動中,各只螢火蟲通過散發熒光素與同伴進行覓食以及求偶等信息交流。一般來說,熒光素越亮的螢火蟲其號召力就越強,最終會出現很多螢火蟲聚集在一些熒光素較亮的螢火蟲周圍。人工螢火蟲算法就是根據這種現象提出的一種新型的仿生群智能優化算法。在人工螢火蟲群優化算法中,每只螢火蟲被視為解空間的一個解,螢火蟲種群作為初始解隨機的分布在搜索空間中,然后根據自然界螢火蟲的移動方式進行解空間中每只螢火蟲的移動。通過每一次的移動,最終使得螢火蟲聚集到較好的螢火蟲周圍,也即是找到多個極值點,從而達到種群尋優的目的。

FA算法的原理是把空間各點看成螢火蟲,利用發光強的螢火蟲會吸引發光弱的螢火蟲的特點。在發光弱的螢火蟲向發光強的螢火蟲移動的過程中,完成位置的迭代,從而找出最優位置,即完成了尋優過程。搜索過程和螢火蟲的兩個重要參數有關:螢火蟲的發光亮度和相互吸引度,發光亮的螢火蟲會吸引發光弱的螢火蟲向它移動,發光越亮代表其位置越好,最亮螢火蟲即代表函數的最優解。發光越亮的螢火蟲對周圍螢火蟲的吸引度越高,若發光亮度一樣,則螢火蟲做隨機運動,這兩個重要參數都與距離成反比,距離越大吸引度越小。

天牛須算法

細菌算法

細菌覓食算法(Bacterial Foraging Optimization,BFO)在2002年,被K.M.Passino在論文“Biomimicry of bacterial foraging for distributed optimization and control”中被提出。BFO算法是模仿Eeoli大腸桿菌在人體腸道內吞噬食物的行為而提出一種新型仿生類算法。在BFO算法中,一個細菌代表一個解,它在尋找最優解時只依靠自己。BFO由于其簡單、高效的特點,在許多工程和科學領域得到了廣泛的應用。然而,在處理更復雜的優化問題,特別是高維多模態問題時,與其他群體智能優化算法相比,BFO算法的收斂性較差

細菌覓食算法是基于細菌覓食行為過程而提出的一種仿生隨機搜索算法。該算法模擬細菌群體的行為,包括趨化,繁殖,驅散等三個個步驟。

細菌覓食算法主要包括三層循環,外層是驅散操作,中間層是繁殖操作,內層是趨化操作.算法的核心是內層的趨化性操作,它對應著細菌在尋找食物過程中所采取的方向選擇策略,對算法的收斂性有著極其重要的影響。

天牛須算法

狼群算法

狼群算法(Wolf Colony Algorithm, WCA)是2011年由Yang等提出的一種群智能優化算法,現已實現在醫學、三維傳感器優化、人工神經網絡、機器人路徑規劃、機器學習、水利水電優化等眾多領域。狼群算法是一種隨機概率搜索算法,使其能夠以較大的概率快速找到最優解;狼群算法還具有并行性,可以在同一時間從多個點出發進行搜索,點與點之間互不影響,從而提高算法的效率。

狼群算法意在模擬狼群的捕獵行為處理函數優化問題,將狼群分為三類:頭狼、探狼和猛狼。算法的基本思想是:從待尋優空間中的某一初始獵物群開始,其中具有最佳適應度值的狼作為頭狼,該操作稱為頭狼生成準則。然后,選取除頭狼外最佳的m匹狼作為探狼,進行預定方向上的尋優搜索,采用新舊獵物規則保留優質的獵物,一旦發現比當前頭狼更優質的獵物,則具有該獵物的探狼成為頭狼,此過程稱為探狼游走行為。頭狼發起嚎叫,通知周圍猛狼迅速走向頭狼靠攏,探尋優質獵物,如果尋優得到的優質獵物比頭狼更優,則該狼代替頭狼再次發起嚎叫,直到猛狼距離獵物一定距離時停止。此過程稱為猛狼奔襲行為。當猛狼距離獵物達到預先設定的閾值時,轉變為圍攻行為,對頭狼附近的優質獵物進行尋優,此過程稱為群狼圍攻行為。

天牛須算法

猴群算法

猴群算法是于2008年由Zhao和Tang提出的一種新的用于求解大規模、多峰優化問題的智能優化算法。其思想在于通過模擬自然界中猴群爬山過程中爬、望和跳的幾個動作,設計了三個搜索過程:爬過程主要用來搜索當前所在位置的局部最優解;望過程主要通過眺望來搜索鄰近領域比當前位置更優的解,以便加速最優解的搜尋過程;跳過程的目的在于由當前搜索區域轉移到其它區域,以避免搜索過程陷入局部最優。在猴群算法中,其花費的CPU時間主要在于尋找局部最優位置的爬過程。爬過程中每次迭代的計算量主要集中在目標函數偽梯度的計算,其只涉及到當前位置的兩個臨近位置的目標函數值而與決策向量的維數無關。這一特征顯著地提高了算法的性能,尤其針對高維優化問題時效果更為明顯。另外,跳過程迫使猴群由當前區域轉移到新的區域,從而避免算法陷于局部最優。作為一種智能算法,MA能夠有效地求解高維的、非線性不可微的函數優化問題。此外,MA需要調整的參數也少,這使得MA易于實現。盡管猴群算法在求解高維數優化問題時有了較大的突破,但其也存在一些不足。首先,對于不同的優化問題,在利用MA求解時需要設置不同的參數,并且這些參數對猴群算法來說很重要,一旦設置的不準確,即便是優化問題的近似最優解也很難找到。另外,猴群算法求解優化問題時耗費的CPU時間也較長,在優化效率方面仍具有很大的提高空間。

經過長期的對猴群活動習性的觀察發現,猴群在爬山的過程中,總是可以分解為攀爬、觀跳、空翻行為。首先,猴子會在較小范圍內爬行,不斷向更高處前進。猴群的攀爬行為就相當于狼群算法中搜尋獵物的過程,尋找局部地區內的一個最優值。找到更優的值,就替換掉原來的值。猴子爬到所在地的最高處時,就觀察附近有沒有更高的位置,如果有,就跳躍至更高處,然后繼續攀爬行為至頂端,這就是狼群的觀跳行為。為了發現全局最高的地方,猴子會空翻至更遠的區域,然后繼續爬行,就是猴群的空翻行為。重復幾次這樣的行為,直至到達全局最高點處。

猴群算法與蜂群算法、狼群算法等群體智能算法有所區別,蜂群算法中有引領蜂、偵查蜂及跟隨蜂,狼群算法則有搜尋狼、頭領狼和圍攻狼,角色之間相互轉換。而在這里,猴群沒有角色的變更,只有階段性的行為變化。其中攀爬行為穿插在整個的前進過程中,例如在觀跳行為的前后和空翻行為前后,是個耗時最長的行為。

天牛須算法

布谷鳥算法(Cuckoo Search)

布谷鳥最特殊的習性是寄巢產卵。大自然中有一些布谷鳥會將自己的卵產在寄主鳥巢中,同時布谷鳥也會移除鳥巢中其他卵使得鳥巢中的卵數量保持相近。因為布谷鳥的卵與寄主的卵相比孵化周期更短,孵出的布谷鳥幼雛勢必本能地把寄主的卵推出卵巢,以此增加自己的存活率,提高競爭性。

在某些情況下,當布谷鳥寄生其卵時,寄主鳥類會攻擊布谷鳥,也有可能發現鳥巢中陌生的卵。這時,寄主鳥類會丟棄布谷鳥所產的卵或直接重新筑巢。與寄主鳥類不停地爭斗中,布谷鳥的卵及孵化的幼雛皆沿著仿照寄主鳥類的方式生長。

布谷鳥搜索(cuckoo search, CS)算法屬于典型的具有迭代搜尋特征的群智能優化算法。作為新型的啟發式搜索算法,是以布谷鳥的寄巢產卵特點及少部分生物的萊維飛行(Levy flights)模式為參照,由Yang等于2009年提出的。其主要思想是通過隨機行走方式產生候選鳥巢以及采用貪婪策略更新鳥巢位置,最終使鳥巢位置達到或者接近全局最優解。

蝙蝠算法

蝙蝠算法(Bat Algorithm,BA) 是Yang教授于2010年基于群體智能提出的啟發式搜索算法,是一種搜索全局最優解的有效方法。該算法是一種基于迭代的優化技術,初始化為一組隨機解,然后通過迭代搜尋最優解,且在最優解周圍通過隨機飛行產生局部新解,加強了局部搜索。與其他算法相比,BA在準確性和有效性方面遠優于其他算法,且沒有許多參數要進行調整。

蝙蝠使用回聲定位技術檢測獵物、避開障礙物以及在黑暗的環境中找到棲息地。其可以發出非常響亮的脈沖并聽取從周圍物體反彈回來的回聲,根據回聲到雙耳的不同時間與強度判斷物體所在的方向和位置;還可以根據目標獵物或者障礙物的特征發出不同性質的脈沖。

BA算法是模擬自然界中蝙蝠利用一種聲吶來探測獵物、避免障礙物的隨機搜索算法即模擬蝙蝠利用超聲波對障礙物或獵物進行最基本的探測、定位能力并將其和優化目標功能相聯系。BA算法的仿生原理將種群數量為的蝙蝠個體映射為D維問題空間中的NP個可行解,將優化過程和搜索模擬成種群蝙蝠個體移動過程和搜尋獵物利用求解問題的適應度函數值來衡量蝙蝠所處位置的優劣,將個體的優勝劣汰過程類比為優化和搜索過程中用好的可行解替代較差可行解的迭代過程。在蝙蝠搜索算法中,為了模擬蝙蝠探測獵物、避免障礙物,需假設如下三個近似的或理想化的規則:

1)所有蝙蝠利用回聲定位的方法感知距離,并且它們采用一種巧妙的方式來區別獵物和背景障礙物之間的不同。

2)蝙蝠在位置\(x_i\)以速度\(v_i\)隨機飛行,以固定的頻率\(f_{min}\)、可變的波長\(\lambda\)和音量\(A_0\)來搜索獵物。蝙蝠根據自身與目標的鄰近程度來自動調整發射的脈沖波長(或頻率)和調整脈沖發射率\(r\)屬于\([0,1]\)。

3)雖然音量的變化方式有多種但在蝙蝠算法中, 假定音量A是從一個最大值A0(整數)變化到固定最小值Amin

天牛須算法
### 蛙跳算法 蛙跳算法(Shuffled Frog Leading Algorithm, SFLA)是一種啟發式算法,通過啟發式函數進行啟發式搜索,從而找到組合最有問題的解。它結合了以遺傳為基礎的memetic算法和以社會行為為基礎的粒子群優化算法的優點。

在SFLA算法中,種群被分為若干個子群(memeplex),每一個子群包括一定數量的青蛙。不同的memeplex具有不同的文化,分別進行局部搜索。在每個子群中,每只青蛙都有自己的想法,并且受到其他青蛙想法的影響,通過memetic進化來發展。這樣經過一定的memetic進化以及跳躍過程,這些想法思路就在各個memeplex中傳播開來,然后,根據需要局部搜索和跳躍,直到收斂或滿足標準為止。

天牛須算法
### 總結 許多工程技術都是來源于生活又服務于生活,比如,在仿生學中,潛水艇是從魚身上得到靈感,雷達是從蝙蝠身上得到的靈感,斑馬線是從斑馬身上得到的靈感。

算法同樣如此,以上這些以動物命名的算法同樣都是學者們通過仔細觀察動物們的行為得到的靈感,從而設計出了各類精彩的算法。這就告訴我們,平時要仔細觀察,善于思考,說不定哪天我們就可以提出一個什么泥鰍算法啊,小貓小狗算法啊之類的,再不濟,我們可以在人家魚群算法的基礎上發展成鯽魚算法,鯉魚算法,海豚算法之類的,哈哈,這當然是開玩笑的。做學術研究不能為了發論文而設計算法,而是要提出問題,針對問題來設計合理有效的算法。

更多精彩內容請關注訂閱號“優化與算法”及添加QQ群1032493483獲取更多資料。

天牛須算法
posted @ 2020-02-10 20:54  優化與算法  閱讀(...)  評論(...編輯  收藏
美人江湖手游