一種元啟發式算法--海島算法

2021-02-15 鄭州大學學報工學版

摘要

在假設海島上植物總量不變的情況下，植物的生長位置隨著海平面的上升，出現越來越集中於最高點的現象。受該現象啟發，提出一種元啟發式算法，海島算法(Island Algorithm IA)。海島算法在每次迭代中包含三個階段，淘汰階段，海平面上升階段，平衡階段。

圖1  三階段關係圖

淘汰階段主要的任務是根據海島範圍的變化量來產生本次迭代需要淘汰植物的個數，即淘汰個數N，由淘汰函數完成，為當前迭代的海平面上升階段做準備。

海平面上升階段的主要任務是產生新的海島範圍以及海島範圍變化量。新的海島範圍為接下來的平衡階段做準備，範圍變化量為下次迭代中淘汰階段做準備。該階段將根據淘汰階段產生的淘汰個數，來提升海平面。海平面的提升表現為海島範圍的縮小，從而產生新的海島範圍。為了避免由於收斂過快，易陷入局部最優位置，將新海島範圍進行一定的擴展。

平衡階段的主要任務是在海平面上升的同時，維持植物的總量不變，並根據位置高度進行排序。具體的實現是在海平面上升階段產生的新範圍內，產生N個新植物，替換N個最差的植物，產生的新植物數與淘汰數相等，保持植物總量不變。為了加快搜索速度，提高搜索精度，將每一個新植物朝著全局最優植物處移動，然後評估該植物，若優於全局最優植物，則將兩者的位置和適應度值進行交換。

通過對算法進行分析，找出算法的優勢原因及適合和不適合求解的函數的特點，並對算法的複雜度和魯棒性進行分析。將算法應用於CEC13函數集中，在多個維度下，同經典的粒子群算法進行比較。實驗結果表明，海島算法在計算具有某類特徵的函數時，差於粒子群算法；在其他多數測試函數的實驗結果中，海島算法在多個維度下，精度和魯棒性均顯著優於粒子群算法，驗證了對算法的分析。

圖2  30維運行結果圖

圖3  50維運行結果圖

作者簡介


    馬吉明，男，山西省陽高人，1965年11月生，鄭州輕工業大學計算機與通信工程學院教授，碩士生導師，CCF會員。主要研究方向為群體智能理論與方法；智能信息處理；大數據。通過省部級技術鑑定項目9項，獲得省部級科技進步獎多項；參與編寫教材，技術書籍10餘本；在國內外發表學術論文30餘篇，第一作者發表SCI、EI收錄論文7篇。E_mail：66347771@qq.com

張嵩，男，河南省信陽人，1993年9月生，2016年到2019年，鄭州輕工業大學計算機與通信工程學院碩士研究生。主要研究方向為群智能算法。參與國家自然科學基金一項，校級研究生科技創新基金一項，軟體著作權兩項。發表EI收錄的會議論文1篇，由《Journal ofPhysics: Conference Series》出版。Email：962606045@qq.com

引用本文

馬吉明,張嵩,蘇日建,等.一種元啟發式算法--海島算法[J].鄭州大學學報(工學版),2019,40(04):10. 
Ma J M, Zhang S, Su R J,et al. A metaheuristic algorithm--island algorithm[J].Journal of Zhengzhou University (Engineering Science), 2019,40(04):10.     

