優(yōu)化算法及其在軟測(cè)量技術(shù)中的應(yīng)用

本章主要內(nèi)容概述遺傳算法微粒群算法蟻群算法第1頁(yè)/共73頁(yè)第一頁(yè)，共74頁(yè)。6.1

概述進(jìn)化計(jì)算(EvolutionaryComputation)是通過(guò)模擬自然界中生物進(jìn)化機(jī)制進(jìn)行搜索的一種算法?！暨z傳算法（GeneticAlgorithms）

◆進(jìn)化策略（EvolutionStrategies）

◆進(jìn)化規(guī)劃（EvolutionProgramming）遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過(guò)人工方式所構(gòu)造的一類(lèi)優(yōu)化搜索算法，是對(duì)生物進(jìn)化過(guò)程進(jìn)行的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的最重要的形式。

第2頁(yè)/共73頁(yè)第二頁(yè)，共74頁(yè)。6.1

概述群智能(SwarmIntelligence)這個(gè)概念來(lái)自對(duì)蜜蜂、螞蟻、大雁等群居生物群體行為的觀察和研究。任何啟發(fā)于群居性昆蟲(chóng)群體和其它動(dòng)物群體的集體行為而設(shè)計(jì)的算法和分布式問(wèn)題解決裝置都稱(chēng)為群智能。群智能是一種在自然界生物群體所表現(xiàn)出的智能現(xiàn)象啟發(fā)下提出的人工智能實(shí)現(xiàn)模式，是對(duì)簡(jiǎn)單生物群體的智能涌現(xiàn)現(xiàn)象的具體模式研究，即簡(jiǎn)單智能的主體通過(guò)合作表現(xiàn)出復(fù)雜智能行為的特性。該智能模式需要以相當(dāng)數(shù)目的智能個(gè)體來(lái)實(shí)現(xiàn)對(duì)問(wèn)題的求解功能。群智能在沒(méi)有集中控制并且不提供全局模型的前提下，為尋找復(fù)雜的分布式問(wèn)題的解決方案提供了基礎(chǔ)。第3頁(yè)/共73頁(yè)第三頁(yè)，共74頁(yè)。6.1

概述群智能的特點(diǎn)：◆分布式：能夠適應(yīng)當(dāng)前網(wǎng)絡(luò)環(huán)境下的工作狀態(tài)◆魯棒性：沒(méi)有中心的控制與數(shù)據(jù)，個(gè)體的故障不影響整個(gè)問(wèn)題的求解◆擴(kuò)充性：個(gè)體的增加，系統(tǒng)的通信開(kāi)銷(xiāo)增加小◆簡(jiǎn)單性：個(gè)體簡(jiǎn)單，實(shí)現(xiàn)也比較簡(jiǎn)單第4頁(yè)/共73頁(yè)第四頁(yè)，共74頁(yè)。6.1

概述群智能的典型實(shí)現(xiàn)模式：◆微粒群算法（Particleswarmoptimization,PSO）：模擬鳥(niǎo)群運(yùn)動(dòng)模式◆蟻群算法（Antcolonyalgorithm）：模擬生物蟻群運(yùn)動(dòng)行為第5頁(yè)/共73頁(yè)第五頁(yè)，共74頁(yè)。6.2

遺傳算法遺傳算法的基本機(jī)理遺傳算法的一般框架遺傳算法的模式理論Matlab遺傳算法工具箱第6頁(yè)/共73頁(yè)第六頁(yè)，共74頁(yè)。6.2.1

遺傳算法的基本機(jī)理遺傳與進(jìn)化的系統(tǒng)觀點(diǎn)：生物的所有遺傳信息的都包含在其染色體中，染色體決定了生物的性狀染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳進(jìn)化過(guò)程發(fā)生在染色體上生物的繁殖過(guò)程是由其基因的復(fù)制過(guò)程來(lái)完成的通過(guò)同源染色體之間的交叉或染色體的變異會(huì)產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀對(duì)環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的機(jī)會(huì)遺傳到下一代第7頁(yè)/共73頁(yè)第七頁(yè)，共74頁(yè)。6.2.1

遺傳算法的基本機(jī)理遺傳算法的基本機(jī)理模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索空間映射為遺傳空間，把可能的解編碼成一個(gè)向量——染色體，向量的每個(gè)元素稱(chēng)為基因。利用選擇、交叉、變異等遺傳算子產(chǎn)生新的染色體，通過(guò)不斷計(jì)算各染色體的適應(yīng)度值，選擇最好的染色體，獲得最優(yōu)解。第8頁(yè)/共73頁(yè)第八頁(yè)，共74頁(yè)。6.2.1

