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

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

概述10/27/20232最優(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é)科。最優(yōu)化方法的研究起源和意義1/210/27/20233隨著近代科學(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ì)等。最優(yōu)化方法的研究起源和意義2/210/27/20234求解優(yōu)化問題的步驟(1)分析待優(yōu)化的問題，建立問題的數(shù)學(xué)模型；(2)分析數(shù)學(xué)模型，選擇合適的最優(yōu)化算法；(3)編寫計(jì)算機(jī)程序、上機(jī)計(jì)算、求出最優(yōu)解；(4)結(jié)果檢驗(yàn)與最后決策。10/27/20235最優(yōu)化問題的數(shù)學(xué)描述轉(zhuǎn)化為最小化問題。10/27/20236求解最優(yōu)化問題的傳統(tǒng)方法以最速下降法、牛頓法和共扼方向法等為代表的傳統(tǒng)優(yōu)化算法具有完善的數(shù)學(xué)基礎(chǔ)，具有計(jì)算效率高、可靠性強(qiáng)和比較成熟等特點(diǎn)。這些算法的基本迭代步驟如下：10/27/20237最速下降法10/27/20238牛頓法10/27/20239共軛方向法10/27/202310對(duì)最優(yōu)化提出的新的需求對(duì)目標(biāo)函數(shù)和約束函數(shù)表達(dá)的要求必須更為寬松計(jì)算的效率比理論上的最優(yōu)性更重要算法隨時(shí)終止能夠隨時(shí)得到較好的解對(duì)優(yōu)化模型中數(shù)據(jù)的質(zhì)量要求更為寬松實(shí)際生活中對(duì)最優(yōu)化方法性能的需求促進(jìn)了最優(yōu)化方法的發(fā)展，最優(yōu)化逐步走出“象牙塔”，面向?qū)嶋H需要，完成了從“方法定向”到“問題定向”的轉(zhuǎn)換。10/27/202311新的優(yōu)化方法不斷出現(xiàn)1/21975年，Holland提出遺傳算法(GeneticAlgorithm)。這種優(yōu)化方法模仿生物種群中優(yōu)勝劣汰的選擇機(jī)制，通過種群中優(yōu)勢(shì)個(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)搜索，從而使算法具有很好的全局搜索能力。10/27/202312新的優(yōu)化方法不斷出現(xiàn)1/220世紀(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)了對(duì)全局搜索能力和局部搜索能力的兼顧。10/27/202313新的算法的一些共同特點(diǎn)不以達(dá)到某個(gè)最優(yōu)性條件或找到理論上的精確最優(yōu)解為目標(biāo)，而是更看重計(jì)算的速度和效率；對(duì)目標(biāo)函數(shù)和約束函數(shù)的要求十分寬松；算法的基本思想都是來自對(duì)某種自然規(guī)律的模仿，具有人工智能的特點(diǎn)；多數(shù)算法含有一個(gè)多個(gè)體的群體，尋優(yōu)過程實(shí)際上就是種群的進(jìn)化過程；理論工作相對(duì)比較薄弱，一般說來都不能保證收斂到最優(yōu)解。10/27/202314不同的名稱由于算法理論薄弱，最早被稱為“現(xiàn)代啟發(fā)式(ModernHeuristics)”或“高級(jí)啟發(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)”。10/27/202315怎樣學(xué)習(xí)研究智能優(yōu)化方法應(yīng)用智能優(yōu)化算法解決各類問題是重點(diǎn)；算法改進(jìn)有很大的創(chuàng)新空間；多種算法結(jié)合的混合算法是一條捷徑；不提倡刻意去追求理論成果；算法性能的測(cè)算是一項(xiàng)要下真功夫的工作；選擇測(cè)試?yán)}的一般規(guī)律：網(wǎng)上題庫中的例題→文獻(xiàn)中的例題→隨機(jī)產(chǎn)生的例題→實(shí)際應(yīng)用問題→自己編的例題；算法性能測(cè)試的主要指標(biāo)：達(dá)優(yōu)率(解的目標(biāo)平均值和最優(yōu)解的目標(biāo)值的比，所有解的目標(biāo)值的標(biāo)準(zhǔn)差等)，計(jì)算速度，計(jì)算大規(guī)模問題的能力；創(chuàng)造出新算法10/27/2023163.2

遺傳算法10/27/202317生物在自然界中的生存繁衍，顯示出了其對(duì)自然環(huán)境的優(yōu)異自適應(yīng)能力。受其啟發(fā)，人們致力于對(duì)生物各種生存特性的機(jī)理研究和行為模擬，為人工自適應(yīng)系統(tǒng)的設(shè)計(jì)和開發(fā)提供了廣闊的前景。遺傳算法(GeneticAlgorithm，簡稱GA)就是這種生物行為的計(jì)算機(jī)模擬中令人矚目的重要成果。基于對(duì)生物遺傳和進(jìn)化過程的計(jì)算機(jī)模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應(yīng)能力和優(yōu)化能力。遺傳算法所借鑒的生物學(xué)基礎(chǔ)就是生物的遺傳和進(jìn)化。10/27/202318雖然人們還未完全揭開遺傳與進(jìn)化的奧秘，既沒有完全掌握其機(jī)制，也不完全清楚染色體編碼和譯碼過程的細(xì)節(jié)，更不完全了解其控制方式，但遺傳與進(jìn)化的以下幾個(gè)特點(diǎn)卻為人們所共識(shí)：(1)生物的所有遺傳信息都包含在其染色休中，染色體決定了生物的性狀。(2)染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進(jìn)化過程發(fā)生在染色體上。(3)生物的繁殖過程是由其基因的復(fù)制過程來完成的：(4)通過同源染色體之間的交叉或染色體的變異會(huì)產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。(5)對(duì)環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的機(jī)會(huì)遺傳到下一代。10/27/202319遺傳算法是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早由美國密執(zhí)安大學(xué)的Holland教授提出，起源于60年代對(duì)自然和人工自適應(yīng)系統(tǒng)的研究。70年代DeJong基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)。在一系列研究工作的基礎(chǔ)上，80年代由Goldberg進(jìn)行歸納總結(jié)，形成了遺傳算法的基本框架。10/27/202320一、遺傳算法概要

