智能算法學(xué)習(xí)筆記作者:hisky(蒼竹琴聲)--

智能算法學(xué)習(xí)筆記作者:hisky(蒼竹琴聲)這是我自己看智能算法的時(shí)候的一些筆記，貼出來給大家看一下，如果有理解錯(cuò)誤的地方，千萬請(qǐng)指出，小生在這里先謝過了^_^一個(gè)比方在工程實(shí)踐中，經(jīng)常會(huì)接觸到一些比較“新穎”的算法或理論，比如模擬退火，遺傳算法，禁忌搜索，神經(jīng)網(wǎng)絡(luò)等。這些算法或理論都有一些共同的特性（比如模擬自然過程），通稱為“智能算法”。它們?cè)诮鉀Q一些復(fù)雜的工程問題時(shí)大有用武之地。這些算法都有什么含義？首先給出個(gè)局部搜索，模擬退火，遺傳算法，禁忌搜索的形象比喻：為了找出地球上最高的山，一群有志氣的兔子們開始想辦法。

1．兔子朝著比現(xiàn)在高的地方跳去。他們找到了不遠(yuǎn)處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是局部搜索，它不能保證局部最優(yōu)值就是全局最優(yōu)值。

2．兔子喝醉了。他隨機(jī)地跳了很長(zhǎng)時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，他漸漸清醒了并朝最高方向跳去。這就是模擬退火。

3．兔子們吃了失憶藥片，并被發(fā)射到太空，然后隨機(jī)落到了地球上的某些地方。他們不知道自己的使命是什么。但是，如果你過幾年就殺死一部分海拔低的兔子，多產(chǎn)的兔子們自己就會(huì)找到珠穆朗瑪峰。這就是遺傳算法。

4.兔子們知道一個(gè)兔的力量是渺小的。他們互相轉(zhuǎn)告著，哪里的山已經(jīng)找過，并且找過的每一座山他們都留下一只兔子做記號(hào)。他們制定了下一步去哪里尋找的策略。這就是禁忌搜索。智能優(yōu)化算法的概述智能優(yōu)化算法要解決的一般是最優(yōu)化問題。最優(yōu)化問題可以分為（1）求解一個(gè)函數(shù)中，使得函數(shù)值最小的自變量取值的函數(shù)優(yōu)化問題和（2）在一個(gè)解空間里面，尋找最優(yōu)解，使目標(biāo)函數(shù)值最小的組合優(yōu)化問題。典型的組合優(yōu)化問題有：旅行商問題（TravelingSalesmanProblem，TSP），加工調(diào)度問題（SchedulingProblem），0－1背包問題（KnapsackProblem），以及裝箱問題（BinPackingProblem）等。優(yōu)化算法有很多，經(jīng)典算法包括：有線性規(guī)劃，動(dòng)態(tài)規(guī)劃等；改進(jìn)型局部搜索算法包括爬山法，最速下降法等，本文介紹的模擬退火、遺傳算法以及禁忌搜索稱作指導(dǎo)性搜索法。而神經(jīng)網(wǎng)絡(luò)，混沌搜索則屬于系統(tǒng)動(dòng)態(tài)演化方法。優(yōu)化思想里面經(jīng)常提到鄰域函數(shù)，它的作用是指出如何由當(dāng)前解得到一個(gè)（組）新解。其具體實(shí)現(xiàn)方式要根據(jù)具體問題分析來定。一般而言，局部搜索就是基于貪婪思想利用鄰域函數(shù)進(jìn)行搜索，若找到一個(gè)比現(xiàn)有值更優(yōu)的解就棄前者而取后者。但是，它一般只可以得到“局部極小解”，就是說，可能這只兔子登“登泰山而小天下”，但是卻沒有找到珠穆朗瑪峰。而模擬退火，遺傳算法，禁忌搜索，神經(jīng)網(wǎng)絡(luò)等從不同的角度和策略實(shí)現(xiàn)了改進(jìn)，取得較好的“全局最小解”。

模擬退火算法（SimulatedAnnealing，SA）

模擬退火算法的依據(jù)是固體物質(zhì)退火過程和組合優(yōu)化問題之間的相似性。物質(zhì)在加熱的時(shí)候，粒子間的布朗運(yùn)動(dòng)增強(qiáng)，到達(dá)一定強(qiáng)度后，固體物質(zhì)轉(zhuǎn)化為液態(tài)，這個(gè)時(shí)候再進(jìn)行退火，粒子熱運(yùn)動(dòng)減弱，并逐漸趨于有序，最后達(dá)到穩(wěn)定。模擬退火的解不再像局部搜索那樣最后的結(jié)果依賴初始點(diǎn)。它引入了一個(gè)接受概率p。如果新的點(diǎn)（設(shè)為pn）的目標(biāo)函數(shù)f（pn）更好，則p=1，表示選取新點(diǎn)；否則，接受概率p是當(dāng)前點(diǎn)（設(shè)為pc）的目標(biāo)函數(shù)f（pc），新點(diǎn)的目標(biāo)函數(shù)f（pn）以及另一個(gè)控制參數(shù)“溫度”T的函數(shù)。也就是說，模擬退火沒有像局部搜索那樣每次都貪婪地尋找比現(xiàn)在好的點(diǎn)，目標(biāo)函數(shù)差一點(diǎn)的點(diǎn)也有可能接受進(jìn)來。隨著算法的執(zhí)行，系統(tǒng)溫度T逐漸降低，最后終止于某個(gè)低溫，在該溫度下，系統(tǒng)不再接受變化。模擬退火的典型特征是除了接受目標(biāo)函數(shù)的改進(jìn)外，還接受一個(gè)衰減極限，當(dāng)T較大時(shí)，接受較大的衰減，當(dāng)T逐漸變小時(shí)，接受較小的衰減，當(dāng)T為0時(shí)，就不再接受衰減。這一特征意味著模擬退火與局部搜索相反，它能避開局部極小，并且還保持了局部搜索的通用性和簡(jiǎn)單性。在物理上，先加熱，讓分子間互相碰撞，變成無序狀態(tài)，內(nèi)能加大，然后降溫，最后的分子次序反而會(huì)更有序，內(nèi)能比沒有加熱前更小。就像那只兔子，它喝醉后，對(duì)比較近的山峰視而不見，迷迷糊糊地跳一大圈子，反而更有可能找到珠峰。值得注意的是，當(dāng)T為0時(shí)，模擬退火就成為局部搜索的一個(gè)特例。

模擬退火的偽碼表達(dá)：

proceduresimulatedannealing

begin

t:=0;

initializetemperatureT

selectacurrentstringvcatrandom;

evaluatevc;

repeat

repeat

selectanewstringvnintheneighborhoodofvc;

(1)

iff(vc)<f(vn)

thenvc:=vn;

elseifrandom[0,1]<exp((f(vn)-f(vc))/T)

(2)

thenvc:=vn;

until(termination-condition)

(3)

T:=g(T,t);

(4)

T:=t+1;

until(stop-criterion)

(5)

end;上面的程序中，關(guān)鍵的是(1)新狀態(tài)產(chǎn)生函數(shù)，(2)新狀態(tài)接受函數(shù)，(3)抽樣穩(wěn)定準(zhǔn)則，(4)退溫函數(shù)，(5)退火結(jié)束準(zhǔn)則（簡(jiǎn)稱三函數(shù)兩準(zhǔn)則）是直接影響優(yōu)化結(jié)果的主要環(huán)節(jié)。雖然實(shí)驗(yàn)結(jié)果證明初始值對(duì)于最后的結(jié)果沒有影響，但是初溫越高，得到高質(zhì)量解的概率越大。所以，應(yīng)該盡量選取比較高的初溫。上面關(guān)鍵環(huán)節(jié)的選取策略：（1）狀態(tài)產(chǎn)生函數(shù)：候選解由當(dāng)前解的鄰域函數(shù)決定，可以取互換，插入，逆序等操作產(chǎn)生，然后根據(jù)概率分布方式選取新的解，概率可以取均勻分布、正態(tài)分布、高斯分布、柯西分布等。（2）狀態(tài)接受函數(shù)：這個(gè)環(huán)節(jié)最關(guān)鍵，但是，實(shí)驗(yàn)表明，何種接受函數(shù)對(duì)于最后結(jié)果影響不大。所以，一般選取min[1,exp((f(vn)-f(vc))/T)]。（3）抽樣穩(wěn)定準(zhǔn)則：一般常用的有：檢驗(yàn)?zāi)繕?biāo)函數(shù)的均值是否穩(wěn)定；連續(xù)若干步的目標(biāo)值變化較?。灰?guī)定一定的步數(shù)；（4）退溫函數(shù)：如果要求溫度必須按照一定的比率下降，SA算法可以采用，但是溫度下降很慢；快速SA中，一般采用。目前，經(jīng)常用的是，是一個(gè)不斷變化的值。（5）退火結(jié)束準(zhǔn)則：一般有：設(shè)置終止溫度；設(shè)置迭代次數(shù)；搜索到的最優(yōu)值連續(xù)多次保持不變；檢驗(yàn)系統(tǒng)熵是否穩(wěn)定。為了保證有比較優(yōu)的解，算法往往采取慢降溫、多抽樣、以及把“終止溫度”設(shè)的比較低等方式，導(dǎo)致算法運(yùn)行時(shí)間比較長(zhǎng)，這也是模擬退火的最大缺點(diǎn)。人喝醉了酒辦起事來都不利索，何況兔子？遺傳算法（GeneticAlgorithm,GA）“物競(jìng)天擇，適者生存”，是進(jìn)化論的基本思想。遺傳算法就是模擬自然界想做的事。遺傳算法可以很好地用于優(yōu)化問題，若把它看作對(duì)自然過程高度理想化的模擬，更能顯出它本身的優(yōu)雅——雖然生存競(jìng)爭(zhēng)是殘酷的。遺傳算法以一種群體中的所有個(gè)體為對(duì)象，并利用隨機(jī)化技術(shù)指導(dǎo)對(duì)一個(gè)被編碼的參數(shù)空間進(jìn)行高效搜索。其中，選擇、交叉和變異構(gòu)成了遺傳算法的遺傳操作；參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)、控制參數(shù)設(shè)定五個(gè)要素組成了遺傳算法的核心內(nèi)容。作為一種新的全局優(yōu)化搜索算法，遺傳算法以其簡(jiǎn)單通用、健壯性強(qiáng)、適于并行處理以及高效、實(shí)用等顯著特點(diǎn)，在各個(gè)領(lǐng)域得到了廣泛應(yīng)用，取得了良好效果，并逐漸成為重要的智能算法之一。遺傳算法的偽碼：proceduregeneticalgorithm

