姓名：范凌峰? ? 學(xué)號(hào)：16020188020
轉(zhuǎn)載自：https://www.zhihu.com/question/304164143/answer/548630682
【嵌牛導(dǎo)讀】：如何從專業(yè)角度解釋「遺傳算法」這一概念?
【嵌牛鼻子】：遺傳算法
【嵌牛提問(wèn)】：如何從專業(yè)角度解釋「遺傳算法」這一概念?
【嵌牛正文】：
遺傳算法（Genetic Algorithm, GA）來(lái)源于進(jìn)化論和群體遺傳學(xué)，由美國(guó)的 Holland 教授于 1975 年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》[1]中首先提出。遺傳算法作為一種非確定性的擬自然算法，為復(fù)雜系統(tǒng)的優(yōu)化提供了一種新思路，對(duì)于諸多NP-Hard問(wèn)題，遺傳算法都有不錯(cuò)的表現(xiàn)。相對(duì)于傳統(tǒng)算法而言，遺傳算法有四大突出優(yōu)點(diǎn)[2]：
1.遺傳算法不需要描述問(wèn)題的全部特點(diǎn)，不需要描述全部需要處理的情況。
2.遺傳算法僅需要對(duì)參數(shù)編碼集進(jìn)行處理，無(wú)需針對(duì)問(wèn)題本身進(jìn)行約束。
3.相對(duì)于傳統(tǒng)算法對(duì)模型線性、連續(xù)、可導(dǎo)的限制，遺傳算法不存在這些限制條件。
4.快速求解。
遺傳算法的相對(duì)不足：
1. 遺傳算法的本質(zhì)是隨機(jī)搜索，不能保證所得解為全局最優(yōu)解（參數(shù)足夠大的情況下是可以求出全局最優(yōu)解，但失去了算法本身的意義）。
2算法的發(fā)展與重心
經(jīng)過(guò)多年的發(fā)展，遺傳算法的研究熱點(diǎn)及發(fā)展方向可以由圖1進(jìn)行展示[3]：
圖1 遺傳算法研究進(jìn)展
遺傳算法的搜索核心是遺傳算子的選擇，因此對(duì)于遺傳算法的研究，其中最常見的內(nèi)容與方向是遺傳算子，遺傳算子的選擇多樣性也導(dǎo)致了算法表現(xiàn)的多樣性，常見的選擇方式如圖2所示：
圖2 遺傳算子的研究
遺傳算法作為一種搜索算法，在諸多領(lǐng)域均有很好的表現(xiàn)[4]，如函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度、自動(dòng)控制、機(jī)器學(xué)習(xí)、圖像處理、人工生命、遺傳編程、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等。
3實(shí)例說(shuō)明
為了更通俗地理解遺傳算法，下面將通過(guò)一些實(shí)例進(jìn)行描述：
如果想在一座連綿的大山上找到其最高點(diǎn)，正常情況下你需要爬遍整座山才可以找到最高峰，但大多數(shù)的智能算法并不需要搜索整個(gè)山峰，不同的智能算法有不同的求解思路，舉幾個(gè)簡(jiǎn)單例子：
1. 爬山算法（也稱為貪心算法）。假設(shè)有一只猴子從山的任意一點(diǎn)出發(fā)，當(dāng)它爬到第一個(gè)高峰值點(diǎn)的時(shí)候便停止前進(jìn)，并認(rèn)為當(dāng)前的山峰為整座山最高的點(diǎn)。這種情況下，運(yùn)氣好可能會(huì)到達(dá)最高點(diǎn)，但是大概率情況下都不會(huì)是最高點(diǎn)。
2. 模擬退火算法。假設(shè)有一只神志不清的猴子，當(dāng)它爬到山峰的時(shí)候，它有一定的概率繼續(xù)出發(fā)，也有概率停止前進(jìn)。這種情況下它也有可能通過(guò)有限的時(shí)間找到整座山的最高點(diǎn)。
3. 遺傳算法。假設(shè)山上有一群猴子，猴子生存的食物只有在山峰處才有，而且山峰越高食物量越充裕。那么這些猴子為了生存，會(huì)不斷聚集在各個(gè)山頭上，而這些山峰可以理解為各種局部最優(yōu)解（圖3中類似綠色和藍(lán)色的地方），如果種群規(guī)模足夠大，勢(shì)必會(huì)有一群猴子聚集在了整座山的最高點(diǎn)，也就是全局最優(yōu)解（圖3中紅色位置）。
圖3 山體示意圖
基于以上三種算法的描述，我們可以對(duì)智能算法有一個(gè)簡(jiǎn)單的了解：無(wú)論是哪種算法，都具有一定的隨機(jī)性，都不能保證最終選擇的山峰為整座山的最高點(diǎn)。但是在實(shí)際生活中，有諸多類似的問(wèn)題，如果要考慮所有的情況可能會(huì)花費(fèi)大量的時(shí)間，而恰巧我們并不需要一個(gè)最好的結(jié)果，我們只需要快速找到一個(gè)相對(duì)較好的結(jié)果便可以滿足要求的時(shí)候，智能算法的意義便得到了體現(xiàn)。
智能算法的核心：犧牲精度，保證效率。
通俗了解后，雖然心里有大概思路，但還是云里霧里，這個(gè)時(shí)候我們可以考慮結(jié)合一些實(shí)際的例子來(lái)理解遺傳算法。
結(jié)語(yǔ)
雖然遺傳算法有著一定的弊端和不足，但是遺傳算法在諸多領(lǐng)域(特別是運(yùn)籌學(xué))還是有著很不錯(cuò)的表現(xiàn)并已經(jīng)運(yùn)用到實(shí)際生活中。為了不斷適應(yīng)各種問(wèn)題，近年來(lái)不斷有學(xué)者提出改進(jìn)策略，以使遺傳算法有更廣泛的應(yīng)用領(lǐng)域。
拓展閱讀:
【學(xué)界】整數(shù)規(guī)劃精確算法/近似算法/(元)啟發(fā)算法/神經(jīng)網(wǎng)絡(luò)反向傳播等算法的區(qū)別與關(guān)聯(lián)
【學(xué)界】人工智能的“引擎”--運(yùn)籌學(xué)，一門建模、優(yōu)化、決策的科學(xué)
參考文獻(xiàn)
[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]葛繼科,邱玉輝,吳春明,蒲國(guó)林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究,2008(10):2911-2916.
[3]馬永杰,云文霞.遺傳算法研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究,2012,29(04):1201-1206+1210.
[4]吉根林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用與軟件,2004(02):69-73.
[5] Nix A E , Vose M D . Modeling genetic algorithms with Markov chains[J]. Annals of Mathematics & Artificial Intelligence, 1992, 5(1):79-88.
