幾種智能算法的原理和應(yīng)用介紹專題培訓(xùn)課件

1、幾種智能算法的原理和應(yīng)用介紹主要內(nèi)容：1. 遺傳算法2. 蟻群算法3. 模擬退火算法4. 粒子群算法5. 總結(jié)與體會(huì)1. 遺傳算法1.1 遺傳算法簡介1.2 遺傳算法的基本思想1.3 遺傳算法的基本操作1.4 遺傳算法的構(gòu)成要素1.5 遺傳算法的操作步驟1.6 遺傳算法的特點(diǎn)1.7 遺傳算法的應(yīng)用領(lǐng)域1.8 遺傳算法的應(yīng)用舉例1.1 遺傳算法簡介 遺傳算法簡稱GA（Genetic Algorithms）是1962年由美國Michigan大學(xué)的Holland教授提出的模擬自然界遺傳機(jī)制和生物進(jìn)化論而成的一種并行隨機(jī)搜索最優(yōu)化方法。 遺傳算法是以達(dá)爾文的自然選擇學(xué)說為基礎(chǔ)發(fā)展起來的。自然選擇學(xué)說包

2、括以下三個(gè)方面： （1）遺傳：這是生物的普遍特征，親代把生物信息交給子代，子代總是和親代具有相同或相似的性狀。生物有了這個(gè)特征，物種才能穩(wěn)定存在。 （2）變異：親代和子代之間以及子代的不同個(gè)體之間的差異，稱為變異。變異是隨機(jī)發(fā)生的，變異的選擇和積累是生命多樣性的根源。 （3）生存斗爭和適者生存：具有適應(yīng)性變異的個(gè)體被保留下來，不具有適應(yīng)性變異的個(gè)體被淘汰，通過一代代的生存環(huán)境的選擇作用，性狀逐漸逐漸與祖先有所不同，演變?yōu)樾碌奈锓N。1.2 遺傳算法的基本思想 遺傳算法將“優(yōu)勝劣汰，適者生存”的生物進(jìn)化原理引入優(yōu)化參數(shù)形成的編碼串聯(lián)群體中，按所選擇的適應(yīng)度函數(shù)并通過遺傳中的復(fù)制、交叉及變異對個(gè)體進(jìn)

3、行篩選，使適適應(yīng)度高的個(gè)體被保留下來，組成新的群體，新的群體既繼承了上一代的信息，又優(yōu)于上一代。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。遺傳算法的算法簡單，可并行處理，并能到全局最優(yōu)解。1.3 遺傳算法的基本操作 遺傳算法的基本操作主要有：復(fù)制、交叉、變異。（1）復(fù)制（Reproduction Operator） 復(fù)制是從一個(gè)舊種群中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過程。具有高適應(yīng)度的位串更有可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。 復(fù)制操作可以通過隨機(jī)方法來實(shí)現(xiàn)。首先產(chǎn)生01之間均勻分布的隨機(jī)數(shù)，若某串的復(fù)制概率為40%，則當(dāng)產(chǎn)生的隨機(jī)數(shù)在0.401.0之間時(shí)，該串被復(fù)制，否

4、則被淘汰。1.3 遺傳算法的基本操作（2）交叉（Crossover Operator） 復(fù)制操作能從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體。而交叉模擬了生物進(jìn)化過程中的繁殖現(xiàn)象，通過兩個(gè)染色體的交換組合，來產(chǎn)生新的優(yōu)良品種。 交叉的過程為：在匹配池中任選兩個(gè)染色體，隨機(jī)選擇一點(diǎn)或多點(diǎn)交換點(diǎn)位置；交換雙親染色體交換點(diǎn)右邊的部分，即可得到兩個(gè)新的染色體數(shù)字串。 交叉體現(xiàn)了自然界中信息交換的思想。交叉有一點(diǎn)交叉、多點(diǎn)交叉、還有一致交叉、順序交叉和周期交叉。一點(diǎn)交叉是最基本的方法，應(yīng)用較廣。它是指染色體切斷點(diǎn)有一處，例：1.3 遺傳算法的基本操作（3）變異(Mutation Operator) 變

5、異運(yùn)算用來模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)地改變遺傳基因（表示染色體的符號(hào)串的某一位）的值。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由1變?yōu)?，或由0變?yōu)?。 若只有選擇和交叉，而沒有變異，則無法在初始基因組合以外的空間進(jìn)行搜索，使進(jìn)化過程在早期就陷入局部解而進(jìn)入終止過程，從而影響解的質(zhì)量。為了在盡可能大的空間中獲得質(zhì)量較高的優(yōu)化解，必須采用變異操作。變異操作如下所示：1.4 遺傳算法的構(gòu)成要素 遺傳算法的構(gòu)成要素主要有：染色體編碼方法、個(gè)體適應(yīng)度評(píng)價(jià)、遺傳算子及遺傳算法的運(yùn)行參數(shù)。（1）染色體編碼方法 基本遺傳算法使用固定長度的二

6、進(jìn)制符號(hào)來表示群體中的個(gè)體，其等位基因是由二值符號(hào)集0,1所組成。初始個(gè)體基因值可用均勻分布的隨機(jī)值生成，如：就可表示一個(gè)個(gè)體，該個(gè)體的染色體長度是18。1.4 遺傳算法的構(gòu)成要素（2）個(gè)體適應(yīng)度評(píng)價(jià) 基本遺傳算法與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的概率多少。為正確計(jì)算這個(gè)概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。因此，必須先確定由目標(biāo)函數(shù)值J到個(gè)體適應(yīng)度f之間的轉(zhuǎn)換規(guī)則。（3）遺傳算子 基本遺傳算法使用下述三種遺傳算子： 選擇運(yùn)算:使用比例選擇算子； 交叉運(yùn)算:使用單點(diǎn)交叉算子； 變異運(yùn)算:使用基本位變異算子或均勻變異算子。1.4 遺傳算法的構(gòu)成要素（4）基本