begin

initializeagroupandevaluatethefitnessvalue;

（1）

whilenotconvergent

（2）

begin

select;

（3）

ifrandom[0,1]<pcthen

crossover;

（4）

ifrandom(0,1)<pmthen

mutation;

（5）

end;

end上述程序中有五個(gè)重要的環(huán)節(jié)：（1）編碼和初始群體的生成：GA在進(jìn)行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)，這些串結(jié)構(gòu)數(shù)據(jù)的不同組合便構(gòu)成了不同的點(diǎn)。然后隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)數(shù)據(jù)，每個(gè)串結(jié)構(gòu)數(shù)據(jù)稱為一個(gè)個(gè)體，N個(gè)體構(gòu)成了一個(gè)群體。GA以這N個(gè)串結(jié)構(gòu)數(shù)據(jù)作為初始點(diǎn)開始迭代。比如，旅行商問題中，可以把商人走過的路徑進(jìn)行編碼，也可以對(duì)整個(gè)圖矩陣進(jìn)行編碼。編碼方式依賴于問題怎樣描述比較好解決。初始群體也應(yīng)該選取適當(dāng)，如果選取的過小則雜交優(yōu)勢(shì)不明顯，算法性能很差（數(shù)量上占了優(yōu)勢(shì)的老鼠進(jìn)化能力比老虎強(qiáng)），群體選取太大則計(jì)算量太大。（2）檢查算法收斂準(zhǔn)則是否滿足，控制算法是否結(jié)束?？梢圆捎门袛嗯c最優(yōu)解的適配度或者定一個(gè)迭代次數(shù)來達(dá)到。（3）適應(yīng)性值評(píng)估檢測(cè)和選擇：適應(yīng)性函數(shù)表明個(gè)體或解的優(yōu)劣性，在程序的開始也應(yīng)該評(píng)價(jià)適應(yīng)性，以便和以后的做比較。不同的問題，適應(yīng)性函數(shù)的定義方式也不同。根據(jù)適應(yīng)性的好壞，進(jìn)行選擇。選擇的目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代為下一代繁殖子孫。遺傳算法通過選擇過程體現(xiàn)這一思想，進(jìn)行選擇的原則是適應(yīng)性強(qiáng)的個(gè)體為下一代貢獻(xiàn)一個(gè)或多個(gè)后代的概率大。選擇實(shí)現(xiàn)了達(dá)爾文的適者生存原則。（4）雜交：按照雜交概率（pc）進(jìn)行雜交。雜交操作是遺傳算法中最主要的遺傳操作。通過雜交操作可以得到新一代個(gè)體，新個(gè)體組合了其父輩個(gè)體的特性。雜交體現(xiàn)了信息交換的思想?？梢赃x定一個(gè)點(diǎn)對(duì)染色體串進(jìn)行互換，插入，逆序等雜交，也可以隨機(jī)選取幾個(gè)點(diǎn)雜交。雜交概率如果太大，種群更新快，但是高適應(yīng)性的個(gè)體很容易被淹沒，概率小了搜索會(huì)停滯。（5）變異：按照變異概率（pm）進(jìn)行變異。變異首先在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)地改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值。同生物界一樣，GA中變異發(fā)生的概率很低。變異為新個(gè)體的產(chǎn)生提供了機(jī)會(huì)。變異可以防止有效基因的缺損造成的進(jìn)化停滯。比較低的變異概率就已經(jīng)可以讓基因不斷變更，太大了會(huì)陷入隨機(jī)搜索。想一下，生物界每一代都和上一代差距很大，會(huì)是怎樣的可怕情形。就像自然界的變異適和任何物種一樣，對(duì)變量進(jìn)行了編碼的遺傳算法沒有考慮函數(shù)本身是否可導(dǎo)，是否連續(xù)等性質(zhì)，所以適用性很強(qiáng)；并且，它開始就對(duì)一個(gè)種群進(jìn)行操作，隱含了并行性，也容易找到“全局最優(yōu)解”。禁忌搜索算法（TabuSearch，TS）為了找到“全局最優(yōu)解”，就不應(yīng)該執(zhí)著于某一個(gè)特定的區(qū)域。局部搜索的缺點(diǎn)就是太貪婪地對(duì)某一個(gè)局部區(qū)域以及其鄰域搜索，導(dǎo)致一葉障目，不見泰山。禁忌搜索就是對(duì)于找到的一部分局部最優(yōu)解，有意識(shí)地避開它（但不是完全隔絕），從而獲得更多的搜索區(qū)間。兔子們找到了泰山，它們之中的一只就會(huì)留守在這里，其他的再去別的地方尋找。就這樣，一大圈后，把找到的幾個(gè)山峰一比較，珠穆朗瑪峰脫穎而出。當(dāng)兔子們?cè)賹ふ业臅r(shí)候，一般地會(huì)有意識(shí)地避開泰山，因?yàn)樗麄冎?，這里已經(jīng)找過，并且有一只兔子在那里看著了。這就是禁忌搜索中“禁忌表（tabulist）”的含義。那只留在泰山的兔子一般不會(huì)就安家在那里了，它會(huì)在一定時(shí)間后重新回到找最高峰的大軍，因?yàn)檫@個(gè)時(shí)候已經(jīng)有了許多新的消息，泰山畢竟也有一個(gè)不錯(cuò)的高度，需要重新考慮，這個(gè)歸隊(duì)時(shí)間，在禁忌搜索里面叫做“禁忌長(zhǎng)度（tabulength）”；如果在搜索的過程中，留守泰山的兔子還沒有歸隊(duì)，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當(dāng)一個(gè)有兔子留守的地方優(yōu)越性太突出，超過了“besttofar”的狀態(tài)，就可以不顧及有沒有兔子留守，都把這個(gè)地方考慮進(jìn)來，這就叫“特赦準(zhǔn)則（aspirationcriterion）”。這三個(gè)概念是禁忌搜索和一般搜索準(zhǔn)則最不同的地方，算法的優(yōu)化也關(guān)鍵在這里。

偽碼表達(dá)：

proceduretabusearch;

begin

initializeastringvcatrandom,clearupthetabulist;

cur:=vc;

repeat

selectanewstringvnintheneighborhoodofvc;

ifva>best_to_farthen{vaisastringinthetabulist}

begin

cur:=va;

letvatakeplaceoftheoldeststringinthetabulist;

best_to_far:=va;

endelse

begin

cur:=vn;

letvntakeplaceoftheoldeststringinthetabulist;

end;

until(termination-condition);

end;以上程序中有關(guān)鍵的幾點(diǎn)：（1）禁忌對(duì)象：可以選取當(dāng)前的值（cur）作為禁忌對(duì)象放進(jìn)tabulist，也可以把和當(dāng)然值在同一“等高線”上的都放進(jìn)tabulist。（2）為了降低計(jì)算量，禁忌長(zhǎng)度和禁忌表的集合不宜太大，但是禁忌長(zhǎng)度太小容易循環(huán)搜索，禁忌表太小容易陷入“局部極優(yōu)解”。（3）上述程序段中對(duì)best_to_far的操作是直接賦值為最優(yōu)的“解禁候選解”，但是有時(shí)候會(huì)出現(xiàn)沒有大于best_to_far的，候選解也全部被禁的“死鎖”狀態(tài)，這個(gè)時(shí)候，就應(yīng)該對(duì)候選解中最佳的進(jìn)行解禁，以能夠繼續(xù)下去。（4）終止準(zhǔn)則：和模擬退火，遺傳算法差不多，常用的有：給定一個(gè)迭代步數(shù)；設(shè)定與估計(jì)的最優(yōu)解的距離小于某個(gè)范圍時(shí)，就終止搜索；當(dāng)與最優(yōu)解的距離連續(xù)若干步保持不變時(shí)，終止搜索；禁忌搜索是對(duì)人類思維過程本身的一種模擬，它通過對(duì)一些局部最優(yōu)解的禁忌（也可以說是記憶）達(dá)到接納一部分較差解，從而跳出局部搜索的目的。

人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork，ANN）神經(jīng)網(wǎng)絡(luò)從名字就知道是對(duì)人腦的模擬。它的神經(jīng)元結(jié)構(gòu)，它的構(gòu)成與作用方式都是在模仿人腦，但是也僅僅是粗糙的模仿，遠(yuǎn)沒有達(dá)到完美的地步。和馮·諾依曼機(jī)不同，神經(jīng)網(wǎng)絡(luò)計(jì)算非數(shù)字，非精確，高度并行，并且有自學(xué)習(xí)功能。生命科學(xué)中，神經(jīng)細(xì)胞一般稱作神經(jīng)元，它是整個(gè)神經(jīng)結(jié)構(gòu)的最基本單位。每個(gè)神經(jīng)細(xì)胞就像一條胳膊，其中像手掌的地方含有細(xì)胞核，稱作細(xì)胞體，像手指的稱作樹突，是信息的輸入通路，像手臂的稱作軸突，是信息的輸出通路；神經(jīng)元之間錯(cuò)綜復(fù)雜地連在一起，互相之間傳遞信號(hào)，而傳遞的信號(hào)可以導(dǎo)致神經(jīng)元電位的變化，一旦電位高出一定值，就會(huì)引起神經(jīng)元的激發(fā)，此神經(jīng)元就會(huì)通過軸突傳出電信號(hào)。而如果要用計(jì)算機(jī)模仿生物神經(jīng)，就需要人工的神經(jīng)網(wǎng)絡(luò)有三個(gè)要素：（1）形式定義人工神經(jīng)元；（2）給出人工神經(jīng)元的連接方式，或者說給出網(wǎng)絡(luò)結(jié)構(gòu)；（3）給出人工神經(jīng)元之間信號(hào)強(qiáng)度的定義。歷史上第一個(gè)人工神經(jīng)網(wǎng)絡(luò)模型稱作M－P模型，非常簡(jiǎn)單：

