第三章求解優(yōu)化問題的智能算法

第三章求解優(yōu)化問題的智能算法9/10/20231第1頁，課件共209頁，創(chuàng)作于2023年2月3.1概述9/10/20232第2頁，課件共209頁，創(chuàng)作于2023年2月最優(yōu)化問題是指在一定的約束條件下，決定某個(gè)或某些可控制的因素應(yīng)有的合理取值，使所選定的目標(biāo)達(dá)到最優(yōu)的問題。解決最優(yōu)化問題的方法稱為最優(yōu)化方法。它具有高度應(yīng)用性和技術(shù)性的特點(diǎn)。最優(yōu)化問題可以追溯到十分古老的極值問題，在17世紀(jì)，偉大科學(xué)家Newton發(fā)明微積分的時(shí)候，已經(jīng)提出了極值問題，后來又出現(xiàn)了Lagrange乘子法，Cauchy則利用最速下降法求解無約束極小化問題。然而，直到1947年Dantzig提出求解一般線性規(guī)劃問題的單純形法之后，它才成為一門獨(dú)立的學(xué)科。3.1概述——最優(yōu)化方法的研究起源和意義

1/29/10/20233第3頁，課件共209頁，創(chuàng)作于2023年2月隨著近代科學(xué)技術(shù)發(fā)展的需要，特別是由于計(jì)算機(jī)技術(shù)的飛速發(fā)展，促進(jìn)了最優(yōu)化方法的迅速發(fā)展，并很快滲透到各個(gè)領(lǐng)域。20世紀(jì)70年代，最優(yōu)化方法這門應(yīng)用技術(shù)科學(xué)又開始產(chǎn)生出最優(yōu)設(shè)計(jì)、最優(yōu)控制與最優(yōu)管理等分支。到20世紀(jì)80年代，最優(yōu)化技術(shù)又在這些分支中發(fā)展出了新的更細(xì)的分支，比如，工程技術(shù)領(lǐng)域的機(jī)械優(yōu)化設(shè)計(jì)、建筑結(jié)構(gòu)優(yōu)化設(shè)計(jì)以及化工石油領(lǐng)域的優(yōu)化設(shè)計(jì)等。3.1概述——最優(yōu)化方法的研究起源和意義

2/29/10/20234第4頁，課件共209頁，創(chuàng)作于2023年2月求解優(yōu)化問題的步驟(1)分析待優(yōu)化的問題，建立問題的數(shù)學(xué)模型；(2)分析數(shù)學(xué)模型，選擇合適的最優(yōu)化算法；(3)編寫計(jì)算機(jī)程序、上機(jī)計(jì)算、求出最優(yōu)解；(4)結(jié)果檢驗(yàn)與最后決策。9/10/20235第5頁，課件共209頁，創(chuàng)作于2023年2月轉(zhuǎn)化為最小化問題。3.1概述——最優(yōu)化問題的數(shù)學(xué)描述9/10/20236第6頁，課件共209頁，創(chuàng)作于2023年2月(1)枚舉法。枚舉出可行解集合內(nèi)的所有可行解，以求出精確最優(yōu)解。對于連續(xù)函數(shù)，該方法要求先對其進(jìn)行離散化處理，這樣就有可能產(chǎn)生離散誤差而永遠(yuǎn)達(dá)不到最優(yōu)解。另外，當(dāng)枚舉空間比較大時(shí)，該方法的求解效率比較低，有時(shí)甚至在目前最先進(jìn)的計(jì)算工具上都無法求解。(2)啟發(fā)式算法。尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，以找到一個(gè)最優(yōu)解或近似最優(yōu)解。該方法的求解效率雖然比較高，但對每一個(gè)需要求解的問題都必須找出其特有的啟發(fā)式規(guī)則，這個(gè)啟發(fā)式規(guī)則無通用性，不適合于其他問題。3.1概述——求最優(yōu)解或近似最優(yōu)解的方法1/29/10/20237第7頁，課件共209頁，創(chuàng)作于2023年2月(3)搜索算法。尋求一種搜索算法，該算法在可行解集合的一個(gè)子集內(nèi)進(jìn)行搜索操作，以找到問題的最優(yōu)解或近似最優(yōu)解。該方法雖然保證不了一定能夠得到問題的最優(yōu)解，但若適當(dāng)?shù)乩靡恍﹩l(fā)知識，就可在近似解的質(zhì)量和求解效率上達(dá)到—種較好的平衡。3.1概述——求最優(yōu)解或近似最優(yōu)解的方法2/29/10/20238第8頁，課件共209頁，創(chuàng)作于2023年2月以最速下降法、牛頓法和共扼方向法等為代表的傳統(tǒng)優(yōu)化算法具有完善的數(shù)學(xué)基礎(chǔ)，具有計(jì)算效率高、可靠性強(qiáng)和比較成熟等特點(diǎn)。這些算法的基本迭代步驟如下：3.1概述——求解最優(yōu)化問題的傳統(tǒng)方法9/10/20239第9頁，課件共209頁，創(chuàng)作于2023年2月3.1概述——求解最優(yōu)化問題的傳統(tǒng)方法——最速下降法9/10/202310第10頁，課件共209頁，創(chuàng)作于2023年2月3.1概述——求解最優(yōu)化問題的傳統(tǒng)方法——牛頓法9/10/202311第11頁，課件共209頁，創(chuàng)作于2023年2月3.1概述——求解最優(yōu)化問題的傳統(tǒng)方法——共軛方向法9/10/202312第12頁，課件共209頁，創(chuàng)作于2023年2月對目標(biāo)函數(shù)和約束函數(shù)表達(dá)的要求必須更為寬松計(jì)算的效率比理論上的最優(yōu)性更重要算法隨時(shí)終止能夠隨時(shí)得到較好的解對優(yōu)化模型中數(shù)據(jù)的質(zhì)量要求更為寬松實(shí)際生活中對最優(yōu)化方法性能的需求促進(jìn)了最優(yōu)化方法的發(fā)展，最優(yōu)化逐步走出“象牙塔”，面向?qū)嶋H需要，完成了從“方法定向”到“問題定向”的轉(zhuǎn)換。3.1概述——對最優(yōu)化提出的新的需求9/10/202313第13頁，課件共209頁，創(chuàng)作于2023年2月1975年，Holland提出遺傳算法(GeneticAlgorithm)。這種優(yōu)化方法模仿生物種群中優(yōu)勝劣汰的選擇機(jī)制，通過種群中優(yōu)勢個(gè)體的繁衍進(jìn)化來實(shí)現(xiàn)優(yōu)化的功能。1977年，Glover提出禁忌搜索(TabuSearch)算法。這種方法將記憶功能引入到最優(yōu)解的搜索過程中，通過設(shè)置禁忌區(qū)阻止搜索過程中的重復(fù)，從而大大提高了尋優(yōu)過程的搜索效率。1983年，Kirkpatrick提出了模擬退火(SimulatedAnnealing)算法。這種算法模擬熱力學(xué)中退火過程能使金屬原子達(dá)到能量最低狀態(tài)的機(jī)制，通過模擬的降溫過程，按玻茲曼(Boltzmann)方程計(jì)算狀態(tài)間的轉(zhuǎn)移概率來引導(dǎo)搜索，從而使算法具有很好的全局搜索能力。3.1概述——新的優(yōu)化方法不斷出現(xiàn)1/29/10/202314第14頁，課件共209頁，創(chuàng)作于2023年2月20世紀(jì)90年代初，Dorigo等提出蟻群優(yōu)化算法(AntColonyOptimization)算法。這種算法借鑒蟻群群體利用信息素相互傳遞信息來實(shí)現(xiàn)路徑優(yōu)化的機(jī)理，通過記憶路徑信息素的變化來解決組合優(yōu)化問題。1995年，Kenedy和Eberhart提出粒子群優(yōu)化(ParticleSwarmOptimization)算法。這種方法模仿鳥類和魚類群體覓食遷移中，個(gè)體與群體協(xié)調(diào)一致的機(jī)理，通過群體最優(yōu)方向、個(gè)體最優(yōu)方向和慣性方向的協(xié)調(diào)來求解實(shí)數(shù)優(yōu)化問題。1999年，Linhares提出了捕食搜索(PredatorySearch)算法。這種算法模擬猛獸捕食中大范圍搜尋和局部蹲守的特點(diǎn)，通過設(shè)置全局搜索和局部搜索間變換的閾值來協(xié)調(diào)兩種不同的搜索模式，從而實(shí)現(xiàn)了對全局搜索能力和局部搜索能力的兼顧。3.1概述——新的優(yōu)化方法不斷出現(xiàn)2/29/10/202315第15頁，課件共209頁，創(chuàng)作于2023年2月不以達(dá)到某個(gè)最優(yōu)性條件或找到理論上的精確最優(yōu)解為目標(biāo)，而是更看重計(jì)算的速度和效率；對目標(biāo)函數(shù)和約束函數(shù)的要求十分寬松；算法的基本思想都是來自對某種自然規(guī)律的模仿，具有人工智能的特點(diǎn)；多數(shù)算法含有一個(gè)多個(gè)體的群體，尋優(yōu)過程實(shí)際上就是種群的進(jìn)化過程；理論工作相對比較薄弱，一般說來都不能保證收斂到最優(yōu)解。3.1概述——新的算法的一些共同特點(diǎn)9/10/202316第16頁，課件共209頁，創(chuàng)作于2023年2月由于算法理論薄弱，最早被稱為“現(xiàn)代啟發(fā)式(ModernHeuristics)”或“高級啟發(fā)式(AdvancedHeuristics)”；從其人工智能的特點(diǎn)，被稱為“智能計(jì)算(IntelligentComputation)”或“智能優(yōu)化算法(IntelligentOptimizationAlgorithms)”；從不以精確解為目標(biāo)的特點(diǎn)，又被歸到“軟計(jì)算(SoftComputing)”方法中；從種群進(jìn)化的特點(diǎn)看，它們又可以稱為“進(jìn)化計(jì)算(EvolutionaryCompuation)”；從模仿自然規(guī)律的特點(diǎn)出發(fā)，又有人將它們稱為“自然計(jì)算(NaturalComputing)”。3.1概述——新的優(yōu)化方法的不同名稱9/10/202317第17頁，課件共209頁，創(chuàng)作于2023年2月應(yīng)用智能優(yōu)化算法解決各類問題是重點(diǎn)；算法改進(jìn)有很大的創(chuàng)新空間；多種算法結(jié)合的混合算法是一條捷徑；不提倡刻意去追求理論成果；算法性能的測算是一項(xiàng)要下真功夫的工作；選擇測試?yán)}的一般規(guī)律：網(wǎng)上題庫中的例題→文獻(xiàn)中的例題→隨機(jī)產(chǎn)生的例題→實(shí)際應(yīng)用問題→自己編的例題；算法性能測試的主要指標(biāo)：達(dá)優(yōu)率(解的目標(biāo)平均值和最優(yōu)解的目標(biāo)值的比，所有解的目標(biāo)值的標(biāo)準(zhǔn)差等)，計(jì)算速度，計(jì)算大規(guī)模問題的能力；創(chuàng)造出新算法3.1概述——怎樣學(xué)習(xí)研究智能優(yōu)化方法9/10/202318第18頁，課件共209頁，創(chuàng)作于2023年2月3.2遺傳算法9/10/202319第19頁，課件共209頁，創(chuàng)作于2023年2月生物在自然界中的生存繁衍，顯示出了其對自然環(huán)境的優(yōu)異自適應(yīng)能力。受其啟發(fā)，人們致力于對生物各種生存特性的機(jī)理研究和行為模擬，為人工自適應(yīng)系統(tǒng)的設(shè)計(jì)和開發(fā)提供了廣闊的前景。遺傳算法(GeneticAlgorithm，簡稱GA)就是這種生物行為的計(jì)算機(jī)模擬中令人矚目的重要成果?；趯ι镞z傳和進(jìn)化過程的計(jì)算機(jī)模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應(yīng)能力和優(yōu)化能力。遺傳算法所借鑒的生物學(xué)基礎(chǔ)就是生物的遺傳和進(jìn)化。3.2遺傳算法——概要9/10/202320第20頁，課件共209頁，創(chuàng)作于2023年2月雖然人們還未完全揭開遺傳與進(jìn)化的奧秘，既沒有完全掌握其機(jī)制，也不完全清楚染色體編碼和譯碼過程的細(xì)節(jié)，更不完全了解其控制方式，但遺傳與進(jìn)化的以下幾個(gè)特點(diǎn)卻為人們所共識：(1)生物的所有遺傳信息都包含在其染色休中，染色體決定了生物的性狀。(2)染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進(jìn)化過程發(fā)生在染色體上。(3)生物的繁殖過程是由其基因的復(fù)制過程來完成的：(4)通過同源染色體之間的交叉或染色體的變異會(huì)產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。(5)對環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的機(jī)會(huì)遺傳到下一代。3.2遺傳算法——概要9/10/202321第21頁，課件共209頁，創(chuàng)作于2023年2月遺傳算法是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早由美國密執(zhí)安大學(xué)的Holland教授提出，起源于60年代對自然和人工自適應(yīng)系統(tǒng)的研究。70年代DeJong基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)。在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架。3.2遺傳算法——概要9/10/202322第22頁，課件共209頁，創(chuàng)作于2023年2月式中，為決策變量，f(X)為目標(biāo)函數(shù)，后兩個(gè)式子為約束條件，U是基本空間，R是U的一個(gè)子集。對于一個(gè)求函數(shù)最大值的優(yōu)化問題(求函數(shù)最小值也類同)，一般可描述為下述數(shù)學(xué)規(guī)劃模型：滿足約束條件的解X稱為可行解，集合R表示由所有滿足約束條件的解所組成的一個(gè)集合，叫做可行解集合。它們之間的關(guān)系如圖所示。3.2遺傳算法——概要9/10/202323第23頁，課件共209頁，創(chuàng)作于2023年2月U基本空間R可行解集合X可行解3.2遺傳算法——概要9/10/202324第24頁，課件共209頁，創(chuàng)作于2023年2月對于上述最優(yōu)化問題，目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的；有的是連續(xù)的，有的是離散的；有的是單峰值的，有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實(shí)，因而求出其近似最優(yōu)解或滿意解是人們的主要著眼點(diǎn)之一。3.2遺傳算法——概要9/10/202325第25頁，課件共209頁，創(chuàng)作于2023年2月遺傳算法中，將n維決策向量用n個(gè)記號xi(n=l，2，

，n)所組成的符號串X來表示：把每一個(gè)xi看作一個(gè)遺傳基因，它的所有可能取值稱為等位基因，這樣，X就可看做是由n個(gè)遺傳基因所組成的一個(gè)染色體。

