第6章智能計算及其應(yīng)用教材：

王萬良《人工智能導(dǎo)論》（第5版）高等教育出版社，20202第6章智能計算及其應(yīng)用受自然界和生物界規(guī)律的啟迪，人們根據(jù)其原理模仿設(shè)計了許多求解問題的算法，包括人工神經(jīng)網(wǎng)絡(luò)、模糊邏輯、遺傳算法、DNA計算、模擬退火算法、禁忌搜索算法、免疫算法、膜計算、量子計算、粒子群優(yōu)化算法、蟻群算法、人工蜂群算法、人工魚群算法以及細(xì)菌群體優(yōu)化算法等，這些算法稱為智能計算也稱為計算智能(computationalintelligence,CI)。3第6章智能計算及其應(yīng)用智能優(yōu)化方法通常包括進(jìn)化計算和群智能等兩大類方法，是一種典型的元啟發(fā)式隨機(jī)優(yōu)化方法，已經(jīng)廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、智能控制、模式識別、規(guī)劃設(shè)計、網(wǎng)絡(luò)安全等領(lǐng)域，是21世紀(jì)有關(guān)智能計算中的重要技術(shù)之一。本章首先簡要介紹進(jìn)化算法的概念，詳細(xì)介紹基本遺傳算法，這是進(jìn)化算法的基本框架。然后介紹雙倍體、雙種群、自適應(yīng)等比較典型的改進(jìn)遺傳算法及其應(yīng)用。介紹了群智能算法產(chǎn)生的背景和粒子群優(yōu)化算法。介紹了蟻群算法及其應(yīng)用。

46.1進(jìn)化算法的產(chǎn)生與發(fā)展6.2基本遺傳算法6.3遺傳算法的改進(jìn)算法6.4遺傳算法的應(yīng)用6.5群智能算法產(chǎn)生的背景6.6粒子群優(yōu)化算法及其應(yīng)用6.7蟻群算法及其應(yīng)用第6章智能計算及其應(yīng)用56.1進(jìn)化算法的產(chǎn)生與發(fā)展

6.2基本遺傳算法6.3遺傳算法的改進(jìn)算法6.4遺傳算法的應(yīng)用6.5群智能算法產(chǎn)生的背景6.6粒子群優(yōu)化算法及其應(yīng)用6.7蟻群算法及其應(yīng)用第6章智能計算及其應(yīng)用66.1.1進(jìn)化算法的概念6.1.2進(jìn)化算法的生物學(xué)背景6.1.3進(jìn)化算法的設(shè)計原則6.1進(jìn)化算法的產(chǎn)生與發(fā)展

76.1.1進(jìn)化算法的概念進(jìn)化算法(evolutionaryalgorithms，EA)是基于自然選擇和自然遺傳等生物進(jìn)化機(jī)制的一種搜索算法。生物進(jìn)化是通過繁殖、變異、競爭和選擇實(shí)現(xiàn)的；而進(jìn)化算法則主要通過選擇、重組和變異這三種操作實(shí)現(xiàn)優(yōu)化問題的求解。進(jìn)化算法是一個“算法簇”，包括遺傳算法(GA)、遺傳規(guī)劃、進(jìn)化策略和進(jìn)化規(guī)劃等。進(jìn)化算法的基本框架是遺傳算法所描述的框架。進(jìn)化算法可廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計和人工生命等領(lǐng)域。86.1.2進(jìn)化算法的生物學(xué)背景適者生存：最適合自然環(huán)境的群體往往產(chǎn)生了更大的后代群體。

生物進(jìn)化的基本過程：染色體(chromosome)：生物的遺傳物質(zhì)的主要載體?；?gene)：擴(kuò)展生物性狀的遺傳物質(zhì)的功能單元和結(jié)構(gòu)單位?；蜃╨ocus）：染色體中基因的位置。等位基因（alleles）：基因所取的值。96.1.3進(jìn)化算法的設(shè)計原則（1）適用性原則：一個算法的適用性是指該算法所能適用的問題種類，它取決于算法所需的限制與假定。（2）可靠性原則：算法的可靠性是指算法對于所設(shè)計的問題，以適當(dāng)?shù)木惹蠼馄渲写蠖鄶?shù)問題的能力。（3）收斂性原則：指算法能否收斂到全局最優(yōu)。在收斂的前提下，希望算法具有較快的收斂速度。（4）穩(wěn)定性原則：指算法對其控制參數(shù)及問題的數(shù)據(jù)的敏感度。（5）生物類比原則：生物界有效方法及操作可以通過類比的方法引入到算法中，有時會帶來較好的結(jié)果。10第6章智能計算及其應(yīng)用6.1進(jìn)化算法的產(chǎn)生與發(fā)展6.2基本遺傳算法6.3遺傳算法的改進(jìn)算法6.4遺傳算法的應(yīng)用6.5群智能算法產(chǎn)生的背景6.6粒子群優(yōu)化算法及其應(yīng)用6.7蟻群算法及其應(yīng)用116.2基本遺傳算法