其中，表示神經(jīng)元i在t時(shí)刻的狀態(tài)，為1表示激發(fā)態(tài)，為0表示抑制態(tài)；是神經(jīng)元i和j之間的連接強(qiáng)度；表示神經(jīng)元i的閾值，超過這個(gè)值神經(jīng)元才能激發(fā)。這個(gè)模型是最簡(jiǎn)單的神經(jīng)元模型。但是功能已經(jīng)非常強(qiáng)大：此模型的發(fā)明人McCulloch和Pitts已經(jīng)證明，不考慮速度和實(shí)現(xiàn)的復(fù)雜性，它可以完成當(dāng)前數(shù)字計(jì)算機(jī)的任何工作。以上這個(gè)M－P模型僅僅是一層的網(wǎng)絡(luò)，如果從對(duì)一個(gè)平面進(jìn)行分割的方面來考慮的話，M－P網(wǎng)絡(luò)只能把一個(gè)平面分成個(gè)半平面，卻不能夠選取特定的一部分。而解決的辦法就是“多層前向網(wǎng)路”。

圖2圖2是多層前向網(wǎng)絡(luò)的示意圖。最下面的稱作輸入層，最上面一層稱作輸出層，任何一個(gè)中間層都接受來自前一層的所有輸入，加工后傳入后一層。每一層的神經(jīng)元之間沒有聯(lián)系，輸入輸出層之間也沒有直接聯(lián)系，并且僅僅是單向聯(lián)系，沒有反饋。這樣的網(wǎng)絡(luò)被稱作“多層前向網(wǎng)絡(luò)”。數(shù)據(jù)在輸入后，經(jīng)過每一層的加權(quán)，最后輸出結(jié)果。

圖3如圖3，用可覆蓋面來說明多層網(wǎng)絡(luò)的功能：?jiǎn)螌泳W(wǎng)絡(luò)只能把平面分成兩部分，雙層網(wǎng)絡(luò)就可以分割任意凸域，多層網(wǎng)絡(luò)則可以分割任意區(qū)域。為了讓這種網(wǎng)絡(luò)有合適的權(quán)值，必須給網(wǎng)絡(luò)一定的激勵(lì)，讓它自己學(xué)習(xí)，調(diào)整。一種方法稱作“向后傳播算法（BackPropagation，BP）”，其基本思想是考察最后輸出解和理想解的差異，調(diào)整權(quán)值，并把這種調(diào)整從輸出層開始向后推演，經(jīng)過中間層，達(dá)到輸入層?？梢?，神經(jīng)網(wǎng)絡(luò)是通過學(xué)習(xí)來達(dá)到解決問題的目的，學(xué)習(xí)沒有改變單個(gè)神經(jīng)元的結(jié)構(gòu)和工作方式，單個(gè)神經(jīng)元的特性和要解決的問題之間也沒有直接聯(lián)系，這里學(xué)習(xí)的作用是根據(jù)神經(jīng)元之間激勵(lì)與抑制的關(guān)系，改變它們的作用強(qiáng)度。學(xué)習(xí)樣本中的任何樣品的信息都包含在網(wǎng)絡(luò)的每個(gè)權(quán)值之中。

BP算法中有考察輸出解和理想解差異的過程，假設(shè)差距為w，則調(diào)整權(quán)值的目的就是為了使得w最小化。這就又包含了前文所說的“最小值”問題。一般的BP算法采用的是局部搜索，比如最速下降法，牛頓法等，當(dāng)然如果想要得到全局最優(yōu)解，可以采用模擬退火，遺傳算法等。當(dāng)前向網(wǎng)絡(luò)采用模擬退火算法作為學(xué)習(xí)方法的時(shí)候，一般成為“波爾茲曼網(wǎng)絡(luò)”，屬于隨機(jī)性神經(jīng)網(wǎng)絡(luò)。在學(xué)習(xí)BP算法學(xué)習(xí)的過程中，需要已經(jīng)有一部分確定的值作為理想輸出，這就好像中學(xué)生在學(xué)習(xí)的時(shí)候，有老師的監(jiān)督。如果沒有了監(jiān)督，人工神經(jīng)網(wǎng)絡(luò)該怎么學(xué)習(xí)？就像沒有了宏觀調(diào)控，自由的市場(chǎng)引入了競(jìng)爭(zhēng)一樣，有一種學(xué)習(xí)方法稱作“無監(jiān)督有競(jìng)爭(zhēng)的學(xué)習(xí)”。在輸入神經(jīng)元i的若干個(gè)神經(jīng)元之間開展競(jìng)爭(zhēng)，競(jìng)爭(zhēng)之后，只有一個(gè)神經(jīng)元為1，其他均為0，而對(duì)于失敗的神經(jīng)元，調(diào)整使得向?qū)Ω?jìng)爭(zhēng)有利的方向移動(dòng)，則最終也可能在一次競(jìng)爭(zhēng)中勝利；人工神經(jīng)網(wǎng)絡(luò)還有反饋網(wǎng)絡(luò)如Hopfield網(wǎng)絡(luò)，它的神經(jīng)元的信號(hào)傳遞方向是雙向的，并且引入一個(gè)能量函數(shù)，通過神經(jīng)元之間不斷地相互影響，能量函數(shù)值不斷下降，最后能給出一個(gè)能量比較低的解。這個(gè)思想和模擬退火差不多。人工神經(jīng)網(wǎng)絡(luò)應(yīng)用到算法上時(shí)，其正確率和速度與軟件的實(shí)現(xiàn)聯(lián)系不大，關(guān)鍵的是它自身的不斷學(xué)習(xí)。這種思想已經(jīng)和馮·諾依曼模型很不一樣?？偨Y(jié)模擬退火，遺傳算法，禁忌搜索，神經(jīng)網(wǎng)絡(luò)在解決全局最優(yōu)解的問題上有著獨(dú)到的優(yōu)點(diǎn)，并且，它們有一個(gè)共同的特點(diǎn)：都是模擬了自然過程。模擬退火思路源于物理學(xué)中固體物質(zhì)的退火過程，遺傳算法借鑒了自然界優(yōu)勝劣汰的進(jìn)化思想，禁忌搜索模擬了人類有記憶過程的智力過程，神經(jīng)網(wǎng)絡(luò)更是直接模擬了人腦。它們之間的聯(lián)系也非常緊密，比如模擬退火和遺傳算法為神經(jīng)網(wǎng)絡(luò)提供更優(yōu)良的學(xué)習(xí)算法提供了思路。把它們有機(jī)地綜合在一起，取長(zhǎng)補(bǔ)短，性能將更加優(yōu)良。這幾種智能算法有別于一般的按照?qǐng)D靈機(jī)進(jìn)行精確計(jì)算的程序，尤其是人工神經(jīng)網(wǎng)絡(luò)，是對(duì)計(jì)算機(jī)模型的一種新的詮釋，跳出了馮·諾依曼機(jī)的圈子，按照這種思想來設(shè)計(jì)的計(jì)算機(jī)有著廣闊的發(fā)展前景[原創(chuàng)]智能算法學(xué)習(xí)筆記(1)——前言2009-04-2811:30最近由于做畢業(yè)設(shè)計(jì)的關(guān)系，抽出了幾天的時(shí)間又學(xué)習(xí)了一些比較熱門的智能算法。發(fā)現(xiàn)身邊不少朋友在學(xué)習(xí)這些算法的時(shí)候遇到了種種困難，所以想到了記錄下自己學(xué)習(xí)時(shí)的一些體會(huì)和總結(jié)。一方面是作為一個(gè)筆記，以便以后自己翻看。另一方面，也算是半個(gè)教程，希望能夠幫到正在各種算法中掙扎的朋友。今天是第一篇，計(jì)劃在這篇中對(duì)各種算法的應(yīng)用情況做一個(gè)總結(jié)（也算是對(duì)后面章節(jié)要介紹的算法做一個(gè)廣告吧），預(yù)計(jì)這個(gè)學(xué)習(xí)筆記系列要介紹的算法包括：人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、粒子群算法、蟻群算法、粒子濾波器；另外，我也打算針對(duì)幾個(gè)常見的專題進(jìn)行一些細(xì)節(jié)的討論，這些專題包括：閉環(huán)控制、二維路徑規(guī)劃及地圖創(chuàng)建、圖像識(shí)別的基礎(chǔ)方法、基本決策方法等。雖然感覺內(nèi)容比較多，但是我還是希望能夠每天更新一部分，最終把這份筆記完成。好了，閑話不多說，下面開始幾天要討論的內(nèi)容：首先，今天要對(duì)各種算法進(jìn)行一些整理，將每種算法的可能應(yīng)用方式和各種算法之間的關(guān)系（比如，從實(shí)際應(yīng)用角度考慮，粒子群算法可以認(rèn)為是一種比遺傳算法速度更快，但是性能較差的輕量級(jí)算法）進(jìn)行簡(jiǎn)單的介紹。對(duì)于我們實(shí)際遇到的問題，基本上可以分為以下幾種情況（名稱是自己起的，主要是為了表示個(gè)意思）：

1確定模型這里的確定模型是指遇到的問題是一個(gè)用已有知識(shí)可以準(zhǔn)確建模（指可以列出描述系統(tǒng)所需的所有方程）、且可在期望時(shí)間內(nèi)可以用一般方法求解的問題。這類問題的解決方法并不在本次學(xué)習(xí)筆記的討論范圍之內(nèi)。需要說明的一點(diǎn)是，如果系統(tǒng)可以用確定模型的方法獲得解，那么，除非有特殊原因，否則不應(yīng)該使用任何所謂的“智能算法”，因?yàn)閹缀蹩梢钥隙ǖ氖?，無論從計(jì)算量還是精度上來講，準(zhǔn)確的方程描敘都要比智能算法以某種隨機(jī)方式訓(xùn)練來的實(shí)際的多。