遺傳算法的基本機(jī)理遺傳學(xué)和遺傳算法中基本術(shù)語(yǔ)對(duì)照表：自然界染色體(chromosome)基因(gene)等位基因(allele)染色體位置(locus)基因型(genotype)表型(phenotype)遺傳算法字符串字符,特征特征值字符串位置結(jié)構(gòu)參數(shù)集,譯碼結(jié)構(gòu)第9頁(yè)/共73頁(yè)第九頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法的構(gòu)成要素：◆染色體編碼方法◆適應(yīng)度函數(shù)◆遺傳算子（選擇、交叉、變異）◆遺傳參數(shù)設(shè)置第10頁(yè)/共73頁(yè)第十頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架編碼與解碼：

◆

將問(wèn)題結(jié)構(gòu)變換為位串形式表示的過(guò)程叫編碼，相反把位串形式表示變換為原問(wèn)題結(jié)構(gòu)的過(guò)程叫解碼

◆

GA常用的編碼方法：二進(jìn)制編碼，實(shí)數(shù)編碼，格雷碼，符號(hào)編碼，多參數(shù)編碼等

第11頁(yè)/共73頁(yè)第十一頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架適應(yīng)度函數(shù)：

◆

一般情況下，適應(yīng)度函數(shù)由目標(biāo)函數(shù)變換而成，適應(yīng)度函數(shù)要求為非負(fù)函數(shù)

◆若目標(biāo)函數(shù)為最大化問(wèn)題，則

◆若目標(biāo)函數(shù)為最小化問(wèn)題，則第12頁(yè)/共73頁(yè)第十二頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算子：

◆

選擇（Selection）：

-從舊的種群中選擇適應(yīng)度高的染色體，放入匹配集（緩沖區(qū)），為以后染色體交叉、變異，產(chǎn)生新的染色體作準(zhǔn)備。

-選擇方法：適應(yīng)度比例法（輪盤(pán)賭法），即按各染色體適應(yīng)度大小比例來(lái)決定其被選擇數(shù)目的多少。某染色體被選的概率：第13頁(yè)/共73頁(yè)第十三頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算子：

◆

交叉（Crossover）：

-隨機(jī)選擇二個(gè)染色體(雙親染色體)，隨機(jī)指定一點(diǎn)或多點(diǎn)，將兩者部分碼值進(jìn)行交換，可得二個(gè)新的染色體(子輩染色體)。新的子輩染色體:A’11010001B’01011110第14頁(yè)/共73頁(yè)第十四頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算子：

◆

變異（Mutation）：

-模擬生物在自然界環(huán)境變化，引起基因的突變。

-在染色體二進(jìn)制編碼中，1變成0，或0變成1-變異產(chǎn)生染色體的多樣性，避免進(jìn)化中早期成熟，陷入局部極值點(diǎn)，變異的概率很低。A10100110A’10110110第15頁(yè)/共73頁(yè)第十五頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳參數(shù)設(shè)置：

◆

N：群體大小，即群體中所含個(gè)體的數(shù)量，一般取20~100

◆

T：GA的終止進(jìn)化代數(shù)，一般取100~500

◆

Pc：交叉概率，一般取0.4~0.99

◆

Pm：變異概率，一般取0.0001~0.1第16頁(yè)/共73頁(yè)第十六頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法進(jìn)行問(wèn)題求解的過(guò)程：

◆初始化群體

◆計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度值

◆按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇進(jìn)入下一代的個(gè)體

◆按概率Pc進(jìn)行交叉操作

◆按概率Pm進(jìn)行變異操作

◆若沒(méi)有滿(mǎn)足某種停止條件，就轉(zhuǎn)到第2步，否則進(jìn)入下一步

◆輸出群體中適應(yīng)度值最優(yōu)的染色體作為問(wèn)題的滿(mǎn)意解或最優(yōu)解第17頁(yè)/共73頁(yè)第十七頁(yè)，共74頁(yè)。第18頁(yè)/共73頁(yè)第十八頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：例4-1

利用遺傳算法求解區(qū)間[0,31]上的二次函數(shù)y=x2的最大值。y=x2

31

XY分析：

