啟發式算法分類 - CSDN

下面是一些學習到的算法，有些沒有具體用到，所以只是概念的解釋，方便自己以後回憶。

一、粒子群算法

1.1基本思想

粒子群算法是模擬群體智能所建立起來的一種優化算法，粒子群算法可以用鳥類在一個空間內隨機覓食為例，所有的鳥都不知道食物具體在哪裡，但是他們知道大概距離多遠，最簡單有效的方法就是搜尋目前離食物最近的鳥的周圍區域。所以，粒子群算法就是把鳥看成一個個粒子，並且他們擁有位置和速度這兩個屬性，然後根據自身已經找到的離食物最近的解和參考整個共享於整個集群中找到的最近的解去改變自己的飛行方向，最後我們會發現，整個集群大致向同一個地方聚集。而這個地方是離食物最近的區域，條件好的話就會找到食物。這就是粒子群算法。

1.2算法描述   

所以，我們需要一個pbest來記錄個體搜索到的最優解，用gbest來記錄整個群體在一次迭代中搜索到的最優解。速度和粒子位置的更新公式如下：

    v[i] = w * v[i] + c1 * rand() *(pbest[i] - present[i]) + c2 * rand() * (gbest - present[i])    

    present[i]=present[i]+v[i]                                                      

    其中v[i]代表第i個粒子的速度，w代表慣性權值,c1和c2表示學習參數，rand()表示在0-1之間的隨機數,pbest[i]代表第i個粒子搜索到的最優值,gbest代表整個集群搜索到的最優值,present[i]代表第i個粒子的當前位置。

 

1.3標準PSO算法的流程：

 

　　Step1:初始化一群微粒(群體規模為m)，包括隨機位置和 速度；

　　Step2:評價每個微粒的適應度；

　　Step3:對每個微粒，將其適應值與其經過的最好位置 pbest作比較，如果較好，則將其作為當前的 最好位置pbest;

　　Step4:對每個微粒，將其適應值與其經過的最好位置 gbest作比較，如果較好，則將其作為當前的 最好位置gbest;

　　Step5:根據(2)、(3)式調整微粒速度和位置；

　　Step6：未達到結束條件則轉Step2。

 

二、模擬退火(SA,Simulated Annealing)思想

      爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個當前最優解，因此只能搜索到局部的最優值。模擬退火其實也是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優解，達到全局的最優解。

2.1模擬退火算法描述：

        若J( Y(i+1) )>= J( Y(i) )  (即移動後得到更優解)，則總是接受該移動

        若J( Y(i+1) )< J( Y(i) )  (即移動後的解比當前解要差)，則以一定的概率接受移動，而且這個概率隨著時間推移逐漸降低（逐漸降低才能趨向穩定）

　　這裡的「一定的概率」的計算參考了金屬冶煉的退火過程，這也是模擬退火算法名稱的由來。

　　根據熱力學的原理，在溫度為T時，出現能量差為dE的降溫的概率為P(dE)，表示為：P(dE) = exp( dE/(kT) )

　　其中k是一個常數，exp表示自然指數，且dE<0。這條公式說白了就是：溫度越高，出現一次能量差為dE的降溫的概率就越大；溫度越低，則出現降溫的概率就越小。又由於dE總是小於0（否則就不叫退火了），因此dE/kT < 0 ，所以P(dE)的函數取值範圍是(0,1) 。

　　隨著溫度T的降低，P(dE)會逐漸降低。

2.2使用模擬退火算法解決旅行商問題

旅行商問題 ( TSP , Traveling Salesman Problem ) ：有N個城市，要求從其中某個問題出發，唯一遍歷所有城市，再回到出發的城市，求最短的路線。

旅行商問題屬於所謂的NP完全問題，精確的解決TSP只能通過窮舉所有的路徑組合，其時間複雜度是O(N!) 。

使用模擬退火算法可以比較快的求出TSP的一條近似最優路徑。模擬退火解決TSP的思路：

1. 產生一條新的遍歷路徑P(i+1)，計算路徑P(i+1)的長度L( P(i+1) )

2. 若L(P(i+1)) < L(P(i))，則接受P(i+1)為新的路徑，否則以模擬退火的那個概率接受P(i+1) ，然後降溫

3. 重複步驟1，2直到滿足退出條件。

2.3產生新的遍歷路徑的方法有很多，下面列舉其中3種：

1. 隨機選擇2個節點，交換路徑中的這2個節點的順序。

2. 隨機選擇2個節點，將路徑中這2個節點間的節點順序逆轉。

3. 隨機選擇3個節點m，n，k，然後將節點m與n間的節點移位到節點k後面。