2有確定的評(píng)價(jià)函數(shù)，求最優(yōu)解這類問題是我們遇到最多的問題，無論是數(shù)學(xué)建模還是機(jī)器人，都要考慮大量這類問題，遺傳算法、粒子群算法這兩種算法是解決復(fù)雜問題時(shí)候效果很好的兩個(gè)算法，類似的包括了免疫算法等等的一系列基于人工生命體的算法，此外，還有更為輕量級(jí)的搜索算法，比如登山法（好像也叫爬山法）、模擬退火法等等等等。這類算法之所以存在，其根本原因（我認(rèn)為的）是因?yàn)椋簩?duì)于一個(gè)可能的解集空間，我們面臨2個(gè)問題，第一，無法直接求得最優(yōu)解，也就是說，我們只能知道在某個(gè)特定解時(shí)，這個(gè)解是否“好”，而無法通過給出一個(gè)期望的“好”的程度，直接獲得一個(gè)解（區(qū)別于確定模型，確定模型可以直接通過求解方程獲得這個(gè)解），這通常是由于我們無法對(duì)系統(tǒng)進(jìn)行準(zhǔn)確描述導(dǎo)致的，所以，我們只能通過不斷地“試驗(yàn)”各種可能的解，來找到一個(gè)最好的。而很不幸的，我們面臨的第二個(gè)問題就是，可能的解如此之多，以至于我們不可能在有限的時(shí)間內(nèi)對(duì)所有解進(jìn)行評(píng)估（注意這個(gè)前提，如果解集空間的規(guī)模允許我們進(jìn)行窮舉，那么使用任何智能算法都是不正確的做法）。所以，我們需要一種“更聰明”的搜索算法，以使得我們可以通過檢驗(yàn)更少的可行解就可以獲得最優(yōu)解——但是，嚴(yán)格的說，除了少數(shù)的例外情況外，我們?nèi)绻麤]有對(duì)系統(tǒng)的所有解集空間進(jìn)行窮舉，那么你獲得的解并不能保證一定是最優(yōu)解，只不過是否是“絕對(duì)最優(yōu)”在一般的情況下，并不重要。有關(guān)此類問題更深入的討論，計(jì)劃將在下一章中進(jìn)行，這里就不再過多敘述了。

3求可行（或最優(yōu)）方案與上一類問題不同，這類問題通常并不能簡(jiǎn)單的用一個(gè)向量來代表我們的最優(yōu)解，而且，在當(dāng)前解（方案）不可行時(shí)，無法進(jìn)行準(zhǔn)確的評(píng)價(jià)其有多“不可行”。而且，方案通常是由多個(gè)步驟組成的。這類問題最典型的就是（簡(jiǎn)單的）博弈問題和基于通道的路徑規(guī)劃問題。求解此類問題的基本方法是使用樹或者圖（如果樹不能描述問題）。也就是說，我們按方案的步驟將其按樹的方式展開，在其中找到一條可行的分支。對(duì)于樹，目前已經(jīng)有很多成熟的方案可以解決，最簡(jiǎn)單的當(dāng)然就是深度優(yōu)先搜索（求可行解）、廣度優(yōu)先搜索（求最優(yōu)解）以及各種啟發(fā)式搜索，其中，最常用（也是基本上就可以解決你遇到的問題的）的啟發(fā)式搜索算法是A*算法（以后會(huì)專門介紹）。對(duì)于更復(fù)雜的問題，蟻群算法有著不錯(cuò)的表現(xiàn)（指可以在更短的時(shí)間內(nèi)，得到更好的解），尤其是對(duì)于圖，我們知道有所謂的NP-難問題的存在（需要指數(shù)復(fù)雜度進(jìn)行求解），所以使用此類性能更好的算法將尤其重要。

4決策問題需要解決的問題就是：我現(xiàn)在又很多方案可以選擇，那么我選擇哪種方案是最好的呢？需要注意的是，一般決策問題的決策結(jié)果很難直接寫出評(píng)價(jià)函數(shù)（如果可以寫出，問題將變得非常簡(jiǎn)單，其也就退化為第2類問題）。所以，決策問題主要關(guān)心的將是我們?nèi)绾螌?duì)策略進(jìn)行評(píng)價(jià)。典型的問題就是，比如一個(gè)復(fù)雜的博弈問題，只有在棋局結(jié)束的時(shí)候計(jì)算機(jī)才能知道準(zhǔn)確的評(píng)價(jià)（贏或者輸），而如果是勝利，那么，究竟哪一步對(duì)勝利是起到了推動(dòng)作用呢？而如果輸了棋，顯然不應(yīng)該是所有的步驟都要對(duì)輸棋負(fù)責(zé)的。