原問(wèn)題可轉(zhuǎn)化為在區(qū)間[0,31]中搜索能使y取最大值的點(diǎn)a的問(wèn)題。那么，[0,31]中的點(diǎn)x就是個(gè)體，函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(gè)解空間。這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼，該問(wèn)題就可以用遺傳算法來(lái)解決。第19頁(yè)/共73頁(yè)第十九頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：

解：(1)

設(shè)定種群規(guī)模，編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4，用5位二進(jìn)制數(shù)編碼染色體，取下列個(gè)體組成初始種群S1:

s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應(yīng)度函數(shù)：f(x)=x2

(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對(duì)其染色體進(jìn)行遺傳操作，直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。第20頁(yè)/共73頁(yè)第二十頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：

首先計(jì)算種群S1中各個(gè)體的適應(yīng)度f(wàn)(si)：

f(s1)=f(13)=132=169，f(s2)=f(24)=242=576f(s3)=f(8)=82=64，f(s4)=f(19)=192=361再計(jì)算種群S1中各個(gè)體的選擇概率：

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31s40.31s20.49s10.14s30.06第21頁(yè)/共73頁(yè)第二十一頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：在算法中賭輪選擇法可用下面的子過(guò)程來(lái)模擬：①在[0,1]區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1，則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N)，則染色體xk被選中。其中的qi稱(chēng)為染色體xi(i=1,2,…,n)的積累概率，其計(jì)算公式為：

第22頁(yè)/共73頁(yè)第二十二頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：

設(shè)從區(qū)間[0,1]中產(chǎn)生4個(gè)隨機(jī)數(shù)如下：

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001第23頁(yè)/共73頁(yè)第二十三頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：于是，經(jīng)復(fù)制得群體：

s1’

=11000（24）,s2’

=01101（13）

s3’

=11000（24）,s4’

=10011（19）設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對(duì)，s3’與s4’配對(duì)。分別交換后兩位基因，得新染色體：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

第24頁(yè)/共73頁(yè)第二十四頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：

設(shè)變異率pm=0.001，這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。

于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）

第25頁(yè)/共73頁(yè)第二十五頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：第二代種群S2中各染色體的情況：

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001第26頁(yè)/共73頁(yè)第二十六頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：假設(shè)這一輪選擇復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：

s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運(yùn)算，讓s1’與s2’，s3’與s4’

分別交換后三位基因：

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

這一輪仍然不會(huì)發(fā)生變異。

第27頁(yè)/共73頁(yè)第二十七頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：第三代種群S3中各染色體的情況：

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001第28頁(yè)/共73頁(yè)第二十八頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：設(shè)這一輪的選擇復(fù)制結(jié)果為：

s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

做交叉運(yùn)算，讓s1’與s2’，s3’與s4’

分別交換后三位基因：

s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍然不會(huì)發(fā)生變異。

第29頁(yè)/共73頁(yè)第二十九頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法應(yīng)用舉例：第四代種群S4中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961。

第30頁(yè)/共73頁(yè)第三十頁(yè)，共74頁(yè)。YYy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度y=x216242831

X第四代種群及其適應(yīng)度第31頁(yè)/共73頁(yè)第三十一頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法的特點(diǎn)：

◆GA是對(duì)參數(shù)集合的編碼而非針對(duì)參數(shù)本身進(jìn)行優(yōu)化

◆GA是從問(wèn)題解的編碼組開(kāi)始而非單個(gè)解開(kāi)始搜索

◆

GA利用目標(biāo)函數(shù)的適應(yīng)度這一信息而非利用導(dǎo)數(shù)或其他輔助信息來(lái)指導(dǎo)搜索

◆

GA利用選擇、交叉、變異等算子而不是確定性規(guī)則進(jìn)行隨機(jī)操作

第32頁(yè)/共73頁(yè)第三十二頁(yè)，共74頁(yè)。6.2.2

遺傳算法的一般框架遺傳算法的局限性：

◆遺傳算法在解決某些問(wèn)題時(shí)速度較慢

◆遺傳算法對(duì)編碼方案的依賴(lài)性較強(qiáng)

◆算法的魯棒性不夠好

第33頁(yè)/共73頁(yè)第三十三頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論遺傳算法的理論基礎(chǔ)是遺傳算法的二進(jìn)制表達(dá)式及模式的含義。模式是能對(duì)染色體之間的相似性進(jìn)行解釋的模板。設(shè)GA的個(gè)體，記集合則稱(chēng)為一個(gè)模式，其中＊是通配符。即模式(schema)是含有通配符(*)的一類(lèi)字符串的通式表達(dá)。每個(gè)“*”可以取“1”或者“0”。第34頁(yè)/共73頁(yè)第三十四頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論模式舉例：