—般情況下，染色體的長度n是固定的，但對一些問題n也可以是變化的。根據(jù)不同的情況，這里的等位基因可以是一組整數(shù)，也可以是某一范圍內(nèi)的實(shí)數(shù)值，或者是純粹的一個(gè)記號。最簡單的等位基因是由0和1這兩個(gè)整數(shù)組成的。相應(yīng)的染色體就可表示為一個(gè)二進(jìn)制符號串。3.2遺傳算法——概要9/10/202326第26頁，課件共209頁，創(chuàng)作于2023年2月這種編碼所形成的排列形式X是個(gè)體的基因型，與它對應(yīng)的X值是個(gè)體的表現(xiàn)型。通常個(gè)體的表現(xiàn)型和其基因型是一一對應(yīng)的，但有時(shí)也允許基因型和表現(xiàn)型是多對一的關(guān)系。染色休X也稱為個(gè)體X。對于每一個(gè)個(gè)體X，要按照一定的規(guī)則確定出其適應(yīng)度；個(gè)體的適應(yīng)度與其對應(yīng)的個(gè)體表現(xiàn)型X的目標(biāo)函數(shù)值相關(guān)聯(lián)，X越接近于目標(biāo)函數(shù)的最優(yōu)點(diǎn)，其適應(yīng)度越大；反之，其適應(yīng)度越小。遺傳算法中，決策變量X組成了問題的解空間。對問題最優(yōu)解的搜索是通過對染色體X的搜索過程來進(jìn)行的，從而由所有的染色體X就組成了問題的搜索空間。通過編碼和解碼，使得問題的解空間和搜索空間一一對應(yīng)。3.2遺傳算法——概要9/10/202327第27頁，課件共209頁，創(chuàng)作于2023年2月生物的進(jìn)化是以集團(tuán)為主體的。與此相對應(yīng)，遺傳算法的運(yùn)算對象是出M個(gè)個(gè)體所組成的集合，稱為群體。與生物一代一代的自然進(jìn)化過程相類似，遺傳算法的運(yùn)算過程也是一個(gè)反復(fù)迭代的過程，第t代群體記做P(t)，經(jīng)過一代遺傳和進(jìn)化后，得到第t+l代群體，它們也是由多個(gè)個(gè)體組成的集合，記做P(t+1)。這個(gè)群體不斷地經(jīng)過遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體更多地遺傳到下一代，這樣最終在群體中將會(huì)得到一個(gè)優(yōu)良的個(gè)體X，它所對應(yīng)的表現(xiàn)型X將達(dá)到或接近于問題的最優(yōu)解X*。生物的進(jìn)化過程主要是通過染色體之間的交叉和染色體的變異來完成的，與此相對應(yīng)，遺傳算法中最優(yōu)解的搜索過程也模仿生物的這個(gè)進(jìn)化過程，使用所謂的遺傳算子(geneticoperators)作用于群體P(t)中，進(jìn)行下述遺傳操作，從而得到新一代群體P(t+1)。3.2遺傳算法——概要9/10/202328第28頁，課件共209頁，創(chuàng)作于2023年2月選擇(selection)：根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中。交叉(crossover)：將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對，對每對個(gè)體，以某個(gè)概率(稱為交叉概率，crossoverrate)交換它們之間的部分染色體。變異(mutation)：對群體P(t)中的每一個(gè)個(gè)體，以某一概率(稱為變異概率，mutationrate)改變某一個(gè)或某一些基因座上的基因值為其他的等位基因。3.2遺傳算法——概要9/10/202329第29頁，課件共209頁，創(chuàng)作于2023年2月使用上述三種遺傳算子(選擇算子、交叉算子、變異算子)的遺傳算法的主要運(yùn)算過程如下所述：步驟一：初始化。設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t