5模式識(shí)別問題最常見的是分類問題，這類問題的基本原理是計(jì)算當(dāng)前樣本與標(biāo)準(zhǔn)模式的某種“距離”，然后取最短距離。另外的一種方法是基于概率的，也就是求當(dāng)前樣本是每種類型的概率，取最大概率。特別的，粒子濾波器通過一種特殊的手法，將我們求解<在檢測(cè)到某些信息時(shí)，計(jì)算其屬于某種情況的概率>轉(zhuǎn)化為了，<假定其是某種情況，計(jì)算能檢測(cè)到已知信息的概率>。其更為形象的描述就是：比如我有一張準(zhǔn)確的地圖，那么，我通過看身邊的東西來在地圖上找到我的位置容易呢？還是，我知道我在地圖上的位置，判斷我能看到什么東西容易呢？顯然后者更加容易一些。有關(guān)粒子濾波器的詳細(xì)討論計(jì)劃將在最近2-3章內(nèi)進(jìn)行，希望大家能關(guān)注，因?yàn)榱Ｗ訛V波算法是我非常推薦的一個(gè)算法，不僅僅是其實(shí)際意義，更重要的是它的啟發(fā)意義。以上幾種情況是以我目前水平和經(jīng)歷總結(jié)的，劃分依據(jù)主要是依賴于我們的解決方法主要需要關(guān)心的問題為準(zhǔn)。當(dāng)然，對(duì)于一個(gè)實(shí)際問題，可能是由多個(gè)部分組成的，不過、幸運(yùn)的是，一般情況下，我們可以將復(fù)雜的問題劃分成若干個(gè)子問題解決。在后續(xù)的文章中，我將分別針對(duì)各種問題進(jìn)行討論，討論內(nèi)容主要包括：?jiǎn)栴}的一般性解決思路、常用的輕量級(jí)算法、智能算法（尤其要討論我們究竟在什么情況下需要引入什么級(jí)別的只能算法）。在第二篇文章中，我將首先討論第二類問題（包括遺傳算法和粒子群算法），希望大家支持。[原創(chuàng)]智能算法學(xué)習(xí)筆記(2)——優(yōu)化問題及粒子群算法2009-04-2811:31（本片寫完后寫的的寫在前面：本來想在這一回中，把優(yōu)化問題的算法都介紹完，可是發(fā)現(xiàn)寫完粒子群內(nèi)容已經(jīng)很多了，而且我也寫累了，所以遺傳算法、以及如何將實(shí)際問題抽象為優(yōu)化問題的內(nèi)容在下一次再討論吧好，閑話少說，直接進(jìn)入本次正題。）所謂優(yōu)化問題，我們需要解決的是這樣的一個(gè)問題：對(duì)于一個(gè)模型，我們已經(jīng)有了對(duì)任意解的評(píng)價(jià)方法（稱為評(píng)價(jià)函數(shù)），這個(gè)評(píng)價(jià)方法可以是一個(gè)函數(shù)表達(dá)式，同樣也可以是一個(gè)環(huán)境、設(shè)備甚至一個(gè)人（即所謂的交互式XX算法，就是用人工評(píng)價(jià)代替函數(shù)評(píng)價(jià)）。那么，如果我們無法通過評(píng)價(jià)函數(shù)直接求得最優(yōu)解（例如如果評(píng)價(jià)函數(shù)是針對(duì)一個(gè)變量的2次函數(shù)，則我們就可以直接得到最優(yōu)解，但對(duì)更復(fù)雜或更高維的函數(shù)，通常我們無法求解），那么我們就只能通過所謂的“試”的方法，對(duì)每個(gè)解使用評(píng)價(jià)函數(shù)進(jìn)行測(cè)試，以找到最優(yōu)解。針對(duì)這類問題，我們將分兩部分進(jìn)行討論：如何求解以及如何把一個(gè)現(xiàn)實(shí)問題轉(zhuǎn)換為優(yōu)化問題。我們先來討論如何求解的問題。在求解時(shí)，有兩個(gè)關(guān)鍵的限制條件是我們首先要考慮的：第一是解得維數(shù)，也就是說，我們需要求的解是由多少個(gè)獨(dú)立量決定的。解得維數(shù)直接決定了解集空間的大小，其直觀意義就是：由于有限時(shí)間內(nèi)，我們只能對(duì)有限多個(gè)樣本進(jìn)行評(píng)價(jià)，所以，如果解集空間越大，那么我們可以評(píng)價(jià)到的比例就越小。對(duì)于很多算法而言，其越難收斂。第二個(gè)限制條件就是，評(píng)價(jià)函數(shù)的“復(fù)雜”程度，這里的復(fù)雜主要是針對(duì)局部極?。ù螅┲刀缘模绻u(píng)價(jià)函數(shù)是一個(gè)“簡(jiǎn)單”函數(shù)，只有一個(gè)極小值，那么顯然我們只要找到一個(gè)解，這個(gè)解的每一維向各個(gè)方向變化均會(huì)導(dǎo)致評(píng)價(jià)結(jié)果變差，那么這個(gè)解就是最優(yōu)解。而相反的，我們就很難評(píng)價(jià)一個(gè)解是否是全局最優(yōu)。在實(shí)際應(yīng)用中，雖然我們很難通過數(shù)學(xué)手段知道一個(gè)評(píng)價(jià)函數(shù)是否“復(fù)雜”，但通常，我們可以通過較為直觀的方法來“猜測(cè)”系統(tǒng)是否具有這樣的特性，比如考慮一個(gè)簡(jiǎn)單的路徑規(guī)劃問題，在起始點(diǎn)和目標(biāo)點(diǎn)處于兩個(gè)房間中，唯一的到達(dá)方法是連接兩個(gè)房間的一道門。那么可以預(yù)料到的，如果我們以距離為評(píng)價(jià)函數(shù)的話，對(duì)于可行路徑，必然只有一個(gè)全局最優(yōu)。而對(duì)于另外一個(gè)簡(jiǎn)單的路徑規(guī)劃問題：起始點(diǎn)和終止點(diǎn)在一個(gè)區(qū)域內(nèi)，中間有一個(gè)圓形障礙物相隔，那么，可以預(yù)測(cè)的到，我們將有兩個(gè)局部極小點(diǎn)，即從左側(cè)緊貼障礙物通過和從右側(cè)緊貼障礙物通過。如果系統(tǒng)涉及的情況足夠復(fù)雜，或者我們對(duì)系統(tǒng)的實(shí)際情況了解非常少，以至于我們無法判斷（注意是無法判斷時(shí)，而不是我們已經(jīng)確認(rèn)系統(tǒng)是一個(gè)“復(fù)雜”函數(shù)），那么，我們也沒有必要直接使用復(fù)雜的算法進(jìn)行求解，我們可以使用一個(gè)簡(jiǎn)單的算法（如馬上要介紹的爬山法）對(duì)系統(tǒng)的情況進(jìn)行估計(jì)，如果算法的解不滿意，那么我們?cè)倏紤]更復(fù)雜的算法；如果解我們滿意……那我們就可以開始寫論文了^.^。下面，我們將按照針對(duì)情況的復(fù)雜度由低到高的順序，介紹幾個(gè)常用算法（包括大家想看的遺傳和粒子群）。首先，是最簡(jiǎn)單的爬山法開始（注意，這里討論了一些對(duì)爬山法的變形，這對(duì)理解后面的粒子群算法很重要）。爬山法的思路很簡(jiǎn)單：隨機(jī)選擇一個(gè)解，然后讓這個(gè)解以一定得步長(zhǎng)（即每個(gè)分量變化一個(gè)非常小的值），向更優(yōu)的方向移動(dòng)?？紤]一個(gè)最簡(jiǎn)單的情況，評(píng)價(jià)函數(shù)是一個(gè)針對(duì)一個(gè)變量的2次函數(shù)（畫圖麻煩，大家自己想象吧），那么我們隨機(jī)選擇一個(gè)x值后，按照以上的描述，我的x必然不斷向函數(shù)的極值移動(dòng)，最終停止在極值處（注意，如果步長(zhǎng)過大，則算法會(huì)在極值附近震蕩，當(dāng)然，一種立刻就能想到的改進(jìn)方案就當(dāng)評(píng)價(jià)值變化變小時(shí)，步長(zhǎng)減小——呵呵，算法改進(jìn)就是這樣的直觀）。這個(gè)算法存在兩個(gè)問題，第一就是如果維數(shù)過大，那么如果我們無法求得評(píng)價(jià)函數(shù)的偏導(dǎo)數(shù)（在實(shí)際環(huán)境下一般不能，因?yàn)閷?shí)際環(huán)境下，評(píng)價(jià)函數(shù)經(jīng)常是個(gè)復(fù)雜的仿真環(huán)境）來獲得方向，那么我們的計(jì)算量將隨著維數(shù)的提升快速增加（維數(shù)的指數(shù)復(fù)雜度）。第二個(gè)，也是更主要的問題就是：這個(gè)算法毫無疑問的會(huì)陷入一個(gè)局部極小值，并且這個(gè)局部極小值的位置與隨機(jī)選擇的初始解的位置相關(guān)（試想一個(gè)sin函數(shù)）。對(duì)于這個(gè)問題，我們有兩個(gè)思路可以改善（注意，同時(shí)應(yīng)用這兩個(gè)思路時(shí)，將引出所謂的“智能算法”的原型）：第一，是我可以多次隨機(jī)初始化出不同的起始位置，這樣，我們就可以獲得多個(gè)不同的局部極小值，然后選擇其中最小的作為最優(yōu)解——顯然，評(píng)價(jià)函數(shù)越復(fù)雜（可以理解為“坑”越多），我們很幸運(yùn)的碰巧隨即到全局最優(yōu)的概率就越小。第二個(gè)思路就是，我們提供一種“跳出”局部極小值的方法，讓算法在進(jìn)入一個(gè)局部極小值后，繼續(xù)搜索。最直觀的方法就是，我們?yōu)槲覀兊摹芭郎秸摺痹黾右粋€(gè)沖量（速度），增加沖量有兩種基本的方式：一種是算法會(huì)一定程度上保持原有的方向，這就好像在一個(gè)坑洼地中滾動(dòng)的足球：由于有沖量的存在，足球就有機(jī)會(huì)離開一個(gè)坑（局部極小點(diǎn)），另一種方式和這種做法沒有本質(zhì)的卻別，不過描述起來更數(shù)學(xué)一些：算法以一定得概率可以接受一個(gè)比當(dāng)前差的解。兩種方法都可以使算法離開當(dāng)前的局部極小值——注意！這個(gè)算法同樣可以使算法離開全局最優(yōu)解，但是，改進(jìn)算法立刻就能想到：我只要額外記錄下目前為止的最優(yōu)解就可以了。呵呵，科學(xué)又進(jìn)步了。這種改進(jìn)方法還有另外一個(gè)問題要解決：直覺上就可以知道，我的沖量需要不斷衰減，否則算法不會(huì)結(jié)束。那么怎么衰減呢？簡(jiǎn)單的辦法是我們令其和執(zhí)行時(shí)間成反比——或者是2次函數(shù)等等，特別的，如果我們讓這個(gè)衰減過程符合一個(gè)特別的函數(shù)：溫度傳遞函數(shù)。那么，我們的算法就有了一個(gè)很著名的名字：模擬退火法——當(dāng)然，這個(gè)和我們選擇簡(jiǎn)單的線性衰減函數(shù)沒有本質(zhì)的區(qū)別。好了，激動(dòng)人心的時(shí)候到了。如前面鋪墊的那樣，我們將兩個(gè)思路結(jié)合起來，然后稍加改動(dòng)，粒子群算法呼之欲出^.^第一項(xiàng)改動(dòng)就是，正如前文所述，我們?nèi)绻啻纬跏蓟煌钠鹗嘉恢茫敲次覀兛梢缘玫礁玫慕?。既然我們多次運(yùn)行了算法多次，那么我們就可以將算法改為一個(gè)并行算法：一上來就隨機(jī)初始化多個(gè)位置（為了和后面術(shù)語(yǔ)相同，從現(xiàn)在開始稱這些“東西”為“個(gè)體”），并在每一周期對(duì)所有的個(gè)體進(jìn)行改變——在接下來的討論中我們將會(huì)發(fā)現(xiàn)，這一改動(dòng)給算法帶來了更多的可能性。好了，現(xiàn)在我們擁有了一個(gè)個(gè)體的“種群”，下面我們考慮剛剛爬山法遇到的另一個(gè)問題：如果我們無法對(duì)評(píng)價(jià)函數(shù)求導(dǎo)，那么我們就要對(duì)每一維的各個(gè)方向進(jìn)行評(píng)價(jià)，以決定哪個(gè)方向“更優(yōu)”以便讓我們的“登山者”有一個(gè)方向，而這需要很大的計(jì)算量。那么，我們現(xiàn)在有了種群，有沒有更好的方法呢？呵呵，對(duì)了，這個(gè)問題在提出的時(shí)候就已經(jīng)有了答案：既然我們有很多的個(gè)體，那么我們只要看看其他人，就知道哪個(gè)方向更好了——具體的說，就是我們現(xiàn)在不再需要向原來那樣通過判斷身邊的情況來決定方向了，我們只需要觀察兩個(gè)量就可以了：最牛的個(gè)體在哪？大家都在哪？然后朝著他們的方向走就可以了。講到這里可能大家有個(gè)問題就出現(xiàn)了：如果這樣的話，那么很快大家就都聚集到一個(gè)點(diǎn)了么？別忘了，剛剛我們還提到了一個(gè)重要的方法：增加沖量（模擬退火法），通過增加沖量，我們可以很容易的避免大家都停在一個(gè)點(diǎn)上。好，現(xiàn)在我們可以用數(shù)學(xué)方法總結(jié)下我們的算法了（此式即標(biāo)準(zhǔn)粒子群算法）：向量形式（就是由解得各個(gè)維數(shù)構(gòu)成的向量）：本周期的變化量=系數(shù)1*上周期變化量+系數(shù)2*0到1隨機(jī)數(shù)*（最優(yōu)個(gè)體位置-自身位置）+系數(shù)3*0到1隨機(jī)數(shù)*（最優(yōu)群體均值-自身位置）分量形式：對(duì)于每一維該維的變化量=系數(shù)1*上周期變化量+系數(shù)2*0到1隨機(jī)數(shù)*（最優(yōu)個(gè)體對(duì)應(yīng)維-自身對(duì)應(yīng)維）+系數(shù)3*0到1隨機(jī)數(shù)*（最優(yōu)群體均值對(duì)應(yīng)維-自身對(duì)應(yīng)維）其中，系數(shù)1、2、3是權(quán)重參數(shù)，其中，系數(shù)1叫慣性權(quán)重（按照之前的叫法可以叫沖量權(quán)重），這些值的選取將會(huì)影響算法的性能，大家在使用的時(shí)候可以多試驗(yàn)試驗(yàn)。下面也將會(huì)有一些定性的討論。現(xiàn)在來解釋一下這個(gè)式子：系數(shù)1對(duì)應(yīng)的項(xiàng)就是咱們以前討論過的沖量，在實(shí)際的粒子群算法中，通常也會(huì)對(duì)系數(shù)1進(jìn)行衰減處理，但是，沒有模擬退火法那么復(fù)雜，設(shè)計(jì)者一般用一個(gè)線性方法進(jìn)行衰減，當(dāng)然，如果我們隊(duì)衰減的特性不滿意，大可以參考模擬退火法選擇溫度函數(shù)——恩，起名叫退火粒子群算法？……好像不是很好聽-.-#。至于后面兩項(xiàng)，如前文所述，就是用看其他個(gè)體的方法，代替了原來的只計(jì)算自身周圍的辦法，這樣可以大大增加算法的速度（前面已經(jīng)討論過了，多維情況下，原來的算法顯指數(shù)復(fù)雜度）。其中，之所以選擇了2個(gè)量，一定程度上出于以下考慮：首先，選擇最優(yōu)可以作為參考無可厚非，這里就不過多討論，唯一要提醒的是，這里的最優(yōu)個(gè)體不是指本周期的最優(yōu)個(gè)體，而是歷史上（包括本周期）的最優(yōu)個(gè)體——記得咱們避免沖量將爬山法帶出全局最優(yōu)解時(shí)候使用的增加一個(gè)歷史最優(yōu)解得做法么？這里也用了這個(gè)辦法。那么我們?yōu)槭裁匆黾右粋€(gè)最有群體均值呢（這個(gè)最優(yōu)群集均值的選取很隨意，各個(gè)周期所有個(gè)體的均值，也可以以一定比例選擇的個(gè)體的均值，當(dāng)然，我們用的還是歷史最優(yōu)），很主要的一個(gè)原因是，群體的抗干擾能力較強(qiáng)，如果只設(shè)置一個(gè)個(gè)體的話，那么如果個(gè)體找到的只是一個(gè)局部最優(yōu)，對(duì)其他粒子的影響太大，而且不穩(wěn)定，用群體就穩(wěn)定很多。具體的情況大家可以再matlab中試驗(yàn)下不用群體或不用個(gè)體的變種算法。好了，以上就是粒子群算法了，名字這么猛的算法算法，原來就是這樣搞出來的，有沒有覺得很失望？下一篇中，我們將在粒子群算法上繼續(xù)做一些小的改進(jìn)，來獲得遺傳算法（雖然當(dāng)年事先提出的遺傳算法……），那時(shí)，你會(huì)發(fā)現(xiàn)，遺傳原來更……另外，下一篇中，我們將會(huì)討論優(yōu)化問題另一個(gè)重要問題：如何把一個(gè)現(xiàn)實(shí)問題變成優(yōu)化問題，尤其是什么樣的問題可以變成優(yōu)化問題（即，遺傳算法和粒子群算法，究竟能解什么問題）。希望大家支持，謝謝[原創(chuàng)]智能算法學(xué)習(xí)筆記(3)——遺傳算法及各種優(yōu)化算法的可行條件2009-04-2900:32今天我們首先來討論下著名的遺傳算法。如上一篇所述，我們將基于對(duì)粒子群算法的認(rèn)識(shí)，進(jìn)而給出遺傳算法的基本形式（如果沒有看過前面內(nèi)容的朋友最好還是先看下，這里就不重復(fù)介紹了）。根據(jù)粒子群算法的描述，我們現(xiàn)在的算法已經(jīng)有了一個(gè)種群，并且有了尋找前進(jìn)方向的辦法（看最優(yōu)個(gè)體和群體），而且還有一個(gè)沖量來避免陷入局部最小和避免所有粒子高度集中。那么，我們?cè)趺磥砝^續(xù)改進(jìn)我們的算法呢？讓我們來重新考慮一下所有基于對(duì)解集空間“試”的搜索算法面臨的主要問題：我們的計(jì)算能力是有限的，所以我們?cè)谟邢迺r(shí)間內(nèi)只能對(duì)固定數(shù)量的解進(jìn)行驗(yàn)證，而各種算法都是通過某種手段，來選擇更可能是最優(yōu)解的點(diǎn)來試驗(yàn)（向更好的方向移動(dòng)）。我們現(xiàn)在先不考慮那些真的不錯(cuò)的點(diǎn)，我們來考慮下系統(tǒng)中那些與最優(yōu)點(diǎn)差距非常遠(yuǎn)的點(diǎn)。顯然，對(duì)于大多數(shù)的評(píng)價(jià)函數(shù)來說，如果一個(gè)解得評(píng)分非常非常差，那么最優(yōu)解在他附近的可能性就很低（一切算法都是這個(gè)前提，如果不符合，那么任何算法都很難有很好的解——窮舉除外）。而之前的算法，對(duì)于每個(gè)個(gè)體，無論他有多差，我們都還通過各種手段來讓他試圖變好，如果我們換個(gè)思路呢？我們將這些點(diǎn)不要，這樣就節(jié)約了計(jì)算量。而由于我們有一個(gè)固定的計(jì)算能力，所以，刪除這些點(diǎn)帶來的空閑時(shí)間，我們可以用來處理一些更好的點(diǎn)。比如對(duì)于粒子群算法來說，我們可以刪除最差的10%的粒子，然后在全局最優(yōu)和最優(yōu)個(gè)體附近，隨機(jī)生成出等量的粒子——這相當(dāng)于，我們對(duì)更可能的區(qū)域進(jìn)行了更細(xì)致（用更多個(gè)體）的搜索，宏觀上看，我們的算法試驗(yàn)解得效率應(yīng)該就變高了。好的，現(xiàn)在，我們又掌握了一種對(duì)算法優(yōu)化的辦法了：將不需要的點(diǎn)刪除，并在更可能的區(qū)域創(chuàng)建更多個(gè)點(diǎn)，以使算法效率更高。當(dāng)然，用手工設(shè)置一個(gè)百分比的方法來設(shè)置我要怎么刪除個(gè)體的方法太不數(shù)學(xué)了，而且實(shí)際效果證明并不理想。那么我們有什么更好的選擇方法呢？一個(gè)統(tǒng)計(jì)學(xué)常用的手段是，我們?yōu)槊恳粋€(gè)粒子設(shè)置一個(gè)權(quán)重，來代表這個(gè)個(gè)體進(jìn)入下一周期的資格程度，顯然，我們可以直接用評(píng)價(jià)函數(shù)的結(jié)果作為這個(gè)權(quán)重。然后，我們對(duì)權(quán)重進(jìn)行歸一化，也就是每個(gè)權(quán)重除以權(quán)重總和，這樣處理之后，我們有所有權(quán)重之和等于1。好了，現(xiàn)在，我們可以將這個(gè)歸一化之后的權(quán)重作為這個(gè)粒子進(jìn)入下一周期的概率來使用了——這個(gè)過程的統(tǒng)計(jì)學(xué)名字為“重采樣”；具體的使用方法是：對(duì)于下一周期進(jìn)入算法的每個(gè)粒子來說，其是上周期任意個(gè)體的概率為那個(gè)個(gè)體的權(quán)重。這個(gè)敘述太過抽象，我們來舉一個(gè)具體的例子說明：試想兩種情況，第一是，當(dāng)前所有粒子的評(píng)價(jià)結(jié)果都一樣，比如我們有100個(gè)粒子，那么，我們每個(gè)粒子的權(quán)重就是1除以100，也就是0.01。那么下一個(gè)周期，新的100個(gè)粒子是什么樣子呢？顯然，每個(gè)粒子進(jìn)入下一個(gè)周期的概率相同，理想情況下，也就是這100個(gè)粒子平均的進(jìn)入了下一個(gè)周期，沒有被刪除的。第二個(gè)情況就是，如果我有一個(gè)粒子的權(quán)重非常大，以至于這個(gè)粒子占到了所有權(quán)重的50%,也就是0.5，另外還有5個(gè)粒子的權(quán)重也很大，5個(gè)一種占了0.4999的概率，而其他的90多個(gè)粒子都非常差勁，加起來才有0.0001。那么，下一周期的粒子會(huì)是什么樣子呢？最可能的情況當(dāng)然是：50個(gè)粒子等于剛剛最好的那個(gè)，另外有5組10個(gè)粒子分別等于另外五個(gè)還不錯(cuò)的粒子，然后，如果運(yùn)氣極好，我們可能會(huì)有1個(gè)粒子會(huì)是剩下的90多個(gè)差勁粒子中的一個(gè)（當(dāng)然，他要占掉前面6種粒子的1個(gè)名額）。好的，現(xiàn)在請(qǐng)大家對(duì)上面的做法留有印象，下面我們?cè)賮矸治隽Ｗ尤核惴ǖ牧硗庖粋€(gè)不足，和前面對(duì)爬山法的分析類似，最終我們將通過這些改進(jìn)來得到遺傳算法?，F(xiàn)在，我們來考慮粒子群算法用來決定每個(gè)個(gè)體方向的辦法：看最好的個(gè)體和群體均值。顯然，我們會(huì)有這樣的一個(gè)感覺：我只關(guān)心目前最好的兩個(gè)位置是否顯得太“呆板”了？如果我考慮更多的優(yōu)秀的個(gè)體，那么我們的算法是否能有更好的性能呢？（試想一個(gè)有10個(gè)粒子都進(jìn)入了一個(gè)局部極小點(diǎn)附近，而其中只有一個(gè)是真正的全局最優(yōu)。那么，哪個(gè)個(gè)體先開始對(duì)對(duì)應(yīng)區(qū)域進(jìn)行搜索必然會(huì)有很大的優(yōu)勢(shì)，我們的其他個(gè)體可能只是因?yàn)闀簳r(shí)沒有找到最好的解，就被其他的粒子搶了風(fēng)頭）那么，我們?cè)趺磥斫⒁粋€(gè)能夠?qū)⒛壳暗膬?yōu)勢(shì)信息在全局傳播的方法呢？答案就是：我們利用生物“交－配”的辦法（汗，不知道這個(gè)詞會(huì)不會(huì)被屏蔽掉）?？紤]我們剛剛進(jìn)行的重采樣過程，在重采樣過程之后，我們保留下來的就是“優(yōu)勢(shì)個(gè)體”了，那么我們可以通過隨機(jī)配對(duì)（這個(gè)詞應(yīng)該沒有問題）的方法，讓新個(gè)體同時(shí)具有父母的優(yōu)勢(shì)信息（當(dāng)然，正如你知道的，新個(gè)體同樣可能是集成了父母的所有缺點(diǎn)，不過，沒有關(guān)系，這個(gè)個(gè)體將在下次重采樣的時(shí)候被“優(yōu)勝劣汰”掉）。這樣，就可以使更多的優(yōu)勢(shì)信息在種群中傳播了。到現(xiàn)在為止，我們已經(jīng)有了算法向更優(yōu)位置前進(jìn)的方法了：通過優(yōu)勝劣汰來找出號(hào)的個(gè)體，然后用這些個(gè)體隨機(jī)繁衍，以使優(yōu)勢(shì)信息擴(kuò)散。那么我們是不是就已經(jīng)獲得了所謂的遺傳算法了呢？很可惜，繁衍的方法帶來了一個(gè)問題：通過前面的介紹我們知道，為了避免很多問題，我們的算法需要有某種形式的“沖量”存在。但現(xiàn)在我們不是通過移動(dòng)而是通過繁衍的方法來獲得新的個(gè)體，我們?cè)趺从?jì)算沖量的方向和大小呢？答案很簡(jiǎn)單：沒法計(jì)算！-.-#那么我們?cè)趺丛O(shè)置沖量呢？既然我們沒有辦法計(jì)算，那么我們就采用最直接的方式：隨機(jī)加一個(gè)沖量。而這個(gè)沖量，就是我們所謂的“基因突變”。好了，現(xiàn)在我們已經(jīng)通過討論粒子群算法的不足，獲得了一套完整的改進(jìn)方案，現(xiàn)在我們總結(jié)一下，正式提出遺傳算法：初始化：（這里是最簡(jiǎn)單的方法）為了突變的執(zhí)行方便，我們將解（向量）使用2進(jìn)制位來表示，每一位代表一個(gè)基因位。具體做法就是，如果解是由4個(gè)獨(dú)立量（維）構(gòu)成，并且每一維的取值可能范圍是0到2^10，那么我們就用一個(gè)40位的2進(jìn)制數(shù)來代表這個(gè)解，其中最高10位是第一維，以此類推。現(xiàn)在，我們已經(jīng)將解從向量形式變成了“基因”形式了，那么按照慣例，我們隨機(jī)初始化種群，即每一位隨機(jī)取0或1.迭代部分：對(duì)于每個(gè)周期，執(zhí)行以下操作首先，對(duì)每一個(gè)個(gè)體，使用評(píng)價(jià)函數(shù)進(jìn)行評(píng)價(jià)，計(jì)算優(yōu)劣。進(jìn)行優(yōu)勝劣汰過程，也就是“重采樣”。進(jìn)行隨機(jī)配對(duì)，最簡(jiǎn)單的配對(duì)方法是：每一對(duì)父母產(chǎn)生一對(duì)后代，正常的是直接“復(fù)制”（這個(gè)是遺傳算法的3個(gè)基本操作之一）到對(duì)應(yīng)個(gè)體，并以一定概率，“交換”（操作之二）其中的隨機(jī)的一段基因（比如互換了第5-10位基因）。對(duì)獲得的新個(gè)體，再以隨機(jī)概率對(duì)每一位進(jìn)行“突變”（操作之三，具體做法就是1變0，0變1，這也就是之前要進(jìn)行編碼的原因）。最終產(chǎn)生新的種群，進(jìn)入下一周期。這個(gè)算法直觀意義很強(qiáng)，就是現(xiàn)實(shí)世界物種進(jìn)化的方法，很好理解。唯一我們要提到的就是，上面算法描述中涉及到了兩個(gè)我們需要自己調(diào)節(jié)的概率：交換的概率和突變的概率。其中比較重要的是突變概率，如果過大，則算法的解將會(huì)很難收斂，并且“行為詭異”，可以想象科幻電影里面描繪的由于核輻射，世界生物發(fā)生劇烈突變的場(chǎng)景……。如果過小，那么算法將會(huì)變得很慢，這個(gè)就更直接了，想象現(xiàn)實(shí)世界，由于突變率不高，我們用了上億年才進(jìn)化成現(xiàn)在這個(gè)樣子……好了，優(yōu)化問題中，常用的重量級(jí)（主要指需要的計(jì)算量）的算法已經(jīng)介紹給大家了，下面我們來討論下一個(gè)更為實(shí)際的問題：究竟什么情況下，我們才能使用這些算法？什么時(shí)候用什么算法最好?這里，我們首先給出評(píng)判的準(zhǔn)則：