式中，為決策變量，f(X)為目標(biāo)函數(shù)，后兩個(gè)式子為約束條件，U是基本空間，R是U的一個(gè)子集。對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問題(求函數(shù)最小值也類同)，—般可描述為下述數(shù)學(xué)規(guī)劃模型：滿足約束條件的解X稱為可行解，集合R表示由所有滿足約束條件的解所組成的一個(gè)集合，叫做可行解集合。它們之間的關(guān)系如圖所示。10/27/202321U基本空間R可行解集合X可行解10/27/202322對(duì)于上述最優(yōu)化問題，目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的；有的是連續(xù)的，有的是離散的；有的是單峰值的，有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識(shí)到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實(shí)，因而求出其近似最優(yōu)解或滿意解是人們的主要著眼點(diǎn)之—。10/27/202323求最優(yōu)解或近似最優(yōu)解的方法(1)枚舉法。枚舉出可行解集合內(nèi)的所有可行解，以求出精確最優(yōu)解。對(duì)于連續(xù)函數(shù)，該方法要求先對(duì)其進(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)解。該方法的求解效率雖然比較高，但對(duì)每—個(gè)需要求解的問題都必須找出其特有的啟發(fā)式規(guī)則，這個(gè)啟發(fā)式規(guī)則無通用性，不適合于其他問題。10/27/202324(3)搜索算法。尋求一種搜索算法，該算法在可行解集合的一個(gè)子集內(nèi)進(jìn)行搜索操作，以找到問題的最優(yōu)解或近似最優(yōu)解。該方法雖然保證不了一定能夠得到問題的最優(yōu)解，但若適當(dāng)?shù)乩靡恍﹩l(fā)知識(shí)，就可在近似解的質(zhì)量和求解效率上達(dá)到—種較好的平衡。而遺傳算法為解決這類問題提供了一個(gè)有效的途徑和通用框架，開創(chuàng)了一種新的全局優(yōu)化搜索算法。10/27/202325遺傳算法中，將n維決策向量用n個(gè)記號(hào)Xi(n＝l，2，

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

—般情況下，染色體的長度n是固定的，但對(duì)一些問題n也可以是變化的。根據(jù)不同的情況，這里的等位基因可以是一組整數(shù)，也可以是某一范圍內(nèi)的實(shí)數(shù)值，或者是純粹的一個(gè)記號(hào)。最簡單的等位基因是由0和l這兩個(gè)整數(shù)組成的。相應(yīng)的染色體就可表示為一個(gè)二進(jìn)制符號(hào)串。10/27/202326這種編碼所形成的排列形式X是個(gè)體的基因型，與它對(duì)應(yīng)的X值是個(gè)體的表現(xiàn)型。通常個(gè)體的表現(xiàn)型和其基因型是一一對(duì)應(yīng)的，但有時(shí)也允許基因型和表現(xiàn)型是多對(duì)一的關(guān)系。染色休X也稱為個(gè)體X。對(duì)于每一個(gè)個(gè)體X，要按照一定的規(guī)則確定出其適應(yīng)度；個(gè)體的適應(yīng)度與其對(duì)應(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組成了問題的解空間。對(duì)問題最優(yōu)解的搜索是通過對(duì)染色體X的搜索過程來進(jìn)行的，從而由所有的染色體X就組成了問題的搜索空間。10/27/202327生物的進(jìn)化是以集團(tuán)為主體的。與此相對(duì)應(yīng)，遺傳算法的運(yùn)算對(duì)象是出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，它所對(duì)應(yīng)的表現(xiàn)型X將達(dá)到或接近于問題的最優(yōu)解X*。生物的進(jìn)化過程主要是通過染色體之間的交叉和染色體的變異來完成的，與此相對(duì)應(yīng)，遺傳算法中最優(yōu)解的搜索過程也模仿生物的這個(gè)進(jìn)化過程，使用所謂的遺傳算子(geneticoperators)作用于群體P(t)中，進(jìn)行下述遺傳操作，從而得到新一代群體P(t+1)。10/27/202328選擇(selection)：根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體P(t+1)中。交叉(crossover)：將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每對(duì)個(gè)體，以某個(gè)概率(稱為交叉概率，crossoverrate)交換它們之間的部分染色體。變異(mutation)：對(duì)群體P(t)中的每一個(gè)個(gè)體，以某一概率(稱為變異概率，mutationrate)改變某一個(gè)或某一些基因座上的基因值為其他的等位基因。10/27/202329二、遺傳算法的運(yùn)算過程

使用上述三種遺傳算子(選擇算子、交叉算子、變異算子)的遺傳算法的主要運(yùn)算過程如下所述：步驟一：初始化。設(shè)置進(jìn)化代數(shù)計(jì)數(shù)器t

0；設(shè)置最大進(jìn)化代數(shù)T；隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)。步驟二：個(gè)體評(píng)價(jià)。計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。步驟三：選擇運(yùn)算。將選擇算子作用于群體。10/27/202330步驟四：交叉運(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ì)算。10/27/202331三、遺傳算法的特點(diǎn)(1)遺傳算法以決策變量的編碼作為運(yùn)算對(duì)象。傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身來進(jìn)行優(yōu)化計(jì)算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運(yùn)算對(duì)象。這種對(duì)決策變量的編碼處理方式，使得我們?cè)趦?yōu)化計(jì)算過程中可以借鑒生物學(xué)中染色體和基因等概念，可以模仿自然界中生物的遺傳和進(jìn)化等機(jī)理，也使得我們可以方便地應(yīng)用遺傳操作算子。特別是對(duì)一些無數(shù)值概念或很難有數(shù)值概念，而只有代碼概念的優(yōu)化問題，編碼處理方式更顯示出了其獨(dú)持的優(yōu)越性。10/27/202332(2)遺傳算法直接以目標(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ù)值等其他一些輔助信息。這個(gè)特性對(duì)很多目標(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)度較高的部分搜索空間中，從而提高了搜索效率。10/27/202333(3)遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息。傳統(tǒng)的優(yōu)化算法往往是從解空間個(gè)的一個(gè)初始點(diǎn)開始最優(yōu)解的這代搜索過程，單個(gè)搜索點(diǎn)所提供的搜索信息畢竟不多，所以搜索效率不高，有時(shí)其至使搜索過程陷入局部最優(yōu)解而停滯不前。遺傳算法從很多個(gè)體所組成的一個(gè)初始群體開始最優(yōu)解的搜索過程，而不是從一個(gè)單一的個(gè)體開始搜索。對(duì)這個(gè)群體所進(jìn)行的選擇、交叉、變異等運(yùn)算，產(chǎn)生出的乃是新一代的群體，在這之中包括了很多群體信息。這些信息可以避免搜索一些不必搜索的點(diǎn)，所以實(shí)際上相當(dāng)于搜索了更多的點(diǎn)，這是遺傳算法所特有的一種隱含并行性。10/27/202334(4)遺傳算法使用概率搜索技術(shù)。傳統(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ù)對(duì)其搜索效果的影響會(huì)盡可能地低。10/27/202335基本遺傳算法的構(gòu)成要素基于對(duì)自然界中生物遺傳與進(jìn)化機(jī)理的模仿，針對(duì)不向的問題，很多學(xué)者設(shè)計(jì)了許多不同的編碼方法來表示問題的可行解，開發(fā)出了許多種不同的遺傳算子來模仿不同環(huán)境下的生物遺傳特。這樣，由不同的編碼方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點(diǎn)，即通過對(duì)生物遺傳和進(jìn)化過程中選擇、交叉、變異機(jī)理的模仿，來完成對(duì)問題最優(yōu)解的自適應(yīng)搜索過程。10/27/202336基于這個(gè)共同特點(diǎn)，Goldberg總結(jié)出了一種統(tǒng)一的最基本的遺傳算法——基本遺傳算法(SimpleGeneticAlgorithms，簡稱SGA)?；具z傳算法使用固定長度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位基因是由二值符號(hào)集{0，1}所組成的。初始群體中各個(gè)個(gè)體的基因值可用均勻分布的隨機(jī)數(shù)來生成?；具z傳算法使用比例選擇算子、單點(diǎn)交叉算子和基本位變異算子這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。10/27/202337基本遺傳算法的運(yùn)行參數(shù)基本遺傳算法有下述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ù)對(duì)遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。10/27/202338在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。一般來說，選擇較大數(shù)目的初始種群可以同時(shí)處理更多的解，因而容易找到全局的最優(yōu)解，其缺點(diǎn)使增加了每次迭代所需要的時(shí)間。交叉概率的選擇決定了交叉操作的頻率。頻率越高，可以越快收斂到最有希望的最優(yōu)解區(qū)域；但是太高的頻率也可能導(dǎo)致收斂于一個(gè)解。變異概率通常只取較小的數(shù)值。若選取高的變異率，一方面可以增加樣本的多樣性，另一方面可能引起不穩(wěn)定。但是若選取太小的變異概率，則可能難于找到全局的最優(yōu)解。10/27/202339基本遺傳算法的實(shí)現(xiàn)——編碼與解碼用二進(jìn)制編碼來離散自變量，碼長根據(jù)離散精度來確定。例如當(dāng)自變量a的變化區(qū)間為[amin，amax]

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

