1. 首頁 > 云知道 > >

超詳細的遺傳算法,遺傳算法實例

云知道詳細

什么是遺傳算法，它有哪些實際應用？

超詳細的遺傳算法,遺傳算法實例


1簡介遺傳算法（Genetic Algorithm, GA）來源于進化論和群體遺傳學，由美國的 Holland 教授于 1975 年在他的專著《自然界和人工系統的適應性》[1]中首先提出 。遺傳算法作為一種非確定性的擬自然算法，為復雜系統的優化提供了一種新思路，對于諸多NP-Hard問題，遺傳算法都有不錯的表現 。
相對于傳統算法而言，遺傳算法有四大突出優點[2]：1.遺傳算法不需要描述問題的全部特點，不需要描述全部需要處理的情況 。2.遺傳算法僅需要對參數編碼集進行處理，無需針對問題本身進行約束 。3.相對于傳統算法對模型線性、連續、可導的限制，遺傳算法不存在這些限制條件 。4.快速求解 。遺傳算法的相對不足：1. 遺傳算法的本質是隨機搜索，不能保證所得解為全局最優解（參數足夠大的情況下是可以求出全局最優解，但失去了算法本身的意義） 。
2算法的發展與重心經過多年的發展，遺傳算法的研究熱點及發展方向可以由圖1進行展示[3]：圖1 遺傳算法研究進展遺傳算法的搜索核心是遺傳算子的選擇，因此對于遺傳算法的研究，其中最常見的內容與方向是遺傳算子，遺傳算子的選擇多樣性也導致了算法表現的多樣性，常見的選擇方式如圖2所示：圖2 遺傳算子的研究遺傳算法作為一種搜索算法，在諸多領域均有很好的表現[4]，如函數優化、組合優化、生產調度、自動控制、機器學習、圖像處理、人工生命、遺傳編程、機器學習、數據挖掘等 。
【超詳細的遺傳算法,遺傳算法實例】3實例說明為了更通俗地理解遺傳算法，下面將通過一些實例進行描述：如果想在一座連綿的大山上找到其最高點，正常情況下你需要爬遍整座山才可以找到最高峰，但大多數的智能算法并不需要搜索整個山峰，不同的智能算法有不同的求解思路，舉幾個簡單例子：1. 爬山算法（也稱為貪心算法） 。假設有一只猴子從山的任意一點出發，當它爬到第一個高峰值點的時候便停止前進，并認為當前的山峰為整座山最高的點 。
這種情況下，運氣好可能會到達最高點，但是大概率情況下都不會是最高點 。2. 模擬退火算法 。假設有一只神志不清的猴子，當它爬到山峰的時候，它有一定的概率繼續出發，也有概率停止前進 。這種情況下它也有可能通過有限的時間找到整座山的最高點 。3. 遺傳算法 。假設山上有一群猴子，猴子生存的食物只有在山峰處才有，而且山峰越高食物量越充裕 。
那么這些猴子為了生存，會不斷聚集在各個山頭上，而這些山峰可以理解為各種局部最優解（圖3中類似綠色和藍色的地方），如果種群規模足夠大，勢必會有一群猴子聚集在了整座山的最高點，也就是全局最優解（圖3中紅色位置） 。圖3 山體示意圖基于以上三種算法的描述，我們可以對智能算法有一個簡單的了解：無論是哪種算法，都具有一定的隨機性，都不能保證最終選擇的山峰為整座山的最高點 。
但是在實際生活中，有諸多類似的問題，如果要考慮所有的情況可能會花費大量的時間，而恰巧我們并不需要一個最好的結果，我們只需要快速找到一個相對較好的結果便可以滿足要求的時候，智能算法的意義便得到了體現 。智能算法的核心：犧牲精度，保證效率 。通俗了解后，雖然心里有大概思路，但還是云里霧里，這個時候我們可以考慮結合一些實際的例子來理解遺傳算法 。
結語雖然遺傳算法有著一定的弊端和不足，但是遺傳算法在諸多領域(特別是運籌學)還是有著很不錯的表現并已經運用到實際生活中 。為了不斷適應各種問題，近年來不斷有學者提出改進策略，以使遺傳算法有更廣泛的應用領域 。拓展閱讀:https://zhuanlan.zhihu.com/p/36212065https://zhuanlan.zhihu.com/p/30140008https://zhuanlan.zhihu.com/p/25579864參考文獻[1] HOLLAND J H． Adaptation in natural and artificial systems: an introductory analysis with applications to biology，control，and artificial intelligence［M］．2nd ed．Cambridge: MIT Press，1992．[2]葛繼科,邱玉輝,吳春明,蒲國林.遺傳算法研究綜述[J].計算機應用研究,2008(10):2911-2916.[3]馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究,2012,29(04):1201-1206 1210.[4]吉根林.遺傳算法研究綜述[J].計算機應用與軟件,2004(02):69-73.[5] Nix A E , Vose M D . Modeling genetic algorithms with Markov chains[J]. Annals of Mathematics

推薦閱讀