7、遺傳算法的運(yùn)行參數(shù) 有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定： M ：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20-100； G ：遺傳算法的終止進(jìn)化代數(shù)，一般取為100-500； Pc：交叉概率，一般取為0.4-0.99； Pm：變異概率，一般取為0.0001-0.1。1.5 遺傳算法的操作步驟 對于一個(gè)需要進(jìn)行優(yōu)化的實(shí)際問題，一般可按下述步驟構(gòu)造遺傳算法： 第一步：確定決策變量及各種約束條件； 第二步：建立優(yōu)化模型，即確定出目標(biāo)函數(shù)的類型及數(shù)學(xué)描述形式或量化方法； 第三步：確定表示可行解的染色體編碼方法； 第四步：確定解碼方法； 第四步：確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，即確定出由目標(biāo)函數(shù)值到個(gè)體適應(yīng)

8、度的轉(zhuǎn)換規(guī)則； 第五步：設(shè)計(jì)遺傳算子，即確定選擇運(yùn)算、交叉運(yùn)算、變異運(yùn)算等遺傳算子的具體操作方法。 第六步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即M,G,Pc,Pm等參數(shù)。1.5 遺傳算法的操作步驟 遺傳算法流程圖：1.6 遺傳算法的特點(diǎn)遺傳算法的主要特點(diǎn)有： （1）遺傳算法是對參數(shù)的編碼進(jìn)行操作，而非對參數(shù)本身，這就是使得我們在優(yōu)化計(jì)算過程中可以借鑒生物學(xué)中染色體和基因等概念，模仿自然界中生物的遺傳和進(jìn)化等機(jī)理； （2）遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息。傳統(tǒng)的優(yōu)化方法往往是從解空間的單個(gè)初始點(diǎn)開始最優(yōu)解的迭代搜索過程，單個(gè)搜索點(diǎn)所提供的信息不多，搜索效率不高，有時(shí)甚至使搜索過程局限于局部最優(yōu)解而

9、停滯不前。 遺傳算法從由很多個(gè)體組成的一個(gè)初始群體開始最優(yōu)解的搜索過程，而不是從一個(gè)單一的個(gè)體開始搜索，這是遺傳算法所特有的一種隱含并行性，因此遺傳算法的搜索效率較高。 （3）遺傳算法直接以目標(biāo)函數(shù)作為搜索信息。傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，而且需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等輔助信息才能確定搜索方向。而遺傳算法僅使用由目標(biāo)函數(shù)值變換來的適應(yīng)度函數(shù)值，就可以確定進(jìn)一步的搜索方向和搜索范圍，無需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。1.6 遺傳算法的特點(diǎn) 遺傳算法可應(yīng)用于目標(biāo)函數(shù)無法求導(dǎo)數(shù)或?qū)?shù)不存在的函數(shù)的優(yōu)化問題，以及組合優(yōu)化問題等。 （4）遺傳算法使用概率搜索技術(shù)。遺傳算法的選擇、交叉、變異等

10、運(yùn)算都是以一種概率的方式來進(jìn)行的，因而遺傳算法的搜索過程具有很好的靈活性。隨著進(jìn)化過程的進(jìn)行，遺傳算法新的群體會(huì)更多地產(chǎn)生出許多新的優(yōu)良的個(gè)體。 （5）遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目地窮舉或完全隨機(jī)搜索； （6）遺傳算法對于待尋優(yōu)的函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，也不要求函數(shù)可微，既可以是數(shù)學(xué)解析式所表示的顯函數(shù)，又可以是映射矩陣甚至是神經(jīng)網(wǎng)絡(luò)的隱函數(shù)，因而應(yīng)用范圍較廣； （7）遺傳算法具有并行計(jì)算的特點(diǎn)，因而可通過大規(guī)模并行計(jì)算來提高計(jì)算速度，適合大規(guī)模復(fù)雜問題的優(yōu)化。 1.7 遺傳算法的應(yīng)用領(lǐng)域 遺傳算法的應(yīng)用領(lǐng)域主要有：函數(shù)優(yōu)化、組合優(yōu)化、生產(chǎn)調(diào)度問題、自動(dòng)控制、機(jī)器人

11、、圖像處理等。（1）函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。尤其是對非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，采用其他優(yōu)化方法較難求解，而遺傳算法卻可以得到較好的結(jié)果。（2）組合優(yōu)化。 隨著問題的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，采用傳統(tǒng)的優(yōu)化方法很難得到最優(yōu)解。遺傳算法是尋求這種滿意解的最佳工具。例如，遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應(yīng)用。1.7 遺傳算法的應(yīng)用領(lǐng)域（3）生產(chǎn)調(diào)度問題 在很多情況下，采用建立數(shù)學(xué)模型的方法難以對生產(chǎn)調(diào)度問題進(jìn)行精確求解。在現(xiàn)實(shí)生產(chǎn)中多采用一些經(jīng)驗(yàn)進(jìn)行調(diào)度。遺傳算法是解決復(fù)雜