0；設(shè)置最大進(jìn)化代數(shù)T；隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)。步驟二：個(gè)體評價(jià)。計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。步驟三：選擇運(yùn)算。將選擇算子作用于群體。3.2遺傳算法——運(yùn)算過程9/10/202330第30頁，課件共209頁，創(chuàng)作于2023年2月步驟四：交叉運(yùn)算。將交叉算子作用于群體。步驟五：變異運(yùn)算。將變異算于作用于群體。群體P(t)經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體P(t+1)。步驟六：終止條件判斷。若t

T，則：t

t+1，轉(zhuǎn)到步驟二。若t＞T，則以進(jìn)化過程中所得到的具有最大適應(yīng)度的個(gè)體作為最優(yōu)解輸出，終止計(jì)算。3.2遺傳算法——運(yùn)算過程9/10/202331第31頁，課件共209頁，創(chuàng)作于2023年2月基于對自然界中生物遺傳與進(jìn)化機(jī)理的模仿，針對不向的問題，很多學(xué)者設(shè)計(jì)了許多不同的編碼方法來表示問題的可行解，開發(fā)出了許多種不同的遺傳算子來模仿不同環(huán)境下的生物遺傳特。這樣，由不同的編碼方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點(diǎn)，即通過對生物遺傳和進(jìn)化過程中選擇、交叉、變異機(jī)理的模仿，來完成對問題最優(yōu)解的自適應(yīng)搜索過程。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)9/10/202332第32頁，課件共209頁，創(chuàng)作于2023年2月基于這個(gè)共同特點(diǎn)，Goldberg總結(jié)出了一種統(tǒng)一的最基本的遺傳算法——基本遺傳算法(SimpleGeneticAlgorithms，簡稱SGA)?；具z傳算法使用固定長度的二進(jìn)制符號串來表示群體中的個(gè)體，其等位基因是由二值符號集{0，1}所組成的。初始群體中各個(gè)個(gè)體的基因值可用均勻分布的隨機(jī)數(shù)來生成?；具z傳算法使用比例選擇算子、單點(diǎn)交叉算子和基本位變異算子這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)9/10/202333第33頁，課件共209頁，創(chuàng)作于2023年2月用二進(jìn)制編碼來離散自變量，碼長根據(jù)離散精度來確定。例如當(dāng)自變量a的變化區(qū)間為[amin，amax]

，當(dāng)離散精度為

時(shí)，碼長m的計(jì)算公式為：相應(yīng)的解碼公式為：3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)——編碼和解碼9/10/202334第34頁，課件共209頁，創(chuàng)作于2023年2月在遺傳算法中，以個(gè)體適應(yīng)度的大小來確定該個(gè)體被遺傳到下一代群體中的概率。個(gè)體的適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體的適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小?；具z傳算法使用比例選擇算子來確定群體中各個(gè)個(gè)體遺傳到下一代群體中的數(shù)量。為正確計(jì)算不同情況下各個(gè)個(gè)體的遺傳概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—適應(yīng)度評價(jià)1/49/10/202335第35頁，課件共209頁，創(chuàng)作于2023年2月對于求目標(biāo)函數(shù)最小值的優(yōu)化問題，理論上只需簡單地對其增加一個(gè)負(fù)號就可將其轉(zhuǎn)化為求目標(biāo)函數(shù)最大值的優(yōu)化問題，即：

minf(X)＝max(－f(X))當(dāng)優(yōu)化目標(biāo)是求函數(shù)最大值，并且目標(biāo)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度F(x)就等于相應(yīng)的目標(biāo)函數(shù)值f(X)，即：F(X)＝f(X)但實(shí)際優(yōu)化問題中的目標(biāo)函數(shù)值有正也有負(fù)，優(yōu)化目標(biāo)有求函數(shù)最大值，也有求函數(shù)最小值。上面兩式保證不了所有情況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)要求。所以必須尋求出一種通用且有效的由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換關(guān)系，由它來保證個(gè)體適應(yīng)度總?cè)》秦?fù)值。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—適應(yīng)度評價(jià)2/49/10/202336第36頁，課件共209頁，創(chuàng)作于2023年2月為滿足適應(yīng)度取非負(fù)值的要求，基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)值f(X)變換為個(gè)體的適應(yīng)度F(x)。式中，Cmin為一個(gè)適當(dāng)?shù)叵鄬Ρ容^小的數(shù)，它可以用下面幾種方法之一來選擇：

方法一：對于求目標(biāo)函數(shù)最大值的優(yōu)化問題，變換方法為：預(yù)先指定的一個(gè)較小的數(shù)。進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—適應(yīng)度評價(jià)3/49/10/202337第37頁，課件共209頁，創(chuàng)作于2023年2月方法二：對于求目標(biāo)函數(shù)最小值的優(yōu)化問題，變換方法為：

式中，Cmax為一個(gè)適當(dāng)?shù)叵鄬Ρ容^大的數(shù)，它可以用下面幾種方法之一來選擇：預(yù)先指定的一個(gè)較大的數(shù)。進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。前代或最近幾代群體中的最大目標(biāo)函數(shù)值。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—適應(yīng)度評價(jià)4/49/10/202338第38頁，課件共209頁，創(chuàng)作于2023年2月選擇算子或復(fù)制算子的作用是從當(dāng)前代群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。最常用和最基本的選擇算子是比例選擇算子。比例選擇實(shí)際上是一種有退還隨機(jī)選擇，也叫做賭盤(Roulettewheel)選擇，因?yàn)檫@種選擇方式與賭博中的賭盤操作原理頗為相似。所謂比例選擇算子，是指個(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子1/49/10/202339第39頁，課件共209頁，創(chuàng)作于2023年2月整個(gè)賭盤被分為大小不同的一些扇面，分別對應(yīng)著價(jià)值各不相同的一些賭博物品。當(dāng)旋轉(zhuǎn)著的賭盤自然停下來時(shí)，其指針?biāo)干让嫔系奈锲肪蜌w賭博者所有。雖然賭盤的指針具體停止在哪一個(gè)扇面是無法預(yù)測的，但指針指向各個(gè)扇面的概率卻是可以估計(jì)的，它與各個(gè)扇面的圓心角大小成正比：圓心角越大，停在該扇面的可能性也越大；圓心角越小，停在該扇面的可能性也越小。與此類似，在遺傳算法中，整個(gè)群體被各個(gè)個(gè)體所分割，各個(gè)個(gè)體的適應(yīng)度在全部個(gè)體的適應(yīng)度之和中所占比例也大小不一，這個(gè)比例值瓜分了整個(gè)賭盤盤面，它們也決定了各個(gè)個(gè)體被遺傳到下一代群體中的概率。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子2/49/10/202340第40頁，課件共209頁，創(chuàng)作于2023年2月金銀銅鐵10％20％30％40％3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子3/49/10/202341第41頁，課件共209頁，創(chuàng)作于2023年2月令：3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子4/49/10/202342第42頁，課件共209頁，創(chuàng)作于2023年2月算子的具體執(zhí)行過程如下：(1)對群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對。若群體的大小為M，則共有[M/2]對相互配對的個(gè)體組。其中[x]表示不大于x的最大整數(shù)。(2)對每一對相互配對的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。若染色體的長度為n，則共有(n-1)個(gè)可能的交叉點(diǎn)位置。(3)對每一對相互配對的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—單點(diǎn)交叉算子1/29/10/202343第43頁，課件共209頁，創(chuàng)作于2023年2月單點(diǎn)交叉示意如下所示：

A：1011011100A’：1011011111B：0001110011B’；0001110000單點(diǎn)交叉交叉點(diǎn)3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—單點(diǎn)交叉算子2/29/10/202344第44頁，課件共209頁，創(chuàng)作于2023年2月對于基本遺傳算法中用二進(jìn)制編碼符號串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將該基因值變?yōu)?；反之，若原有基因值為l，則變異操作將其變?yōu)?。A：10l0101010A’：10l0001010基本位變異

變異點(diǎn)

(1)對個(gè)體的每一個(gè)基因座，依變異概率pm指定其為變異點(diǎn)。(2)對每一個(gè)指定的變異點(diǎn)，對其基因值做取反運(yùn)算或用其它等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—基本位變異算子9/10/202345第45頁，課件共209頁，創(chuàng)作于2023年2月基本遺傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20

1000T：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為100

500Pc：交叉概率，—般取為0.4

0.99。Pm：變異概率，一般取為0.0001

0.1這4個(gè)運(yùn)行參數(shù)對遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。3.2遺傳算法——遺傳算法的運(yùn)行參數(shù)

1/29/10/202346第46頁，課件共209頁，創(chuàng)作于2023年2月在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。一般來說，選擇較大數(shù)目的初始種群可以同時(shí)處理更多的解，因而容易找到全局的最優(yōu)解，其缺點(diǎn)使增加了每次迭代所需要的時(shí)間。交叉概率的選擇決定了交叉操作的頻率。頻率越高，可以越快收斂到最有希望的最優(yōu)解區(qū)域；但是太高的頻率也可能導(dǎo)致收斂于一個(gè)解。變異概率通常只取較小的數(shù)值。若選取高的變異率，一方面可以增加樣本的多樣性，另一方面可能引起不穩(wěn)定。但是若選取太小的變異概率，則可能難于找到全局的最優(yōu)解。3.2遺傳算法——遺傳算法的運(yùn)行參數(shù)