-模式*10101110與以下兩個(gè)字符串匹配：010101110110101110

-模式*1010＊110與以下四個(gè)字符串匹配：010100110010101110110100110110101110第35頁(yè)/共73頁(yè)第三十五頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論一個(gè)模式s的階(order)是出現(xiàn)在模式中的“0”和“1”的數(shù)目，記為o(s)。

-如：模式“0****”的階為1，模式“10*1*”的階為3一個(gè)模式s的長(zhǎng)度(Length)是出現(xiàn)在模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離，記為。

-如：模式“01***”的長(zhǎng)度為1，模式“0***1”的長(zhǎng)度為3。第36頁(yè)/共73頁(yè)第三十六頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論復(fù)制對(duì)模式的影響：

假定在給定的時(shí)間（代）t，一個(gè)特定的模式s在群體P(t)中包含有m個(gè)代表串，記為m=m(s,t)。每個(gè)串根據(jù)適應(yīng)值的大小獲得不同的復(fù)制概率。串i的復(fù)制概率為：

則在群體P(t+1)中，模式s的代表串的數(shù)量的期望值為

其中，表示模式s在t時(shí)刻的所有代表串的適應(yīng)值的均值，稱(chēng)為模式s的適應(yīng)值。第37頁(yè)/共73頁(yè)第三十七頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論復(fù)制對(duì)模式的影響：若記P(t)中所有個(gè)體的適應(yīng)值的平均值為：則有：上式表明，模式s的代表串的數(shù)目隨時(shí)間增長(zhǎng)的幅度正比于模式s的適應(yīng)值與群體平均適應(yīng)值的比值。即：適應(yīng)值高于群體平均值的模式在下一代的代表串?dāng)?shù)目將會(huì)增加，而適應(yīng)值低于群體平均值的模式在下一代的代表串?dāng)?shù)目將會(huì)減少。

第38頁(yè)/共73頁(yè)第三十八頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論復(fù)制對(duì)模式的影響：

假設(shè)模式的適應(yīng)值為，其中c是一個(gè)常數(shù)，則有：

上式表明，在平均適應(yīng)值之上（之下）的模式，將會(huì)按指數(shù)增長(zhǎng)（衰減）的方式被復(fù)制。復(fù)制的結(jié)果并沒(méi)有生成新的模式。因而，為了探索搜索空間中的未搜索部分，需要利用交叉和變異操作。

第39頁(yè)/共73頁(yè)第三十九頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論交叉對(duì)模式的影響：

交叉會(huì)改變模式的一部分，模式的長(zhǎng)度越長(zhǎng)，被破壞的概率越大。假定模式s在交叉后不被破壞的概率為ps，則：

若交叉概率為pc，則s不被破壞的概率為：

第40頁(yè)/共73頁(yè)第四十頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論交叉對(duì)模式的影響：

若綜合考慮復(fù)制和交叉的影響，特定模式在下一代中的數(shù)量可用下式來(lái)估計(jì)：可見(jiàn)，對(duì)于那些高于平均適應(yīng)度且具有短短定義長(zhǎng)度的模式將更多地出現(xiàn)在下一代中。

第41頁(yè)/共73頁(yè)第四十一頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論變異對(duì)模式的影響：變異算子以概率pm隨機(jī)地改變個(gè)體某一位的值，只有當(dāng)o(s)個(gè)確定位的值不被破壞時(shí)，模式s才不被破壞。模式s在變異后不被破壞的概率：由于Pm<<1，可近似地表示為：

第42頁(yè)/共73頁(yè)第四十二頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論變異對(duì)模式的影響：綜合考慮復(fù)制、交叉及變異操作，可得特定模式s的數(shù)量為：

第43頁(yè)/共73頁(yè)第四十三頁(yè)，共74頁(yè)。6.2.3

遺傳算法的模式理論模式理論(SchemaTheorem)：

適應(yīng)值在群體適應(yīng)值之上的、長(zhǎng)度較短的、低階的模式在GA的迭代中將按指數(shù)增長(zhǎng)方式被復(fù)制?！胺e木塊假設(shè)”(BuildingBlockHypothesis):低階、長(zhǎng)度較短、高于平均適應(yīng)度的模式(積木塊)在遺傳算子的作用下，相互結(jié)合，能生成高階、長(zhǎng)度較長(zhǎng)、適應(yīng)度較高的模式，并得到全局最優(yōu)解。