1.我們必須可以用有限多個(gè)變量，來描述我們要求解的東西。

2.我們至少要有一個(gè)評(píng)價(jià)一個(gè)解好壞的方法。這個(gè)評(píng)價(jià)方法可以不是一個(gè)函數(shù)（當(dāng)然最好是個(gè)函數(shù)），甚至可以是一個(gè)人進(jìn)行手工評(píng)價(jià)。

3.我們必須可以通過隨機(jī)方式，獲得足夠多的可評(píng)判解。這個(gè)原則的實(shí)際意義在后面具體解釋。下面我們來仔細(xì)的討論下以上兩點(diǎn)。對(duì)于第一點(diǎn)，我們使用的變量數(shù)量應(yīng)該盡可能的少，就像之前討論過的，獨(dú)立量越多（維數(shù)越多），解集空間越大，找到最優(yōu)的可能性就越小。而如果我們的問題無法使用不多的幾個(gè)獨(dú)立數(shù)值來描述，那么，這個(gè)問題就是沒有可能使用遺傳、粒子群等算法求解的問題。下面我們來舉一個(gè)具體例子說明：考慮一個(gè)簡(jiǎn)單的路徑規(guī)劃問題：在一個(gè)空曠區(qū)域內(nèi)，有一個(gè)起始點(diǎn)和一個(gè)目標(biāo)點(diǎn)，中間有一個(gè)障礙物（比如圓形）。我們的目的是找到一條最短路徑，繞過障礙物到達(dá)目標(biāo)點(diǎn)。如果我們想使用粒子群算法進(jìn)行路徑規(guī)劃，根據(jù)以上原則，我們必須要把這條路徑用一個(gè)多維向量來描述出來，否則就不能使用。直接用一個(gè)多維向量去描述一條路徑顯然是不可能的，你可以先自己考慮一下。那么，我們?cè)趺从靡粋€(gè)多維向量來描述一條路徑呢？一個(gè)可以想到的辦法就是，我將路徑變?yōu)橛邢薅鄠€(gè)點(diǎn)（比如5個(gè)），每個(gè)點(diǎn)用2個(gè)量（坐標(biāo)X,Y）來描述，那么這條路徑就可以用一個(gè)10維向量來描述出來。那么，有沒有更簡(jiǎn)單的描述方法呢？呵呵，這里賣個(gè)關(guān)子，在之后推出的路徑規(guī)劃專題中，大家可以看到一種將10維向量變?yōu)?維向量的方法——顯然，這樣的一半維數(shù)的做法可以讓算法性能大大提高。以上介紹的只是一個(gè)簡(jiǎn)單的例子，我想說明的問題主要是：不要被算法名字迷惑了，不要看到“粒子群”，就直覺的覺得，這個(gè)算法可以讓一堆粒子在地圖里面亂跑，然后把跑的路徑記錄下來就好了——粒子群算法根本沒有提供這樣的功能。這里推薦一個(gè)我常用的判斷原則：在不考慮實(shí)際性能（是否陷入局部最小等等）的前提下，看看我要求解的問題能不能用最最簡(jiǎn)單的爬山法去解。如果能用爬山法（雖然最終的解很差），那么，這個(gè)算法就有可能用粒子群或者遺傳等等，如果不能使用爬山法（即你沒有辦法寫出這樣一個(gè)程序，完全不知道怎么描述問題），那么，很遺憾，你同樣用不了粒子群和遺傳。爬山法和遺傳的唯一區(qū)別就是：解是否夠能變得更好。好的，剛剛我們已經(jīng)看到，問題可能的描述方法限制了你使用算法的可能性，下面我們來討論評(píng)價(jià)方法的限制：對(duì)于評(píng)價(jià)方法的約束，一般來說是比較弱的，基本上可以認(rèn)為，你只要能提供一種無論什么方式的評(píng)價(jià)方法，算法就可以工作。不過，對(duì)于這個(gè)評(píng)價(jià)標(biāo)準(zhǔn)，我們還是有一些定性的要求的。第一，就是我們要考慮你使用的評(píng)價(jià)方法的真實(shí)程度，顯然，如果你使用的評(píng)價(jià)方法并不能真實(shí)的反映一個(gè)解的好壞，那么一切的計(jì)算都是在做無用功。評(píng)價(jià)真實(shí)程度有兩個(gè)方面的標(biāo)準(zhǔn)，第一：使用的評(píng)價(jià)函數(shù)必須與真實(shí)的評(píng)價(jià)結(jié)果是單調(diào)的，也就是說，當(dāng)我比較兩個(gè)解得時(shí)候，如果實(shí)際一個(gè)解比另一個(gè)解好，那么我的評(píng)價(jià)函數(shù)應(yīng)該作出同樣的判斷，而究竟好多少的量化標(biāo)準(zhǔn)時(shí)無所謂的（比如你對(duì)評(píng)價(jià)函數(shù)乘10，或者乘3次方，不會(huì)影響算法的性能）。第二就是評(píng)價(jià)方法的速度：如果評(píng)價(jià)方法是個(gè)數(shù)學(xué)函數(shù)，那評(píng)價(jià)速度可以忽略不計(jì)，因?yàn)閷?duì)一個(gè)確定函數(shù)帶入變量求值是非?？斓模覀冎饕懻摰氖?，如果我的評(píng)價(jià)函數(shù)是個(gè)仿真系統(tǒng)或是個(gè)環(huán)境甚至是個(gè)人，那么，對(duì)樣本的評(píng)價(jià)就是問題了：比如我使用的是一個(gè)仿真環(huán)境，這個(gè)環(huán)境對(duì)一組解進(jìn)行仿真需要1秒的時(shí)間，那么，如果我們希望算法在1個(gè)小時(shí)內(nèi)出解，我們就只可能對(duì)3600個(gè)解進(jìn)行評(píng)價(jià)，在這種條件下，使用重量級(jí)算法（尤其是并行的種群式的算法）進(jìn)行求解就是不可行的了，我們只能使用爬山或者模擬退火這樣性能較差，但是計(jì)算個(gè)體少的算法。一個(gè)常規(guī)的估計(jì)就是：遺傳算法的話，一般至少要上百個(gè)個(gè)體，進(jìn)行數(shù)百次演化，算法才穩(wěn)定（收斂），粒子群需要對(duì)近百個(gè)粒子，進(jìn)行至少50次以上的迭代，才能收斂。而模擬退火的收斂速度只和我們選擇的沖量衰減的速度有關(guān)，基本爬山法的話，通常我們還有時(shí)間進(jìn)行多次求解，以緩解局部最小問題。下面，我們要談一談最重要的一個(gè)判斷標(biāo)準(zhǔn)了：