遺傳算法（geneticalgorithms，GA）：一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法,非常適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性優(yōu)化問題。遺傳算法可廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計和人工生命等領(lǐng)域。126.2.1遺傳算法的基本思想生物遺傳概念遺產(chǎn)算法中的應(yīng)用適者生存目標(biāo)值比較大的解被選擇的可能性大個體（Individual）解染色體（Chromosome）解的編碼（字符串、向量等）基因（Gene）解的編碼中每一分量適應(yīng)性（Fitness）適應(yīng)度函數(shù)值群體（Population）根據(jù)適應(yīng)度值選定的一組解（解的個數(shù)為群體的規(guī)模）婚配（Marry）交叉（Crossover）選擇兩個染色體進(jìn)行交叉產(chǎn)生一組新的染色體的過程變異（Mutation）編碼的某一分量發(fā)生變化的過程136.2.1遺傳算法的基本思想

遺傳算法的基本思想：在求解問題時從多個解開始，然后通過一定的法則進(jìn)行逐步迭代以產(chǎn)生新的解。146.2.2遺傳算法的發(fā)展歷史1962年，F(xiàn)raser提出了自然遺傳算法。1965年，Holland首次提出了人工遺傳操作的重要性。1967年，Bagley首次提出了遺傳算法這一術(shù)語。1970年，Cavicchio把遺傳算法應(yīng)用于模式識別中。1971年，Hollstien在論文《計算機(jī)控制系統(tǒng)中人工遺傳自適應(yīng)方法》中闡述了遺傳算法用于數(shù)字反饋控制的方法。1975年，美國J.Holland出版了《自然系統(tǒng)和人工系統(tǒng)的適配》；DeJong完成了重要論文《遺傳自適應(yīng)系統(tǒng)的行為分析》。

20世紀(jì)80年代以后，遺傳算法進(jìn)入興盛發(fā)展時期。Char9pp.15例：用遺傳算法求解下面一個Rastrigin函數(shù)的最小值。x2x1x1x1x2fChar9pp.16初始種群：例：用遺傳算法求解下面一個Rastrigin函數(shù)的最小值。x2x1x1Char9pp.17

初始種群第二代種群例：用遺傳算法求解下面一個Rastrigin函數(shù)的最小值。x2x1x2x1Char9pp.18在迭代60、80、95、100次時的種群196.2.3編碼

位串編碼一維染色體編碼方法：將問題空間的參數(shù)編碼為一維排列的染色體的方法。二進(jìn)制編碼：用若干二進(jìn)制數(shù)表示一個個體，將原問題的解空間映射到位串空間B={0，1}上，然后在位串空間上進(jìn)行遺傳操作。

（1）二進(jìn)制編碼206.2.3編碼

(1)二進(jìn)制編碼（續(xù)）●優(yōu)點(diǎn)：類似于生物染色體的組成，算法易于用生物遺傳理論解釋，遺傳操作如交叉、變異等易實(shí)現(xiàn)；算法處理的模式數(shù)最多?！袢秉c(diǎn)：①相鄰整數(shù)的二進(jìn)制編碼可能具有較大的Hamming距離，降低了遺傳算子的搜索效率。

15：01111

16：10000②要先給出求解的精度。③求解高維優(yōu)化問題的二進(jìn)制編碼串長，算法的搜索效率低。216.2.3編碼

位串編碼（2）Gray編碼Gray編碼:將二進(jìn)制編碼通過一個變換進(jìn)行轉(zhuǎn)換得到的編碼。二進(jìn)制串

Gray

二進(jìn)制編碼

Gray編碼Gray編碼

二進(jìn)制編碼226.2.3編碼

2.實(shí)數(shù)編碼

采用實(shí)數(shù)表達(dá)法不必進(jìn)行數(shù)制轉(zhuǎn)換，可直接在解的表現(xiàn)型上進(jìn)行遺傳操作。

多參數(shù)映射編碼的基本思想：把每個參數(shù)先進(jìn)行二進(jìn)制編碼得到子串，再把這些子串連成一個完整的染色體。多參數(shù)映射編碼中的每個子串對應(yīng)各自的編碼參數(shù)，所以，可以有不同的串長度和參數(shù)的取值范圍。

23初始種群的產(chǎn)生6.2.4群體設(shè)定

●隨機(jī)產(chǎn)生群體規(guī)模數(shù)目的個體作為初始群體。

●隨機(jī)產(chǎn)生一定數(shù)目的個體，從中挑選最好的個體加到初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。

●根據(jù)問題固有知識，把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。242.種群規(guī)模的確定6.2.4群體設(shè)定

模式定理表明：若群體規(guī)模為M，則遺傳操作可從這M個個體中生成和檢測個模式，并在此基礎(chǔ)上能夠不斷形成和優(yōu)化積木塊，直到找到最優(yōu)解。

群體規(guī)模太小，遺傳算法的優(yōu)化性能不太好，易陷入局部最優(yōu)解。群體規(guī)模太大，計算復(fù)雜。25將目標(biāo)函數(shù)映射成適應(yīng)度函數(shù)的方法

6.2.5適應(yīng)度函數(shù)

●

若目標(biāo)函數(shù)為最大化問題，則●若目標(biāo)函數(shù)為最小化問題，則將目標(biāo)函數(shù)轉(zhuǎn)換為求最大值的形式,且保證函數(shù)值非負(fù)！

●

若目標(biāo)函數(shù)為最大化問題，則●若目標(biāo)函數(shù)為最小化問題，則26適應(yīng)度函數(shù)的尺度變換●