2.4對於華為比賽使用模擬退火開始時得不到好的結果的原因分析

退火算法首先設定一定的溫度，外層循環為降溫的一個過程，內層循環為一個遍歷的過程。

1、只考慮滿足需求的伺服器，因為可能改變某個伺服器的位置就會滿足需求了，而且從一個局部的解過度到全局最優解，中間很大的可能要先不滿足流量需求。

2、不是在每次內層循環得到的最優解的基礎上進行的下次循環。因為對於一個比較好的解，可能改變某個伺服器的位置就達到全局最優了，每次的內層循環有可能把中間某步得到的好的解給改變太多了，下次又從這個相對不太好的解上出發得到比較好的解的概率降低了。

三、什麼是歸一化？（神經網絡中用到的） 

數據歸一化，就是將數據映射到[0,1]或[-1,1]區間或更小的區間，比如(0.1,0.9) 。

3.1為什麼要歸一化處理？ 

<1>輸入數據的單位不一樣，有些數據的範圍可能特別大，導致的結果是神經網絡收斂慢、訓練時間長。

<2>數據範圍大的輸入在模式分類中的作用可能會偏大，而數據範圍小的輸入作用就可能會偏小。

<3>由於神經網絡輸出層的激活函數的值域是有限制的，因此需要將網絡訓練的目標數據映射到激活函數的值域。例如神經網絡的輸出層若採用S形激活函數，由於S形函數的值域限制在(0,1)，也就是說神經網絡的輸出只能限制在(0,1)，所以訓練數據的輸出就要歸一化到[0,1]區間。

<4>S形激活函數在(0,1)區間以外區域很平緩，區分度太小。例如S形函數f(X)在參數a=1時，f(100)與f(5)只相差0.0067。

四、遺傳算法

借鑑生物進化論，遺傳算法將要解決的問題模擬成一個生物進化的過程，通過複製、交叉、突變等操作產生下一代的解，並逐步淘汰掉適應度函數值低的解，增加適應度函數值高的解。這樣進化N代後就很有可能會進化出適應度函數值很高的個體。

舉個例子，使用遺傳算法解決「0-1背包問題」的思路：0-1背包的解可以編碼為一串0-1字符串（0：不取，1：取） ；首先，隨機產生M個0-1字符串，然後評價這些0-1字符串作為0-1背包問題的解的優劣；然後，隨機選擇一些字符串通過交叉、突變等操作產生下一代的M個字符串，而且較優的解被選中的概率要比較高。這樣經過G代的進化後就可能會產生出0-1背包問題的一個「近似最優解」。（注意轉化，例如華為的編程題，同樣可以把每個點轉化為0，1，0代表不取，1代表取。再通過最小費用最大流得出不同個體的費用，從而求解）

 

二進位編碼與浮點數編碼的區別，主要在於解碼的快捷。如果一個個體有多維信息（眼耳口鼻等），每一個都要有對應一個染色體上不同的位置。（也即是若是二進位編碼，一個長的二進位不同位置代表不同的特徵，不易區分。二用浮點數編碼，如上，是分開的，很容易解碼與運算）

下面這個轉載自http://www.cnblogs.com/BreezeDust/p/3352090.html 

 

4.1基本思想

 

遺傳算法是模擬達爾文的進化論思想，我想"生存競爭，適者生存"正好簡要的闡述了這一算法的基本特質。用適應函數去考核每個基因的生存能力，用選擇交叉變異去實現進化，搜索出種群的近似最優解，其主要步驟如下：

1.初始化種群

2.適應選擇

3.交叉變異

4.2算法描述

為了更好的描述，這裡我以一個01背包問題為例子來簡單的闡述遺傳算法。

給定一個背包C=100，N=5個物品，其重量和價值分別如下，求這個背包能裝的最大價值是多少

177 92 2 22 22 3 29 87 4 50 46 5 99 90

4.2.1編碼

那麼針對上面這個問題，首先我們要考慮編碼，也就是把它轉換成我們的基因型的形式，這裡，我們用一個長度為5的二進位字符串表示相應物品的取捨。其基因型（染色體）就是10100,那麼表現型就是選擇了1號物品和3號物品。有編碼自然就有解碼，就是把基因型轉換成表現型，編碼個人認為是遺傳算法中至關重要的一步，怎麼根據問題去選擇編碼方式，直接影響了後面所提到的適應函數的簡與複雜。

把問題映射到基因型上我們已經解決了，現在就是怎麼去考核一個基因型對當前環境的適應度，換句話說就是更有可能存活遺傳下去，那麼這裡我們必須得設計一個適應函數f，因為是求背包的最大值，又因為不能超過背包所能承受的總重量，所以用h(x)表示第二個不超過總重量的條件，f(y)表示背包的價值，所以得到適應函數f(h(x))。