2/29/10/202347第47頁，課件共209頁，創(chuàng)作于2023年2月該函數(shù)有兩個(gè)局部極大值，分別是f(2.048,-2.048)=3905.7324和f(-2.048,-2.048)=3905.9262，其中后者為全局最大值。首先確定決策變量和約束條件，確定優(yōu)化模型例：Rosenbrock函數(shù)的全局最大值計(jì)算。3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定優(yōu)化模型9/10/202348第48頁，課件共209頁，創(chuàng)作于2023年2月用長度為l0位的二進(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)到1111111111(1023)之間的二進(jìn)制編碼。再將分別表示x1，x2的二個(gè)10位長的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問題的染色體編碼方法。例如X：000011011l1101110001就表示一個(gè)個(gè)體的基因型，其中前10位表示x1，后10為表示x2。3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定編碼方法9/10/202349第49頁，課件共209頁，創(chuàng)作于2023年2月解碼時(shí)需先將20位長的二進(jìn)制編碼串切斷為二個(gè)10位長的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。例如，對于前述個(gè)體X：000011011l1101110001它由這樣的兩個(gè)代碼所組成：y1＝55y2＝881經(jīng)解碼處理后，可得到：x1=－1.828x2=1.476依據(jù)前述個(gè)體編碼方法和對定義域的離散化方法可知，將代碼yi轉(zhuǎn)換為變量xi的解碼公式為：3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定解碼方法9/10/202350第50頁，課件共209頁，創(chuàng)作于2023年2月第六步：設(shè)計(jì)遺傳算子。可知，Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故這里可將個(gè)體的適應(yīng)度直接取為對應(yīng)的目標(biāo)函數(shù)值，即有：F(X)=f(x1，x2)選擇運(yùn)算使用比例選擇算子；交叉運(yùn)算使用單點(diǎn)交叉算子；變異運(yùn)算使用基本位變異算子。3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定個(gè)體評價(jià)方法9/10/202351第51頁，課件共209頁，創(chuàng)作于2023年2月對于本例，設(shè)定基本遺傳算法的運(yùn)行參數(shù)如下：群體大?。篗＝80終止代數(shù)：T＝200交叉概率：pc＝0.6變異概率：pm＝0.001通過上述七個(gè)步驟就可構(gòu)成用于Rosenbrock函數(shù)優(yōu)化計(jì)算的基本遺傳算法。3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定運(yùn)行參數(shù)9/10/202352第52頁，課件共209頁，創(chuàng)作于2023年2月myGA.mfunction[xv,fv]=myGA(fitness,a,b,NP,NG,Pc,Pm,eps)functionresult=Initial(length)functiony=Dec(a,b,x,L)myGA2.m3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—程序9/10/202353第53頁，課件共209頁，創(chuàng)作于2023年2月傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身來進(jìn)行優(yōu)化計(jì)算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運(yùn)算對象。這種對決策變量的編碼處理方式，使得我們在優(yōu)化計(jì)算過程中可以借鑒生物學(xué)中染色體和基因等概念，可以模仿自然界中生物的遺傳和進(jìn)化等機(jī)理，也使得我們可以方便地應(yīng)用遺傳操作算子。特別是對一些無數(shù)值概念或很難有數(shù)值概念，而只有代碼概念的優(yōu)化問題，編碼處理方式更顯示出了其獨(dú)持的優(yōu)越性。3.2遺傳算法——特點(diǎn)—以決策變量的編碼作為運(yùn)算對象9/10/202354第54頁，課件共209頁，創(chuàng)作于2023年2月傳統(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ù)值等其他一些輔助信息。這個(gè)特性對很多目標(biāo)函數(shù)無法或是很難求導(dǎo)數(shù)的函數(shù)，或?qū)?shù)不存在的函數(shù)的優(yōu)化問題，以及組合優(yōu)化問題等，應(yīng)用遺傳算法時(shí)就顯得比較方便，因?yàn)樗荛_了函數(shù)求導(dǎo)這個(gè)障礙。再者，直接利用目標(biāo)函數(shù)值或個(gè)體適應(yīng)度，也可使得我們可以把搜索范圍集中到適應(yīng)度較高的部分搜索空間中，從而提高了搜索效率。3.2遺傳算法——特點(diǎn)—直接以目標(biāo)函數(shù)值作為搜索信息9/10/202355第55頁，課件共209頁，創(chuàng)作于2023年2月傳統(tǒng)的優(yōu)化算法往往是從解空間個(gè)的一個(gè)初始點(diǎn)開始最優(yōu)解的這代搜索過程，單個(gè)搜索點(diǎn)所提供的搜索信息畢竟不多，所以搜索效率不高，有時(shí)其至使搜索過程陷入局部最優(yōu)解而停滯不前。遺傳算法從很多個(gè)體所組成的一個(gè)初始群體開始最優(yōu)解的搜索過程，而不是從一個(gè)單一的個(gè)體開始搜索。對這個(gè)群體所進(jìn)行的選擇、交叉、變異等運(yùn)算，產(chǎn)生出的乃是新一代的群體，在這之中包括了很多群體信息。這些信息可以避免搜索一些不必搜索的點(diǎn)，所以實(shí)際上相當(dāng)于搜索了更多的點(diǎn)，這是遺傳算法所特有的一種隱含并行性。3.2遺傳算法——特點(diǎn)—同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息9/10/202356第56頁，課件共209頁，創(chuàng)作于2023年2月傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法，一個(gè)搜索點(diǎn)到另一個(gè)搜索點(diǎn)的轉(zhuǎn)移有確定的轉(zhuǎn)移方法和轉(zhuǎn)移關(guān)系，這種確定性往往也有可能使得搜索永遠(yuǎn)達(dá)不到最優(yōu)點(diǎn)，因而也限制了算法的應(yīng)用范圍。遺傳算法屬于一種自適應(yīng)概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了其搜索過程的靈活性。雖然這種概率特性也會(huì)使群體中產(chǎn)生一些適應(yīng)度不高的個(gè)體，但隨著進(jìn)化過程的進(jìn)行，新的群體中總會(huì)更多地產(chǎn)生出許多優(yōu)良的個(gè)體，實(shí)踐和理論都已證明了在一定條件下遺傳算法總是以概率1收斂于問題的最優(yōu)解。當(dāng)然，交叉概率和變異概率等參數(shù)也會(huì)影響算法的搜索效果和搜索效率，所以如何選擇遺傳算法的參數(shù)在其應(yīng)用中是一個(gè)比較重要的問題。而另一方面，與其他一些算法相比遺傳算法的魯棒性又會(huì)使得參數(shù)對其搜索效果的影響會(huì)盡可能地低。3.2遺傳算法——特點(diǎn)—使用概率搜索技術(shù)9/10/202357第57頁，課件共209頁，創(chuàng)作于2023年2月約束優(yōu)化(ConstrainedOptimization)是處理具有等式和(或)不等式約束的目標(biāo)函數(shù)問題，其一般形式可以表示為：可記約束集（可行集）為：用于操作染色體的遺傳算法常會(huì)產(chǎn)生不可行的染色體的問題。3.2遺傳算法——約束的處理1/39/10/202358第58頁，課件共209頁，創(chuàng)作于2023年2月——拒絕策略：拋棄進(jìn)化過程中產(chǎn)生的所有不可行解。這是遺傳算法處理約束問題的最簡單也是效率最低的方法?！迯?fù)策略：在進(jìn)化過程中獲得不可行解后，將其修復(fù)為可行解。對于很多組合優(yōu)化問題創(chuàng)建修復(fù)過程相對容易，但可能導(dǎo)致失去種群的多樣性?！獞土P策略：對約束進(jìn)行處理的最一般的方式，是通過對不可行解的懲罰來將約束問題轉(zhuǎn)化為無約束問題。任何對于約束的違反都要在目標(biāo)函數(shù)中添加懲罰項(xiàng)。需要設(shè)計(jì)合適的懲罰函數(shù)，不合適的懲罰函數(shù)會(huì)掩蓋目標(biāo)函數(shù)的優(yōu)化。3.2遺傳算法——約束的處理2/39/10/202359第59頁，課件共209頁，創(chuàng)作于2023年2月——特殊的編碼和遺傳策略：使用特殊的編碼策略，在編碼時(shí)就充分考慮約束問題，在編碼時(shí)產(chǎn)生的都是符合約束的染色體。為了使染色體在遺傳操作后仍然保持可行性，也有使用特殊的遺傳策略，使遺傳操作后染色體仍然保持可行。3.2遺傳算法——約束的處理3/39/10/202360第60頁，課件共209頁，創(chuàng)作于2023年2月現(xiàn)實(shí)的生產(chǎn)和生活中人們常常遇到存在的目標(biāo)超過一個(gè)，并且需要同時(shí)處理的情況，而這些不同的目標(biāo)又往往是相互沖突的，這就是多目標(biāo)優(yōu)化(MultiobjectiveOptimization)問題。具有p個(gè)目標(biāo)的多目標(biāo)問題的一般形式為：3.2遺傳算法——多目標(biāo)的處理1/49/10/202361第61頁，課件共209頁，創(chuàng)作于2023年2月在大多數(shù)情況下，各個(gè)目標(biāo)函數(shù)間可能是沖突的。這就使得多目標(biāo)優(yōu)化問題不存在唯一的全局最優(yōu)解，使所有目標(biāo)函數(shù)同時(shí)最優(yōu)。但是，可以存在這樣的解：對一個(gè)或幾個(gè)目標(biāo)函數(shù)不可能進(jìn)一步優(yōu)化，而對其他目標(biāo)函數(shù)不至于劣化，這樣的解稱之為非劣最優(yōu)解，也稱有效解，或Pareto最優(yōu)解。遺傳算法種群進(jìn)化特征使其適合于這樣的問題。處理多目標(biāo)問題時(shí)，遺傳算法遇到的一個(gè)主要問題是如何根據(jù)多個(gè)目標(biāo)函數(shù)值來確定個(gè)體的適應(yīng)值，即適應(yīng)值分配機(jī)制。3.2遺傳算法——多目標(biāo)的處理2/49/10/202362第62頁，課件共209頁，創(chuàng)作于2023年2月——向量評價(jià)方法：采用向量形式評價(jià)的適應(yīng)值度量來產(chǎn)生下一代，而不是使用標(biāo)量適應(yīng)值度量方式來評價(jià)染色體。對于有p個(gè)目標(biāo)的給定問題，每代中的選擇過程是一個(gè)循環(huán)，它重復(fù)p次，每次循環(huán)依次使用一個(gè)目標(biāo)，選出下一代中的一部分個(gè)體。——權(quán)重和方法：為每個(gè)目標(biāo)函數(shù)分配權(quán)重并將權(quán)重目標(biāo)組合為單一目標(biāo)函數(shù)。權(quán)重的調(diào)整方法包括：固定權(quán)重方法、隨機(jī)權(quán)重方法、適用性權(quán)重方法。3.2遺傳算法——多目標(biāo)的處理3/49/10/202363第63頁，課件共209頁，創(chuàng)作于2023年2月——基于Pareto的方法：有兩種基于Pareto的方法：Pareto排序和Pareto競爭?！讌f(xié)方法：通過某種距離的度量來確定與理想解最近的解。——目標(biāo)規(guī)劃方法：采用基于排序的適應(yīng)值分配方法來判斷個(gè)體的價(jià)值。具體過程為：根據(jù)第一優(yōu)先目標(biāo)進(jìn)行種群排序，如果某些個(gè)體具有相同的目標(biāo)值，根據(jù)第二優(yōu)先目標(biāo)進(jìn)行排序，如此進(jìn)行下去。如果各個(gè)目標(biāo)上各個(gè)個(gè)體均相同，則隨機(jī)對其進(jìn)行排序。然后采用從最好到最差的指數(shù)插值進(jìn)行個(gè)體的適應(yīng)值分配。3.2遺傳算法——多目標(biāo)的處理4/49/10/202364第64頁，課件共209頁，創(chuàng)作于2023年2月GADS這個(gè)是Matlab7.0版本自帶的工具箱，全名叫GeneticAlgorithmandDirectSearchToolbox。在Matlab7.0的Help里面有對這個(gè)工具箱的詳細(xì)介紹，還有很多例子作演示。它還提供了一個(gè)圖形用戶界面的工具，名為“GeneticAlgorithmTool”，有了這個(gè)工具就可以不必輸入繁瑣的命令行參數(shù)，能方便而且直觀的觀察算法的運(yùn)行過程。在命令行里輸入“gatool”，就可以進(jìn)入該圖形用戶界面。3.2遺傳算法——MATLAB遺傳算法工具箱9/10/202365第65頁，課件共209頁，創(chuàng)作于2023年2月[xfval]=ga(@fitnessfun,nvars,options)Where@fitnessfunisahandletothefitnessfunction.nvarsisthenumberofindependentvariablesforthefitnessfunction.optionsisastructurecontainingoptionsforthegeneticalgorithm.Ifyoudonotpassinthisargument,gausesitsdefaultoptions.Theresultsaregivenby:x—Pointatwhichthefinalvalueisattainedfval—Finalvalueofthefitnessfunction3.2遺傳算法——MATLAB遺傳算法工具箱—命令行函數(shù)9/10/202366第66頁，課件共209頁，創(chuàng)作于2023年2月3.2遺傳算法——MATLAB遺傳算法工具箱—圖形用戶界面9/10/202367第67頁，課件共209頁，創(chuàng)作于2023年2月求下列函數(shù)的最小值：建立適應(yīng)函數(shù)FitFun.m文件：functiony=FitFun(x)y=0.01;fori=1:5y=y+1/(i+(x(i)-1)^2);endy=1/y3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例9/10/202368第68頁，課件共209頁，創(chuàng)作于2023年2月適應(yīng)度函數(shù)的文件名待尋優(yōu)變量的個(gè)數(shù)變量的下邊界和上邊界3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例9/10/202369第69頁，課件共209頁，創(chuàng)作于2023年2月尋優(yōu)結(jié)果優(yōu)化參數(shù)迭代次數(shù)3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例9/10/202370第70頁，課件共209頁，創(chuàng)作于2023年2月該例題的理論最小值為0.436，且在(x1,x2,x3,x4,x5)=(1,1,1,1,1)時(shí)取到。從結(jié)果的比較可以看出，遺傳算法求出的結(jié)果精度是很高的。3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例9/10/202371第71頁，課件共209頁，創(chuàng)作于2023年2月建立適應(yīng)函數(shù)FitFun.m文件：functiony=FitFun(x)y=x(1)^2+2*x(2)^2-4*x(1)-8*x(2)+15;建立非線性約束函數(shù)NonCon.m文件：function[c,ceq]=NonCon(x)c=x(1)^2+x(2)^2-9;ceq=[];3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例9/10/202372第72頁，課件共209頁，創(chuàng)作于2023年2月非線性約束函數(shù)Nonlinearconstraintfunctiondefinesthenonlinearconstraints.Specifythefunctionasananonymousfunctionorasafunctionhandleoftheform@nonlcon,wherenonlcon.misanM-filethatreturnsthevectorscandceq.Thenonlinearequalitiesareoftheformceq=0,andthenonlinearinequalitiesareoftheformc