在遺傳算法中，將所有妨礙適應(yīng)度值高的個體產(chǎn)生，從而影響遺傳算法正常工作的問題統(tǒng)稱為欺騙問題（deceptiveproblem）。

6.2.5適應(yīng)度函數(shù)

●

過早收斂：縮小這些個體的適應(yīng)度，以降低這些超級個體的競爭力?！?/p>

停滯現(xiàn)象：改變原始適應(yīng)值的比例關(guān)系，以提高個體之間的競爭力?！?/p>

尺度變換（fitnessscaling）或定標(biāo)：對適應(yīng)度函數(shù)值域的某種映射變換。27適應(yīng)度函數(shù)的尺度變換(續(xù)）

（1）線性變換：6.2.5適應(yīng)度函數(shù)

滿足滿足最小適應(yīng)度值非負(fù)28適應(yīng)度函數(shù)的尺度變換(續(xù)）

（2）冪函數(shù)變換法：

6.2.5適應(yīng)度函數(shù)

（3）指數(shù)變換法：296.2.6選擇

個體選擇概率分配方法●

選擇操作也稱為復(fù)制（reproduction）操作：從當(dāng)前群體中按照一定概率選出優(yōu)良的個體，使它們有機(jī)會作為父代繁殖下一代子孫?！衽袛鄠€體優(yōu)良與否的準(zhǔn)則是各個個體的適應(yīng)度值：個體適應(yīng)度越高，其被選擇的機(jī)會就越多。

306.2.6選擇

個體選擇概率分配方法（1）適應(yīng)度比例方法（fitnessproportionalmodel）或蒙特卡羅法（MonteCarlo）

●

各個個體被選擇的概率和其適應(yīng)度值成比例?！?/p>

個體被選擇的概率為：

316.2.6選擇

1.個體選擇概率分配方法（2）排序方法（rank-basedmodel）①線性排序：J.E.Baker

群體成員按適應(yīng)值大小從好到壞依次排列：個體按轉(zhuǎn)盤式選擇的方式選擇父體326.2.6選擇

1.個體選擇概率分配方法（2）排序方法（rank-basedmodel）②非線性排序：Z.Michalewicz

●

將群體成員按適應(yīng)值從好到壞依次排列，并按下式分配選擇概率：336.2.6選擇

1.個體選擇概率分配方法（2）排序方法（rank-basedmodel）

●

可用其他非線性函數(shù)來分配選擇概率，只要滿足以下條件：

346.2.6選擇

2.選擇個體方法（1）轉(zhuǎn)盤賭選擇

按個體的選擇概率產(chǎn)生一個輪盤，輪盤每個區(qū)的角度與個體的選擇概率成比例。產(chǎn)生一個隨機(jī)數(shù)，它落入轉(zhuǎn)盤的哪個區(qū)域就選擇相應(yīng)的個體交叉。356.2.6選擇

2.選擇個體方法（1）轉(zhuǎn)盤賭選擇第1輪產(chǎn)生一個隨機(jī)數(shù)：0.81

第2輪產(chǎn)生一個隨機(jī)數(shù)：0.32

366.2.6選擇

2.選擇個體方法（2）錦標(biāo)賽選擇方法（tournamentselectionmodel）

●

錦標(biāo)賽選擇方法：從群體中隨機(jī)選擇個個體，將其中適應(yīng)度最高的個體保存到下一代。這一過程反復(fù)執(zhí)行，直到保存到下一代的個體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)量為止。●

隨機(jī)競爭方法（stochastictournament）：每次按賭輪選擇方法選取一對個體，然后讓這兩個個體進(jìn)行競爭，適應(yīng)度高者獲勝。如此反復(fù)，直到選滿為止。

376.2.6選擇

2.選擇個體方法●

最佳個體（elitistmodel）保存方法：把群體中適應(yīng)度最高的個體不進(jìn)行交叉而直接復(fù)制到下一代中，保證遺傳算法終止時得到的最后結(jié)果一定是歷代出現(xiàn)過的最高適應(yīng)度的個體。（3）最佳個體保存方法

386.2.7交叉

1.基本的交叉算子（1）一點(diǎn)交叉（single-pointcrossover）●

一點(diǎn)交叉：在個體串中隨機(jī)設(shè)定一個交叉點(diǎn)，實(shí)行交叉時，該點(diǎn)前或后的兩個個體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個新的個體?！?/p>

二點(diǎn)交叉：隨機(jī)設(shè)置兩個交叉點(diǎn)，將兩個交叉點(diǎn)之間的碼串相互交換。（2）二點(diǎn)交叉（two-pointcrossover）396.2.7交叉

2.修正的交叉方法部分匹配交叉PMX：GoldbergD.E.和R.Lingle(1985)

406.2.8變異

●位點(diǎn)變異：群體中的個體碼串，隨機(jī)挑選一個或多個基因座，并對這些基因座的基因值以變異概率作變動?！衲孓D(zhuǎn)變異：在個體碼串中隨機(jī)選擇兩點(diǎn)（逆轉(zhuǎn)點(diǎn)），然后將兩點(diǎn)之間的基因值以逆向排序插入到原位置中。

●插入變異：在個體碼串中隨機(jī)選擇一個碼，然后將此碼插入隨機(jī)選擇的插入點(diǎn)中間。●互換變異：隨機(jī)選取染色體的兩個基因進(jìn)行簡單互換。●移動變異：隨機(jī)選取一個基因，向左或者向右移動一個隨機(jī)位數(shù)。416.2.9遺傳算法的一般步驟426.2.9遺傳算法的一般步驟（1）使用隨機(jī)方法或者其它方法，產(chǎn)生一個有N個染色體的初始群體pop(1)，；

（2）對群體中的每一個染色體popi(t)，計算其適應(yīng)值（3）若滿足停止條件，則算法停止；否則，以概率從pop(t)中隨機(jī)選擇一些染色體構(gòu)成一個新種群436.2.9遺傳算法的一般步驟（4）以概率進(jìn)行交叉產(chǎn)生一些新的染色體，得到一個新的群體

（5）以一個較小的概率使染色體的一個基因發(fā)生變異，形成；，成為一個新的群體

返回（2）。

446.2.10遺傳算法的特點(diǎn)

遺傳算法是一種全局優(yōu)化概率算法，主要特點(diǎn)有：遺傳算法對所求解的優(yōu)化問題沒有太多的數(shù)學(xué)要求，由于進(jìn)化特性，搜素過程中不需要問題的內(nèi)在性質(zhì)，可直接對結(jié)構(gòu)對象進(jìn)行操作。利用隨機(jī)技術(shù)指導(dǎo)對一個被編碼的參數(shù)空間進(jìn)行高效率搜索采用群體搜索策略，易于并行化。僅用適應(yīng)度函數(shù)值來評估個體，并在此基礎(chǔ)上進(jìn)行遺傳操作，使種群中個體之間進(jìn)行信息交換。遺傳算法能夠非常有效地進(jìn)行概率意義的全局搜素。456.1進(jìn)化算法的產(chǎn)生與發(fā)展6.2基本遺傳算法6.3遺傳算法的改進(jìn)算法6.4遺傳算法的應(yīng)用6.5群智能算法產(chǎn)生的背景6.6粒子群優(yōu)化算法及其應(yīng)用6.7蟻群算法及其應(yīng)用第6章智能計算及其應(yīng)用466.3遺傳算法的改進(jìn)算法

6.3.1雙倍體遺傳算法6.3.2雙種群遺傳算法6.3.3自適應(yīng)遺傳算法476.3.1雙倍體遺傳算法1.基本思想雙倍體遺傳算法采用顯性和隱性兩個染色體同時進(jìn)行進(jìn)化，提供了一種記憶以前有用的基因塊的功能。雙倍體遺傳算法采用顯性遺傳。

雙倍體遺傳延長了有用基因塊的壽命，提高了算法的收斂能力，在變異概率低的情況下能保持一定水平的多樣性。48

6.3.1雙倍體遺傳算法2.雙倍體遺傳算法的設(shè)計（1）編碼/解碼：兩個染色體（顯性、隱性）（2）復(fù)制算子：計算顯性染色體的適應(yīng)度，按照顯性染色體的復(fù)制概率將個體復(fù)制到下一代群體中。（3）交叉算子：兩個個體的顯性染色體交叉、隱性染色體也同時交叉。（4）變異算子：個體的顯性染色體按正常的變異概率變異；隱性染色體按較大的變異概率變異。（5）雙倍體遺傳算法顯隱性重排算子：個體中適應(yīng)值較大的染色體設(shè)為顯性染色體，適應(yīng)值較小的染色體設(shè)為隱性染色體。49

雙種群遺傳算法程序流程圖

506.3.2雙種群遺傳算法

基本思想在遺傳算法中使用多種群同時進(jìn)化，并交換種群之間優(yōu)秀個體所攜帶的遺傳信息，以打破種群內(nèi)的平衡態(tài)達(dá)到更高的平衡態(tài)，有利于算法跳出局部最優(yōu)。

多種群遺傳算法：建立兩個遺傳算法群體，分別獨(dú)立地運(yùn)行復(fù)制、交叉、變異操作，同時當(dāng)每一代運(yùn)行結(jié)束以后，選擇兩個種群中的隨機(jī)個體及最優(yōu)個體分別交換。516.3.2雙種群遺傳算法2.雙種群遺傳算法的設(shè)計●編碼/解碼設(shè)計●交叉算子、變異算子●雜交算子設(shè)種群A與種群B，當(dāng)A與B種群都完成了選擇、交叉、變異算子后，產(chǎn)生一個隨機(jī)數(shù)num，隨機(jī)選擇A中num個個體與A中最優(yōu)個體，隨機(jī)選擇B中num個個體與B中最優(yōu)個體，交換兩者，以打破平衡態(tài)。k個隨機(jī)個體最優(yōu)個體k個隨機(jī)個體最優(yōu)個體種群A種群B52

雙種群遺傳算法程序流程圖536.3.3自適應(yīng)遺傳算法

1.基本思想●SrinvivasM.，PatnaikL.M.等在1994年提出一種自適應(yīng)遺傳算法(adaptivegeneticalgorithms，AGA)：能隨適應(yīng)度自動改變。●AGA：當(dāng)種群各個體適應(yīng)度趨于一致或者趨于局部最優(yōu)時，使增加，以跳出局部最優(yōu)；而當(dāng)群體適應(yīng)度比較分散時，使減少，以利于優(yōu)良個體的生存?！?/p>

同時，對于適應(yīng)度高于群體平均適應(yīng)值的個體，選擇較低的，使得該解得以保護(hù)進(jìn)入下一代；對低于平均適應(yīng)值的個體，選擇較高的值，使該解被淘汰。546.3.3自適應(yīng)遺傳算法

2.自適應(yīng)遺傳算法的步驟（1）編碼/解碼設(shè)計。（2）初始種群產(chǎn)生：N（N是偶數(shù)）個候選解，組成初始解集。（3）定義適應(yīng)度函數(shù)：，計算適應(yīng)度。（4）按輪盤賭規(guī)則選擇N個個體，計算。（5）將群體中的各個個體隨機(jī)搭配成對，共組成N/2對，對每一對個體，按照自適應(yīng)公式計算自適應(yīng)交叉概率，隨機(jī)產(chǎn)生R(0,1)，如果則對該對染色體進(jìn)行交叉操作。552.自適應(yīng)遺傳算法的步驟（續(xù)）（6）對于群體中的所有個體，共N個，按照自適應(yīng)變異公式計算自適應(yīng)變異概率，隨機(jī)產(chǎn)生R(0,1)，如果則對該染色體進(jìn)行交叉操作。（7）計算由交叉和變異生成新個體的適應(yīng)度，新個體與父代一起構(gòu)成新群體。（8）判斷是否達(dá)到預(yù)定的迭代次數(shù)，是則結(jié)束；否則轉(zhuǎn)（4）。

6.3.3自適應(yīng)遺傳算法

563.適應(yīng)的交叉概率與變異概率6.3.3自適應(yīng)遺傳算法

普通自適應(yīng)算法中，當(dāng)個體適應(yīng)度值越接近最大適應(yīng)度值時，交叉概率與變異概率就越小；當(dāng)?shù)扔谧畲筮m應(yīng)度值時，交叉概率和變異概率為零。

