智能算法學習筆記作者

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

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

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

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

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

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

模擬退火算法（SimulatedAnnealing，SA）

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

模擬退火的偽碼表達：

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

begin

initializeagroupandevaluatethefitnessvalue;

（1）

whilenotconvergent

（2）

begin

select;

（3）

ifrandom[0,1]<pcthen

crossover;

（4）

ifrandom(0,1)<pmthen

mutation;

（5）

end;

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

偽碼表達：

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

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

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

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

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

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

1確定模型這里的確定模型是指遇到的問題是一個用已有知識可以準確建模（指可以列出描述系統(tǒng)所需的所有方程）、且可在期望時間內可以用一般方法求解的問題。這類問題的解決方法并不在本次學習筆記的討論范圍之內。需要說明的一點是，如果系統(tǒng)可以用確定模型的方法獲得解，那么，除非有特殊原因，否則不應該使用任何所謂的“智能算法”，因為幾乎可以肯定的是，無論從計算量還是精度上來講，準確的方程描敘都要比智能算法以某種隨機方式訓練來的實際的多。

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

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

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

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

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

2.我們至少要有一個評價一個解好壞的方法。這個評價方法可以不是一個函數(shù)（當然最好是個函數(shù)），甚至可以是一個人進行手工評價。

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

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