第44頁(yè)/共73頁(yè)第四十四頁(yè)，共74頁(yè)。6.2.4

Matlab遺傳算法工具箱在Matlab7.0以上版本中包含了遺傳算法工具箱GADS，該工具箱可以用遺傳算法求解如下帶約束非線(xiàn)性?xún)?yōu)化問(wèn)題：

第45頁(yè)/共73頁(yè)第四十五頁(yè)，共74頁(yè)。6.2.4

Matlab遺傳算法工具箱GADS工具箱可通過(guò)圖形界面方式和命令行方式調(diào)用。在命令行中輸入：

>>gatool圖形界面如圖：

第46頁(yè)/共73頁(yè)第四十六頁(yè)，共74頁(yè)。6.2.4

Matlab遺傳算法工具箱GADS工具箱可通過(guò)命令行或m文件調(diào)用，其核心函數(shù)為：[x,

fval,

reason,

output]=ga(fitnessfcn,

nvars,A,b,Aeq,beq,LB,UB,nonlcon,

options)函數(shù)參數(shù)說(shuō)明如下：

輸入?yún)?shù)fitnessfcn：適應(yīng)度函數(shù)f(x)nvars：變量數(shù)量A,b：線(xiàn)性不等式約束條件下A1x≤b1的參數(shù)Aeq,beq：線(xiàn)性等式約束條件A2x=b2的參數(shù)LB：x的取值下限v1UB：x的取值上限v2nonlcon：非線(xiàn)性約束條件c1(x)≤0和c2(x)=0options:：與算法性能相關(guān)的參數(shù)輸出參數(shù)x：最優(yōu)值fval：最優(yōu)值下的適應(yīng)度函數(shù)值reason：算法停止原因output：每次迭代信息及其他算法信息第47頁(yè)/共73頁(yè)第四十七頁(yè)，共74頁(yè)。6.2.4

Matlab遺傳算法工具箱影響遺傳算法性能的參數(shù)由結(jié)構(gòu)體options給定，可使用如下命令查看options的默認(rèn)值：

>>options=gaoptimset

GADS中默認(rèn)的options參數(shù)值為：

PopulationType:'doubleVector’種群數(shù)據(jù)類(lèi)型InitialPopulation:[]初始種群PopInitRange:[2*1double]初始種群中個(gè)體取值范圍InitialScores:[]初始適應(yīng)度PopulationSize:20種群規(guī)模InitialPenalty:10初始懲罰參數(shù)EliteCount:2在每代中保留下來(lái)的個(gè)體數(shù)量PenaltyFactor:100懲罰更新參數(shù)CrossoverFraction:0.8000交叉概率PlotInterval:1繪制函數(shù)調(diào)用間隔Migrationdirection:

‘forword’變異方向CreationFcn:@gacreationuniform初始種群函數(shù)的句柄MigrationInterval:20子群中發(fā)生變異的代數(shù)間隔FitnessScalingFcn:@fitscalingrank調(diào)節(jié)適應(yīng)度的函數(shù)句柄MigrationFraction:0.2000變異概率SelectionFcn:@selectionstochunif選擇函數(shù)句柄Generations:100最大迭代次數(shù)CrossoverFcn:@crossoverscattered交叉函數(shù)句柄TimeLimit:Inf最大運(yùn)行時(shí)間MutationFcn:@mutationgaussian變異函數(shù)句柄FitnessLimit:-Inf當(dāng)適應(yīng)度函數(shù)達(dá)該值時(shí)算法停止HybridFcn:[]GA終止后繼續(xù)優(yōu)化的函數(shù)句柄StallGenLimit:50算法停止的代數(shù)Display:‘final’顯示方式StallTimeLimit:20算法停止的時(shí)間PlotFcns:[]繪制函數(shù)的句柄TolFun:1.0000e-006當(dāng)適應(yīng)度函數(shù)在StallGenLimit設(shè)定的代數(shù)內(nèi)變化小于該值算法停止OutputFcns:[]在每代中調(diào)用的函數(shù)TolCon:1.0000e-006非線(xiàn)性約束的可行性Vectorized:‘off’適應(yīng)度函數(shù)是否矢量化第48頁(yè)/共73頁(yè)第四十八頁(yè)，共74頁(yè)。6.2.4

Matlab遺傳算法工具箱如果需要修改上述options中的參數(shù)值，例如修改PopulationSize至100，可采用如下命令：