時(shí)，碼長m的計(jì)算公式為：相應(yīng)的解碼公式為：10/27/202340基本遺傳算法的實(shí)現(xiàn)——適應(yīng)度評(píng)價(jià)

在遺傳算法中，以個(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ù)。10/27/202341對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，理論上只需簡單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(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ù)值?；具z傳算法的實(shí)現(xiàn)——適應(yīng)度評(píng)價(jià)

10/27/202342為滿足適應(yīng)度取非負(fù)值的要求，基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)值f(X)變換為個(gè)體的適應(yīng)度F(x)。式中，Cmin為一個(gè)適當(dāng)?shù)叵鄬?duì)比較小的數(shù)，它可以用下面幾種方法之一來選擇：

方法一：對(duì)于求目標(biāo)函數(shù)最大值的優(yōu)化問題，變換方法為：預(yù)先指定的一個(gè)較小的數(shù)。進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值?；具z傳算法的實(shí)現(xiàn)——適應(yīng)度評(píng)價(jià)

10/27/202343方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，變換方法為：

式中，Cmax為一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可以用下面幾種方法之一來選擇：預(yù)先指定的一個(gè)較大的數(shù)。進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。前代或最近幾代群體中的最大目標(biāo)函數(shù)值。基本遺傳算法的實(shí)現(xiàn)——適應(yīng)度評(píng)價(jià)

10/27/202344選擇算子或復(fù)制算子的作用是從當(dāng)前代群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。最常用和最基本的選擇算子是比例選擇算子。比例選擇實(shí)際上是一種有退還隨機(jī)選擇，也叫做賭盤(Roulettewheel)選擇，因?yàn)檫@種選擇方式與賭博中的賭盤操作原理頗為相似。所謂比例選擇算子，是指個(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。基本遺傳算法的實(shí)現(xiàn)——比例選擇算子

10/27/202345整個(gè)賭盤被分為大小不同的一些扇面，分別對(duì)應(yīng)著價(jià)值各不相同的一些賭博物品。當(dāng)旋轉(zhuǎn)著的賭盤自然停下來時(shí)，其指針?biāo)干让嫔系奈锲肪蜌w賭博者所有。雖然賭盤的指針具體停止在哪一個(gè)扇面是無法預(yù)測(cè)的，但指針指向各個(gè)扇面的概率卻是可以估計(jì)的，它與各個(gè)扇面的圓心角大小成正比：圓心角越大，停在該扇面的可能性也越大；圓心角越小，停在該扇面的可能性也越小。與此類似，在遺傳算法中，整個(gè)群體被各個(gè)個(gè)體所分割，各個(gè)個(gè)體的適應(yīng)度在全部個(gè)體的適應(yīng)度之和中所占比例也大小不一，這個(gè)比例值瓜分了整個(gè)賭盤盤面，它們也決定了各個(gè)個(gè)體被遺傳到下一代群體中的概率?；具z傳算法的實(shí)現(xiàn)——比例選擇算子

10/27/202346金銀銅鐵10％20％30％40％基本遺傳算法的實(shí)現(xiàn)——比例選擇算子

10/27/202347比例選擇算子的具體執(zhí)行過程令：10/27/202348單點(diǎn)交叉算子是最常用和最基本的交叉操作算子。算子的具體執(zhí)行過程如下：(1)對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)。若群體的大小為M，則共有[M/2]對(duì)相互配對(duì)的個(gè)體組。其中[x]表示不大于x的最大整數(shù)。(2)對(duì)每一對(duì)相互配對(duì)的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。若染色體的長度為n，則共有(n-1)個(gè)可能的交叉點(diǎn)位置。(3)對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體?；具z傳算法的實(shí)現(xiàn)——單點(diǎn)交叉算子

10/27/202349單點(diǎn)交叉示意如下所示：

A：1011011100A’：1011011111B：0001110011B’；0001110000單點(diǎn)交叉交叉點(diǎn)基本遺傳算法的實(shí)現(xiàn)——單點(diǎn)交叉算子

10/27/202350對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將該基因值變?yōu)?；反之，若原有基因值為l，則變異操作將其變?yōu)?。A：10l0101010A’：10l0001010基本位變異

變異點(diǎn)

(1)對(duì)個(gè)體的每一個(gè)基因座，依變異概率pm指定其為變異點(diǎn)。(2)對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體?；具z傳算法的實(shí)現(xiàn)——基本位變異算子

10/27/202351基本遺傳算法在函數(shù)優(yōu)化中的應(yīng)用

該函數(shù)有兩個(gè)局部極大值，分別是f(2.048,-2.048)=3905.7324和f(-2.048,-2.048)=3905.9262，其中后者為全局最大值。下面介紹求解該問題的遺傳算法的構(gòu)造過程。第一步：確定決策變量和約束條件。第二步：建立優(yōu)化模型。例：Rosenbrock函數(shù)的全局最大值計(jì)算。10/27/202352用長度為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，依次讓它們分別對(duì)應(yīng)于從0000000000(0)到1111111111(1023)之間的二進(jìn)制編碼。再將分別表示x1，x2的二個(gè)10位長的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問題的染色體編碼方法。使用這種編碼方法．解空間和遺傳算法的搜索空間具有一一對(duì)應(yīng)的關(guān)系。例如X：000011011l1101110001就表示一個(gè)個(gè)體的基因型，其中前10位表示x1，后10為表示x2。10/27/202353第四步：確定解碼方法。