0.線性等式和不等式約束3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例9/10/202373第73頁，課件共209頁，創(chuàng)作于2023年2月此例題的理論最小值為3，在(x1,x2)=(2,2)時(shí)取得。從結(jié)果可以看出，結(jié)果精度是很高的。3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例9/10/202374第74頁，課件共209頁，創(chuàng)作于2023年2月如果雙親的基因非常相近，所產(chǎn)生的后代相對于雙親也必然比較接近。這樣所期待的性能改善也必然較小。類似于“近親繁殖”。所以基因模式的單一性不僅減慢進(jìn)化歷程，而且可能導(dǎo)致進(jìn)化停滯，過早地收斂于局部的極值解。Srinvivas等提出一種自適應(yīng)遺傳算法，交叉概率和變異概率能夠隨適應(yīng)度自動(dòng)改變。當(dāng)種群各個(gè)個(gè)體適應(yīng)度趨于一致或者趨于局部最優(yōu)時(shí)，使交叉概率和變異概率二者增加，而當(dāng)群體適應(yīng)度比較分散時(shí)，使交叉概率和變異概率減少。同時(shí)，對于適應(yīng)值高于群體平均適應(yīng)值的個(gè)體，對應(yīng)于較低的交叉概率和變異概率，使該個(gè)體得以保護(hù)進(jìn)入下一代；而低于平均適應(yīng)值的個(gè)體，相對于較高的交叉概率和變異概率，使該個(gè)體被淘汰。3.2遺傳算法——改進(jìn)—自適應(yīng)遺傳算法9/10/202375第75頁，課件共209頁，創(chuàng)作于2023年2月因此，自適應(yīng)遺傳算法能夠提供相對某個(gè)解的最佳交叉概率和變異概率。自適應(yīng)遺傳算法中交叉概率和變異概率的計(jì)算公式為：3.2遺傳算法——改進(jìn)—自適應(yīng)遺傳算法9/10/202376第76頁，課件共209頁，創(chuàng)作于2023年2月設(shè)PG為上一代進(jìn)化到下一代時(shí)被替換的個(gè)體的比例，則按此比例，部分個(gè)體被新的個(gè)體所取代，而其他部分的個(gè)體則直接進(jìn)入下一代。PG越大，進(jìn)化得越快，但算法的穩(wěn)定性和收斂性將受到影響；而PG越小，算法的穩(wěn)定性越好，但進(jìn)化速度將變慢?？梢?，應(yīng)該尋求運(yùn)行速度與穩(wěn)定性、收斂性之間的協(xié)調(diào)平衡。3.2遺傳算法——改進(jìn)—部分替代法9/10/202377第77頁，課件共209頁，創(chuàng)作于2023年2月這種方法對于每代中一定數(shù)量的最優(yōu)個(gè)體，使之直接進(jìn)入下一代。這樣可以防止優(yōu)秀個(gè)體由于復(fù)制、交叉或變異中的偶然因素而被破壞掉。這是增強(qiáng)算法穩(wěn)定性和收斂性的有效方法。但同時(shí)也可能使遺傳算法陷入局部的極值范圍。3.2遺傳算法——改進(jìn)—優(yōu)秀個(gè)體保護(hù)法9/10/202378第78頁，課件共209頁，創(chuàng)作于2023年2月該方法將一個(gè)總的群體分為若干個(gè)子群，各子群將具有略微不同的基因模式，它們各自的遺傳過程具有相對的獨(dú)立性和封閉性，因而進(jìn)化的方向也略有差異，從而保證了搜索的充分性及收斂結(jié)果的全局最優(yōu)性。另一方面，在各子群之間又以一定的比例定期地進(jìn)行優(yōu)良個(gè)體的遷移，即每個(gè)子群將其中最優(yōu)的幾個(gè)個(gè)體輪流送到其他子群中。這樣做的目的是期望使各子群能共享優(yōu)良的基因模式以防止某些子群向局部最優(yōu)方向收斂。分布式遺傳算法模擬了生物進(jìn)化過程中的基因隔離和基因遷移，即各子群之間有相關(guān)的封閉性，又有必要的交流和溝通。研究表明，在總的種群個(gè)數(shù)相同的情況下，分布式遺傳算法可以得到比單一種群遺傳算法更好的效果。3.2遺傳算法——改進(jìn)—分布式遺傳算法9/10/202379第79頁，課件共209頁，創(chuàng)作于2023年2月其它改進(jìn)——順序選擇遺傳算法——適應(yīng)值函數(shù)標(biāo)定的遺傳算法——大變異遺傳算法——雙切點(diǎn)交叉遺傳算法——多變異位自適應(yīng)遺傳算法3.2遺傳算法——改進(jìn)9/10/202380第80頁，課件共209頁，創(chuàng)作于2023年2月3.3蟻群算法9/10/202381第81頁，課件共209頁，創(chuàng)作于2023年2月群智能(swarmintelligence,SI)的概念首次由Beni和Wang在研究元胞機(jī)器人系統(tǒng)中提出，由無智能的機(jī)器人組成的系統(tǒng)呈現(xiàn)集體智能行為。但當(dāng)時(shí)他們對于“群體”和“智能”的定義較為特定，即僅針對機(jī)器人系統(tǒng)及它們所具備的智能。之后，機(jī)器人專家研究采用機(jī)器人群體完成特定任務(wù)，但進(jìn)展緩慢。而生物學(xué)家及仿生算法專家等在群智能領(lǐng)域卻取得較大的進(jìn)展，相繼提出了兩類典型的群智能優(yōu)化算法，即Dorig等于1991年提出的蟻群優(yōu)化算法(antcolonyoptimization，ACO)，和Kennedy等于1995年提出的粒子群優(yōu)化算法(particleswarmoptimization，PSO)。3.3蟻群算法——群智能優(yōu)化算法9/10/202382第82頁，課件共209頁，創(chuàng)作于2023年2月1999年，Bonabeau等在著作《SwarmIntelligence:FromNaturaltoArtificialSystems》中對群智能進(jìn)行了詳細(xì)的論述，并定義為：任何一種基于社會(huì)生物群體行為機(jī)制設(shè)計(jì)出的算法或分布式問題求解的策略均屬于群智能。之后，Bonabeau將群智能的定義進(jìn)一步推廣為：無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現(xiàn)出智能行為的特性。2001年，Kennedy等在著作《SwarmIntelligence》中對群智能的理論與方法進(jìn)行了總結(jié)，并介紹了粒子群優(yōu)化算法。他們不反對Bonabeau關(guān)于群智能定義的基本思想，但反對定義中的“主體”一詞，認(rèn)為“主體”所帶有的自治性和特殊性是許多群體的個(gè)體所不具備和擁有的，這將大大限制群智能的定義范圍。他們認(rèn)為暫時(shí)無法給出群智能合適的定義。3.3蟻群算法——群智能優(yōu)化算法9/10/202383第83頁，課件共209頁，創(chuàng)作于2023年2月至目前為止，雖然學(xué)術(shù)界對群智能的定義仍存在爭議，且其理論本身還不成熟，但是群智能具備處理復(fù)雜系統(tǒng)的獨(dú)特優(yōu)勢，吸引了越來越多的專家學(xué)者投身于群智能理論與應(yīng)用的研究。隨著研究的進(jìn)展，對群智能的理解與認(rèn)識亦逐漸深入，應(yīng)用領(lǐng)域不斷拓寬。2003年IEEE第一屆國際群智能研討會(huì)在美國印第安納州首府首次召開，且每年舉辦一次群智能國際研討會(huì)。2007年9月，Dorigo與Birattari在學(xué)術(shù)百科全書網(wǎng)站發(fā)表了一篇“SwarmIntelligence”論文，并對群智能給出了定義：群智能是一門采用分散控制和自組織理論協(xié)調(diào)處理由多個(gè)個(gè)體組成的自然和人工系統(tǒng)的學(xué)科；特別的，群智能學(xué)科主要研究由個(gè)體之間以及個(gè)體與環(huán)境之間的局部相互作用而產(chǎn)生的集體行為。同年，由Springer出版社出版的雜志《SwarmIntelligence》創(chuàng)刊，由Dorigo任主編。3.3蟻群算法——群智能優(yōu)化算法9/10/202384第84頁，課件共209頁，創(chuàng)作于2023年2月研究蟻群的覓食行為后發(fā)現(xiàn)，由僅具備簡單行為的螞蟻組成的群體通過信息素的釋放與跟隨，實(shí)現(xiàn)正反饋和分布式協(xié)作，突現(xiàn)出復(fù)雜的群體智能行為，即蟻群能找到蟻穴與食物源之間的最短路徑。受此啟發(fā)，Dorig等于1991年首次提出了蟻群優(yōu)化算法，此為一種基于種群的元啟發(fā)式(metaheuristics)算法，已廣泛地用于組合優(yōu)化問題的求解，如旅行商問題、順序排列問題、調(diào)度問題、網(wǎng)絡(luò)路由問題、集合覆蓋問題等。3.3蟻群算法——概述9/10/202385第85頁，課件共209頁，創(chuàng)作于2023年2月像螞蟻這類群居昆蟲，雖然沒有視覺，卻能找到由蟻穴到食物源的最短路徑。雖然單只螞蟻的行為極其簡單，但由這樣的單個(gè)簡單個(gè)體所組成的蟻群群體卻表現(xiàn)出極其復(fù)雜的行為，能夠完成復(fù)雜的任務(wù)，不僅如此，螞蟻還能適應(yīng)環(huán)境的變化，如：在螞蟻運(yùn)動(dòng)路線上突然出現(xiàn)障礙物時(shí)，螞蟻能夠很快重新找到最優(yōu)路徑。人們經(jīng)過大量的研究發(fā)現(xiàn)，螞蟻個(gè)體間通過一種稱之為信息素(pheromone)的物質(zhì)進(jìn)行信息傳遞，從而能夠相互協(xié)作，完成復(fù)雜的任務(wù)。螞蟻之所以表現(xiàn)出復(fù)雜有序的行為，個(gè)體之間的信息交流和相互協(xié)作起著重要的作用。3.3蟻群算法——概述——螞蟻覓食的生物學(xué)基礎(chǔ)9/10/202386第86頁，課件共209頁，創(chuàng)作于2023年2月螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下該物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向。螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后者選擇該路徑的概率越大。螞蟻個(gè)體之間就是通過這種信息的交流達(dá)到搜索食物的目的。3.3蟻群算法——概述——螞蟻覓食的生物學(xué)基礎(chǔ)9/10/202387第87頁，課件共209頁，創(chuàng)作于2023年2月食物蟻巢ADBC障礙物1112213.3蟻群算法——概述——蟻群系統(tǒng)示意圖9/10/202388第88頁，課件共209頁，創(chuàng)作于2023年2月假定障礙物的周圍有兩條道路可從螞蟻的巢穴到達(dá)食物源，分別具有長度4和6。螞蟻在單位時(shí)間內(nèi)可移動(dòng)一個(gè)單位長度的距離。開始時(shí)所有道路上都未留有任何信息素。在t=0時(shí)刻，20只螞蟻從巢穴出發(fā)移動(dòng)到A，它們以相同的概率選擇左側(cè)或右側(cè)道路，因此平均有10只螞蟻?zhàn)咦髠?cè)，10只走右側(cè)。t=4時(shí)刻，第一組到達(dá)食物源的螞蟻將折回，此時(shí)第二組的螞蟻到達(dá)CD中點(diǎn)處。t=5時(shí)刻，兩組螞蟻將在D點(diǎn)相遇。此時(shí)BD上的信息素和CD上的相同，因?yàn)楦饔?0只螞蟻選擇了相應(yīng)的道路，從而有5只返回的螞蟻將選擇BD，而另5只將選擇CD，第二組螞蟻繼續(xù)向食物方向移動(dòng)。3.3蟻群算法——概述——蟻群系統(tǒng)示意圖9/10/202389第89頁，課件共209頁，創(chuàng)作于2023年2月t=8時(shí)刻，前5只螞蟻將返回巢穴，此時(shí)在AC中點(diǎn)處、CD中點(diǎn)處以及B點(diǎn)上各有5只螞蟻。t=9時(shí)刻，前5只螞蟻又回到A點(diǎn)，并且再次面對往左還是往右的選擇。這時(shí)，AB上的軌跡數(shù)是20而AC上是15，因此將有較為多數(shù)的螞蟻選擇往左，從而增強(qiáng)了該路線上的信息素。隨著該過程的繼續(xù)，兩條道路上的信息素的差距將越來越大，直至絕大多數(shù)螞蟻都選擇了最短的路線。正是由于一條道路要比另一條道路短，因此，在相同的時(shí)間區(qū)間內(nèi)，短的路線有更多的機(jī)會(huì)被選擇。3.3蟻群算法——蟻群系統(tǒng)示意圖9/10/202390第90頁，課件共209頁，創(chuàng)作于2023年2月螞蟻的集群活動(dòng)：通過一只螞蟻的運(yùn)動(dòng)很難到達(dá)食物源，但整個(gè)蟻群進(jìn)行搜索就完全不同。當(dāng)某些路徑上通過的螞蟻越來越多時(shí)，在路徑上留下的信息素?cái)?shù)量也越來越多，導(dǎo)致信息素強(qiáng)度增大，螞蟻選擇該路徑的概率隨之增加，從而進(jìn)一步增加該路徑的信息素強(qiáng)度。而某些路徑上通過的螞蟻較少時(shí)，路徑上的信息素就會(huì)隨時(shí)間的推移而蒸發(fā)。模擬這種現(xiàn)象即可利用群體智能建立路徑選擇機(jī)制，使蟻群算法的搜索向最優(yōu)解推進(jìn)。蟻群算法所利用的搜索機(jī)制呈現(xiàn)出一種自催化或正反饋的特征，可將蟻群算法模型理解成增強(qiáng)型學(xué)習(xí)系統(tǒng)。3.3蟻群算法——概述9/10/202391第91頁，課件共209頁，創(chuàng)作于2023年2月蟻群算法是一種隨機(jī)搜索算法，與其他模型進(jìn)化算法一樣，通過候選解組成的群體的進(jìn)化來尋求最優(yōu)解。該過程包括兩個(gè)階段：適應(yīng)階段和協(xié)作階段。在適應(yīng)階段，各候選解根據(jù)積累的信息不斷調(diào)整自身結(jié)構(gòu)；在協(xié)作階段，候選解之間通過信息交流，以期產(chǎn)生性能更好的解。作為與遺傳算法同屬一類的通用型隨機(jī)優(yōu)化算法，蟻群算法不需要任何先驗(yàn)知識，最初只是隨機(jī)地選擇搜索路徑，隨著對解空間的“了解”，搜索變得更有規(guī)律，并逐漸逼近直至最終達(dá)到全局最優(yōu)解。3.3蟻群算法——概述9/10/202392第92頁，課件共209頁，創(chuàng)作于2023年2月相同點(diǎn)之一：兩個(gè)群體中都存在個(gè)體相互交流的通信機(jī)制真實(shí)螞蟻在經(jīng)過的路徑上留下信息素，用以影響蟻群中的其他個(gè)體。且信息素隨著時(shí)間推移逐漸揮發(fā)，減小歷史遺留信息對蟻群的影響。同樣，人工螞蟻改變其所經(jīng)過路徑上存儲(chǔ)的數(shù)字化信息素，該信息素記錄了人工螞蟻當(dāng)前解和歷史解的性能狀態(tài)，而且可被后繼人工螞蟻?zhàn)x寫。數(shù)字化的信息素同樣具有揮發(fā)性，它像真實(shí)的信息量揮發(fā)一樣使人工螞蟻逐漸忘卻歷史遺留信息，在選擇路徑時(shí)不局限于以前人工螞蟻所存留的經(jīng)驗(yàn)。3.3蟻群算法——概述——人工螞蟻與真實(shí)螞蟻的異同9/10/202393第93頁，課件共209頁，創(chuàng)作于2023年2月相同點(diǎn)之二：都要完成尋找最短路徑的任務(wù)真實(shí)螞蟻要尋找一條從巢穴到食物源的最短路徑。人工螞蟻要尋找一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)間的最短路徑。兩種螞蟻都只能在相鄰節(jié)點(diǎn)間一步步移動(dòng)，直到遍歷所有節(jié)點(diǎn)。相同點(diǎn)之三：都采用根據(jù)當(dāng)前信息進(jìn)行路徑選擇的隨機(jī)策略真實(shí)螞蟻和人工螞蟻從某一節(jié)點(diǎn)到下一節(jié)點(diǎn)的移動(dòng)都是利用概率選擇策略實(shí)現(xiàn)的。這里的概率選擇策略是基于當(dāng)前信息來預(yù)測未來情況的一種方法。3.3蟻群算法——概述——人工螞蟻與真實(shí)螞蟻的異同9/10/202394第94頁，課件共209頁，創(chuàng)作于2023年2月不同點(diǎn)人工螞蟻具有記憶功能，而真實(shí)螞蟻沒有。人工螞蟻可以記住曾經(jīng)走過的路徑或訪問過的節(jié)點(diǎn)，可提高算法的效率。人工螞蟻選擇路徑時(shí)并不是完全盲目的，受到問題空間特征的啟發(fā)，按一定的算法規(guī)律有意識地尋找最短路徑（如在旅行商問題中，可以預(yù)先知道下一個(gè)目標(biāo)的距離）。人工螞蟻生活在離散時(shí)間的環(huán)境中，即問題的求解規(guī)劃空間是離散的，而真實(shí)螞蟻生活在連續(xù)時(shí)間的環(huán)境中。3.3蟻群算法——概述——人工螞蟻與真實(shí)螞蟻的異同9/10/202395第95頁，課件共209頁，創(chuàng)作于2023年2月旅行商問題即TSP問題(TravelingSalesmanProblem)指給定n座城市和兩兩城市之間的距離，要求確定一條經(jīng)過各個(gè)城市當(dāng)且僅當(dāng)一次的最短路線。其圖論描述為：給定圖G=(V,A)，其中V為頂點(diǎn)集，A為各頂點(diǎn)相互連接組成的邊集，已知各頂點(diǎn)間的連接距離，要求確定一條長度最短的Hamilton回路，即遍歷所有頂點(diǎn)當(dāng)且僅當(dāng)一次的最短回路。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—TSP問題9/10/202396第96頁，課件共209頁，創(chuàng)作于2023年2月（1）它根據(jù)以城市距離和連接邊上的信息素軌跡強(qiáng)度的數(shù)量為變量的概率函數(shù)選擇下一個(gè)城市。（2）規(guī)定螞蟻?zhàn)吆戏肪€，除非周游完成，不允許轉(zhuǎn)到已訪問的城市，由禁忌表控制（設(shè)tabuk表示第k只螞蟻的禁忌表，tabuk(s)表示禁忌表中的第s個(gè)元素。）（3）它完成周游后，螞蟻在它每一條訪問的邊上留下信息素。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—每只螞蟻的特征9/10/202397第97頁，課件共209頁，創(chuàng)作于2023年2月bi(t)(i=1,2,

,n)：在t時(shí)刻城市i的螞蟻數(shù)：全部螞蟻數(shù)dij：兩城市之間的距離