12、調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。（4）自動(dòng)控制 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已經(jīng)在其中得到了初步的應(yīng)用。例如，利用遺傳算法進(jìn)行控制器參數(shù)的優(yōu)化、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、基于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化和權(quán)值學(xué)習(xí)等。1.7 遺傳算法的應(yīng)用領(lǐng)域（5）機(jī)器人 例如，遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。（6）圖像處理 遺傳算法可用于圖像處理過程中的掃描、特征提取、圖像分割等的優(yōu)化計(jì)算。目前遺傳算

13、法已經(jīng)在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用。1.8 遺傳算法的應(yīng)用舉例1 用遺傳算法求函數(shù)極值利用遺傳算法求Rosenbrock函數(shù)的極大值：求解該問題遺傳算法的構(gòu)造過程：（1）確定決策變量和約束條件決策變量為：（2）建立優(yōu)化模型1.8 遺傳算法的應(yīng)用舉例（3）確定編碼方法 用長度為10位的二進(jìn)制編碼串來分別表示兩個(gè)決策變量x1,x2。10位二進(jìn)制編碼串可以表示從0到1023之間的1024個(gè)不同的數(shù)，故將x1,x2的定義域離散化為1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有1024個(gè)不同的離散點(diǎn)。 從離散點(diǎn)-2.048到離散點(diǎn)2.048 ，分別對應(yīng)于從0000000000(0)

14、到1111111111(1023)之間的二進(jìn)制編碼。 將x1,x2分別表示的兩個(gè)10位長的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間就具有一一對應(yīng)的關(guān)系。例如：表示一個(gè)個(gè)體的基因型，其中前10位表示x1，后10位表示x2。1.8 遺傳算法的應(yīng)用舉例（4）確定解碼方法 解碼時(shí)需要將20位長的二進(jìn)制編碼串切斷為兩個(gè)10位長的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。 依據(jù)個(gè)體編碼方法和對定義域的離散化方法可知，將代碼y轉(zhuǎn)換為變量x的解碼公式為：例如，對個(gè)體：它由兩

15、個(gè)代碼所組成上述兩個(gè)代碼經(jīng)過解碼后，可得到兩個(gè)實(shí)際的值1.8 遺傳算法的應(yīng)用舉例（5）確定個(gè)體評(píng)價(jià)方法 由于Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故可將個(gè)體的適應(yīng)度直接取為對應(yīng)的目標(biāo)函數(shù)值，即選個(gè)體適應(yīng)度的倒數(shù)作為目標(biāo)函數(shù) 選擇運(yùn)算使用比例選擇算子，交叉運(yùn)算使用單點(diǎn)交叉算子，變異運(yùn)算使用基本位變異算子。（6）確定個(gè)體評(píng)價(jià)方法 群體大小M=80，終止進(jìn)化代數(shù)G=100，交叉概率Pc=0.60，變異概率Pm=0.10。（7）確定遺傳算法的運(yùn)行參數(shù)1.8 遺傳算法的應(yīng)用舉例（8）實(shí)驗(yàn)過程完全隨機(jī)生成初始種群 循環(huán)八次，達(dá)到暫時(shí)的最優(yōu)值：3414.8 對應(yīng)的x1、x2

16、坐標(biāo)為：(-1.9799,-1.9159) 種群向暫時(shí)的最優(yōu)染色體靠近。1.8 遺傳算法的應(yīng)用舉例平均分配坐標(biāo)軸生成初始種群 循環(huán)八次，達(dá)到最優(yōu)值：3905.9 對應(yīng)的x1、x2坐標(biāo)為：(-2.0480,-2.0480) 種群向最優(yōu)染色體靠近。1.8 遺傳算法的應(yīng)用舉例 上述七個(gè)步驟構(gòu)成了用于求函數(shù)極大值的優(yōu)化計(jì)算基本遺傳算法。采用上述方法進(jìn)行仿真，經(jīng)過100步迭代，最佳樣本為即當(dāng)時(shí)，Rosenbrock函數(shù)具有極大值，極大值為3905.9。1.8 遺傳算法的應(yīng)用舉例2 用遺傳算法進(jìn)行圖像匹配（1）問題描述： 從一張圖片中找出與另一張圖片相似的部分。（為了便于說明問題，本實(shí)驗(yàn)中目標(biāo)圖片為匹配圖

17、片加黑色背景隨機(jī)生成，如下圖所示：）1.8 遺傳算法的應(yīng)用舉例2 用遺傳算法進(jìn)行圖像匹配（2）編碼 對匹配圖片左上角第一個(gè)像素在目標(biāo)圖片內(nèi)的位置進(jìn)行編碼（要求匹配圖片不能超出目標(biāo)圖片的邊界），采用二進(jìn)制編碼。（3）計(jì)算適應(yīng)度 適應(yīng)度函數(shù)取為兩幅圖片對應(yīng)位置上的值差的平方和的倒數(shù)。（4）選擇 按適應(yīng)度函數(shù)的大小計(jì)算種群中某個(gè)體被選中的概率，按概率選擇下一代種群。1.8 遺傳算法的應(yīng)用舉例2 用遺傳算法進(jìn)行圖像匹配（5）交叉 單點(diǎn)交叉、多點(diǎn)交叉（要求匹配圖片不能超出目標(biāo)圖片的邊界）。（6）變異 要求匹配圖片不能超出目標(biāo)圖片的邊界。1.8 遺傳算法的應(yīng)用舉例（7）實(shí)驗(yàn)結(jié)果與分析 對于此類簡單的圖片匹