改進(jìn)的思想：當(dāng)前代的最優(yōu)個體不被破壞，仍然保留（最優(yōu)保存策略）；但較優(yōu)個體要對應(yīng)于更高的交叉概率與變異概率。57576.1進(jìn)化算法的產(chǎn)生與發(fā)展6.2基本遺傳算法6.3遺傳算法的改進(jìn)算法6.4遺傳算法的應(yīng)用6.5群智能算法產(chǎn)生的背景6.6粒子群優(yōu)化算法及其應(yīng)用6.7蟻群算法及其應(yīng)用第6章智能計算及其應(yīng)用581.流水車間調(diào)度問題

問題描述：n個工件要在m臺機(jī)器上加工，每個工件需要經(jīng)過m道工序，每道工序要求不同的機(jī)器，n個工件在m臺機(jī)器上的加工順序相同。工件在機(jī)器上的加工時間是給定的，設(shè)為

問題的目標(biāo)：確定n個工件在每臺機(jī)器上的最優(yōu)加工順序，使最大流程時間達(dá)到最小。6.4遺傳算法的應(yīng)用591.流水車間調(diào)度問題

假設(shè)：

(1)

每個工件在機(jī)器上的加工順序是給定的。

(2)

每臺機(jī)器同時只能加工一個工件。