3.我們必須可以通過隨機(jī)方式，獲得足夠多的可評(píng)判解。回想一下，我們已經(jīng)詳細(xì)討論過的4種算法（實(shí)際對(duì)任何此類算法都是如此），他們共同的做法就是：隨機(jī)初始化一個(gè)解，對(duì)其評(píng)價(jià)，再以某種方式改變。而我們最主要的限制就出現(xiàn)在了第一步上：隨機(jī)初始化解。我們考慮這樣一個(gè)系統(tǒng)：迷宮地圖。我們已經(jīng)用了某種方式將路徑向量化了之后，我們需要隨機(jī)生成一個(gè)路徑，然后對(duì)其進(jìn)行評(píng)價(jià)。但是，如果這條路徑是非法的呢（比如，穿墻了），對(duì)于可行路徑，我們很好評(píng)價(jià)這條路徑是否足夠好（只要計(jì)算路徑長(zhǎng)度就可以），但是對(duì)于不可行路徑，我們?cè)趺茨苷f明他有多“不好”呢？顯然，這個(gè)函數(shù)幾乎沒有辦法寫出，也沒有可能通過任何實(shí)際方式獲得（一個(gè)感覺是我通過描述我穿了幾次墻來說明這個(gè)解憂多不可行，但是很容易驗(yàn)證，這個(gè)評(píng)判標(biāo)準(zhǔn)絕對(duì)不單調(diào)）。那么，我們就只能拋棄這個(gè)非法的解，或者，我們用一個(gè)非常大（小）的值來代表，比如令不可行解得評(píng)價(jià)值為100000000。對(duì)于第一種做法（拋棄），如果是一個(gè)復(fù)雜的迷宮地圖，那么顯然，我能通過隨機(jī)方式得到一條路徑的可能性幾乎是沒有（在迷宮里面閉著眼睛隨便畫條線就能走出迷宮？你買彩票時(shí)候記得叫上我）。那么我就就需要不斷地拋棄當(dāng)前生成的東西，最終，我們的算法隨機(jī)隨了幾個(gè)小時(shí)，還沒完成初始化……而對(duì)于第二種做法，那問題就更明顯了，初始化結(jié)束，所以個(gè)體評(píng)價(jià)值都是10000000，然后無論用什么方法對(duì)粒子進(jìn)行改變，還是都是10000000——這完全等同于我們?cè)诼o目的的窮舉。這也就說明了，為什么我們?cè)诰W(wǎng)上看到的，用XX算法進(jìn)行路徑規(guī)劃的論文，解決的都是一個(gè)只有幾個(gè)障礙物組成的地圖：因?yàn)橹挥心菢拥牡貓D，我才能有很大概率隨機(jī)出可評(píng)價(jià)的解。（廣告：在路徑規(guī)劃專題中，我將介紹一種我設(shè)計(jì)的（不知道有沒有其他人這樣干）、能解決任意復(fù)雜地圖的規(guī)劃算法——只要有解，我就能解，敬請(qǐng)期待）好了，有關(guān)優(yōu)化算法的一般性問題我們就討論到這里了，更為具體的應(yīng)用在以后的各個(gè)專題中會(huì)再次涉及。下面，我們對(duì)比較重要的幾點(diǎn)再總結(jié)下：一.任何優(yōu)化算法沒有本質(zhì)的區(qū)別，只是在最終解得質(zhì)量和求解時(shí)間上面有所不同，這些算法都能（且只能）求解符合我前文所給的3個(gè)評(píng)價(jià)原則的問題。二.如果確定一個(gè)問題可解，那么我們將根據(jù)時(shí)間限制和解的質(zhì)量要求，選擇一種算法，這里提到的4中算法，質(zhì)量從低到高（速度從快到慢）排序?yàn)椋号郎?、退火、粒子群、遺傳。三.對(duì)于一個(gè)具體問題，我們可以隨意將多個(gè)算法的不同特性組合、來滿足實(shí)際要求。例如，我們可以對(duì)遺傳算法的沖量（即突變）的系數(shù)（概率）使用退火法的衰減方法，以使其獲得一些新的特性；也可以讓粒子群算法在看其他個(gè)體的同時(shí)，也像爬山法一樣判斷身邊的情況，來獲得一個(gè)計(jì)算更復(fù)雜的、但是性能應(yīng)該更好（沒實(shí)際論證過，但直覺上問題不大）的算法。好了，這篇就到這里了，下次我將向大家隆重推薦“粒子濾波”算法，這個(gè)算法給我?guī)砹朔浅４蟮膯⑹咀饔?，是一個(gè)非常優(yōu)秀的算法。相信大家無論是否會(huì)實(shí)際用到這個(gè)算法，學(xué)習(xí)他都能給你帶來不小的用途。智能算法學(xué)習(xí)筆記(4)——蒙特卡洛、貝葉斯方法2009-05-0102:35(由于粒子濾波算法是同時(shí)應(yīng)用蒙特卡洛和貝葉斯理論的產(chǎn)物，所以今天先介紹這兩種方法。本來計(jì)劃一次都寫完的，結(jié)果發(fā)現(xiàn)：內(nèi)容又有點(diǎn)多，所以粒子濾波明天再說。）今天，我們開始討論和概率模型相關(guān)的智能算法。這類算法能解決的問題很多，包括模式識(shí)別（分類問題）、預(yù)測(cè)、決策等等。是非常具有實(shí)際應(yīng)用價(jià)值的一類算法。當(dāng)然，這類算法體系也非常的龐大，尤其是其中涉及高深的數(shù)學(xué)原理的方法眾多。但是，顯然，我們要討論的問題算法并不屬于此類（很大原因是因?yàn)槲腋怕蕭炝耍Ｎ覀兘裉煊懻摰闹攸c(diǎn)將放在：如果一個(gè)概率我無法求得，那么我們有什么其他辦法獲得。首先，我們來考慮著名的“蒙特卡洛法”——又是是個(gè)名字很猛，其實(shí)很“直白”的算法?？紤]這樣一個(gè)問題：投3個(gè)骰子，扔出8點(diǎn)的概率是多少？很簡(jiǎn)單是不是，但是其實(shí)算出來還是有一點(diǎn)點(diǎn)麻煩（記住，“懶惰”對(duì)于一個(gè)程序員來時(shí)說一個(gè)優(yōu)秀的品質(zhì)，“懶惰”的人會(huì)詳盡辦法使問題變得容易處理）。那么，我們可不可以讓計(jì)算機(jī)幫我們計(jì)算呢？計(jì)算機(jī)的最大特點(diǎn)是：計(jì)算快，但是不擅推理。所以我們用一個(gè)和他很相配的辦法來計(jì)算這個(gè)概率：試。具體來說就是，讓計(jì)算機(jī)去投骰子，投100萬次，看看其中有多少次是8點(diǎn)，然后我們就知道實(shí)際概率了——這便是蒙特卡洛法，再簡(jiǎn)單不過的方法了，這個(gè)方法沒有復(fù)雜的公式，沒有麻煩的步驟，只是一個(gè)簡(jiǎn)單的思想：通過仿真來模擬現(xiàn)實(shí)，再用簡(jiǎn)單的統(tǒng)計(jì)方法得到概率?，F(xiàn)在大家對(duì)蒙特卡洛有了一個(gè)基本的認(rèn)識(shí)，那么來詳細(xì)討論下在什么情況下，我們可以使用蒙特卡洛法——當(dāng)然，在這之前，我們先要考慮一個(gè)更一般的問題：在什么情況下，我們可以使用一個(gè)（任何一種）基于概率論的方法？對(duì)于剛剛的提出的骰子的問題，我們來考慮一個(gè)最最基本的問題：如果我只扔了1次骰子，那么我們可不可以認(rèn)為結(jié)果就表示了實(shí)際概率呢？1000次呢？對(duì)于第一個(gè)問題，所有人相信馬上就會(huì)回答：不可以。但是1000次呢？有些人可能就猶豫了：應(yīng)該可以了吧？那么，我們究竟應(yīng)該扔多少次才可以得到我們想要的概率呢？這里，請(qǐng)大家先沐浴更衣，因?yàn)槲覀円莱鲆粋€(gè)有關(guān)概率論最最基礎(chǔ)，也最有用的經(jīng)驗(yàn)值：對(duì)于使用概率問題討論的系統(tǒng)，其必然存在的誤差將約為（根號(hào)下樣本數(shù)量）分之一。這個(gè)經(jīng)驗(yàn)公式是薛定諤提出的，注意：這只是一個(gè)經(jīng)驗(yàn)公式，沒有任何的推理過程和證明，我們甚至“不好意思”在正式公