解碼時(shí)需先將20位長的二進(jìn)制編碼串切斷為二個(gè)10位長的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。例如，對(duì)于前述個(gè)體

X：000011011l1101110001它由這樣的兩個(gè)代碼所組成：y1＝55y2＝881經(jīng)解碼處理后，可得到：x1=－1.828x2=1.476依據(jù)前述個(gè)體編碼方法和對(duì)定義域的離散化方法可知，將代碼yi轉(zhuǎn)換為變量xi的解碼公式為：10/27/202354第五步：確定個(gè)體評(píng)價(jià)方法。第六步：設(shè)計(jì)遺傳算子?？芍琑osenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故這里可將個(gè)體的適應(yīng)度直接取為對(duì)應(yīng)的目標(biāo)函數(shù)值，即有：F(X)=f(x1，x2)選擇運(yùn)算使用比例選擇算子；交叉運(yùn)算使用單點(diǎn)交叉算子；變異運(yùn)算使用基本位變異算子。10/27/202355第七步：確定遺傳算法的運(yùn)行參數(shù)。對(duì)于本例，設(shè)定基本遺傳算法的運(yùn)行參數(shù)如下：群體大小：M＝80終止代數(shù)：T＝200交叉概率：pc＝0.6變異概率：pm＝0.001通過上述七個(gè)步驟就可構(gòu)成用于Rosenbrock函數(shù)優(yōu)化計(jì)算的基本遺傳算法。10/27/202356基本遺傳算法程序示例myGA.mfunction[xv,fv]=myGA(fitness,a,b,NP,NG,Pc,Pm,eps)functionresult=Initial(length)functiony=Dec(a,b,x,L)myGA2.m10/27/202357基本遺傳算法程序示例myGA2.m10/27/202358MATLAB遺傳算法工具箱GADS這個(gè)是Matlab7.0版本自帶的工具箱，全名叫GeneticAlgorithmandDirectSearchToolbox。在Matlab7.0的Help里面有對(duì)這個(gè)工具箱的詳細(xì)介紹，還有很多例子作演示。它還提供了一個(gè)圖形用戶界面的工具，名為“GeneticAlgorithmTool”，有了這個(gè)工具就可以不必輸入繁瑣的命令行參數(shù)，能方便而且直觀的觀察算法的運(yùn)行過程。在命令行里輸入“gatool”，就可以進(jìn)入該圖形用戶界面。10/27/202359[xfval]=ga(@fitnessfun,nvars,options)Where@fitnessfunisahandletothefitnessfunction.nvarsisthenumberofindependentvariablesforthefitnessfunction.optionsisastructurecontainingoptionsforthegeneticalgorithm.Ifyoudonotpassinthisargument,gausesitsdefaultoptions.Theresultsaregivenby:x—Pointatwhichthefinalvalueisattainedfval—FinalvalueofthefitnessfunctionMATLAB遺傳算法工具箱——命令行函數(shù)10/27/202360MATLAB遺傳算法工具箱——圖形用戶界面10/27/202361MATLAB遺傳算法工具箱——應(yīng)用實(shí)例求下列函數(shù)的最小值：建立適應(yīng)函數(shù)FitFun.m文件：functiony=FitFun(x)y=0.01;fori=1:5y=y+1/(i+(x(i)-1)^2);endy=1/y10/27/202362MATLAB遺傳算法工具箱——應(yīng)用實(shí)例適應(yīng)度函數(shù)的文件名待尋優(yōu)變量的個(gè)數(shù)變量的下邊界和上邊界10/27/202363MATLAB遺傳算法工具箱——應(yīng)用實(shí)例尋優(yōu)結(jié)果優(yōu)化參數(shù)迭代次數(shù)10/27/202364MATLAB遺傳算法工具箱——應(yīng)用實(shí)例該例題的理論最小值為0.436，且在(x1,x2,x3,x4,x5)=(1,1,1,1,1)時(shí)取到。從結(jié)果的比較可以看出，遺傳算法求出的結(jié)果精度是很高的。10/27/202365MATLAB遺傳算法工具箱——應(yīng)用實(shí)例建立適應(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=[];10/27/202366MATLAB遺傳算法工具箱——應(yīng)用實(shí)例非線性約束函數(shù)Nonlinearconstraintfunctiondefinesthenonlinearconstraints.Specifythefunctionasananonymousfunctionorasafunctionhandleoftheform@nonlcon,wherenonlcon.misanM-filethatreturnsthevectorscandceq.Thenonlinearequalitiesareoftheformceq=0,andthenonlinearinequalitiesareoftheformc

0.10/27/202367MATLAB遺傳算法工具箱——應(yīng)用實(shí)例此例題的理論最小值為3，在(x1,x2)=(2,2)時(shí)取得。從結(jié)果可以看出，結(jié)果精度是很高的。10/27/202368改進(jìn)——自適應(yīng)遺傳算法如果雙親的基因非常相近，所產(chǎn)生的后代相對(duì)于雙親也必然比較接近。這樣所期待的性能改善也必然較小。類似于“近親繁殖”。所以基因模式的單一性不僅減慢進(jìn)化歷程，而且可能導(dǎo)致進(jìn)化停滯，過早地收斂于局部的極值解。遺傳算法的改進(jìn)Srinvivas等提出一種自適應(yīng)遺傳算法，交叉概率和變異概率能夠隨適應(yīng)度自動(dòng)改變。當(dāng)種群各個(gè)個(gè)體適應(yīng)度趨于一致或者趨于局部最優(yōu)時(shí)，使交叉概率和變異概率二者增加，而當(dāng)群體適應(yīng)度比較分散時(shí)，使交叉概率和變異概率減少。同時(shí)，對(duì)于適應(yīng)值高于群體平均適應(yīng)值的個(gè)體，對(duì)應(yīng)于較低的交叉概率和變異概率，使該個(gè)體得以保護(hù)進(jìn)入下一代；而低于平均適應(yīng)值的個(gè)體，相對(duì)于較高的交叉概率和變異概率，使該個(gè)體被淘汰。10/27/202369改進(jìn)——自適應(yīng)遺傳算法因此，自適應(yīng)遺傳算法能夠提供相對(duì)某個(gè)解的最佳交叉概率和變異概率。自適應(yīng)遺傳算法中交叉概率和變異概率的計(jì)算公式為：10/27/202370改進(jìn)——部分替代法設(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)平衡。10/27/202371改進(jìn)——優(yōu)秀個(gè)體保護(hù)法這種方法對(duì)于每代中一定數(shù)量的最優(yōu)個(gè)體，使之直接進(jìn)入下一代。這樣可以防止優(yōu)秀個(gè)體由于復(fù)制、交叉或變異中的偶然因素而被破壞掉。這是增強(qiáng)算法穩(wěn)定性和收斂性的有效方法。但同時(shí)也可能使遺傳算法陷入局部的極值范圍。10/27/202372改進(jìn)——分布式遺傳算法該方法將一個(gè)總的群體分為若干個(gè)子群，各子群將具有略微不同的基因模式，它們各自的遺傳過程具有相對(duì)的獨(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ù)相同的情況下，分布式遺傳算法可以得到比單一種群遺傳算法更好的效果。10/27/202373其它改進(jìn)

——順序選擇遺傳算法

——適應(yīng)值函數(shù)標(biāo)定的遺傳算法

——大變異遺傳算法

——雙切點(diǎn)交叉遺傳算法

——多變異位自適應(yīng)遺傳算法10/27/2023743.3蟻群算法10/27/202375群智能優(yōu)化算法群智能(swarmintelligence,SI)的概念首次由Beni和Wang在研究元胞機(jī)器人系統(tǒng)中提出，由無智能的機(jī)器人組成的系統(tǒng)呈現(xiàn)集體智能行為。但當(dāng)時(shí)他們對(duì)于“群體”和“智能”的定義較為特定，即僅針對(duì)機(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)。10/27/2023761999年，Bonabeau等在著作《SwarmIntelligence:FromNaturaltoArtificialSystems》中對(duì)群智能進(jìn)行了詳細(xì)的論述，并定義為：任何一種基于社會(huì)生物群體行為機(jī)制設(shè)計(jì)出的算法或分布式問題求解的策略均屬于群智能。之后，Bonabeau將群智能的定義進(jìn)一步推廣為：無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現(xiàn)出智能行為的特性。2001年，Kennedy等在著作《SwarmIntelligence》中對(duì)群智能的理論與方法進(jìn)行了總結(jié)，并介紹了粒子群優(yōu)化算法。他們不反對(duì)Bonabeau關(guān)于群智能定義的基本思想，但反對(duì)定義中的“主體”一詞，認(rèn)為“主體”所帶有的自治性和特殊性是許多群體的個(gè)體所不具備和擁有的，這將大大限制群智能的定義范圍。他們認(rèn)為暫時(shí)無法給出群智能合適的定義。10/27/202377至目前為止，雖然學(xué)術(shù)界對(duì)群智能的定義仍存在爭議，且其理論本身還不成熟，但是群智能具備處理復(fù)雜系統(tǒng)的獨(dú)特優(yōu)勢(shì)，吸引了越來越多的專家學(xué)者投身于群智能理論與應(yīng)用的研究。隨著研究的進(jìn)展，對(duì)群智能的理解與認(rèn)識(shí)亦逐漸深入，應(yīng)用領(lǐng)域不斷拓寬。2003年IEEE第一屆國際群智能研討會(huì)在美國印第安納州首府首次召開，且每年舉辦一次群智能國際研討會(huì)。2007年9月，Dorigo與Birattari在學(xué)術(shù)百科全書網(wǎng)站發(fā)表了一篇“SwarmIntelligence”論文，并對(duì)群智能給出了定義：群智能是一門采用分散控制和自組織理論協(xié)調(diào)處理由多個(gè)個(gè)體組成的自然和人工系統(tǒng)的學(xué)科；特別的，群智能學(xué)科主要研究由個(gè)體之間以及個(gè)體與環(huán)境之間的局部相互作用而產(chǎn)生的集體行為。同年，由Springer出版社出版的雜志《SwarmIntelligence》創(chuàng)刊，由Dorigo任主編。10/27/202378研究了蟻群的覓食行為后發(fā)現(xiàn)，由僅具備簡單行為的螞蟻組成的群體通過信息素的釋放與跟隨，實(shí)現(xiàn)正反饋和分布式協(xié)作，突現(xiàn)出復(fù)雜的群體智能行為，即蟻群能找到蟻穴與食物源之間的最短路徑。受此啟發(fā)，Dorig等于1991年首次提出了蟻群優(yōu)化算法，此為一種基于種群的元啟發(fā)式(metaheuristics)算法，已廣泛地用于組合優(yōu)化問題的求解，如旅行商問題、順序排列問題、調(diào)度問題、網(wǎng)絡(luò)路由問題、集合覆蓋問題等。蟻群優(yōu)化算法10/27/202379像螞蟻這類群居昆蟲，雖然沒有視覺，卻能找到由蟻穴到食物源的最短路徑。雖然單只螞蟻的行為極其簡單，但由這樣的單個(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é)作起著重要的作用。螞蟻覓食的生物學(xué)基礎(chǔ)10/27/202380螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下該物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向。螞蟻傾向于朝著該物質(zhì)強(qiáng)度高的方向移動(dòng)。因此，由大量螞蟻組成的蟻群的集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后者選擇該路徑的概率越大。螞蟻個(gè)體之間就是通過這種信息的交流達(dá)到搜索食物的目的。10/27/202381蟻群系統(tǒng)示意圖食物蟻巢ADBC障礙物11122110/27/202382假定障礙物的周圍有兩條道路可從螞蟻的巢穴到達(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)。10/27/202383t=8時(shí)刻，前5只螞蟻將返回巢穴，此時(shí)在AC中點(diǎn)處、CD中點(diǎn)處以及B點(diǎn)上各有5只螞蟻。t=9時(shí)刻，前5只螞蟻又回到A點(diǎn)，并且再次面對(duì)往左還是往右的選擇。這時(shí)，AB上的軌跡數(shù)是20而AC上是15，因此將有較為多數(shù)的螞蟻選擇往左，從而增強(qiáng)了該路線上的信息素。隨著該過程的繼續(xù)，兩條道路上的信息素的差距將越來越大，直至絕大多數(shù)螞蟻都選擇了最短的路線。正是由于一條道路要比另一條道路短，因此，在相同的時(shí)間區(qū)間內(nèi)，短的路線有更多的機(jī)會(huì)被選擇。10/27/202384螞蟻的集群活動(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)。10/27/202385蟻群算法是一種隨機(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)知識(shí)，最初只是隨機(jī)地選擇搜索路徑，隨著對(duì)解空間的“了解”，搜索變得更有規(guī)律，并逐漸逼近直至最終達(dá)到全局最優(yōu)解。10/27/202386人工螞蟻與真實(shí)螞蟻的異同相同點(diǎn)之一：兩個(gè)群體中都存在個(gè)體相互交流的通信機(jī)制真實(shí)螞蟻在經(jīng)過的路徑上留下信息素，用以影響蟻群中的其他個(gè)體。且信息素隨著時(shí)間推移逐漸揮發(fā)，減小歷史遺留信息對(duì)蟻群的影響。同樣，人工螞蟻改變其所經(jīng)過路徑上存儲(chǔ)的數(shù)字化信息素，該信息素記錄了人工螞蟻當(dāng)前解和歷史解的性能狀態(tài)，而且可被后繼人工螞蟻?zhàn)x寫。數(shù)字化的信息素同樣具有揮發(fā)性，它像真實(shí)的信息量揮發(fā)一樣使人工螞蟻逐漸忘卻歷史遺留信息，在選擇路徑時(shí)不局限于以前人工螞蟻所存留的經(jīng)驗(yàn)。10/27/202387相同點(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ù)測(cè)未來情況的一種方法。10/27/202388不同點(diǎn)人工螞蟻具有記憶功能，而真實(shí)螞蟻沒有。人工螞蟻可以記住曾經(jīng)走過的路徑或訪問過的節(jié)點(diǎn)，可提高算法的效率。人工螞蟻選擇路徑時(shí)并不是完全盲目的，受到問題空間特征的啟發(fā)，按一定的算法規(guī)律有意識(shí)地尋找最短路徑（如在旅行商問題中，可以預(yù)先知道下一個(gè)目標(biāo)的距離）。人工螞蟻生活在離散時(shí)間的環(huán)境中，即問題的求解規(guī)劃空間是離散的，而真實(shí)螞蟻生活在連續(xù)時(shí)間的環(huán)境中。10/27/202389旅行商問題旅行商問題即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)一次的最短回路。10/27/202390蟻群算法應(yīng)用于旅行商問題的基本算法（1）它根據(jù)以城市距離和連接邊上的信息素軌跡強(qiáng)度的數(shù)量為變量的概率函數(shù)選擇下一個(gè)城市。（2）規(guī)定螞蟻?zhàn)吆戏肪€，除非周游完成，不允許轉(zhuǎn)到已訪問的城市，由禁忌表控制（設(shè)tabuk表示第k只螞蟻的禁忌表，tabuk(s)表示禁忌表中的第s個(gè)元素。）（3）它完成周游后，螞蟻在它每一條訪問的邊上留下信息素。每只螞蟻所具有的特征10/27/202391bi(t)(i=1,2,

,n)：在t時(shí)刻城市i的螞蟻數(shù)算法中的基本符號(hào)：全部螞蟻數(shù)dij：兩城市之間的距離