>>options=gaoptimset(‘PopulationSize’,100)

也可通過(guò)上述命令同時(shí)修改多個(gè)參數(shù)在實(shí)際應(yīng)用中，通常需要根據(jù)應(yīng)用需求編寫(xiě)適當(dāng)?shù)倪m應(yīng)度函數(shù)，在編寫(xiě)函數(shù)的時(shí)候需注意GADS是求最小值的，編寫(xiě)好的適應(yīng)度函數(shù)需存成m文件放在同一目錄下。

第49頁(yè)/共73頁(yè)第四十九頁(yè)，共74頁(yè)。6.2.4

Matlab遺傳算法工具箱例：當(dāng)x1∈[-3.0,12.1]，x2∈[4.1,5.8]時(shí)，求函數(shù)

f(x1,x2)=21.5+x1*sin(4*pi*x1)+x2*sin(20*pi*x2)的極大值。解：首先編寫(xiě)適應(yīng)度函數(shù)如下：

functionscore=my_func1(x)

score=-21.5-x(1)*sin(4*pi*x(1))-x(2)*sin(20*pi*x(2));

然后選用合適的參數(shù)調(diào)用ga函數(shù)：

opt1=gaoptimset;

opt1.PopInitRange=[[-3.04.1];[12.15.8]];

opt1.PopulationSize=1000;

opt1.MutationFcn=@mutationuniform;

[x,fval]=ga(@my_func1,2,opt1)

第50頁(yè)/共73頁(yè)第五十頁(yè)，共74頁(yè)。6.2.4

Matlab遺傳算法工具箱運(yùn)行結(jié)果如下：

Optimizationterminated:stallgenerationslimitexceeded.

x=

11.62885.7244

fval=

-38.8354需要注意到是：由于遺傳算法是一種隨機(jī)搜索算法，每次運(yùn)行得到的結(jié)果很可能不同，這主要是Matlab在每次迭代時(shí)，采用rand和randn這兩個(gè)隨機(jī)數(shù)生成函數(shù)來(lái)隨機(jī)選擇樣本，每次Matlab調(diào)用這兩個(gè)函數(shù)時(shí)，他們的狀態(tài)是不同的，因此產(chǎn)生的隨機(jī)數(shù)也不同，從而導(dǎo)致最終結(jié)果也不同。

第51頁(yè)/共73頁(yè)第五十一頁(yè)，共74頁(yè)。6.3

微粒群算法微粒群算法的基本思想：PSO是J.Kennedy和R.C.Eberhart于1995年提出的一種新的優(yōu)化算法，其基本思想來(lái)源于鳥(niǎo)群捕食過(guò)程的社會(huì)行為研究。PSO將群體中的成員描述為空間內(nèi)一個(gè)沒(méi)有質(zhì)量、沒(méi)有體積的微粒，所有微粒通過(guò)一個(gè)適應(yīng)度函數(shù)來(lái)確定其在空間中的適應(yīng)度。進(jìn)化初期，每個(gè)微粒的位置和速度都被隨機(jī)初始化，微粒在飛行過(guò)程中相互合作，根據(jù)自身和同伴的運(yùn)動(dòng)狀態(tài)及時(shí)調(diào)整自己的速度和位置，以便在適應(yīng)度較好的位置降落。第52頁(yè)/共73頁(yè)第五十二頁(yè)，共74頁(yè)。6.3

微粒群算法微粒群算法數(shù)學(xué)描述：設(shè)微粒群體規(guī)模為N，其中每個(gè)微粒在D維空間中的坐標(biāo)位置可表示為Xi=(xi1,xi2,…,xiD)，微粒i的速度定義為每次迭代中微粒移動(dòng)的距離，表示為Vi=(vi1,vi2,…,viD)，Pi表示微粒i所經(jīng)歷的最好位置，Pg為群體中所有微粒所經(jīng)過(guò)的最好位置，則微粒i在第d維子空間中的飛行速度vid根據(jù)下式進(jìn)行調(diào)整：微粒通過(guò)下式調(diào)整自身位置：第53頁(yè)/共73頁(yè)第五十三頁(yè)，共74頁(yè)。6.3

微粒群算法微粒群算法數(shù)學(xué)描述：