18、配的問題，遺傳算法通常能較快的收斂到一個(gè)較好的位置，但對于復(fù)雜一些的圖片匹配問題，容易收斂到局部極值點(diǎn)。2. 蟻群算法2.1 螞蟻生物學(xué)特征2.2 Deneubourg雙橋?qū)嶒?yàn)2.3 蟻群算法的定義2.4 蟻群算法的原理2.5 蟻群算法的規(guī)則2.6 蟻群算法的特點(diǎn)2.7 蟻群算法的應(yīng)用領(lǐng)域2.8 蟻群算法的應(yīng)用舉例2.1 螞蟻的生理學(xué)特征 螞蟻在8000萬年前就建立起了自己的社會(huì)。許多“螞蟻城市”往往由5000萬個(gè)成員組成，并且是一個(gè)組織完好的復(fù)雜“城市”。 螞蟻的群體行為主要包括尋找食物、任務(wù)分配和構(gòu)造墓穴。 研究中主要是以螞蟻尋找食物之后能選擇一條最短路徑來連接蟻穴和食物源。 螞蟻具有智能

19、么？ 生物學(xué)家通過對螞蟻的長期觀察研究發(fā)現(xiàn)，每只螞蟻的智能并不高，看起來沒有集中的指揮，但他們卻能協(xié)同的工作，集中食物建立起穩(wěn)固的蟻穴，依靠群體的能力發(fā)揮出了超出個(gè)體的智能。2.2 Deneubourg雙橋?qū)嶒?yàn) Pasteels，Deneubourg和Goss（1987）全部都在實(shí)驗(yàn)中研究真實(shí)螞蟻信息素的遺留行為，他們稱之為“雙橋?qū)嶒?yàn)”。在這個(gè)雙橋?qū)嶒?yàn)?zāi)Ｐ椭校佈ㄍㄟ^一個(gè)蟻穴和食物源之間用兩個(gè)長度相等的橋連接。作者使用能夠辨認(rèn)路徑的阿根廷螞蟻，簡而言之這些螞蟻可以預(yù)測或者搜索他們的群類。2.2 Deneubourg雙橋?qū)嶒?yàn)等長雙橋?qū)嶒?yàn) 在前面的設(shè)定下，螞蟻開始探索蟻穴周圍的環(huán)境最終到達(dá)食物源。

20、沿著他們的在蟻穴和食物源之間的路徑，阿根廷釋放信息素，開始每個(gè)螞蟻都隨機(jī)選擇兩條橋之間的的一個(gè)，在隨后的階段里因?yàn)殡S機(jī)的波動(dòng)，其中一個(gè)橋的信息素表現(xiàn)出比另外一條的信息素更為集中，因此吸引了更多的螞蟻。這個(gè)行為增加了這個(gè)橋上的信息素，也就吸引了更多的螞蟻。因此，過了一段時(shí)間以后，整個(gè)種群都聚合于使用這個(gè)高度集中的橋運(yùn)送。2.2 Deneubourg雙橋?qū)嶒?yàn) Goss，Aron，Deneubourg和Pasteel（1989）提出上述雙橋?qū)嶒?yàn)的變種，在其中一個(gè)橋要比另一個(gè)橋更長，如下圖所示；在這種情況下，螞蟻選擇了近的路徑首先到達(dá)了蟻穴。因此，短橋比長橋得到了更為密集的信息素增長了螞蟻選擇短橋的的

21、可能性。Goss，Aron，Deneubourg和Pasteel（1990）將觀察的的真實(shí)的螞蟻建立到假設(shè)的模型中。首先，假設(shè)橋上殘留的信息素量和過去一段時(shí)間經(jīng)過該橋的螞蟻數(shù)成正比(信息素?fù)]發(fā)的情況);其次某一時(shí)刻螞蟻按照橋上信息素量的多少來選擇某支橋，即螞蟻選擇某支橋的概率與經(jīng)過該橋的螞蟻數(shù)成正比。當(dāng)所有的m只螞蟻都經(jīng)過兩支橋以后，設(shè)Am和Bm分別為經(jīng)過A橋和B橋的螞蟻數(shù)(Am+Bm=m)，則第m+1只螞蟻選擇A(B)橋的概率為:2.2 Deneubourg雙橋?qū)嶒?yàn)公式表明：往A走的螞蟻越多，選擇分支A的概率就越高。 n和k用以匹配真實(shí)實(shí)驗(yàn)數(shù)據(jù)。 “n”決定選擇公式的非線性程度。（n越大，信

22、息素多一點(diǎn)的分支選擇概率越高） “k”表示對未標(biāo)記的分支的吸引程度。（k越大，則進(jìn)行非隨機(jī)化選擇所需的信息素濃度越高） 這種概率的表達(dá)方式是實(shí)際的螞蟻路徑選擇實(shí)驗(yàn)推導(dǎo)而來的，比較符合實(shí)驗(yàn)的參數(shù)設(shè)置是n=2和k=20.2.3 蟻群算法的定義 蟻群算法(ant colony optimization, ACO)，又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。 這種算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征，本質(zhì)上是進(jìn)化算法中的一種新型的啟發(fā)式優(yōu)化算法。 人工蟻群與真實(shí)螞蟻的異同比較：相同點(diǎn)： （1）都存在一個(gè)群體中個(gè)體相互交流通信的機(jī)制 （2）都要完成一個(gè)相同的任務(wù) （3）利用當(dāng)前信