ij

：路徑(i，j)上的能見度，反映城市i到城市j的啟發(fā)程度，先驗(yàn)知識，由要解決的問題給出。TSP問題中一般取=1/dij

ij(t)：t時(shí)刻路徑(i,j)上的信息素軌跡強(qiáng)度初始時(shí)刻，各條路徑上的信息量相等，設(shè)

ij(0)＝C。n：城市數(shù)目3.3蟻群算法——應(yīng)用于TSP問題的基本算法—基本符號9/10/202398第98頁，課件共209頁，創(chuàng)作于2023年2月螞蟻k(k=1,2,

,m)在運(yùn)動(dòng)過程中，根據(jù)各條路徑上積累的信息素軌跡強(qiáng)度和啟發(fā)式信息決定轉(zhuǎn)移方向。表示在t時(shí)刻螞蟻k由位置i轉(zhuǎn)移到位置j的概率，也就是其選擇策略。allowedk={0,1,

,n-1}-tabuk：表示螞蟻k下一步允許選擇的城市。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—基本符號9/10/202399第99頁，課件共209頁，創(chuàng)作于2023年2月tabuk(k=1,2,

,m)：與實(shí)際蟻群不同，人工蟻群系統(tǒng)具有記憶功能，用tabuk記錄螞蟻k當(dāng)前所走過的城市，集合tabuk隨著進(jìn)化過程做動(dòng)態(tài)調(diào)整。當(dāng)所有n座城市都加入到tabuk中時(shí)，螞蟻k便完成了一次循環(huán)，此時(shí)螞蟻k所走過的路徑就是問題的一個(gè)解。之后，禁忌表被清空，該螞蟻又可以自由選擇，開始下一個(gè)循環(huán)。和：表示信息素強(qiáng)度的相對重要性，表示能見度的相對重要性。分別反映了螞蟻在運(yùn)動(dòng)過程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對重要性：3.3蟻群算法——應(yīng)用于TSP問題的基本算法—基本符號9/10/2023100第100頁，課件共209頁，創(chuàng)作于2023年2月為了避免信息素過多而淹沒啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛲瓿蓪λ衝個(gè)城市的遍歷后，要對殘留信息素進(jìn)行更新：：第k只螞蟻在本次循環(huán)中留在路徑ij上的信息量：本次循環(huán)中路徑ij上的信息量增量