速度調(diào)整公式：第一項(xiàng)為微粒先前速度乘一個(gè)權(quán)值進(jìn)行加速，表示微粒對(duì)當(dāng)前自身速度狀態(tài)的信任，依據(jù)自身的速度進(jìn)行慣性運(yùn)動(dòng)，因此稱(chēng)這個(gè)權(quán)值為慣性權(quán)值第二項(xiàng)為微粒當(dāng)前位置與自身最優(yōu)位置之間的距離，為認(rèn)知部分，表示微粒本身的思考，即微粒的運(yùn)動(dòng)來(lái)源于自己經(jīng)驗(yàn)的部分第三項(xiàng)為微粒當(dāng)前位置與群體最優(yōu)位置之間的距離，為社會(huì)部分，表示微粒間的信息共享與相互合作，即微粒的運(yùn)動(dòng)中來(lái)源于群體中其他微粒經(jīng)驗(yàn)的部分第54頁(yè)/共73頁(yè)第五十四頁(yè)，共74頁(yè)。6.3

微粒群算法微粒群算法基本流程：

(1)Initial:

隨機(jī)初始化每一微粒的位置和速度。

(2)Evaluation：依據(jù)適應(yīng)度函數(shù)計(jì)算每個(gè)微粒的適應(yīng)度值，以作為判斷每一微粒之好壞。

(3)FindthePbest：找出每一微粒到目前為止的搜尋過(guò)程中最佳解，這個(gè)最佳解稱(chēng)為Pbest。

(4)FindtheGbest：找出所有微粒到目前為止所搜尋到的整體最佳解，此最佳解稱(chēng)之為Gbest。

(5)UpdatetheVelocity：更新每一微粒的速度與位置

(6)回到步驟(2)繼續(xù)執(zhí)行，直到獲得一個(gè)令人滿(mǎn)意的結(jié)果或符合終止條件為止。

第55頁(yè)/共73頁(yè)第五十五頁(yè)，共74頁(yè)。6.3

微粒群算法微粒群算法基本流程：第56頁(yè)/共73頁(yè)第五十六頁(yè)，共74頁(yè)。6.3

微粒群算法PSO的參數(shù)設(shè)置：

◆種群規(guī)模:

一般取20-40◆粒子長(zhǎng)度：由優(yōu)化問(wèn)題決定，就是問(wèn)題解的長(zhǎng)度◆粒子范圍：由優(yōu)化問(wèn)題決定，每一維可設(shè)定不同的范圍◆最大速度：決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離，通常設(shè)為粒子的范圍寬度◆學(xué)習(xí)因子：二者相等且在[0,4]之間，通常取為2◆終止條件：最大循環(huán)次數(shù)以及最小錯(cuò)誤要求，由具體問(wèn)題確定◆慣性權(quán)值：第57頁(yè)/共73頁(yè)第五十七頁(yè)，共74頁(yè)。6.3

微粒群算法PSO與GA的比較：

(1)共同之處:

兩者都隨機(jī)初始化種群，而且都使用適應(yīng)值來(lái)評(píng)價(jià)系統(tǒng)，并且都根據(jù)適應(yīng)值來(lái)進(jìn)行一定的隨機(jī)搜索，兩個(gè)系統(tǒng)都不是保證一定找到最優(yōu)解

(2)區(qū)別：

-PSO沒(méi)有遺傳操作如交叉、變異等，而是根據(jù)自己的速度來(lái)決定搜索

-粒子還有一個(gè)重要的特點(diǎn)，就是有記憶，而GA沒(méi)有

-PSO的信息共享機(jī)制與GA也很不同，在GA中染色體互相共享信息，整個(gè)種群的移動(dòng)是比較平均的向最優(yōu)區(qū)域移動(dòng)，而在PSO中只有Gbest給出信息給其他的粒子，整個(gè)搜索更新過(guò)程是跟隨當(dāng)前最優(yōu)解的過(guò)程。第58頁(yè)/共73頁(yè)第五十八頁(yè)，共74頁(yè)。6.4

蟻群算法蟻群算法（Antcolonyalgorithm）是20世紀(jì)90年代初意大利學(xué)者M(jìn).Dorigo，V.Maniezzo，A.Colorni等從生物進(jìn)化的機(jī)制中受到啟發(fā)，通過(guò)模擬自然界螞蟻搜索路徑的行為提出來(lái)的一種新型的模擬進(jìn)化算法。螞蟻在運(yùn)動(dòng)過(guò)程中，能夠在它所經(jīng)過(guò)的路徑上留下一種稱(chēng)之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過(guò)程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過(guò)的螞蟻越多，則后來(lái)者選擇該路徑的概率就越大。最優(yōu)路徑上的激素濃度越來(lái)越大，而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。第59頁(yè)/共73頁(yè)第五十九頁(yè)，共74頁(yè)。6.4