(3)

一個工件不能同時在不同的機(jī)器上加工。

(4)

工序不能預(yù)定。

(5)

工序的準(zhǔn)備時間與順序無關(guān)，且包含在加工時間中。

(6)工件在每臺機(jī)器上的加工順序相同，且是確定的。

6.4遺傳算法的應(yīng)用601.流水車間調(diào)度問題6.4遺傳算法的應(yīng)用

問題的數(shù)學(xué)模型：

個工件、臺機(jī)器的流水車間調(diào)度問題的完工時間：

612.求解流水車間調(diào)度問題的遺傳算法設(shè)計

（1）FSP的編碼方法對于FSP，最自然的編碼方式是用染色體表示工件的順序。6.4遺傳算法的應(yīng)用對于有四個工件的FSP，第個染色體，表示工件的加工順序?yàn)椋骸?/p>

622.求解流水車間調(diào)度問題的遺傳算法設(shè)計

（2）FSP的適應(yīng)度函數(shù)

:個染色體的最大流程時間，F(xiàn)SP的適應(yīng)度函數(shù)：

6.4遺傳算法的應(yīng)用63求解FSP的遺傳算法實(shí)例

例6.1Ho和Chang(1991)給出的5個工件、4臺機(jī)器問題。

工件131412530219553343234227641322141353355719

加工時間表

6.4遺傳算法的應(yīng)用64用遺傳算法求解。選擇交叉概率，變異概,種群規(guī)模為20，迭代次數(shù)。

表9.3遺傳算法運(yùn)行的結(jié)果

總運(yùn)行次數(shù)最好解最壞解平均最好解的頻率最好解的平均代數(shù)20213221213.950.85126.4遺傳算法的應(yīng)用用窮舉法求得最優(yōu)解：4-2-5-1-3，加工時間：213；最劣解：1-4-2-3-5，加工時間：294；平均解的加工時間：265。