：表示軌跡的持久性，(1－

)稱為信息的揮發(fā)系數(shù)，表示信息消逝程度，隨時(shí)間推移，以前留下的信息逐漸消失。通常設(shè)置系數(shù)0<

<1來避免路徑上信息素的無限累加。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—基本符號9/10/2023101第101頁，課件共209頁，創(chuàng)作于2023年2月根據(jù)信息素更新策略的不同，DorigoM提出了三種不同的基本蟻群算法模型，分別稱為蟻周模型、蟻量模型和蟻密模型。三種模型的差別在于求法不同。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—信息素修改ant-cyclealgorithm（蟻環(huán)算法）蟻環(huán)算法（蟻周算法）的特點(diǎn)是行走的路徑越短，對應(yīng)保存的信息素的值就越大。9/10/2023102第102頁，課件共209頁，創(chuàng)作于2023年2月ant-quantityalgorithm（蟻量算法）ant-densityalgorithm（蟻密算法）信息濃度會(huì)因?yàn)槌鞘芯嚯x的減小而增大。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—信息素修改9/10/2023103第103頁，課件共209頁，創(chuàng)作于2023年2月蟻周模型利用整體信息，螞蟻完成一個(gè)循環(huán)后才更新所有路徑上的信息。蟻量和蟻密模型利用局部信息，螞蟻每走一步就要更新路徑上的信息素。蟻周模型在求解TSP問題時(shí)效果較好，應(yīng)用也比較廣泛。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—信息素修改9/10/2023104第104頁，課件共209頁，創(chuàng)作于2023年2月（1）t0（t為迭代步數(shù)或搜索次數(shù)）；參數(shù)初始化。（2）假設(shè)有m只螞蟻在工作，將各螞蟻的初始出發(fā)點(diǎn)置于當(dāng)前解集中；對每只螞蟻k，按概率移至下一個(gè)頂點(diǎn)j；將頂點(diǎn)j置于當(dāng)前解集，直至每只螞蟻完成任務(wù)，完成內(nèi)循環(huán)，即每只螞蟻獨(dú)立完成一個(gè)解。（3）計(jì)算各螞蟻的路徑長度Lk；記錄當(dāng)前最好解。（4）修改信息素。（5）tt+1。（6）若t<預(yù)定的迭代次數(shù)，且無退化行為（即找到的都是相同的解），則轉(zhuǎn)步驟2。（7）輸出目前最好解。3.3蟻群算法——應(yīng)用于TSP問題的基本算法9/10/2023105第105頁，課件共209頁，創(chuàng)作于2023年2月3.3蟻群算法——應(yīng)用于TSP問題的基本算法9/10/2023106第106頁，課件共209頁，創(chuàng)作于2023年2月ACO蟻環(huán)算法偽代碼：begin初始化過程：ncycle=1;bestcycle=1;