相關焦點

  • 啟發式算法分類 - CSDN
    下面是一些學習到的算法，有些沒有具體用到，所以只是概念的解釋，方便自己以後回憶。一、粒子群算法1.1基本思想粒子群算法是模擬群體智能所建立起來的一種優化算法，粒子群算法可以用鳥類在一個空間內隨機覓食為例，所有的鳥都不知道食物具體在哪裡，但是他們知道大概距離多遠，最簡單有效的方法就是搜尋目前離食物最近的鳥的周圍區域。
  • 自我代碼提升之啟發式算法(番外篇)
    本期給大家帶來一些啟發式算法的介紹和代碼實現。嚴格來說，啟發式算法並不屬於機器學習領域的方法，其解決的問題也並不是分類和回歸預測，因此本篇屬於該系列番外篇。啟發式算法簡介在數學建模的經典問題當中，有一種問題是最優化問題，即在給定條件下，給出能夠是的目標實現最優的答案的方法。
  • A* 路徑搜索算法
    假設地圖中存在起點和終點，路徑搜索算法可以用於搜索起點到終點的路徑。在機器人路徑規劃，或者遊戲中都需要用到路徑搜索算法。本文介紹一種經典的 A* 算法，和 Dijkstra 算法相比，A* 採用啟發式的搜索策略，能夠更快地搜索出最短路徑。
  • 基於MOPSO-SA混合算法的礦山微震震源定位方法
    該方法通過震源檢波探測器接收震源初至時刻來反演震源的位置，包括非啟發式和啟發式 2 種 。 非啟發式方法主要包括牛頓法、擬牛頓法和梯度下降法等。 楊俊峰等提出了一種基於 DTOA 和牛頓法的震源定位方法，發現該方法能有效地提高震源定位的準確性。 為解決遠場震源定位問題，李月等在基於無需測速的震源定位模型中，先利用遺傳算法的全局優化能力縮小搜索範圍，再通過擬牛頓法實現局部精確尋優。
  • 編程世界中的18個重要的算法
    也歡迎你留下你覺得有意義的算法。(註：本篇文章並非翻譯，其中的算法描述大部份摘自Wikipedia，因為維基百科描述的很專業了)A*搜尋算法俗稱A星算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的算法。常用於遊戲中的NPC的移動計算，或線上遊戲的BOT的移動計算上。
  • 幾種常見的車輛路徑規划算法
    Lee 算法的複雜度很難表示，而且對於多圖層的路徑規劃則需要很大的空間。 3. Floyd 算法 Floyd 算法是由 Floyd 於 1962 年提出的，是一種計算圖中任意兩點間的最短距離的算法。
  • 淺析基於優化算法的能量管理控制策略(二)
    ，NN）滑模控制（Sliding ModeControl，SMC）無導數優化算法——模擬退火（Simulated Annealing，SA）無導數優化算法——遺傳算法（Genetic Algorithm，GA）無導數優化算法——粒子群算法（Particle Swarm Optimization，PSO）無導數優化算法——DIRECT
  • 新一代算法「鑑黃師」誕生,中科院計算所研究生一作
    從電商到直播：一套架構應對全場景AI鑑黃不是新鮮事，2018年，微軟、谷歌、亞馬遜等等巨頭還搞過算法鑑黃大賽，谷歌摘得桂冠。但是，以往的鑑黃算法，只針對特定場景。即使同樣針對圖像的算法，在面對不同的應用案例，比如社交媒體或電商時，也需要重新收集數據進行訓練。
  • 一種基於A*算法的用於道路場景的軌跡規劃方法
    一種基於A*算法的用於道路場景的軌跡規劃方法 李倩 發表於 2018-10-19 11:17:54 本文提出了一種基於A*算法的用於道路場景的軌跡規劃方法，該方法中
  • NeurIPS2020論文：新一代算法鑑黃師，中科院碩士一作
    從電商到直播：一套架構應對全場景AI鑑黃不是新鮮事，2018年，微軟、谷歌、亞馬遜等等巨頭還搞過算法鑑黃大賽，谷歌摘得桂冠。但是，以往的鑑黃算法，只針對特定場景。即使同樣針對圖像的算法，在面對不同的應用案例，比如社交媒體或電商時，也需要重新收集數據進行訓練。
  • 第四章 蜘蛛猴優化算法
    蜘蛛猴優化(SpiderMonkey Optimization，SMO)是一種全局優化算法，靈感來自於蜘蛛猴在覓食過程中的裂變融合社會(Fission-Fusionsocial，FFS)結構。SMO巧妙地描述了群體智能的兩個基本概念：自組織和分工。SMO作為一種基於群體智能的算法，近年來得到了廣泛的應用，並被應用於許多工程優化問題中。這一部分詳細介紹了蜘蛛猴優化算法。
  • 遺傳算法:組合優化算法,按照進化論的方式啟發搜索尋優解
    遺傳算法是由美國密西根大學的 Holland教授創立於20世紀六七十年代，受達爾文「進化論」思想的啟發而設計實現。遺傳算法不是通過暴力搜索解的方法，而是通過模擬種群的基因交叉和突變，經過種群一代一代的適者生存的方式尋找問題優解的方法，這在解決組合優化時解空間組合爆炸中應用廣泛。
  • 無人機集群——航跡規劃你不知道的各種算法優缺點
    其算法可分可行性方向算法、通用動態算法及實時優化算法。根據規劃範圍可分為全局規划算法及局部尋優算法。如Dynapath算法是一種前向鏈動態規劃技術，在大的任務區域內進行航線規劃是典型的大範圍優化問題，Dynapath 算法可以得到問題的全局最優解。但該算法具有維數爆炸特性的缺陷。
  • 機器學習特徵選擇常用算法
    圖2. 產生過程算法分類 ( M. Dash and H.2.2.2 啟發式搜索(1)序列前向選擇( SFS , Sequential Forward Selection )算法描述：特徵子集X從空集開始，每次選擇一個特徵x加入特徵子集X，使得特徵函數J( X)最優。簡單說就是，每次都選擇一個使得評價函數的取值達到最優的特徵加入，其實就是一種簡單的貪心算法。
  • Science子刊:人腦存在加速學習機制,算力賽過最新AI算法
    新智元報導來源：Science等編輯：嘯林機器學習和深度學習算法的起源，是連接大腦中神經元的突觸強度的學習機制，它越來越多地影響著當代生活的幾乎所有方面。半個世紀以前，研究人員試圖模仿這些大腦的功能，將神經科學和人工智慧聯繫起來。
  • OpenAI提出Reptile:可擴展的元學習算法
    近日，OpenAI發布了簡單元學習算法Reptile，該算法對一項任務進行重複採樣，執行隨機梯度下降，更新初始參數直到習得最終參數。該方法的性能可與MAML（一種廣泛應用的元學習算法）媲美，且比後者更易實現，計算效率更高。
  • 詳解遺傳算法
    遺傳算法是受達爾文的進化論的啟發，借鑑生物進化過程而提出的一種啟發式搜索算法。因此在介紹遺傳算法前有必要簡單的介紹生物進化知識。 編碼需要將問題的解編碼成字符串的形式才能使用遺傳算法。最簡單的一種編碼方式是二進位編碼，即將問題的解編碼成二進位位數組的形式。例如，問題的解是整數，那麼可以將其編碼成二進位位數組的形式。將0-1字符串作為0-1背包問題的解就屬於二進位編碼。
  • 基於改進的LM算法的可見光定位研究
    文獻[7]提出了一種基於自適應混合蛙跳算法的可見光定位方法，雖然啟發式算法具有優越的全局搜索能力，但是獲得全局收斂解卻需要大量計算時間，因此並不適用於嵌入式設備。文獻[8]提出了一種基於融合神經網絡與指紋的可見光定位算法，雖然算法在仿真條件下能得到極高的精度，但是由於BPNN神經的輸入數量是固定的，在複雜的定位條件下算法可能無法靈活的運用冗餘光源信息而導致魯棒性不強。
  • 複雜網絡關鍵參與者 快速識別算法實現新突破
    記者近日從國防科技大學獲悉，該校系統工程學院研究人員創造性地提出了一種名為FINDER的深度強化學習AI算法，實現了對複雜網絡中關鍵參與者的準確快速識別，在效果、性能及普適性等方面均超越了現有的解決方案。相關研究成果近日在《自然·機器智能》發表。在複雜網絡中，如果節點數增加，尋找關鍵節點的時間會呈指數級增長，這在計算機科學中被稱為NP-hard問題，是優化算法領域的終極挑戰。
  • 《簡捷啟發式》如何確保制定決策的合理性
    現實生活並不是這樣，這本書，就把時間也當做一種寶貴資源，納入到決策的考量中，如果我們能夠找到一些決策方法，用足夠少的信息，做出足夠好的決策，這樣就能最大限度地節約時間資源。這樣的決策方法，在這本書中就叫「簡捷啟發式」。