23、息進(jìn)行路徑選擇的隨機(jī)選擇策略不同點(diǎn)： （1）人工螞蟻他們的移動(dòng)是從一個(gè)狀態(tài)到另一個(gè) 狀態(tài)的轉(zhuǎn)換 （2）人工螞蟻具有一個(gè)記憶其本身過去行為的內(nèi)在狀態(tài) （3）人工螞蟻存在于一個(gè)與時(shí)間無關(guān)聯(lián)的環(huán)境之中 （4）人工蟻不是盲從的，受環(huán)境空間的啟發(fā) （5）人工蟻可以根據(jù)要求增加功能2.4 蟻群算法的原理 螞蟻在運(yùn)動(dòng)過程中會(huì)通過在路上釋放一種特殊的分泌物信息素來尋找路徑。當(dāng)它碰到一個(gè)還沒有走過的路口是就隨機(jī)的選擇一條路徑前行，同時(shí)釋放出與路徑長度有關(guān)的信息素。螞蟻?zhàn)叩穆吩介L，則釋放的信息量越小。當(dāng)后來的螞蟻再次碰到這個(gè)路口時(shí)，選擇信息量較大的路徑的概率相對較大，這樣便形成了一個(gè)正反饋機(jī)制。最優(yōu)路徑上得信息量

24、越來越大，而其他路徑上的信息量卻隨時(shí)間逐漸減少最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。 （1）蟻群之間通過信息素和環(huán)境進(jìn)行通信。 （2）螞蟻對環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。 （3）個(gè)體水平上，每個(gè)螞蟻相對獨(dú)立；群體水平上，每只螞蟻的行為是隨機(jī)的。 蟻群算法的理論假設(shè)2.5 蟻群算法的規(guī)則蟻群算法中的螞蟻滿足的規(guī)則主要有以下幾個(gè)方面： 螞蟻觀察到的范圍是一個(gè)方格世界，螞蟻有一個(gè)參數(shù)為速度半徑（一般是3），那么它能觀察到的范圍就是3*3個(gè)方格世界，并且能移動(dòng)的距離也在這個(gè)范圍之內(nèi)。 （1）范圍 螞蟻所在的環(huán)境是一個(gè)虛擬的世界，其中有障礙物，有別的螞蟻，還有信息素，信息素有兩種，一種是找到食物的螞蟻灑下的食物信息

25、素，一種是找到窩的螞蟻灑下的窩的信息素。每個(gè)螞蟻都僅僅能感知它范圍內(nèi)環(huán)境信息。環(huán)境以一定的速率讓信息素消失 。 （2）環(huán)境2.5 蟻群算法的規(guī)則 在每只螞蟻能感知的范圍內(nèi)尋找是否有食物，如果有就直接過去。否則看是否有信息素，并且比較在能感知的范圍內(nèi)哪一點(diǎn)的信息素最多，這樣，它就朝信息素多的地方走，并且每只螞蟻都會(huì)以小概率犯錯(cuò)誤，從而并不是往信息素最多的點(diǎn)移動(dòng)。螞蟻找窩的規(guī)則和上面一樣，只不過它對窩的信息素做出反應(yīng)，而對食物信息素沒反應(yīng)。 （3）覓食規(guī)則 每只螞蟻都朝向信息素最多的方向移，并且，當(dāng)周圍沒有信息素指引的時(shí)候，螞蟻會(huì)按照自己原來運(yùn)動(dòng)的方向慣性的運(yùn)動(dòng)下去，并且，在運(yùn)動(dòng)的方向有一個(gè)隨機(jī)的

26、小的擾動(dòng)。為了防止螞蟻原地轉(zhuǎn)圈，它會(huì)記住最近剛走過了哪些點(diǎn)，如果發(fā)現(xiàn)要走的下一點(diǎn)已經(jīng)在最近走過了，它就會(huì)盡量避開。 （4）移動(dòng)規(guī)則2.5 蟻群算法的規(guī)則 如果螞蟻要移動(dòng)的方向有障礙物擋住，它會(huì)隨機(jī)的選擇另一個(gè)方向，并且有信息素指引的話，它會(huì)按照覓食的規(guī)則行為。 （5）避障規(guī)則 每只螞蟻在剛找到食物或者窩的時(shí)候撒發(fā)的信息素最多，并隨著它走遠(yuǎn)的距離，播撒的信息素越來越少。 （6）撒播信息素規(guī)則 根據(jù)這幾條規(guī)則，螞蟻之間并沒有直接的關(guān)系，但是每只螞蟻都和環(huán)境發(fā)生交互，而通過信息素這個(gè)紐帶，實(shí)際上把各個(gè)螞蟻之間關(guān)聯(lián)起來了。比如，當(dāng)一只螞蟻找到了食物，它并沒有直接告訴其它螞蟻這兒有食物，而是向環(huán)境播撒信

27、息素，當(dāng)其它的螞蟻經(jīng)過它附近的時(shí)候，就會(huì)感覺到信息素的存在，進(jìn)而根據(jù)信息素的指引找到了食物。2.6 蟻群算法的特點(diǎn) 在系統(tǒng)論中，自組織和它組織是組織的兩個(gè)基本分類，其區(qū)別在于組織力或組織指令是來自于系統(tǒng)的內(nèi)部還是來自于系統(tǒng)的外部，來自于系統(tǒng)內(nèi)部的是自組織，來自于系統(tǒng)外部的是他組織。如果系統(tǒng)在獲得空間的、時(shí)間的或者功能結(jié)構(gòu)的過程中，沒有外界的特定干預(yù)，我們便說系統(tǒng)是自組織的。在抽象意義上講，自組織就是在沒有外界作用下使得系統(tǒng)墑增加的過程(即是系統(tǒng)從無序到有序的變化過程)。蟻群算法充分休現(xiàn)了這個(gè)過程，以螞蟻群體優(yōu)化為例子說明。當(dāng)算法開始的初期，單個(gè)的人工螞蟻無序的尋找解，算法經(jīng)過一段時(shí)間的演化，人