ij=0=C;；；；q0;

ij(由某種啟發(fā)式算法確定)；tabuk=while(notterminationcondition){

for(k=1;k<m;k++){將m只螞蟻隨機(jī)放置于初始城市上；}

for(index=0;index<n;index++){

for(k=1;k<m;k++){ 按轉(zhuǎn)移概率確定每只螞蟻要轉(zhuǎn)移的位置；將剛剛選擇的城市j加入到tabuk中；}

}

計(jì)算各螞蟻的路徑長度Lk

確定本次循環(huán)中找到的最佳路徑L=min(Lk),k=1,2,…,m;蟻環(huán)算法信息素更新；ncycle=ncylce+1;}3.3蟻群算法——應(yīng)用于TSP問題的基本算法9/10/2023107第107頁，課件共209頁，創(chuàng)作于2023年2月探索(exploration)和開發(fā)(exploitation)能力的平衡是影響算法性能的一個(gè)重要方面，也是蟻群算法研究的關(guān)鍵問題之一。探索能力是指蟻群算法要在解空間中測試不同區(qū)域以找到一個(gè)局優(yōu)解的能力；開發(fā)能力是指蟻群算法在一個(gè)有希望的區(qū)域內(nèi)進(jìn)行精確搜索的能力。探索和開發(fā)實(shí)際上就是全局搜索能力和局域搜索能力。通過設(shè)定蟻群算法中的各種參數(shù)，實(shí)現(xiàn)探索和開發(fā)能力的平衡。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—參數(shù)選擇9/10/2023108第108頁，課件共209頁，創(chuàng)作于2023年2月螞蟻系統(tǒng)需要確定的參數(shù)有：m，Q、C、

、

、

。由于蟻群算法參數(shù)空間的龐大性能和各參數(shù)之間的關(guān)聯(lián)性，很難確定最優(yōu)組合參數(shù)使蟻群算法求解性能最佳。到目前還沒有研究出螞蟻算法模型的數(shù)學(xué)分析方法使之能夠在每個(gè)情況下都能生成最優(yōu)的參數(shù)設(shè)置，實(shí)際的應(yīng)用中需要逐步試湊得到最優(yōu)參數(shù)組合。目前已經(jīng)公布的蟻群算法參數(shù)設(shè)置都是就特定問題所采用的特定蟻群算法而言，以應(yīng)用最多的蟻周模型為例，其最好的試驗(yàn)結(jié)果為：0

5，0

5，0.1

0.99，10Q100003.3蟻群算法——應(yīng)用于TSP問題的基本算法—參數(shù)選擇9/10/2023109第109頁，課件共209頁，創(chuàng)作于2023年2月（1）信息素和啟發(fā)函數(shù)對蟻群算法性能的影響信息素是表征過去信息的載體，而啟發(fā)函數(shù)則是表示未來信息的載體，它們直接影響到蟻群算法的全局收斂性和求解效率。（2）信息素殘留因子

對蟻群算法性能的影響在0.10.99范圍內(nèi)，

與迭代次數(shù)近似成正比。當(dāng)

很大時(shí)，路徑上的殘留信息占主導(dǎo)地位，信息正反饋?zhàn)饔孟鄬^弱，搜索的隨機(jī)性增強(qiáng)，因而蟻群算法的收斂速度很慢。當(dāng)

較小時(shí)，正反饋?zhàn)饔谜贾鲗?dǎo)地位，搜索的隨機(jī)性減弱，導(dǎo)致收斂速度加快，但易于陷入局部最優(yōu)。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—參數(shù)選擇9/10/2023110第110頁，課件共209頁，創(chuàng)作于2023年2月（3）螞蟻數(shù)目對蟻群算法性能的影響m大，會(huì)提高蟻群算法的全局搜索能力和穩(wěn)定性，但數(shù)量太大會(huì)導(dǎo)致大量曾被搜索過的路徑上的信息量變化趨于平均，信息正反饋?zhàn)饔脺p弱，隨機(jī)性增強(qiáng)，收斂速度減慢。m小，會(huì)使從未被搜索到的解上的信息量減小到接近于0，隨機(jī)性減弱，雖然收斂速度加快，但會(huì)使算法的穩(wěn)定性變差，出現(xiàn)過早停滯現(xiàn)象。（4）信息素強(qiáng)度Q對蟻群算法性能的影響Q為螞蟻循環(huán)一周時(shí)釋放在所經(jīng)路徑上的信息素總量。Q越大，螞蟻在已遍歷路徑上信息素的累積越快，加強(qiáng)螞蟻搜索時(shí)的正反饋性，有助于算法的收斂速度。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—參數(shù)選擇9/10/2023111第111頁，課件共209頁，創(chuàng)作于2023年2月（5）

、

對蟻群算法性能的影響

反映螞蟻在運(yùn)動(dòng)過程中所積累的信息量在指導(dǎo)蟻群搜索中的相對重要程度。

越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機(jī)性減弱；

越小，易使蟻群算法過早陷入局優(yōu)。

反映螞蟻啟發(fā)式信息在指導(dǎo)蟻群搜索中的相對重要程度，這些啟發(fā)式信息表現(xiàn)為尋優(yōu)過程中先驗(yàn)性、確定性因素。

越大，螞蟻在局部點(diǎn)上選擇局部最優(yōu)路徑的可能性越大，雖然加快了收斂速度，但減弱了隨機(jī)性，易于陷入局部最優(yōu)。如果

=0，則是傳統(tǒng)的貪心算法，如果

=0，則是純粹的正反饋的啟發(fā)式算法。3.3蟻群算法——應(yīng)用于TSP問題的基本算法—參數(shù)選擇9/10/2023112第112頁，課件共209頁，創(chuàng)作于2023年2月可以使用以下三步走的原則:2)參數(shù)粗調(diào)