ij

：路徑(i，j)上的能見度，反映城市i到城市j的啟發(fā)程度，一般取=1/dij

ij(t)

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

ij(0)＝C。n：城市數(shù)目10/27/202392螞蟻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下一步允許選擇的城市。10/27/202393tabuk(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)度的相對(duì)重要性，表示能見度的相對(duì)重要性。分別反映了螞蟻在運(yùn)動(dòng)過程中所積累的信息和啟發(fā)信息在螞蟻選擇路徑中的相對(duì)重要性：10/27/202394經(jīng)過n個(gè)時(shí)刻(n即為城市數(shù)目)，螞蟻完成一次循環(huán)，各路徑上的信息量要根據(jù)以下公式做調(diào)整：：第k只螞蟻在本次循環(huán)中留在路徑ij上的信息量：本次循環(huán)中路徑ij上的信息量增量：表示軌跡的持久性，(1－)稱為信息的揮發(fā)系數(shù)，表示信息消逝程度，隨時(shí)間推移，以前留下的信息逐漸消失。通常設(shè)置系數(shù)0<<1來避免路徑上信息素的無限累加。10/27/202395信息素修改ant-cyclealgorithm（蟻環(huán)算法）蟻環(huán)算法（蟻周算法）利用的是整體信息，在求解TSP問題時(shí)，性能較好。該算法的特點(diǎn)是行走的路徑越短，對(duì)應(yīng)保存的信息素的值就越大。10/27/202396ant-quantityalgorithm（蟻量算法）ant-densityalgorithm（蟻密算法）后兩種模型利用的是局部信息。信息濃度會(huì)因?yàn)槌鞘芯嚯x的減小而增大。10/27/202397在線和離線信息素修改信息素的更新可分為離線和在線兩種方式。離線方式，也稱為同步更新方式，其主要思想是在若干只螞蟻完成n個(gè)城市的訪問后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。信息素在線更新，也稱為異步更新，螞蟻每行一步，馬上回溯并且更新行走路線上的信息素。10/27/202398對(duì)于離線方式的信息素更新，進(jìn)一步可以細(xì)分為單螞蟻離線更新和蟻群離線更新兩種方式。蟻群更新是在蟻群中的m只螞蟻全部完成n個(gè)城市的訪問后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。蟻群中螞蟻的先后出行順序沒有相關(guān)性，前面出行的螞蟻不影響后面出行的螞蟻的行為，但每次循環(huán)需要記錄m只螞蟻的行走路徑，以便最后比較選擇最好的路徑。單螞蟻更新是在第s只螞蟻完成對(duì)所有n個(gè)城市的訪問后，進(jìn)行路徑回溯，更新行走路徑上的信息素，同時(shí)釋放分配給它的資源。記憶信息相對(duì)較少。信息量記憶更小的是信息素的在線更新方式。螞蟻每行一步，馬上回溯并且更新行走路徑上的信息素。10/27/202399參數(shù)選擇對(duì)蟻群算法性能的影響探索(exploration)和開發(fā)(exploitation)能力的平衡是影響算法性能的一個(gè)重要方面，也是蟻群算法研究的關(guān)鍵問題之一。探索能力是指蟻群算法要在解空間中測(cè)試不同區(qū)域以找到一個(gè)局優(yōu)解的能力；開發(fā)能力是指蟻群算法在一個(gè)有希望的區(qū)域內(nèi)進(jìn)行精確搜索的能力。探索和開發(fā)實(shí)際上就是全局搜索能力和局域搜索能力。通過設(shè)定蟻群算法中的各種參數(shù)，實(shí)現(xiàn)探索和開發(fā)能力的平衡。10/27/2023100螞蟻系統(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é)果為：05，05，0.10.99，10Q1000010/27/2023101（1）信息素和啟發(fā)函數(shù)對(duì)蟻群算法性能的影響信息素是表征過去信息的載體，而啟發(fā)函數(shù)則是表示未來信息的載體，它們直接影響到蟻群算法的全局收斂性和求解效率。（2）信息素殘留因子

