爬山算法、模擬退火算法、遺傳算法

1、一.爬山算法爬山算法(HillClimbing)介紹模擬退火前，先介紹爬山算法。爬山算法是一種簡(jiǎn)單的貪心搜索算法，該算法每次從當(dāng)前解的臨近解空間中選擇一個(gè)最優(yōu)解作為當(dāng)前解，直到達(dá)到一個(gè)局部最優(yōu)解。爬山算法實(shí)現(xiàn)很簡(jiǎn)單，其主要缺點(diǎn)是會(huì)陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如圖1所示：假設(shè)C點(diǎn)為當(dāng)前解，爬山算法搜索到A點(diǎn)這個(gè)局部最優(yōu)解就會(huì)停止搜索，因?yàn)樵贏(yíng)點(diǎn)無(wú)論向那個(gè)方向小幅度移動(dòng)都不能得到更優(yōu)的解。二.模擬退火模擬退火(SASimul

2、atedAnnealing)思想（跟人一樣找不思想（跟人一樣找不到最優(yōu)解就最產(chǎn)生疑惑，我到底需不需要堅(jiān)持，隨著時(shí)間的推到最優(yōu)解就最產(chǎn)生疑惑，我到底需不需要堅(jiān)持，隨著時(shí)間的推移，逐漸的慢慢的放棄去追尋最優(yōu)解的念頭）移，逐漸的慢慢的放棄去追尋最優(yōu)解的念頭）爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個(gè)當(dāng)前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火其實(shí)也是一種貪心算法，但是它的搜索過(guò)程引入了隨機(jī)因素。模擬退火算法以一定的概率以一定的概率

3、來(lái)接受一個(gè)比當(dāng)前解要差的解，因此有可能有可能會(huì)跳出這個(gè)局部的最優(yōu)解，達(dá)到全局的最優(yōu)解。以圖1為例，模擬退火算法在搜索到局部最優(yōu)解A后，會(huì)以一定的概率以一定的概率接受到E的移動(dòng)。也許經(jīng)過(guò)幾次這樣的不是局部最優(yōu)的移動(dòng)后會(huì)到達(dá)D點(diǎn)，于是就跳出了局部最大值A(chǔ)。若J(Y(i1))=J(Y(i))(即移動(dòng)后得到更優(yōu)解)，則總是接受該移動(dòng)若J(Y(i1))J(Y(i))(即移動(dòng)后的解比當(dāng)前解要差)，則以一定的概率接以一定的概率接受移動(dòng)，而且這個(gè)概率隨

4、著時(shí)間推移逐漸降低（逐漸降低才能趨向穩(wěn)定）受移動(dòng)，而且這個(gè)概率隨著時(shí)間推移逐漸降低（逐漸降低才能趨向穩(wěn)定）這里的“一定的概率”的計(jì)算參考了金屬冶煉的退火過(guò)程，這也是模擬退火算法名稱(chēng)的由來(lái)。若r過(guò)大，則搜索到全局最優(yōu)解的可能會(huì)較高，但搜索的過(guò)程也就較長(zhǎng)。若r過(guò)小，則搜索的過(guò)程會(huì)很快，但最終可能會(huì)達(dá)到一個(gè)局部最優(yōu)值i模擬退火算法是一種隨機(jī)算法，并不一定能找到全局的最優(yōu)解，可以比較快的找到問(wèn)題的近似最優(yōu)解。如果參數(shù)設(shè)置得當(dāng)，模擬退火算法搜索效

5、率比窮舉法要高。遺傳算法遺傳算法(GAGeicAlgithm)，也稱(chēng)進(jìn)化算法。遺傳算法是受達(dá)爾文的進(jìn)化論的啟發(fā)，借鑒生物進(jìn)化過(guò)程而提出的一種啟發(fā)式搜索算法。因此在介紹遺傳算法前有必要簡(jiǎn)單的介紹生物進(jìn)化知識(shí)。一.進(jìn)化論知識(shí)進(jìn)化論知識(shí)作為遺傳算法生物背景的介紹，下面內(nèi)容了解即可：種群種群(Population)：生物的進(jìn)化以群體的形式進(jìn)行，這樣的一個(gè)群體稱(chēng)為種群。個(gè)體個(gè)體：組成種群的單個(gè)生物?；蚧?Gene)：一個(gè)遺傳因子。染色體染色體

6、(Chromosome)：包含一組的基因。生存競(jìng)爭(zhēng)，適者生存生存競(jìng)爭(zhēng)，適者生存：對(duì)環(huán)境適應(yīng)度高的、牛B的個(gè)體參與繁殖的機(jī)會(huì)比較多，后代就會(huì)越來(lái)越多。適應(yīng)度低的個(gè)體參與繁殖的機(jī)會(huì)比較少，后代就會(huì)越來(lái)越少。遺傳與變異遺傳與變異：新個(gè)體會(huì)遺傳父母雙方各一部分的基因，同時(shí)有一定的概率發(fā)生基因變異。簡(jiǎn)單說(shuō)來(lái)就是：繁殖過(guò)程，會(huì)發(fā)生基因交叉(Crossover)，基因突變(Mutation)，適應(yīng)度(Fitness)低的個(gè)體會(huì)被逐步淘汰，而適應(yīng)度高的

7、個(gè)體會(huì)越來(lái)越多。那么經(jīng)過(guò)N代的自然選擇后，保存下來(lái)的個(gè)體都是適應(yīng)度很高的，其中很可能包含史上產(chǎn)生的適應(yīng)度最高的那個(gè)個(gè)體。三.遺傳算法思想遺傳算法思想借鑒生物進(jìn)化論，遺傳算法將要解決的問(wèn)題模擬成一個(gè)生物進(jìn)化的過(guò)程，通過(guò)復(fù)制、交叉、突變等操作產(chǎn)生下一代的解，并逐步淘汰掉適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解。這樣進(jìn)化N代后就很有可能會(huì)進(jìn)化出適應(yīng)度函數(shù)值很高的個(gè)體。舉個(gè)例子，使用遺傳算法解決“01背包問(wèn)題”的思路：01背包的解可以編碼為一