遺傳算法運(yùn)行的結(jié)果65表9.3遺傳算法運(yùn)行的結(jié)果

最優(yōu)解收斂圖

6.4遺傳算法的應(yīng)用66平均值收斂圖

6.4遺傳算法的應(yīng)用67機(jī)器甘特圖

6.4遺傳算法的應(yīng)用686.1進(jìn)化算法的產(chǎn)生與發(fā)展6.2基本遺傳算法6.3遺傳算法的改進(jìn)算法6.4遺傳算法的應(yīng)用6.5群智能算法產(chǎn)生的背景6.6粒子群優(yōu)化算法及其應(yīng)用6.7蟻群算法及其應(yīng)用第6章智能計算及其應(yīng)用696.5群智能算法產(chǎn)生的背景

群智能算法（swarmalgorithms，SI）：受動物群體智能啟發(fā)的算法。群體智能：由簡單個體組成的群落與環(huán)境以及個體之間的互動行為。

群智能算法包括：粒子群優(yōu)化算法、蟻群算法、蜂群算法、……706.5群智能算法產(chǎn)生的背景716.1進(jìn)化算法的產(chǎn)生與發(fā)展6.2基本遺傳算法6.3遺傳算法的改進(jìn)算法6.4遺傳算法的應(yīng)用6.5群智能算法產(chǎn)生的背景6.6粒子群優(yōu)化算法及其應(yīng)用6.7蟻群算法及其應(yīng)用第6章智能計算及其應(yīng)用726.6粒子群優(yōu)化算法及其應(yīng)用產(chǎn)生背景粒子群優(yōu)化（ParticleSwarmOptimization,PSO）算法是由美國普渡大學(xué)的Kennedy和Eberhart于1995年提出，它的基本概念源于對鳥群覓食行為的研究。設(shè)想這樣一個場景：一群鳥在隨機(jī)搜尋食物，在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在哪里，但是它們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢?最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。736.6.1粒子群優(yōu)化算法的基本原理6.6.2粒子群優(yōu)化算法的參數(shù)分析6.6粒子群優(yōu)化算法及其應(yīng)用746.6.1粒子群優(yōu)化算法的基本原理

基本思想將每個個體看作n維搜索空間中一個沒有體積質(zhì)量的粒子，在搜索空間中以一定的速度飛行，該速度決定粒子飛行的方向和距離。所有粒子有一個由優(yōu)化函數(shù)決定的適應(yīng)值。基本原理PSO初始化為一群隨機(jī)粒子，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己。第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值。另個一是整個種群目前找到的最優(yōu)解，這個解稱為全局極值。756.6.1粒子群優(yōu)化算法的基本原理

算法定義在n維連續(xù)搜索空間中，對粒子群中的第i

(i=1,2,,m)個粒子進(jìn)行定義：●：表示搜索空間中粒子的當(dāng)前位置?！瘢罕硎驹摿Ｗ又两袼@得的具有最優(yōu)適應(yīng)度的位置?！瘢罕硎驹摿Ｗ拥乃阉鞣较?。766.6.1粒子群優(yōu)化算法的基本原理

每個粒子經(jīng)歷過的最優(yōu)位置（pbest）記為，群體經(jīng)歷過的最優(yōu)位置(gbest)記為

，則基本的PSO算法為：——（6.20a）——（6.20b）其中，

是慣性權(quán)重因子。

1

，

2

是加速度常數(shù)，均為非負(fù)值。

和

為[0,a1]、[0,a2]范圍內(nèi)的具有均勻分布的隨機(jī)數(shù)，a1

與a2

為相應(yīng)的控制參數(shù)。776.6.1粒子群優(yōu)化算法的基本原理

第1部分是粒子在前一時刻的速度；第2部分為個體“認(rèn)知”分量，表示粒子本身的思考，將現(xiàn)有的位置和曾經(jīng)經(jīng)歷過的最優(yōu)位置相比。第3部分是群體“社會(social)”分量，表示粒子間的信息共享與相互合作。

1，

2分別控制個體認(rèn)知分量和群體社會分量相對貢獻(xiàn)的學(xué)習(xí)率。隨機(jī)系數(shù)增加搜索方向的隨機(jī)性和算法多樣性。786.6.1粒子群優(yōu)化算法的基本原理

基于學(xué)習(xí)率，，

Kennedy給出以下4種類型的PSO模型：若

1>0，

2>0，則稱該算法為PSO全模型。若

1>0，

2=

0，則稱該算法為PSO認(rèn)知模型。若

1=0，

2>0，則稱該算法為PSO社會模型。若

1=

0，

2>0且gi，則稱該算法為PSO無私模型。796.6.1粒子群優(yōu)化算法的基本原理

粒子群優(yōu)化算法的流程：（1）初始化每個粒子。在允許范圍內(nèi)隨機(jī)設(shè)置每個粒子的初始位置和速度。（2）評價每個粒子的適應(yīng)度。計算每個粒子的目標(biāo)函數(shù)。（3）設(shè)置每個粒子的。對每個粒子，將其適應(yīng)度與其經(jīng)歷過的最好位置進(jìn)行比較，如果優(yōu)于，則將其作為該粒子的最好位置。806.6.1粒子群優(yōu)化算法的基本原理