對(duì)蟻群算法性能的影響在0.10.99范圍內(nèi)，與迭代次數(shù)近似成正比。當(dāng)很大時(shí)，路徑上的殘留信息占主導(dǎo)地位，信息正反饋?zhàn)饔孟鄬?duì)較弱，搜索的隨機(jī)性增強(qiáng)，因而蟻群算法的收斂速度很慢。當(dāng)較小時(shí)，正反饋?zhàn)饔谜贾鲗?dǎo)地位，搜索的隨機(jī)性減弱，導(dǎo)致收斂速度加快，但易于陷入局部最優(yōu)。10/27/2023102（3）螞蟻數(shù)目對(duì)蟻群算法性能的影響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對(duì)蟻群算法性能的影響Q為螞蟻循環(huán)一周時(shí)釋放在所經(jīng)路徑上的信息素總量。Q越大，螞蟻在已遍歷路徑上信息素的累積越快，加強(qiáng)螞蟻搜索時(shí)的正反饋性，有助于算法的收斂速度。10/27/2023103（5）、對(duì)蟻群算法性能的影響反映螞蟻在運(yùn)動(dòng)過程中所積累的信息量在指導(dǎo)蟻群搜索中的相對(duì)重要程度。越大，螞蟻選擇以前走過的路徑的可能性越大，搜索的隨機(jī)性減弱；越小，易使蟻群算法過早陷入局優(yōu)。反映螞蟻啟發(fā)式信息在指導(dǎo)蟻群搜索中的相對(duì)重要程度，這些啟發(fā)式信息表現(xiàn)為尋優(yōu)過程中先驗(yàn)性、確定性因素。越大，螞蟻在局部點(diǎn)上選擇局部最優(yōu)路徑的可能性越大，雖然加快了收斂速度，但減弱了隨機(jī)性，易于陷入局部最優(yōu)。如果=0，則是傳統(tǒng)的貪心算法，如果=0，則是純粹的正反饋的啟發(fā)式算法。10/27/2023104可以使用以下三步走的原則:2)參數(shù)粗調(diào)，即調(diào)整取值范圍較大的信息素啟發(fā)因子