4.2.2選擇

然後就是怎麼去選擇的問題，我們用p(x)=f(y)/totall(f(y))來表示某個基因型佔總體的概率，現在我們就採用輪盤賭的方法，什麼是輪盤賭呢，這裡簡要提及一下，我們把各個概率放在一個輪盤裡，然後轉動這個輪盤，最後輪盤停止，指針停在哪裡就代表選擇哪個概率的事件。

比如在01背包中，我們根據適應函數算出各個基因型的適應度，也算出了每個基因型所佔的比例，然後我們根據輪盤賭的方法從中選擇出n條基因型出來，然後n條基因型隨機兩兩配對交叉產生兩個子代。

4.2.3交叉

那麼什麼是交叉呢，和生物學中染色體交叉是一樣的概念，就是互換某一段基因，如下圖，這裡我們採用的是單點交叉。

4.2.4變異

變異是指，在某一個比較小的概率下，某個基因在遺傳時，某個基因座上的基因由0邊成1，或者由1變成0。

新產生的基因型，如果原來的種群中沒有的話，就加進這個種群，然後再按上面所述去迭代，直到找到我們比較滿意的基因型為止，現在我們什麼都準備好了，就讓它們去交配把，去創建一個種族吧。

實際上基本的遺傳算法是有很多不足的，如容易選入局部收斂，全局搜索能力不夠強，但是基本的遺傳算法是有很多可以改進的地方，如交叉算子的設計、變異算子的設計、選擇策略等等，有關遺傳算法個人覺得作為一種智能啟發式搜索算法它甚至比別的普通算法（如動態規劃）理解起來還容易，而且它特別容易與別的算法相結合，設計新的混合算法，另外在基本遺傳算法的基礎上還衍生出了很多別的算法，如免疫遺傳算法，這些都是一些比較高級的算法。

五、局部搜索

局部搜索是解決最優化問題的一種啟發式算法。對於某些計算起來非常複雜的最優化問題，比如各種NP完全問題，要找到最優解需要的時間隨問題規模呈指數增長，因此誕生了各種啟發式算法來退而求其次尋找次優解，是一種近似算法（Approximate algorithms），以時間換精度的思想。局部搜索就是其中的一種方法。

鄰域動作是一個函數，通過這個函數，對當前解s，產生其相應的鄰居解集合。例如：對於一個bool型問題，其當前解為：s = 1001，當將鄰域動作定義為翻轉其中一個bit時，得到的鄰居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，當將鄰域動作定義為互換相鄰bit時，得到的鄰居解的集合N(s)={0101,1001,1010}.

5.1過程描述

局部搜索算法從一個初始解開始，通過鄰域動作，產生其鄰居解，判斷鄰居解的質量，根據某種策略，來選擇鄰居解，重複上述過程，至到達終止條件。不同局部搜索算法的區別就在於：鄰域動作的定義和選擇鄰居解的策略，也是決定算法好壞的關鍵（集中性和發散性，Intensification and Diversification）。

5.2迭代局部搜索（IteratedLocal Search, ILS）

在局部搜索得到的局部最優解上，加入了擾動，再重新進行局部搜索。其思想是：物以類聚，好的解之間會有一些共性，所以在局部最優解上做擾動，比隨機的選擇一個初始解在進行局部搜索，效果更好。

5.3變鄰域搜索（VariableNeighborhood Search, VNS）

·變鄰域搜索算法的主要思想是：採用多個不同的鄰域進行系統搜索。首先採用最小的鄰域搜索，當無法改進解時，則切換到稍大一點的鄰域。如果能繼續改進解，則退回到最小的鄰域，否則繼續切換到更大的鄰域。

·變鄰域搜索的特點是利用不同的動作構成的鄰域結構進行交替搜索，在集中性和疏散性之間達到很好的平衡。

·其思想可以概括為「變則通」。

等，還有其他的局部搜索算法。

六、網上好的總結

啟發式算法蘊含著許多人生哲學，它雖不是數學方法，其思想更類似於人類解決問題的思想和一些人生中總結的道理，值得好好體會。最後用網上一段描述局部搜索的例子來作為總結：

為了找出地球上最高的山，一群有志氣的兔子們開始想辦法。

· 兔子朝著比現在高的地方跳去。他們找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是Iterative Improvement，它不能保證局部最優值就是全局最優值。

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

·兔子們知道一個兔的力量是渺小的。他們互相轉告著，哪裡的山已經找過，並且找過的每一座山他們都留下一隻兔子做記號。他們制定了下一步去哪裡尋找的策略。這就是禁忌搜索。

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