粒子群優(yōu)化算法的流程：（4）設(shè)置全局最優(yōu)值。對每個粒子，將其適應(yīng)度與群體經(jīng)歷過的最好位置進(jìn)行比較，如果優(yōu)于，則將其作為當(dāng)前群體的最好位置。（5）更新粒子的速度和位置。根據(jù)式（6.20）更新粒子的速度和位置。（6）檢查終止條件。如果未達(dá)到設(shè)定條件（預(yù)設(shè)誤差或者迭代的次數(shù)），則返回第（2）步。816.6.1粒子群優(yōu)化算法流程圖826.6.2粒子群優(yōu)化算法的參數(shù)分析PSO算法的參數(shù)包括：群體規(guī)模m，慣性權(quán)重

，加速度

1，

2，最大速度Vmax，最大代數(shù)Gmax。對速度vi，算法中有最大速度Vmax作為限制，如果當(dāng)前粒子的某維速度大于最大速度Vmax，則該維的速度就被限制為最大速度Vmax。（1）最大速度Vmax（2）權(quán)重因子3個權(quán)重因子：慣性權(quán)重

，加速度

1，

2

。836.6.2粒子群優(yōu)化算法的參數(shù)分析2.位置更新方程中各部分的影響（1）只有第1部分，即

1=

2=0

粒子將一直以當(dāng)前的速度飛行，直到達(dá)邊界。由于它只能搜索有限的區(qū)域，所以很難找到好解。846.6.2粒子群優(yōu)化算法的參數(shù)分析2.位置更新方程中各部分的影響（2）沒有第1部分，即

=0速度只取決于粒子當(dāng)前位置和其歷史最好位置Pi

和

Pg，速度本身沒有記憶性。856.6.2粒子群優(yōu)化算法的參數(shù)分析（3）沒有第2部分，即

1=0

粒子沒有認(rèn)知能力，也就是“只有社會模型”。在粒子的相互作用下，有能力達(dá)到新的搜索空間。但對復(fù)雜問題，容易陷入局部最優(yōu)點(diǎn)。866.6.2粒子群優(yōu)化算法的參數(shù)分析（4）沒有第3部分，即

2=0

粒子間沒有社會共享信息，也就是“只有認(rèn)知”模型。因?yàn)閭€體間沒有交互，一個規(guī)模為M的群體等價于M個單個粒子的運(yùn)行，因而得到最優(yōu)解的機(jī)率非常小。876.6.2粒子群優(yōu)化算法的參數(shù)分析3.參數(shù)設(shè)置早期的實(shí)驗(yàn)：

固定為1.0，

1和

2固定為2.0，因此Vmax成為唯一需要調(diào)節(jié)的參數(shù)，通常設(shè)為每維變化范圍10％~20%。Suganthan的實(shí)驗(yàn)表明，

1和

2為常數(shù)時可以得到較好的解，但不一定必須為2。這些參數(shù)也可以通過模糊系統(tǒng)進(jìn)行調(diào)節(jié)。Shi和Eberhart提出一個模糊系統(tǒng)來調(diào)節(jié)

。886.6.3粒子群優(yōu)化算法應(yīng)用領(lǐng)域（1）神經(jīng)網(wǎng)絡(luò)訓(xùn)練（7）經(jīng)濟(jì)領(lǐng)域（2）化工系統(tǒng)領(lǐng)域（8）圖像處理領(lǐng)域（3）電力系統(tǒng)領(lǐng)域（9）生物信息領(lǐng)域（4）機(jī)械設(shè)計領(lǐng)域（10）醫(yī)學(xué)領(lǐng)域（5）通訊領(lǐng)域（11）運(yùn)籌學(xué)領(lǐng)域（6）機(jī)器人領(lǐng)域………….粒子群優(yōu)化算法已在諸多領(lǐng)域得到應(yīng)用，歸納如下：89車輛路徑問題（VRP）的模型6.6.4粒子群優(yōu)化算法求解車輛路徑問題車輛路徑問題：假定配送中心最多可以用

輛車對

個客戶進(jìn)行運(yùn)輸配送，

表示倉庫。每個車輛載重為

，每個客戶的需求為

，客戶i到客戶

j的運(yùn)輸成本為

cij（可以是距離，時間，費(fèi)用等）。定義如下變量：90車輛路徑問題（VRP）的模型6.6.4粒子群優(yōu)化算法在車輛路徑問題中的應(yīng)用車輛路徑問題的數(shù)學(xué)模型：(6.21a)(6.21b)每輛車的能力約束(6.21c)保證每個客戶都被服務(wù)(6.21d)保證客戶是僅被一輛車訪問(6.21e)保證客戶是僅被一輛車訪問(6.21f)消除子回路(6.21g)表示變量的取值范圍(6.21h)表示變量的取值范圍916.6.4粒子群優(yōu)化算法在車輛路徑問題中的應(yīng)用2.編碼與初始種群

對這類組合優(yōu)化問題，編碼方式、初始解的設(shè)置對問題的求解都有很大的影響。采用常用的自然數(shù)編碼方式。

對于K輛車和L個客戶的問題，用從1到L的自然數(shù)隨機(jī)排列來產(chǎn)生一組解