、期望因子

以及信息素強(qiáng)度Q等參數(shù)，以得到最好的解。3)參數(shù)細(xì)調(diào)，即調(diào)整取值范圍較小的信息素?fù)]發(fā)因子P。以上步驟反復(fù)進(jìn)行，直到最終確定出一組較好的組合參數(shù)。1)確定螞蟻數(shù)目：如下公式大致確定螞蟻個(gè)數(shù)10/27/2023105終止條件有三類：第一類為一個(gè)給定的外循環(huán)最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作；第二類為當(dāng)前最優(yōu)解連續(xù)K次相同而停止的規(guī)則，其中K是一個(gè)給定的整數(shù)，表示算法已收斂，不需要再繼續(xù)；第三類為目標(biāo)控制規(guī)則，給定優(yōu)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。終止條件10/27/2023106TSP問題的蟻群算法基本步驟（1）t0（t為迭代步數(shù)或搜索次數(shù)）；參數(shù)初始化。（2）假設(shè)有m只螞蟻在工作，將各螞蟻的初始出發(fā)點(diǎn)置于當(dāng)前解集中；對(duì)每只螞蟻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）輸出目前最好解。10/27/2023107蟻群算法流程10/27/2023108蟻周系統(tǒng)應(yīng)用于TSP問題仿真指導(dǎo)蟻周系統(tǒng)搜索過程的反饋信息是全局信息，即螞蟻釋放的信息素的量正比于所生成解的優(yōu)劣度。螞蟻生成的路徑越短，它在這條路徑上貢獻(xiàn)的信息素量就越多，蟻周系統(tǒng)模型的性能遠(yuǎn)好于其它兩種模型。以20城市的TSP問題為例，對(duì)蟻周系統(tǒng)進(jìn)行仿真，先做如下規(guī)定：x,y是兩個(gè)向量，用來表示20城市的橫縱坐標(biāo)，向量元素的順序就表示了城市的位置序號(hào)，并且規(guī)定要求的距離為歐幾里德距離。即第i，j個(gè)城市之間的距離為：10/27/2023109蟻周模型的參數(shù)的選擇如下：m=20；Q=10；nc

=500；

=1;

=5；

=0.7。最優(yōu)路徑在121次循環(huán)中找到，最優(yōu)距離f=25.6396。依次經(jīng)過各個(gè)城市的順序：8－4－3－12－2－9－15－10－19－7－18－16－5－13－20－6－17－1－14－11－8。20城市問題即求：，當(dāng)且僅當(dāng)每個(gè)城市經(jīng)過一次。x=[5.294，4.286，4.719，4.185，0.915，4.771，1.524，3.447，3.718，2.649，4.439，4.660，1.232，5.036，2.710，1.072，5.855，0.194，1.762，2.862]y=[1.558，3.622，2.774，2.230，3.821，6.041，2.871，2.111，3.665，2.556，1.194，2.949，6.440，0.244，3.140，3.454，6.203，1.862，2.693，6.097]10/27/2023110最短路徑示意圖10/27/2023111在初始階段，信息素的軌跡量被均勻的分布在各條邊上，搜索只能由能見度指導(dǎo)，隨后較優(yōu)的路經(jīng)上信息素得到增強(qiáng)，而較差的路徑邊上的信息素被完全揮發(fā)掉。結(jié)果最差路經(jīng)上的邊被從圖上刪除，從而使得搜索空間變小，最后螞蟻收斂到同一路徑上。10/27/2023112tsp_30=[

87，7；91，38；83，46；71，44；64，60；

68，58；83，69；87，76；74，78；71，71；

58，69；54，62；51，67；37，84；41，94；

2，99；7，64；22，60；25，62；18，54；

4，50；13，40；18，40；24，42；25，38；

41，26；45，21；44，35；58，35；62，32]30個(gè)城市的TSP問題Oliver30數(shù)據(jù)10/27/2023113改進(jìn)及擴(kuò)展的離散蟻群算法離散蟻群算法在求解TSP問題上的出色表現(xiàn)，使得它足以與許多同類智能算法如GA,SA等相媲美，并發(fā)展出許多改進(jìn)的離散蟻群算法：自適應(yīng)蟻群算法、基于信息素?cái)U(kuò)散的蟻群算法、基于去交叉局部優(yōu)化策略的蟻群算法、多態(tài)蟻群算法、基于模式學(xué)習(xí)的小窗口蟻群算法、基于混合行為蟻群算法、帶聚類處理的蟻群算法、基于云模式理論的蟻群算法、具有感覺和知覺特征的蟻群算法、具有隨機(jī)擾動(dòng)特性的蟻群算法、基于信息熵的改進(jìn)蟻群算法等。10/27/2023114自適應(yīng)蟻群算法即對(duì)蟻群算法中的狀態(tài)轉(zhuǎn)移概率、信息素?fù)]發(fā)因子、信息量等因素，采用自適應(yīng)調(diào)節(jié)策略為一種基本改進(jìn)思路的蟻群算法。自適應(yīng)蟻群算法中兩個(gè)最經(jīng)典的方法：蟻群系統(tǒng)(AntColonySystem,ACS)最大最小蟻群系統(tǒng)(MAX-MINAntSystem,MMAS)10/27/2023115蟻群系統(tǒng)(AntColonySystem,ACS)ACS解決了基本蟻群算法在構(gòu)造解的過程中，隨機(jī)選擇策略造成的算法進(jìn)化速度慢的缺點(diǎn)。該算法在每一次的循環(huán)中僅讓最短路徑上的信息量做更新，且以較大的概率讓信息量最大的路徑被選中，充分利用學(xué)習(xí)機(jī)制，強(qiáng)化最優(yōu)信息的反饋。ACS的核心思想是：螞蟻在尋找最佳路徑的過程中只能使用局部信息，即采用局部信息對(duì)路徑上的信息量進(jìn)行調(diào)整；在所有進(jìn)行尋優(yōu)的螞蟻結(jié)束路徑的搜索后，路徑上的信息量會(huì)再一次調(diào)整，這次采用的是全局信息，而且只對(duì)過程中發(fā)現(xiàn)的最好路徑上的信息量進(jìn)行加強(qiáng)。10/27/2023116ACS模型與AS模型的主要區(qū)別有3點(diǎn)：螞蟻的狀態(tài)轉(zhuǎn)移規(guī)則不同；全局更新規(guī)則不同；新增了對(duì)各條路徑信息量調(diào)節(jié)的局部更新規(guī)則。10/27/2023117ACS的狀態(tài)轉(zhuǎn)移規(guī)則：為了避免停滯現(xiàn)象的出現(xiàn)，ACS采用確定性選擇和隨機(jī)性選擇相結(jié)合的選擇策略，并在搜索過程中動(dòng)態(tài)調(diào)整狀態(tài)轉(zhuǎn)移概率。對(duì)于位于城市i的螞蟻k，按照(1)式選擇下一個(gè)城市：(2)(1)10/27/2023118Jk(i)是第k只螞蟻在訪問到城市i后尚需訪問的城市集合；q為一個(gè)區(qū)間[0,1]內(nèi)的隨機(jī)數(shù)，q0是一個(gè)[0,1]之間的算法參數(shù)。(1)式所確定的螞蟻轉(zhuǎn)移到下一個(gè)城市的方法稱為自適應(yīng)偽隨機(jī)概率選擇規(guī)則。在這種規(guī)則下，每當(dāng)螞蟻要選擇下個(gè)城市時(shí)，就產(chǎn)生在[0,1]之間的隨機(jī)數(shù)，根據(jù)這個(gè)隨機(jī)數(shù)的大小確定用哪種方法產(chǎn)生螞蟻轉(zhuǎn)移的方向。10/27/2023119全局更新規(guī)則：在ACS中，全局更新不再用于所有的螞蟻，只對(duì)每一次循環(huán)中最優(yōu)的螞蟻使用。(3)10/27/2023120局部更新規(guī)則：局部更新規(guī)則是在所有的螞蟻完成一次轉(zhuǎn)移后執(zhí)行：第3種方案的ACS算法被稱為Ant-Q強(qiáng)化學(xué)習(xí)算法。實(shí)驗(yàn)結(jié)果表明與基本蟻群算法比較，該模型具有一般性，更有利于全局搜索。(4)10/27/2023121ACS的偽代碼：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++){

產(chǎn)生隨機(jī)數(shù)q；按公式(1)和(2)規(guī)則確定每只螞蟻要轉(zhuǎn)移的位置；將剛剛選擇的城市j加入到tabuk中；按公式(4)執(zhí)行局部更新規(guī)則；}

}