28、工螞蟻間通過信息激素的作用，自發(fā)的越來越趨向于尋找到接近最優(yōu)解的一些解，這就是一個(gè)無序到有序的過程。（1）蟻群算法是一種自組織的算法。2.6 蟻群算法的特點(diǎn) 每只螞蟻搜索的過程彼此獨(dú)立，僅通過信息激素進(jìn)行通信。所以蟻群算法則可以看作是一個(gè)分布式的多agent系統(tǒng)，它在問題空間的多點(diǎn)同時(shí)開始進(jìn)行獨(dú)立的解搜索，不僅增加了算法的可靠性，也使得算法具有較強(qiáng)的全局搜索能力。（2）蟻群算法是一種本質(zhì)上并行的算法。2.6 蟻群算法的特點(diǎn) 從真實(shí)螞蟻的覓食過程中我們不難看出，螞蟻能夠最終找到最短路徑，直接依賴于最短路徑上信息激素的堆積，而信息激素的堆積卻是一個(gè)正反饋的過程。對蟻群算法來說，初始時(shí)刻在環(huán)境中存在

29、完全相同的信息激素，給予系統(tǒng)一個(gè)微小擾動(dòng)，使得各個(gè)邊上的軌跡濃度不相同，螞蟻構(gòu)造的解就存在了優(yōu)劣，算法采用的反饋方式是在較優(yōu)的解經(jīng)過的路徑留下更多的信息激素，而更多的信息激素又吸引了更多的螞蟻，這個(gè)正反饋的過程使得初始的不同得到不斷的擴(kuò)大，同時(shí)又引導(dǎo)整個(gè)系統(tǒng)向最優(yōu)解的方向進(jìn)化。因此，正反饋是螞蟻算法的重要特征，它使得算法演化過程得以進(jìn)行。 （3）蟻群算法是一種正反饋的算法。2.6 蟻群算法的特點(diǎn) 相對于其它算法，蟻群算法對初始路線要求不高，即蟻群算法的求解結(jié)果不依賴子初始路線的選擇，而且在搜索過程中不需要進(jìn)行人工的調(diào)整。其次，蟻群算法的參數(shù)數(shù)目少，設(shè)置簡單，易于蟻群算法應(yīng)用到其它組合優(yōu)化問題的

30、求解。 （4）蟻群算法具有較強(qiáng)的魯棒性。2.7 蟻群算法的應(yīng)用領(lǐng)域 蟻群算法主要應(yīng)用于：組合優(yōu)化問題、車間作業(yè)調(diào)度問題、網(wǎng)絡(luò)路由問題、車輛路徑問題、機(jī)器人領(lǐng)域、電力系統(tǒng)、故障診斷、控制參數(shù)優(yōu)化、巖土工程、生命科學(xué)等若干領(lǐng)域。2.8 蟻群算法的應(yīng)用舉例蟻群算法解決TSP問題 旅行商問題，即TSP問題（Travelling Salesman Problem）又譯為旅行推銷員問題、貨郎擔(dān)問題，是數(shù)學(xué)領(lǐng)域中著名問題之一。假設(shè)有一個(gè)旅行商人要拜訪n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標(biāo)是要求得的路徑路程為所有路徑之中的最小值。 TS

31、P問題是一個(gè)組合優(yōu)化問題。該問題可以被證明具有NPC計(jì)算復(fù)雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評(píng)價(jià)和關(guān)注。2.8.1 問題描述2.8 蟻群算法的應(yīng)用舉例（1）螞蟻主體具有的特征：2.8.2 用蟻群算法解決TSP問題 在從城市i到j(luò)的過程中或者一次循環(huán)結(jié)束，在邊（i，j）釋放信息素。 有概率的訪問下一個(gè)城市，這個(gè)概率是兩城市間和連接兩城市的路徑上存有軌跡量的函數(shù)。 不允許螞蟻訪問已經(jīng)訪問過的城市2.8 蟻群算法的應(yīng)用舉例（2）引入相關(guān)記號(hào) 為了模擬實(shí)際蟻群的行為首先引入以下記號(hào)：2.8 蟻群算法的應(yīng)用舉例（3）螞蟻從一個(gè)城市移動(dòng)到另一個(gè)城市的概率 在初始時(shí)刻，各條路徑上

32、的信息素量相等，設(shè)。 螞蟻k（k=1，2，m）在運(yùn)動(dòng)中根據(jù)各條路徑上的信息素量決定轉(zhuǎn)移方向。 位于城市i的螞蟻k選擇移動(dòng)到城市j的概率為：公式 12.8 蟻群算法的應(yīng)用舉例（4）禁忌表 與真實(shí)蟻不同，人工蟻群系統(tǒng)具有記憶功能。為了滿足螞蟻必須經(jīng)過所有n個(gè)不同的城市這個(gè)約束條件，為每只螞蟻都設(shè)計(jì)了一個(gè)數(shù)據(jù)結(jié)構(gòu)，成為禁忌表。用來記錄了t時(shí)刻螞蟻已經(jīng)經(jīng)過的城市，不允許該螞蟻在本次循環(huán)中再經(jīng)過這些城市。當(dāng)本次循環(huán)結(jié)束后禁忌表被用來計(jì)算該螞蟻所建立的解決方案。之后禁忌表清空螞蟻又可以自由地選擇。2.8 蟻群算法的應(yīng)用舉例（5）信息素的調(diào)整 經(jīng)過n個(gè)時(shí)刻，螞蟻完成一次循環(huán)，各路徑上的信息素根據(jù)如下公式調(diào)整