蟻群算法簡(jiǎn)單的螞蟻尋食過(guò)程：螞蟻從A點(diǎn)出發(fā)，速度相同，食物在D點(diǎn)，可能隨機(jī)選擇路線(xiàn)ABD或ACD。假設(shè)初始時(shí)每條分配路線(xiàn)一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過(guò)9個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)，而走ACD的螞蟻剛好走到C點(diǎn)，為一半路程。第60頁(yè)/共73頁(yè)第六十頁(yè)，共74頁(yè)。6.4

蟻群算法簡(jiǎn)單的螞蟻尋食過(guò)程：本圖為從開(kāi)始算起，經(jīng)過(guò)18個(gè)時(shí)間單位時(shí)的情形：走ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn)A，而走ACD的螞蟻剛好走到D點(diǎn)。第61頁(yè)/共73頁(yè)第六十一頁(yè)，共74頁(yè)。6.4

蟻群算法簡(jiǎn)單的螞蟻尋食過(guò)程：

◆假設(shè)螞蟻每經(jīng)過(guò)一處所留下的信息素為一個(gè)單位，則經(jīng)過(guò)36個(gè)時(shí)間單位后，所有開(kāi)始一起出發(fā)的螞蟻都經(jīng)過(guò)不同路徑從D點(diǎn)取得了食物，此時(shí)ABD的路線(xiàn)往返了2趟，每一處的信息素為4個(gè)單位，而ACD的路線(xiàn)往返了一趟，每一處的信息素為2個(gè)單位，其比值為2：1。

◆尋找食物的過(guò)程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在ABD路線(xiàn)上增派一只螞蟻（共2只），而ACD路線(xiàn)上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線(xiàn)路上的信息素單位積累為12和4，比值為3：1。

◆若按以上規(guī)則繼續(xù)，蟻群在ABD路線(xiàn)上再增派一只螞蟻（共3只），而ACD路線(xiàn)上仍然為一只螞蟻。再經(jīng)過(guò)36個(gè)時(shí)間單位后，兩條線(xiàn)路上的信息素單位積累為24和6，比值為4：1。

◆若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄ACD路線(xiàn)，而都選擇ABD路線(xiàn)。這也就是前面所提到的正反饋效應(yīng)。第62頁(yè)/共73頁(yè)第六十二頁(yè)，共74頁(yè)。6.4

蟻群算法人工蟻群算法：

◆基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問(wèn)題，可以構(gòu)造人工蟻群，來(lái)解決最優(yōu)化問(wèn)題，如TSP問(wèn)題。

◆

人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。

◆兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在TSP問(wèn)題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。第63頁(yè)/共73頁(yè)第六十三頁(yè)，共74頁(yè)。6.4

蟻群算法蟻群算法與TSP問(wèn)題：

TSP問(wèn)題表示為一個(gè)N個(gè)城市的有向圖G=（N,A），其中 城市之間距離目標(biāo)函數(shù)為

其中為城市1,2，…n的一個(gè)排列，且有第64頁(yè)/共73頁(yè)第六十四頁(yè)，共74頁(yè)。6.4

蟻群算法蟻群算法與TSP問(wèn)題：

◆TSP問(wèn)題的人工蟻群算法中，假設(shè)m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問(wèn)題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類(lèi)參數(shù)決定：(1)信息素值，也稱(chēng)信息素痕跡。(2)可見(jiàn)度，即先驗(yàn)值。

◆信息素的更新方式有2種：一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過(guò)程；二是增強(qiáng)，給評(píng)價(jià)值“好”(有螞蟻?zhàn)哌^(guò))的邊增加信息素。第65頁(yè)/共73頁(yè)第六十五頁(yè)，共74頁(yè)。6.4

蟻群算法蟻群算法與TSP問(wèn)題：

◆螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過(guò)一個(gè)隨機(jī)原則來(lái)實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲(chǔ)的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，逐此往復(fù)，越來(lái)越接近最優(yōu)解。

◆螞蟻在尋找過(guò)程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。第66頁(yè)/共73頁(yè)第六十六頁(yè)，共74頁(yè)。6.4

蟻群算法蟻群算法步驟：

STEP0

對(duì)n個(gè)城市的TSP問(wèn)題，城市間的距離矩陣為