。然后分別用節(jié)約法或者最近插入法構(gòu)造初始解。(3)實(shí)驗(yàn)結(jié)果粒子群優(yōu)化算法的各個參數(shù)設(shè)置如下：種群規(guī)模：50迭代次數(shù)：1000c1的初始值為1，隨迭代的進(jìn)行，線性減小到0C2=c3=1.4Vmax<1000優(yōu)化結(jié)果及其與遺傳算法的比較如表6.4所示。926.6.4粒子群優(yōu)化算法在車輛路徑問題中的應(yīng)用936.1進(jìn)化算法的產(chǎn)生與發(fā)展6.2基本遺傳算法6.3遺傳算法的改進(jìn)算法6.4遺傳算法的應(yīng)用6.5群智能算法產(chǎn)生的背景6.6粒子群優(yōu)化算法及其應(yīng)用6.7蟻群算法及其應(yīng)用第6章智能計算及其應(yīng)用94●

20世紀(jì)90年代初，意大利科學(xué)家MarcoDorigo等受螞蟻覓食行為的啟發(fā)，提出蟻群算法(AntColonyOptimization，ACO)。6.7蟻群算法及其應(yīng)用●

一種應(yīng)用于組合優(yōu)化問題的啟發(fā)式搜索算法?！?/p>

在解決離散組合優(yōu)化方面具有良好的性能。

產(chǎn)生背景95基本思想●

信息素跟蹤：按照一定的概率沿著信息素較強(qiáng)的路徑覓食。●

信息素遺留：會在走過的路上會釋放信息素，使得在一定的范圍內(nèi)的其他螞蟻能夠覺察到并由此影響它們的行為。6.7蟻群算法及其應(yīng)用96

（1）環(huán)境：有障礙物、有其他螞蟻、有信息素。（2）覓食規(guī)則：范圍內(nèi)尋找是否有食物，否則看是否有信息素，每只螞蟻都會以小概率犯錯。（3）移動規(guī)則：都朝信息素最多的方向移動，無信息素則繼續(xù)朝原方向移動，且有隨機(jī)的小的擾動，有記憶性。（4）避障規(guī)則：移動的方向如有障礙物擋住，螞蟻會隨機(jī)選擇另一個方向。（5）信息素規(guī)則：越靠近食物播撒的信息素越多，越離開食物播撒的信息素越少。6.7蟻群算法及其應(yīng)用976.7.1基本蟻群算法模型6.7.2蟻群算法的參數(shù)選擇6.7.3蟻群算法的應(yīng)用6.7蟻群算法及其應(yīng)用986.7.1基本蟻群算法模型蟻群優(yōu)化算法的第一個應(yīng)用是著名的旅行商問題。旅行商問題闡明

蟻群系統(tǒng)模型旅行商問題（TravelingSalesmanProblem，TSP）：在尋求單一旅行者由起點(diǎn)出發(fā)，通過所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。螞蟻搜索食物的過程：通過個體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的最短路徑。99蟻群系統(tǒng)的模型

6.7.1基本蟻群算法模型

m是蟻群中螞蟻的數(shù)量表示元素(城市)和元素(城市)之間的距離

表示能見度，稱為啟發(fā)信息函數(shù)，等于距離

的倒數(shù)，即

表示t時刻位于城市x的螞蟻的個數(shù)，

表示t時刻在xy連線上殘留的信息素，初始時

刻，各條路徑上的信息素相等即

螞蟻k在運(yùn)動過程中，根據(jù)各條路徑上的信息素決定轉(zhuǎn)移方向。1006.7.1基本蟻群算法模型

表示在t時刻螞蟻k選擇從元素(城市)x轉(zhuǎn)移到元素(城市)y的概率，也稱為隨機(jī)比例規(guī)則。信息素共同決定局部啟發(fā)信息蟻群系統(tǒng)的模型1016.7.1基本蟻群算法模型

表示如下：

（6.22）其中：

表示螞蟻k下一步允許選擇的城市

記錄螞蟻k當(dāng)前所走過的城市

是信息素啟發(fā)式因子，表示軌跡的相對重要性1026.7.1基本蟻群算法模型

表示如下：

（6.22）其中：

值越大該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，該狀態(tài)轉(zhuǎn)移概率越接近于貪婪規(guī)則。當(dāng)=0時不再考慮信息素水平，算法就成為有多重起點(diǎn)的隨機(jī)貪婪算法。當(dāng)=0時算法就成為純粹的正反饋的啟發(fā)式算法。1036.7.1基本蟻群算法模型用參數(shù)1-

表示信息素消逝程度，螞蟻完成一次循環(huán)，各路徑上信息素濃度消散規(guī)則為：

（6.23）蟻群的信息素濃度更新規(guī)則為：（6.24）M.Dorigo給出

的三種不同模型104螞蟻圈系統(tǒng)（Ant-cycleSystem）6.7.1基本蟻群算法模型單只螞蟻所訪問路徑上的信息素濃度更新規(guī)則為：

（6.25）其中：

為當(dāng)前路徑上的信息素

為路徑（x,y）上信息素的增量

第k只螞蟻留在路徑（x,y）上的信息素的增量Q為常數(shù)Lk

為優(yōu)化問題的目標(biāo)函數(shù)值，表示第k只螞蟻在本次循環(huán)