蟻群算法、遺傳算法、模擬退火算法介紹

蟻群算法、遺傳算法、模擬退火算法介紹窮舉法列舉所有可能，然后一個(gè)個(gè)去，得到最優(yōu)的結(jié)果。如圖一，需要從A點(diǎn)一直走到G點(diǎn)，才能知道，F(xiàn)是最高的（最優(yōu)解）。這種算法得到的最優(yōu)解肯定是最好的，但也是效率最低的。窮舉法雖然能得到最好的最優(yōu)解，但效率是極其低下的。為了能提高效率，可以不要枚舉所有的結(jié)果，只枚舉結(jié)果集中的一部分，如果某個(gè)解在這部分解中是最優(yōu)的，那么就把它當(dāng)成最優(yōu)解。顯然這樣有可能不能得到真正的最優(yōu)解，但效率卻比窮舉法高很多。只枚舉部分解的方法很多。貪心法在枚舉所有解時(shí)，當(dāng)遇到的解在當(dāng)前情況下是最優(yōu)時(shí)，就認(rèn)為它是最優(yōu)解。如圖一，當(dāng)從A點(diǎn)到B點(diǎn)時(shí)，由于B點(diǎn)比A點(diǎn)的解更優(yōu)，所以會(huì)認(rèn)為B點(diǎn)是最優(yōu)解。顯然這樣的效率很高，但得到的最優(yōu)解質(zhì)量也很差。爬山法貪心法是只和前面的一個(gè)比較，為了提高最優(yōu)解的質(zhì)量，可以不僅和前一個(gè)解比較，也和后一個(gè)解比較，如果比前面和后面的解都優(yōu)，那么就認(rèn)為它是最優(yōu)解。如圖一，當(dāng)?shù)紺點(diǎn)時(shí)，發(fā)現(xiàn)它比前面的B和后面的D點(diǎn)的解都好，所以認(rèn)為它是最優(yōu)解。模擬退火算法爬山算法實(shí)現(xiàn)很簡(jiǎn)單，其主要缺點(diǎn)是會(huì)陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖一，搜索到A點(diǎn)后就停止了搜索。如果能跳出局部最優(yōu)解，那么得到的最優(yōu)解的質(zhì)量相對(duì)就會(huì)好很多。如當(dāng)搜索到A點(diǎn)時(shí)以一定的概率跳轉(zhuǎn)到另外一個(gè)地方。這樣就有可能跳出局部最優(yōu)解A。如果經(jīng)過(guò)一定次數(shù)的跳躍，跳到了E點(diǎn)，那么就會(huì)找到全局的最優(yōu)解了。如果這個(gè)概率不變，那么就會(huì)一直跳躍下去，不會(huì)結(jié)束?？梢宰屵@個(gè)概率逐漸變小，到最后趨于穩(wěn)定。這里的概率逐漸減小類(lèi)似于金屬冶煉的退火過(guò)程，所以稱(chēng)之為模擬退火算法。模擬退火算法（SimulatedAnnealing，SA）最早由Kirkpatrick等應(yīng)用于組合優(yōu)化領(lǐng)域，它是基于Mente-Carlo迭代求解策略的一種隨機(jī)尋優(yōu)算法，其出發(fā)點(diǎn)是基于物理中固體物質(zhì)的退火過(guò)程與一般組合優(yōu)化問(wèn)題之間的相似性。模擬退火算法從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，結(jié)合概率突跳特性在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解，即在局部最優(yōu)解能概率性地跳出并最終趨于全局最優(yōu)。模擬退火算法的關(guān)鍵在于控制溫度（概率）降低快慢的參數(shù)r，這個(gè)參數(shù)范圍是0<r<1。如果參數(shù)r過(guò)大，則搜索到全局最優(yōu)解的可能會(huì)較高，但搜索的過(guò)程也就較長(zhǎng)。若r過(guò)小，則搜索的過(guò)程會(huì)很快，但最終可能會(huì)達(dá)到一個(gè)局部最優(yōu)值。模擬退火算法不能保證得到真正的最優(yōu)解，但它能在效率不錯(cuò)的情況下得到質(zhì)量較高的最優(yōu)解。遺傳算法遺傳算法是計(jì)算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來(lái)的，生物在繁衍發(fā)展的過(guò)程，會(huì)通過(guò)繁殖，發(fā)生基因交叉，基因突變，適應(yīng)度低的個(gè)體會(huì)被逐步淘汰，而適應(yīng)度高的個(gè)體會(huì)越來(lái)越多。那么經(jīng)過(guò)N代的自然選擇后，保存下來(lái)的個(gè)體都是適應(yīng)度很高的。遺傳算法初始是一個(gè)較差解的解集種群，通過(guò)遺傳交叉繁殖出下一代的解集種群。在交叉的過(guò)程中，有一定的概率發(fā)生基因突變。在下一代的解集種群中，通過(guò)適者生存的自然選擇，淘汰那些較差的解（個(gè)體），只讓較好的解（個(gè)體）繁殖后代，這樣產(chǎn)生出代表新的解集的種群。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境。經(jīng)過(guò)許多代的繁殖和自然選擇后，就能得到接近于真正最優(yōu)解的解?？梢杂镁⒅髁x原則來(lái)對(duì)基本遺傳算法進(jìn)行優(yōu)化。所謂精英主義原則，就是為了防止進(jìn)化過(guò)程中產(chǎn)生的最優(yōu)解被交叉和變異所破壞，可以將每一代中的最優(yōu)解原封不動(dòng)的復(fù)制到下一代中。蟻群算法蟻群算法（AntColonyOptimizationACO），又稱(chēng)螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由MarcoDorigo于1992年在他的博士論文中提出，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。螞蟻在路徑上前進(jìn)時(shí)會(huì)根據(jù)前邊走過(guò)的螞蟻所留下的分泌物選擇其要走的路徑。其選擇一條路徑的概率與該路徑上分泌物的強(qiáng)度成正比。因此，由大量螞蟻組成的群體的集體行為實(shí)際上構(gòu)成一種學(xué)習(xí)信息的正反饋現(xiàn)象：某一條路徑走過(guò)的螞蟻越多，后面的螞蟻選擇該路徑的可能性就越大。螞蟻的個(gè)體間通過(guò)這種信息的交流尋求通向食物的最短路徑。蟻群算法就是根據(jù)這一特點(diǎn)，通過(guò)模仿螞蟻的行為，從而實(shí)現(xiàn)尋優(yōu)。當(dāng)程序最開(kāi)始找到目標(biāo)的時(shí)候，路徑幾乎不可能是最優(yōu)的，甚至可能是包含了無(wú)數(shù)錯(cuò)誤的選擇而極度冗長(zhǎng)的。但是，程序可以通過(guò)螞蟻尋找食物的時(shí)候的信息素原理，不斷地去修正原來(lái)的路線(xiàn)，使整個(gè)路線(xiàn)越來(lái)越短，最終找到最佳路線(xiàn)。這種優(yōu)化過(guò)程的本質(zhì)在于：選擇機(jī)制：信息素越多的路徑，被選擇的概率越大。更新機(jī)制：路徑上面的信息素會(huì)隨螞蟻的經(jīng)過(guò)而增長(zhǎng)，而且同時(shí)也隨時(shí)間的推移逐漸揮發(fā)消失。協(xié)調(diào)機(jī)制：螞蟻間實(shí)際上是通過(guò)分泌物來(lái)互相通信、協(xié)同工作的。通過(guò)個(gè)體之間的信息交流與相互協(xié)作最終找到最優(yōu)