確定本次循環(huán)中找到的最佳路徑L=min(Lk),k=1,2,…,m;

按照公式(3)執(zhí)行全局更新規(guī)則；

ncycle=ncylce+1;}10/27/2023122最大最小蟻群系統(tǒng)(MAX-MINAntSystem,MMAS)通過對(duì)蟻群系統(tǒng)的研究表明，將螞蟻搜索行為集中到最優(yōu)解的附近可以提高解的質(zhì)量和收斂速度，從而提高算法的性能。但這種方式會(huì)使算法過早收斂而出現(xiàn)早熟現(xiàn)象，從而提出了MMAS。MMAS的基本思想：僅讓每一代中的最好個(gè)體所走路徑上的信息量做調(diào)整，從而更好地利用了歷史信息，以加快收斂速度。但這樣更容易出現(xiàn)過早收斂的現(xiàn)象，為避免算法過早收斂于非全局最優(yōu)解，將各條路徑上的信息量允許值在區(qū)間[

min，max]之內(nèi)，可以避免某條路徑上信息量遠(yuǎn)大于其他路徑而造成所有螞蟻都集中到同一條路徑上。。10/27/2023123MMAS在AS基礎(chǔ)上作了3點(diǎn)改進(jìn)：首先初始化信息量設(shè)為最大值

max

；其次各個(gè)螞蟻在一次循環(huán)后，只有找到最短路徑的螞蟻才能在其經(jīng)過的路徑上釋放信息素，即：最后將

ij限制在[

min，max]之間。（5）10/27/2023124MMAS的偽代碼：begin初始化過程：ncycle=1;bestcycle=1;

max;min;

ij=0;；；；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++){

按照概率選擇下一個(gè)城市j；將剛剛選擇的城市j加入到tabuk中；按公式(4)執(zhí)行局部更新規(guī)則；}

}

確定本次循環(huán)中找到的最佳路徑L=min(Lk),k=1,2,…,m;

按照公式(5)更新信息素；

ncycle=ncylce+1;}10/27/2023125除了以上兩種自適應(yīng)改進(jìn)蟻群算法外，還有很多離散域改進(jìn)蟻群算法。雖然這些改進(jìn)策略的側(cè)重點(diǎn)和改進(jìn)形式不同，但是其目的是相同的，及避免陷入局部最優(yōu)，縮短搜索時(shí)間，提高蟻群算法的全局收斂性能。10/27/2023126蟻群算法在參數(shù)尋優(yōu)中的應(yīng)用由于蟻群算法應(yīng)用于離散優(yōu)化問題所表現(xiàn)出的優(yōu)異性能，很自然地讓人想到把蟻群算法擴(kuò)展到連續(xù)優(yōu)化問題。由于離散優(yōu)化問題和連續(xù)優(yōu)化問題性質(zhì)的不同，導(dǎo)致在信息素分布方式上的差異，解決離散優(yōu)化問題的蟻群算法并不能自接用于求解連續(xù)優(yōu)化問題。一種解決辦法是，將各螞蟻本身視為頂點(diǎn)，信息素直接分布在解空間內(nèi)各螞蟻所在的位置上。另一種辦法是，把解的各個(gè)分量離散成固定長度的區(qū)間，將各分量子區(qū)間視為頂點(diǎn)，信息素分布在各層分量的子區(qū)間上，具有代表性的是CACA算法。10/27/2023127不失一般性，定義連續(xù)函數(shù)優(yōu)化問題為：在連續(xù)函數(shù)優(yōu)化問題，目標(biāo)函數(shù)f為任意非線性函數(shù)，設(shè)計(jì)變量，約束條件構(gòu)成Rn上的一個(gè)n維區(qū)域。10/27