33、：其中：表示第k只螞蟻在時(shí)刻(t,t+1)留在路徑(i,j)上的信息素。表示本次循環(huán)路徑(i,j)上的信息素增量。公式 32.8 蟻群算法的應(yīng)用舉例（6）實(shí)現(xiàn)過程2.8 蟻群算法的應(yīng)用舉例2.8 蟻群算法的應(yīng)用舉例2.8 蟻群算法的應(yīng)用舉例（5）仿真結(jié)果 采用MATLAB來仿真實(shí)現(xiàn)蟻群算法解TSP問題 。對全國31個(gè)省會(huì)城市的一個(gè)TSP計(jì)算。通過程序仿真得到。實(shí)驗(yàn)結(jié)果非常好！2.8.3 用遺傳算法解決TSP問題（1）用遺傳算法解TSP問題主要集中在以下幾個(gè)方面：2.8.3 用遺傳算法解決TSP問題 采用適當(dāng)?shù)谋硎痉椒ū硎緜€(gè)體的編碼； 設(shè)計(jì)可用的遺傳算子，以保持父代的特性避免新個(gè)體的不可行性；

34、防止算法過早的收斂。（2）編碼 路徑表示是TSP問題最自然、最直接的表示方式。它直接采用城市在路徑中的相對位置來進(jìn)行表示。 例如，路徑517862934直接表示成（5 1 7 8 6 2 9 3 4）。2.8.3 用遺傳算法解決TSP問題（3）交叉部分映射雜交 首先隨機(jī)地在父體中選取兩個(gè)雜交點(diǎn)，并交換相應(yīng)的段，再根據(jù)該段內(nèi)的城市確定部分映射。在每個(gè)父體上先填入無沖突的城市，而對有沖突的城市依照映射關(guān)系選擇候選的城市，直到找到無沖突的城市填入，按此方法獲得了雜交后的兩個(gè)后代。 實(shí)例：如兩父串及匹配區(qū)域?yàn)?A9 8 4 | 5 6 7 | 1 3 2 0 B8 7 1 | 2 3 0 | 9 5

35、4 6 首先交換A和B的兩個(gè)匹配區(qū)域，得到 A9 8 4 | 2 3 0 | l 3 2 0 B8 7 1 | 5 6 7 | 9 5 4 對于A、B兩子串中匹配區(qū)域以外出現(xiàn)的遍歷重復(fù)，依據(jù)匹配區(qū)域內(nèi)的位置映射關(guān)系，逐一進(jìn)行交換。對于A有2到5，3到6，0到7的位置符號(hào)映射，對A的匹配區(qū)以外的2，3，0分別以5，6，7替換，則得 A”9 8 4 | 2 3 0 | 1 6 5 7同理可得： B”8 0 1 | 5 6 7 | 9 2 4 3這樣，每個(gè)子串的次序部分地由其父串確定。 2.8.3 用遺傳算法解決TSP問題（3）變異倒置變異 利用簡單的倒置操作來進(jìn)行變異。即首先在父體中隨機(jī)地選擇兩個(gè)

36、截?cái)帱c(diǎn)，然后將該兩點(diǎn)內(nèi)的子串中的城市進(jìn)行反序操作。 A 1 2 3 | 4 5 6 | 7 8 9 0A1 2 3 | 6 5 4 | 7 8 9 0插入變異插入算子就是隨機(jī)選擇一個(gè)城市，并將它插入到一個(gè)隨機(jī)位置中去。 A 1 2 3 4 5 6 7 8 9 A1 2 5 3 4 6 7 8 9移位變異 移位算子是選擇一個(gè)子路徑巡回，然后把它插入一個(gè)隨機(jī)的位置 互換變異互換變異也被稱作基于次序的變異（order-based mutation），操作方法是：隨機(jī)的選擇兩個(gè)城市，并交換其所處的位置對于串AA 1 2 3 4 | 5 6 7 | 8 9若對換點(diǎn)為4，7，則經(jīng)對換后，A為A1 2 3

37、7 | 5 6 4 | 8 92.8.3 用遺傳算法解決TSP問題 從群體規(guī)模來看，有變化規(guī)模的方式，也有恒定規(guī)模的群體構(gòu)成方式等。 在遺傳算法中，最常見的選擇機(jī)制是依據(jù)適應(yīng)度的比例概率選擇機(jī)制；在有限規(guī)模的群體中，適應(yīng)度較高的個(gè)體有較大的機(jī)會(huì)繁殖后代，即生物進(jìn)化論上的適者生存規(guī)則。在新一代群體構(gòu)成方法方面存在： N方式：全部替換上一代群體的全刷新代際更新方式。 E方式：保留一個(gè)最好的父串的最佳保留（elitist）群體構(gòu)造方式。 G方式：按一定比例更新群體中的部分個(gè)體的部分更新方式（或稱代溝方法，這種情況的極端是每代僅刪去一個(gè)最不適的個(gè)體的最劣死亡方式）。 B方式：從產(chǎn)生的子代和父代中挑選最

