對一般群智能計算,通常要求滿足以下五條基本原則:
鄰近原則:群內的個體具有對簡單的空間或時間進行計算和評估的能力;
品質原則:群內的個體具有對環境以及群內其他個體的品質作出響應的能力;
多樣性原則:群內的不同個體能夠對環境中某些變化做出不同的多樣反應;
穩定性原則:群內個體的行為模式不會在每次環境發生變化時都發生改變;
適應性原則:群內個體能夠在所需代價不高的情況下,適當改變自身的行為模式。
群智能計算現含蟻群算法、蜂群算法、雞群算法、貓群算法、魚群算法、象群算法、狼群算法、果蠅算法、飛蛾撲火算法、螢火蟲算法、細菌覓食算法、混合蛙跳算法、粒子群算法等諸多智能算法。下面對它們中間常用的一些重要算法進行一些簡單介紹。
蟻群算法(Ant Colony Algorithm),受螞蟻覓食過程及其通信機制的啟發,對螞蟻群落的食物采集過程進行模擬,可用來解決計算機算法中的經典“貨郎擔問題”,即求出需要對所有n個城市進行訪問且只訪問一次的最短路徑及其距離。
在解決貨郎擔問題時,蟻群算法設計的虛擬“螞蟻”將摸索不同路線,并留下會隨時間逐漸消失的虛擬“信息素”。虛擬的“信息素”會因揮發而減少;每只螞蟻每次隨機選擇要走的路徑,它們傾向于選擇路徑比較短的、信息素比較濃的路徑。根據“信息素較濃的路線更近”的原則,即可選擇出最佳路線。由于這個算法利用了正反饋機制,使得較短的路徑能夠有較大的機會得到選擇,并且由于采用了概率算法,所以它能夠不局限于局部最優解。蟻群算法具有很多特點,簡單說來,它是一種自組織的并行算法,具有較強的算法的可靠性、穩健性和全局搜索能力。
蟻群基本算法由三個操作過程組成,它們分別是解構建,信息素更新和后臺操作。
(1)解構建:一定數目的虛擬螞蟻在完全連接圖中按照某種規則出發,各自獨立地根據信息素和啟發式信息,采用一個概率規則選擇下一步的移動,直到建立優化問題一個完整的解,并對構成的解進行質量評估。
(2)信息素更新:包括信息素的釋放過程和蒸發過程。信息素釋放往往根據構成解的質量決定釋放量的大小,而信息素蒸發通常是以一個固定比例值衰減所有邊上的信息素。整個更新過程一般是在解的構建完成后,但有時也會出現在解構建的每一步中。每條邊上信息素的量直接影響螞蟻對這條邊的選擇概率,因而信息素的分布情況決定了整個蟻群的搜索空間方向。
(3)后臺操作:以靈活的機制執行單獨螞蟻不能完成的宏觀操作,如搜集全局信息素情況,采取局部搜索措施等,從而對整個算法的行為進行調控。
以上三個操作過程的結合方式是根據算法設計者考慮問題特征時自由指定的,可以并行、獨立、交叉以及同步,從某種程度上來說它們之間是相互作用的。
蟻群算法對于解決貨郎擔問題并不是最好的方法,但它首先提出了一種解決貨郎擔問題的新思路;其次,由于這種算法特有的解決方案,已成功用于解決其他組合優化問題,如圖著色、最短超串等;最后,通過對蟻群算法進行的精心研究和應用開發,現己被大量應用于數據分析、機器人協作問題求解,也在電力、通信、水利、采礦、化工、建筑、交通等領域得到成功的應用。
蜂群算法(Bee Colony Algorithm)根據蜜蜂各自的分工不同,對蜂群信息共享和交流及進行采蜜活動等的觀察和研究,對蜂群的采蜜行為進行計算機模擬,以此找到問題的最優解,是一種基于群智能的全局優化算法。
經過對蜜蜂采蜜機制的觀察和研究,可將除蜂王外的整個蜂群的蜜蜂分為三類,即采蜜蜂、觀察蜂和偵察蜂,整個蜂群的目標是尋找花蜜量最大的蜜源。在蜂群算法中,采蜜蜂利用先前的蜜源信息采蜜,尋找新的蜜源并與觀察蜂分享蜜源信息;觀察蜂依據與采蜜蜂分享的信息尋找新的蜜源;偵查蜂的任務是尋找一個新的更有價值的蜜源,它們在蜂房附近隨機地尋找蜜源。蜂群算法通過對三類蜜蜂功能的模擬,以尋找最短路徑、最大蜜源為目標,用于尋求問題的最優解。
狼群算法(Wolf Colony Algorithm)是基于狼群群體智能,模擬狼群捕食行為及其獵物分配方式,抽象出游走、召喚、圍攻三種智能行為以及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制,提出一種新的群智能算法。算法采用基于狼主體的自下而上的設計方法和基于職責分工的協作式搜索路徑結構,通過狼群個體對獵物氣味、環境信息的探知、人工狼相互間信息的共享和交互以及人工狼基于自身職責的個體行為決策最終實現了狼群捕獵的全過程模擬。
粒子群算法(Particle Swarm Algorithm)源于對鳥群和獸群捕食行為的研究,基本核心是利用群體中的個體對信息的共享從而使得整個群體的運動在問題求解空間中產生從無序到有序的演化過程,從而獲得問題的最優解。
可以利用一個有關粒子群算法的經典描述,對粒子群算法進行直觀描述和簡要介紹。
設想這么一個場景:一群鳥進行覓食,而遠處有一片玉米地,所有的鳥都不知道玉米地到底在哪里,但是它們知道自己當前的位置距玉米地不遠。找到玉米地的最佳策略,就是搜尋目前距離玉米地最近的周圍區域。粒子群算法就是從這種群體覓食的行為中得到了啟示,從而構建的一種優化模型。
在粒子群算法中,把搜索空間中的鳥稱之為“粒子”,而問題的“最優解”對應為鳥群要尋找的“玉米地”。所有的粒子都具有一個位置向量(粒子在解空間的位置)和速度向量(決定下次飛行的方向和速度),并可以根據目標函數來計算當前的所在位置的適應值,可以將其理解為距離“玉米地”的距離。在每次的迭代中,群中的粒子除了根據自身的“經驗”(歷史位置)進行學習以外,還可以根據種群中最優粒子的“經驗”來學習,從而確定下一次迭代時需要如何調整和改變飛行的方向和速度,進行逐步迭代,最終整個種群的粒子就會逐步趨于最優解。
粒子群算法的計算步驟如下:
步驟1 種群初始化:可以進行隨機初始化或者根據被優化的問題設計特定的初始化方法,然后計算個體的適應值,從而選擇出個體的局部最優位置向量和種群的全局最優位置向量。
步驟2 迭代設置:設置迭代次數;
步驟3 速度更新:更新每個個體的速度向量;
步驟4 位置更新:更新每個個體的位置向量;
步驟5 局部位置向量和全局位置向量更新;
步驟6 終止條件判斷:判斷迭代次數是否達到要求,如滿足,輸出計算結果;否則繼續進行迭代,跳轉至步驟3。
在粒子群算法的應用中,主要是對速度和位置向量迭代算子的設計。迭代算子是否有效將決定整個粒子群算法算法性能的優劣,所以如何設計粒子群算法的迭代算子是粒子群算法算法應用的研究重點和難點。
通過上面幾個群智能算法的介紹,不難看出,它們一般都具有如下一些特點:群體中相互合作的個體是分布式的,這樣更能夠適應當前網絡環境下的工作狀態;沒有中心的控制與數據,這樣的系統更具有穩健性,不會由于某一個或者某幾個個體的故障而影響整個問題的求解;可以不通過個體之間直接通信而是通過非直接通信進行合作,這樣的系統具有更好的可擴充性;由于系統中個體的增加而隨之增加的開銷十分小,系統中每個個體的能力十分簡單,這樣每個個體的執行時間比較短,并且實現起來也比較簡單,具有簡單性,在計算機上容易實現編程和并行處理。
此外,需要對群智能算法實行進一步研發和改進,經常遇到的問題有:
從上面已經列出的十多種群智能算法來看,類似性似乎比較多,應按照數學的抽象性、理論性、應用性和計算機程序的編程類似性等進行合理整頓,需要合并的就進行合并,能略去的就略去,更應加強算法收斂性、有效性等的基礎研究;
智能算法重在應用,要特別加強已有算法的應用研究,不斷擴大應用范圍和領域;
對現有的群智能算法在加強理論研究的同時,進行必要的算法改進,提高應用的廣泛性和有效性,克服諸如精度不高、收斂速度較慢、容易收斂到局部極小值、多樣性下降過快、參數敏感等問題;
進一步尋求更好、更快、更新和更高效的群智能算法。
群智能算法和傳統優化算法相比,具有簡單、并行、適用性強等優點,它不要求問題連續可微,特別適用于具有高度可重入性、高度隨機性、大規模、多目標、多約束等特征的各類典型優化問題求解。但是,由于群體智能計算是一種新興的理論和算法,其理論基礎還不夠完善,數學基礎相對薄弱,因此,如何提高算法在解空間內的搜索效率,算法收斂性分析與證明以及對算法模型框架本身的研究都需要進行更深入的探索,特別是對群體智能歸納出統一的計算模式和框架建模理念。
群體智能來源于對自然界中生物群體行為的模擬,而智能個體在群體中的行為在很多方面類似于生物群體在自然環境中的生態行為,物種乃至整個生態系統的進化都離不開種群之間的協同作用。因此,可以從自然界中獲取很多具有參考意義的科學法則以及相關理論,用來指導群體智能計算模式的研究及其算法改進。如借鑒自然界中種群生態學中的競爭、捕食和協同進化等機制以及自然系統中的混沌現象與機理以及運行規律來進行群體智能計算模式的設計與改進研究,將是一個很有意義的研究領域。
群智能計算因為具有以上諸多特點,雖說研究還處于初級階段,理論上存在不少缺空,并有諸多困難和問題,但是由于其具有的分布式、自組織、協作性、穩健性和實現簡單等特點,在諸如優化問題求解、機器人領域、電力系統領域、網絡及通訊領域、計算機領域、交通領域和半導體制造領域等取得了較為成功的應用,為尋找復雜問題的解決方案提供了快速可靠的基礎,為人工智能、認知科學等領域的基礎理論問題的研究開辟了新的途徑。因此,可以預見群智能的研究代表了以后各類算法研究發展的一個重要方向,具有重要意義和廣闊的不可忽視的應用前景,會逐漸成為一個新的重要研究方向,值得給予更多的重視。
2024-08-29 14:47
2024-02-05 22:01
2024-01-17 07:00
2023-12-25 05:49
2023-12-25 05:12
2023-12-21 09:21
2023-09-10 07:56
2023-08-21 09:49
2021-12-31 16:10
2021-02-08 08:26