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

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

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

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

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

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

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

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