38、好的若干個(gè)個(gè)體的群體構(gòu)成形式。 一般講，N方式的全局搜索性能最好，但收斂速度最慢；B方式收斂速度最快，但全局搜索性能最差；E方式和G方式的性能介于N方式和B方式之間。在求解貨郎擔(dān)問題的應(yīng)用中，多選用E方式。 （4）選擇機(jī)制和群體構(gòu)成2.8.3 用遺傳算法解決TSP問題 算法簡單，從總體趨勢上看，算法總是朝著路徑和變小的方向收斂的，得到的結(jié)果也較好，不過收斂速度較慢，且存在比較好的染色體（路徑）被淘汰的情況。（5）實(shí)驗(yàn)結(jié)果與分析3.模擬退火 算法3.1 模擬退火算法簡介3.2 模擬退火算法基本原理3.3 優(yōu)化問題與物理退火的類比3.1 模擬退火算法簡介模擬退火的思想 開始使勁晃動(dòng)(先高溫加熱)然

39、后慢慢降低搖晃的強(qiáng)度(逐漸降溫)退火過程。 想象在不平的表面上如何使一個(gè)乒乓球掉到最深的裂縫中如果只讓其在表面滾動(dòng)，則它只會(huì)停留在局部極小點(diǎn)/ 如果晃動(dòng)平面，可以使乒乓球彈出局部極小點(diǎn)/ 技巧是晃動(dòng)足夠大使乒乓球彈出局部極小點(diǎn)，但又不能太大把它從全局極小點(diǎn)中趕出。模擬退火的思路算法的目的 解決NP復(fù)雜性問題； 克服優(yōu)化過程陷入局部極??； 克服初值依賴性。3.2 模擬退火算法基本原理（1）物理退火過程 加溫過程。其目的是增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置。當(dāng)溫度足夠高時(shí)，固體將溶解為液體，溶解過程與系統(tǒng)的熵增過程聯(lián)系，系統(tǒng)能量也隨溫度的升高而增大，使得每一粒子的狀態(tài)都具有充分的隨機(jī)性。 等溫過程

40、。物理學(xué)的知識(shí)告訴我們，對于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀態(tài)的自發(fā)變化總是朝自由能減少的方向進(jìn)行，當(dāng)自由能達(dá)到最小時(shí)，系統(tǒng)達(dá)到平衡態(tài)。 冷卻過程。目的是使粒子的熱運(yùn)動(dòng)減弱并漸趨有序，系統(tǒng)能量逐漸下降，從而得到低能的晶體結(jié)構(gòu)。在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小。 退火是指將固體加熱到足夠高的溫度，使分子呈隨機(jī)排列狀態(tài)，然后逐步降溫使之冷卻，最后分子以低能狀態(tài)排列， 固體達(dá)到某種穩(wěn)定狀態(tài)。 物理退火過程的發(fā)展階段3.2 模擬退火算法基本原理（2）數(shù)學(xué)表述 物體加熱至一定溫度后，所有分子在狀態(tài)空間D中自由運(yùn)動(dòng)，隨著溫度的下降，分子逐漸停留在不同的狀態(tài)。在溫度最低時(shí)，分子重新以一定的結(jié)構(gòu)排

41、列。 在溫度T, 分子停留在狀態(tài)r滿足Boltzmann概率分布:其中：表示分子能量的一個(gè)隨機(jī)變量；表示狀態(tài)r的能量；為Boltzmann常數(shù)，為概率分布的標(biāo)準(zhǔn)化因子：；。3.2 模擬退火算法基本原理在同一個(gè)溫度T，選定兩個(gè)能量E1E2，有四個(gè)能量點(diǎn)r = 1, 2, 3, 4三個(gè)溫度點(diǎn)t = 20, 5, 0.5狀態(tài)與溫度關(guān)系的例子r=1r=2r=3r=4T=200.2690.2560.2430.232T=50.3290.2690.2210.181T=0.50.8650.1170.0160.0023.2 模擬退火算法基本原理 （1）在同一個(gè)溫度，分子停留在能量小狀態(tài)的概率大于停留在能量大狀態(tài)

42、的概率; （2）溫度越高，不同能量狀態(tài)對應(yīng)的概率相差越??；溫度足夠高時(shí)， 各狀態(tài)對應(yīng)概率基本相同; （3）隨著溫度的下降，能量最低狀態(tài)對應(yīng)概率越來越大；溫度趨于0 時(shí)，其狀態(tài)趨于1。 在一定溫度下，搜索從一個(gè)狀態(tài)隨機(jī)地變化到另一個(gè)狀態(tài)；隨著溫度的不斷下降直到最低溫度，搜索過程以概率1停留在最優(yōu)解。上表表明：模擬退火算法求解思路：3.3 優(yōu)化問題與物理退火的類比優(yōu)化問題物理退火解分子狀態(tài)最優(yōu)解能量最低狀態(tài)目標(biāo)函數(shù)能量設(shè)定初始溫度熔解過程Metropolis抽樣等溫過程溫度的下降冷卻過程4.粒子群算法4.1 粒子群算法簡介4.2 粒子群算法的基本原則4.3 粒子群算法的基本條件4.4 粒子群算法的數(shù)學(xué)表述4.1 粒子群算法簡介 粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart在1995年提出，該算法模擬鳥集群飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達(dá)到最優(yōu)目的，是一種基于Swarm Intellige