第三章求解優(yōu)化問(wèn)題的智能算法課件

第三章求解優(yōu)化問(wèn)題的智能算法12023/10/3第三章12023/8/1010203概況三點(diǎn)擊此處輸入相關(guān)文本內(nèi)容整體概況概況一點(diǎn)擊此處輸入相關(guān)文本內(nèi)容概況二點(diǎn)擊此處輸入相關(guān)文本內(nèi)容2010203概況三整體概況概況一概況二23.1

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

1/242023/10/3最優(yōu)化問(wèn)題是指在一定的約束條件下，決定某個(gè)或某些可控制的因素隨著近代科學(xué)技術(shù)發(fā)展的需要，特別是由于計(jì)算機(jī)技術(shù)的飛速發(fā)展，促進(jìn)了最優(yōu)化方法的迅速發(fā)展，并很快滲透到各個(gè)領(lǐng)域。20世紀(jì)70年代，最優(yōu)化方法這門(mén)應(yīng)用技術(shù)科學(xué)又開(kāi)始產(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/252023/10/3隨著近代科學(xué)技術(shù)發(fā)展的需要，特別是由于計(jì)算機(jī)技術(shù)的飛速發(fā)展，求解優(yōu)化問(wèn)題的步驟(1)分析待優(yōu)化的問(wèn)題，建立問(wèn)題的數(shù)學(xué)模型；(2)分析數(shù)學(xué)模型，選擇合適的最優(yōu)化算法；(3)編寫(xiě)計(jì)算機(jī)程序、上機(jī)計(jì)算、求出最優(yōu)解；(4)結(jié)果檢驗(yàn)與最后決策。62023/10/3求解優(yōu)化問(wèn)題的步驟(1)分析待優(yōu)化的問(wèn)題，建立問(wèn)題的數(shù)學(xué)模型轉(zhuǎn)化為最小化問(wèn)題。3.1概述——最優(yōu)化問(wèn)題的數(shù)學(xué)描述72023/10/3轉(zhuǎn)化為最小化問(wèn)題。3.1概述——最優(yōu)化問(wèn)題的數(shù)學(xué)描述720(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ì)算工具上都無(wú)法求解。(2)啟發(fā)式算法。尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，以找到一個(gè)最優(yōu)解或近似最優(yōu)解。該方法的求解效率雖然比較高，但對(duì)每一個(gè)需要求解的問(wèn)題都必須找出其特有的啟發(fā)式規(guī)則，這個(gè)啟發(fā)式規(guī)則無(wú)通用性，不適合于其他問(wèn)題。3.1概述——求最優(yōu)解或近似最優(yōu)解的方法1/282023/10/3(1)枚舉法。(2)啟發(fā)式算法。3.1概述——求最優(yōu)解或近(3)搜索算法。尋求一種搜索算法，該算法在可行解集合的一個(gè)子集內(nèi)進(jìn)行搜索操作，以找到問(wèn)題的最優(yōu)解或近似最優(yōu)解。該方法雖然保證不了一定能夠得到問(wèn)題的最優(yōu)解，但若適當(dāng)?shù)乩靡恍﹩l(fā)知識(shí)，就可在近似解的質(zhì)量和求解效率上達(dá)到—種較好的平衡。3.1概述——求最優(yōu)解或近似最優(yōu)解的方法2/292023/10/3(3)搜索算法。尋求一種搜索算法，該算法在可行解集合的一個(gè)子以最速下降法、牛頓法和共扼方向法等為代表的傳統(tǒng)優(yōu)化算法具有完善的數(shù)學(xué)基礎(chǔ)，具有計(jì)算效率高、可靠性強(qiáng)和比較成熟等特點(diǎn)。這些算法的基本迭代步驟如下：3.1概述——求解最優(yōu)化問(wèn)題的傳統(tǒng)方法102023/10/3以最速下降法、牛頓法和共扼方向法等為代表的傳統(tǒng)優(yōu)化算法具有完3.1概述——求解最優(yōu)化問(wèn)題的傳統(tǒng)方法——最速下降法112023/10/33.1概述——求解最優(yōu)化問(wèn)題的傳統(tǒng)方法——最速下降法1123.1概述——求解最優(yōu)化問(wèn)題的傳統(tǒng)方法——牛頓法122023/10/33.1概述——求解最優(yōu)化問(wèn)題的傳統(tǒng)方法——牛頓法122023.1概述——求解最優(yōu)化問(wèn)題的傳統(tǒng)方法——共軛方向法132023/10/33.1概述——求解最優(yōu)化問(wèn)題的傳統(tǒng)方法——共軛方向法132對(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需要，完成了從“方法定向”到“問(wèn)題定向”的轉(zhuǎn)換。3.1概述——對(duì)最優(yōu)化提出的新的需求142023/10/3對(duì)目標(biāo)函數(shù)和約束函數(shù)表達(dá)的要求必須更為寬松實(shí)際生活中對(duì)最優(yōu)化1975年，Holland提出遺傳算法(GeneticAlgorithm)。這種優(yōu)化方法模仿生物種群中優(yōu)勝劣汰的選擇機(jī)制，通過(guò)種群中優(yōu)勢(shì)個(gè)體的繁衍進(jìn)化來(lái)實(shí)現(xiàn)優(yōu)化的功能。1977年，Glover提出禁忌搜索(TabuSearch)算法。這種方法將記憶功能引入到最優(yōu)解的搜索過(guò)程中，通過(guò)設(shè)置禁忌區(qū)阻止搜索過(guò)程中的重復(fù)，從而大大提高了尋優(yōu)過(guò)程的搜索效率。1983年，Kirkpatrick提出了模擬退火(SimulatedAnnealing)算法。這種算法模擬熱力學(xué)中退火過(guò)程能使金屬原子達(dá)到能量最低狀態(tài)的機(jī)制，通過(guò)模擬的降溫過(guò)程，按玻茲曼(Boltzmann)方程計(jì)算狀態(tài)間的轉(zhuǎn)移概率來(lái)引導(dǎo)搜索，從而使算法具有很好的全局搜索能力。3.1概述——新的優(yōu)化方法不斷出現(xiàn)1/2152023/10/31975年，Holland提出遺傳算法(GeneticAl20世紀(jì)90年代初，Dorigo等提出蟻群優(yōu)化算法(AntColonyOptimization)算法。這種算法借鑒蟻群群體利用信息素相互傳遞信息來(lái)實(shí)現(xiàn)路徑優(yōu)化的機(jī)理，通過(guò)記憶路徑信息素的變化來(lái)解決組合優(yōu)化問(wèn)題。1995年，Kenedy和Eberhart提出粒子群優(yōu)化(ParticleSwarmOptimization)算法。這種方法模仿鳥(niǎo)類(lèi)和魚(yú)類(lèi)群體覓食遷移中，個(gè)體與群體協(xié)調(diào)一致的機(jī)理，通過(guò)群體最優(yōu)方向、個(gè)體最優(yōu)方向和慣性方向的協(xié)調(diào)來(lái)求解實(shí)數(shù)優(yōu)化問(wèn)題。1999年，Linhares提出了捕食搜索(PredatorySearch)算法。這種算法模擬猛獸捕食中大范圍搜尋和局部蹲守的特點(diǎn)，通過(guò)設(shè)置全局搜索和局部搜索間變換的閾值來(lái)協(xié)調(diào)兩種不同的搜索模式，從而實(shí)現(xiàn)了對(duì)全局搜索能力和局部搜索能力的兼顧。3.1概述——新的優(yōu)化方法不斷出現(xiàn)2/2162023/10/320世紀(jì)90年代初，Dorigo等提出蟻群優(yōu)化算法(Ant不以達(dá)到某個(gè)最優(yōu)性條件或找到理論上的精確最優(yōu)解為目標(biāo)，而是更看重計(jì)算的速度和效率；對(duì)目標(biāo)函數(shù)和約束函數(shù)的要求十分寬松；算法的基本思想都是來(lái)自對(duì)某種自然規(guī)律的模仿，具有人工智能的特點(diǎn)；多數(shù)算法含有一個(gè)多個(gè)體的群體，尋優(yōu)過(guò)程實(shí)際上就是種群的進(jìn)化過(guò)程；理論工作相對(duì)比較薄弱，一般說(shuō)來(lái)都不能保證收斂到最優(yōu)解。3.1概述——新的算法的一些共同特點(diǎn)172023/10/3不以達(dá)到某個(gè)最優(yōu)性條件或找到理論上的精確最優(yōu)解為目標(biāo)，而是更由于算法理論薄弱，最早被稱(chēng)為“現(xiàn)代啟發(fā)式(ModernHeuristics)”或“高級(jí)啟發(fā)式(AdvancedHeuristics)”；從其人工智能的特點(diǎn)，被稱(chēng)為“智能計(jì)算(IntelligentComputation)”或“智能優(yōu)化算法(IntelligentOptimizationAlgorithms)”；從不以精確解為目標(biāo)的特點(diǎn)，又被歸到“軟計(jì)算(SoftComputing)”方法中；從種群進(jìn)化的特點(diǎn)看，它們又可以稱(chēng)為“進(jìn)化計(jì)算(EvolutionaryCompuation)”；從模仿自然規(guī)律的特點(diǎn)出發(fā)，又有人將它們稱(chēng)為“自然計(jì)算(NaturalComputing)”。3.1概述——新的優(yōu)化方法的不同名稱(chēng)182023/10/3由于算法理論薄弱，最早被稱(chēng)為“現(xiàn)代啟發(fā)式(ModernHe應(yīng)用智能優(yōu)化算法解決各類(lèi)問(wèn)題是重點(diǎn)；算法改進(jìn)有很大的創(chuàng)新空間；多種算法結(jié)合的混合算法是一條捷徑；不提倡刻意去追求理論成果；算法性能的測(cè)算是一項(xiàng)要下真功夫的工作；選擇測(cè)試?yán)}的一般規(guī)律：網(wǎng)上題庫(kù)中的例題→文獻(xiàn)中的例題→隨機(jī)產(chǎn)生的例題→實(shí)際應(yīng)用問(wèn)題→自己編的例題；算法性能測(cè)試的主要指標(biāo)：達(dá)優(yōu)率(解的目標(biāo)平均值和最優(yōu)解的目標(biāo)值的比，所有解的目標(biāo)值的標(biāo)準(zhǔn)差等)，計(jì)算速度，計(jì)算大規(guī)模問(wèn)題的能力；創(chuàng)造出新算法3.1概述——怎樣學(xué)習(xí)研究智能優(yōu)化方法192023/10/3應(yīng)用智能優(yōu)化算法解決各類(lèi)問(wèn)題是重點(diǎn)；3.1概述——怎樣學(xué)習(xí)3.2

遺傳算法202023/10/33.2遺傳算法202023/8/1生物在自然界中的生存繁衍，顯示出了其對(duì)自然環(huán)境的優(yōu)異自適應(yīng)能力。受其啟發(fā)，人們致力于對(duì)生物各種生存特性的機(jī)理研究和行為模擬，為人工自適應(yīng)系統(tǒng)的設(shè)計(jì)和開(kāi)發(fā)提供了廣闊的前景。遺傳算法(GeneticAlgorithm，簡(jiǎn)稱(chēng)GA)就是這種生物行為的計(jì)算機(jī)模擬中令人矚目的重要成果。基于對(duì)生物遺傳和進(jìn)化過(guò)程的計(jì)算機(jī)模擬，遺傳算法使得各種人工系統(tǒng)具有優(yōu)良的自適應(yīng)能力和優(yōu)化能力。遺傳算法所借鑒的生物學(xué)基礎(chǔ)就是生物的遺傳和進(jìn)化。3.2遺傳算法——概要212023/10/3生物在自然界中的生存繁衍，顯示出了其對(duì)自然環(huán)境的優(yōu)異自適應(yīng)能雖然人們還未完全揭開(kāi)遺傳與進(jìn)化的奧秘，既沒(méi)有完全掌握其機(jī)制，也不完全清楚染色體編碼和譯碼過(guò)程的細(xì)節(jié)，更不完全了解其控制方式，但遺傳與進(jìn)化的以下幾個(gè)特點(diǎn)卻為人們所共識(shí)：(1)生物的所有遺傳信息都包含在其染色休中，染色體決定了生物的性狀。(2)染色體是由基因及其有規(guī)律的排列所構(gòu)成的，遺傳和進(jìn)化過(guò)程發(fā)生在染色體上。(3)生物的繁殖過(guò)程是由其基因的復(fù)制過(guò)程來(lái)完成的：(4)通過(guò)同源染色體之間的交叉或染色體的變異會(huì)產(chǎn)生新的物種，使生物呈現(xiàn)新的性狀。(5)對(duì)環(huán)境適應(yīng)性好的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體有更多的機(jī)會(huì)遺傳到下一代。3.2遺傳算法——概要222023/10/3雖然人們還未完全揭開(kāi)遺傳與進(jìn)化的奧秘，既沒(méi)有完全掌握其機(jī)制，遺傳算法是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。它最早由美國(guó)密執(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é)，形成了遺傳算法的基本框架。3.2遺傳算法——概要232023/10/3遺傳算法是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過(guò)程而形成的一種自式中，為決策變量，f(X)為目標(biāo)函數(shù)，后兩個(gè)式子為約束條件，U是基本空間，R是U的一個(gè)子集。對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問(wèn)題(求函數(shù)最小值也類(lèi)同)，一般可描述為下述數(shù)學(xué)規(guī)劃模型：滿(mǎn)足約束條件的解X稱(chēng)為可行解，集合R表示由所有滿(mǎn)足約束條件的解所組成的一個(gè)集合，叫做可行解集合。它們之間的關(guān)系如圖所示。3.2遺傳算法——概要242023/10/3式中，為決策變量，f(X)為U基本空間R可行解集合X可行解3.2遺傳算法——概要252023/10/3U基本空間R可行解集合X可行解3.2遺傳算法——概要252對(duì)于上述最優(yōu)化問(wèn)題，目標(biāo)函數(shù)和約束條件種類(lèi)繁多，有的是線(xiàn)性的，有的是非線(xiàn)性的；有的是連續(xù)的，有的是離散的；有的是單峰值的，有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識(shí)到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實(shí)，因而求出其近似最優(yōu)解或滿(mǎn)意解是人們的主要著眼點(diǎn)之一。3.2遺傳算法——概要262023/10/3對(duì)于上述最優(yōu)化問(wèn)題，目標(biāo)函數(shù)和約束條件種類(lèi)繁多，有的是線(xiàn)性的遺傳算法中，將n維決策向量用n個(gè)記號(hào)xi(n=l，2，

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

—般情況下，染色體的長(zhǎng)度n是固定的，但對(duì)一些問(wèn)題n也可以是變化的。根據(jù)不同的情況，這里的等位基因可以是一組整數(shù)，也可以是某一范圍內(nèi)的實(shí)數(shù)值，或者是純粹的一個(gè)記號(hào)。最簡(jiǎn)單的等位基因是由0和1這兩個(gè)整數(shù)組成的。相應(yīng)的染色體就可表示為一個(gè)二進(jìn)制符號(hào)串。3.2遺傳算法——概要272023/10/3遺傳算法中，將n維決策向量這種編碼所形成的排列形式X是個(gè)體的基因型，與它對(duì)應(yīng)的X值是個(gè)體的表現(xiàn)型。通常個(gè)體的表現(xiàn)型和其基因型是一一對(duì)應(yīng)的，但有時(shí)也允許基因型和表現(xiàn)型是多對(duì)一的關(guān)系。染色休X也稱(chēng)為個(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組成了問(wèn)題的解空間。對(duì)問(wèn)題最優(yōu)解的搜索是通過(guò)對(duì)染色體X的搜索過(guò)程來(lái)進(jìn)行的，從而由所有的染色體X就組成了問(wèn)題的搜索空間。通過(guò)編碼和解碼，使得問(wèn)題的解空間和搜索空間一一對(duì)應(yīng)。3.2遺傳算法——概要282023/10/3這種編碼所形成的排列形式X是個(gè)體的基因型，與它對(duì)應(yīng)的X值是個(gè)生物的進(jìn)化是以集團(tuán)為主體的。與此相對(duì)應(yīng)，遺傳算法的運(yùn)算對(duì)象是出M個(gè)個(gè)體所組成的集合，稱(chēng)為群體。與生物一代一代的自然進(jìn)化過(guò)程相類(lèi)似，遺傳算法的運(yùn)算過(guò)程也是一個(gè)反復(fù)迭代的過(guò)程，第t代群體記做P(t)，經(jīng)過(guò)一代遺傳和進(jìn)化后，得到第t+l代群體，它們也是由多個(gè)個(gè)體組成的集合，記做P(t+1)。這個(gè)群體不斷地經(jīng)過(guò)遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體更多地遺傳到下一代，這樣最終在群體中將會(huì)得到一個(gè)優(yōu)良的個(gè)體X，它所對(duì)應(yīng)的表現(xiàn)型X將達(dá)到或接近于問(wèn)題的最優(yōu)解X*。生物的進(jìn)化過(guò)程主要是通過(guò)染色體之間的交叉和染色體的變異來(lái)完成的，與此相對(duì)應(yīng)，遺傳算法中最優(yōu)解的搜索過(guò)程也模仿生物的這個(gè)進(jìn)化過(guò)程，使用所謂的遺傳算子(geneticoperators)作用于群體P(t)中，進(jìn)行下述遺傳操作，從而得到新一代群體P(t+1)。3.2遺傳算法——概要292023/10/3生物的進(jìn)化是以集團(tuán)為主體的。與此相對(duì)應(yīng)，遺傳算法的運(yùn)算對(duì)象是選擇(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è)概率(稱(chēng)為交叉概率，crossoverrate)交換它們之間的部分染色體。變異(mutation)：對(duì)群體P(t)中的每一個(gè)個(gè)體，以某一概率(稱(chēng)為變異概率，mutationrate)改變某一個(gè)或某一些基因座上的基因值為其他的等位基因。3.2遺傳算法——概要302023/10/3選擇(selection)：根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的使用上述三種遺傳算子(選擇算子、交叉算子、變異算子)的遺傳算法的主要運(yùn)算過(guò)程如下所述：步驟一：初始化。設(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)算。將選擇算子作用于群體。3.2遺傳算法——運(yùn)算過(guò)程312023/10/3使用上述三種遺傳算子(選擇算子、交叉算子、變異算子)的遺傳算步驟四：交叉運(yùn)算。將交叉算子作用于群體。步驟五：變異運(yùn)算。將變異算于作用于群體。群體P(t)經(jīng)過(guò)選擇、交叉、變異運(yùn)算之后得到下一代群體P(t+1)。步驟六：終止條件判斷。若t

T，則：t

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

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

時(shí)，碼長(zhǎng)m的計(jì)算公式為：相應(yīng)的解碼公式為：3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)——編碼和解碼352023/10/3用二進(jìn)制編碼來(lái)離散自變量，碼長(zhǎng)根據(jù)離散精度來(lái)確定。相應(yīng)的解碼在遺傳算法中，以個(gè)體適應(yīng)度的大小來(lái)確定該個(gè)體被遺傳到下一代群體中的概率。個(gè)體的適應(yīng)度越大，該個(gè)體被遺傳到下一代的概率也越大；反之，個(gè)體的適應(yīng)度越小，該個(gè)體被遺傳到下一代的概率也越小?；具z傳算法使用比例選擇算子來(lái)確定群體中各個(gè)個(gè)體遺傳到下一代群體中的數(shù)量。為正確計(jì)算不同情況下各個(gè)個(gè)體的遺傳概率，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—適應(yīng)度評(píng)價(jià)1/4362023/10/3在遺傳算法中，以個(gè)體適應(yīng)度的大小來(lái)確定該個(gè)體被遺傳到下一代群對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，理論上只需簡(jiǎn)單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn)化為求目標(biāo)函數(shù)最大值的優(yōu)化問(wèn)題，即：

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)化問(wèn)題中的目標(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)系，由它來(lái)保證個(gè)體適應(yīng)度總?cè)》秦?fù)值。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—適應(yīng)度評(píng)價(jià)2/4372023/10/3對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，理論上只需簡(jiǎn)單地對(duì)其增加一個(gè)為滿(mǎn)足適應(yīng)度取非負(fù)值的要求，基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)值f(X)變換為個(gè)體的適應(yīng)度F(x)。式中，Cmin為一個(gè)適當(dāng)?shù)叵鄬?duì)比較小的數(shù)，它可以用下面幾種方法之一來(lái)選擇：

方法一：對(duì)于求目標(biāo)函數(shù)最大值的優(yōu)化問(wèn)題，變換方法為：

預(yù)先指定的一個(gè)較小的數(shù)。

進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。

當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—適應(yīng)度評(píng)價(jià)3/4382023/10/3為滿(mǎn)足適應(yīng)度取非負(fù)值的要求，基本遺傳算法一般采用下面兩種方法方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，變換方法為：

式中，Cmax為一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可以用下面幾種方法之一來(lái)選擇：

預(yù)先指定的一個(gè)較大的數(shù)。

進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。

前代或最近幾代群體中的最大目標(biāo)函數(shù)值。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—適應(yīng)度評(píng)價(jià)4/4392023/10/3方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，變換方法為：式中，選擇算子或復(fù)制算子的作用是從當(dāng)前代群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。最常用和最基本的選擇算子是比例選擇算子。比例選擇實(shí)際上是一種有退還隨機(jī)選擇，也叫做賭盤(pán)(Roulettewheel)選擇，因?yàn)檫@種選擇方式與賭博中的賭盤(pán)操作原理頗為相似。所謂比例選擇算子，是指?jìng)€(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子1/4402023/10/3選擇算子或復(fù)制算子的作用是從當(dāng)前代群體中選擇出一些比較優(yōu)良的整個(gè)賭盤(pán)被分為大小不同的一些扇面，分別對(duì)應(yīng)著價(jià)值各不相同的一些賭博物品。當(dāng)旋轉(zhuǎn)著的賭盤(pán)自然停下來(lái)時(shí)，其指針?biāo)干让嫔系奈锲肪蜌w賭博者所有。雖然賭盤(pán)的指針具體停止在哪一個(gè)扇面是無(wú)法預(yù)測(cè)的，但指針指向各個(gè)扇面的概率卻是可以估計(jì)的，它與各個(gè)扇面的圓心角大小成正比：圓心角越大，停在該扇面的可能性也越大；圓心角越小，停在該扇面的可能性也越小。與此類(lèi)似，在遺傳算法中，整個(gè)群體被各個(gè)個(gè)體所分割，各個(gè)個(gè)體的適應(yīng)度在全部個(gè)體的適應(yīng)度之和中所占比例也大小不一，這個(gè)比例值瓜分了整個(gè)賭盤(pán)盤(pán)面，它們也決定了各個(gè)個(gè)體被遺傳到下一代群體中的概率。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子2/4412023/10/3整個(gè)賭盤(pán)被分為大小不同的一些扇面，分別對(duì)應(yīng)著價(jià)值各不相同的一金銀銅鐵10％20％30％40％3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子3/4422023/10/3金銀銅鐵10％20％30％40％3.2遺傳算法——基本遺傳令：3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子4/4432023/10/3令：3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—比例選擇算子4算子的具體執(zhí)行過(guò)程如下：(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)。若染色體的長(zhǎng)度為n，則共有(n-1)個(gè)可能的交叉點(diǎn)位置。(3)對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—單點(diǎn)交叉算子1/2442023/10/3算子的具體執(zhí)行過(guò)程如下：(1)對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配單點(diǎn)交叉示意如下所示：

A：1011011100A’：

1011011111B：0001110011B’；

0001110000單點(diǎn)交叉交叉點(diǎn)3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—單點(diǎn)交叉算子2/2452023/10/3單點(diǎn)交叉示意如下所示：A：10110111對(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)算或用其它等位基因值來(lái)代替，從而產(chǎn)生出一個(gè)新的個(gè)體。3.2遺傳算法——基本遺傳算法的實(shí)現(xiàn)—基本位變異算子462023/10/3對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行基本遺傳算法有下述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é)果和求解效率都有一定的影響，但目前尚無(wú)合理選擇它們的理論依據(jù)。3.2遺傳算法——遺傳算法的運(yùn)行參數(shù)

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

2/2482023/10/3在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過(guò)多次試算后才能確定出這些該函數(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)化模型492023/10/3該函數(shù)有兩個(gè)局部極大值，分別是f(2.048,-2.048)用長(zhǎng)度為l0位的二進(jìn)制編碼串來(lái)分別表示二個(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位長(zhǎng)的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長(zhǎng)的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的染色體編碼方法。例如X：000011011l1101110001就表示一個(gè)個(gè)體的基因型，其中前10位表示x1，后10為表示x2。3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定編碼方法502023/10/3用長(zhǎng)度為l0位的二進(jìn)制編碼串來(lái)分別表示二個(gè)決策變量x1，x2解碼時(shí)需先將20位長(zhǎng)的二進(jìn)制編碼串切斷為二個(gè)10位長(zhǎng)的二進(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的解碼公式為：3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定解碼方法512023/10/3解碼時(shí)需先將20位長(zhǎng)的二進(jìn)制編碼串切斷為二個(gè)10位長(zhǎng)的二進(jìn)制第六步：設(shè)計(jì)遺傳算子?？芍?，Rosenbrock函數(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)算使用基本位變異算子。3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定個(gè)體評(píng)價(jià)方法522023/10/3第六步：設(shè)計(jì)遺傳算子?？芍?，Rosenbrock函數(shù)的值域總對(duì)于本例，設(shè)定基本遺傳算法的運(yùn)行參數(shù)如下：群體大?。篗＝80終止代數(shù)：T＝200交叉概率：pc＝0.6變異概率：pm＝0.001通過(guò)上述七個(gè)步驟就可構(gòu)成用于Rosenbrock函數(shù)優(yōu)化計(jì)算的基本遺傳算法。3.2遺傳算法——在函數(shù)優(yōu)化中的應(yīng)用—確定運(yùn)行參數(shù)532023/10/3對(duì)于本例，設(shè)定基本遺傳算法的運(yùn)行參數(shù)如下：群體大?。篗＝80myGA.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)用—程序542023/10/3myGA.mmyGA2.m3.2遺傳算法——在函數(shù)優(yōu)化中的傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身來(lái)進(jìn)行優(yōu)化計(jì)算，但遺傳算法不是直接以決策變量的值，而是以決策變量的某種形式的編碼為運(yùn)算對(duì)象。這種對(duì)決策變量的編碼處理方式，使得我們?cè)趦?yōu)化計(jì)算過(guò)程中可以借鑒生物學(xué)中染色體和基因等概念，可以模仿自然界中生物的遺傳和進(jìn)化等機(jī)理，也使得我們可以方便地應(yīng)用遺傳操作算子。特別是對(duì)一些無(wú)數(shù)值概念或很難有數(shù)值概念，而只有代碼概念的優(yōu)化問(wèn)題，編碼處理方式更顯示出了其獨(dú)持的優(yōu)越性。3.2遺傳算法——特點(diǎn)—以決策變量的編碼作為運(yùn)算對(duì)象552023/10/3傳統(tǒng)的優(yōu)化算法往往直接利用決策變量的實(shí)際值本身來(lái)進(jìn)行優(yōu)化計(jì)算傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，而且往往需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息才能確定搜索方向。而遺傳算法僅使用由目標(biāo)函數(shù)值變換來(lái)的適應(yīng)度函數(shù)值，就可確定進(jìn)一步的搜索方向和搜索范圍，無(wú)需目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他一些輔助信息。這個(gè)特性對(duì)很多目標(biāo)函數(shù)無(wú)法或是很難求導(dǎo)數(shù)的函數(shù)，或?qū)?shù)不存在的函數(shù)的優(yōu)化問(wèn)題，以及組合優(yōu)化問(wèn)題等，應(yīng)用遺傳算法時(shí)就顯得比較方便，因?yàn)樗荛_(kāi)了函數(shù)求導(dǎo)這個(gè)障礙。再者，直接利用目標(biāo)函數(shù)值或個(gè)體適應(yīng)度，也可使得我們可以把搜索范圍集中到適應(yīng)度較高的部分搜索空間中，從而提高了搜索效率。3.2遺傳算法——特點(diǎn)—直接以目標(biāo)函數(shù)值作為搜索信息562023/10/3傳統(tǒng)的優(yōu)化算法不僅需要利用目標(biāo)函數(shù)值，而且往往需要目標(biāo)函數(shù)的傳統(tǒng)的優(yōu)化算法往往是從解空間個(gè)的一個(gè)初始點(diǎn)開(kāi)始最優(yōu)解的這代搜索過(guò)程，單個(gè)搜索點(diǎn)所提供的搜索信息畢竟不多，所以搜索效率不高，有時(shí)其至使搜索過(guò)程陷入局部最優(yōu)解而停滯不前。遺傳算法從很多個(gè)體所組成的一個(gè)初始群體開(kāi)始最優(yōu)解的搜索過(guò)程，而不是從一個(gè)單一的個(gè)體開(kāi)始搜索。對(duì)這個(gè)群體所進(jìn)行的選擇、交叉、變異等運(yùn)算，產(chǎn)生出的乃是新一代的群體，在這之中包括了很多群體信息。這些信息可以避免搜索一些不必搜索的點(diǎn)，所以實(shí)際上相當(dāng)于搜索了更多的點(diǎn)，這是遺傳算法所特有的一種隱含并行性。3.2遺傳算法——特點(diǎn)—同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息572023/10/3傳統(tǒng)的優(yōu)化算法往往是從解空間個(gè)的一個(gè)初始點(diǎn)開(kāi)始最優(yōu)解的這代搜傳統(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)算都是以一種概率的方式來(lái)進(jìn)行的，從而增加了其搜索過(guò)程的靈活性。雖然這種概率特性也會(huì)使群體中產(chǎn)生一些適應(yīng)度不高的個(gè)體，但隨著進(jìn)化過(guò)程的進(jìn)行，新的群體中總會(huì)更多地產(chǎn)生出許多優(yōu)良的個(gè)體，實(shí)踐和理論都已證明了在一定條件下遺傳算法總是以概率1收斂于問(wèn)題的最優(yōu)解。當(dāng)然，交叉概率和變異概率等參數(shù)也會(huì)影響算法的搜索效果和搜索效率，所以如何選擇遺傳算法的參數(shù)在其應(yīng)用中是一個(gè)比較重要的問(wèn)題。而另一方面，與其他一些算法相比遺傳算法的魯棒性又會(huì)使得參數(shù)對(duì)其搜索效果的影響會(huì)盡可能地低。3.2遺傳算法——特點(diǎn)—使用概率搜索技術(shù)582023/10/3傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法，一個(gè)搜索點(diǎn)到另一約束優(yōu)化(ConstrainedOptimization)是處理具有等式和(或)不等式約束的目標(biāo)函數(shù)問(wèn)題，其一般形式可以表示為：可記約束集（可行集）為：用于操作染色體的遺傳算法常會(huì)產(chǎn)生不可行的染色體的問(wèn)題。3.2遺傳算法——約束的處理

1/3592023/10/3約束優(yōu)化(ConstrainedOptimization)——拒絕策略：拋棄進(jìn)化過(guò)程中產(chǎn)生的所有不可行解。這是遺傳算法處理約束問(wèn)題的最簡(jiǎn)單也是效率最低的方法?！迯?fù)策略：在進(jìn)化過(guò)程中獲得不可行解后，將其修復(fù)為可行解。對(duì)于很多組合優(yōu)化問(wèn)題創(chuàng)建修復(fù)過(guò)程相對(duì)容易，但可能導(dǎo)致失去種群的多樣性?！獞土P策略：對(duì)約束進(jìn)行處理的最一般的方式，是通過(guò)對(duì)不可行解的懲罰來(lái)將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題。任何對(duì)于約束的違反都要在目標(biāo)函數(shù)中添加懲罰項(xiàng)。需要設(shè)計(jì)合適的懲罰函數(shù)，不合適的懲罰函數(shù)會(huì)掩蓋目標(biāo)函數(shù)的優(yōu)化。3.2遺傳算法——約束的處理

2/3602023/10/3——拒絕策略：3.2遺傳算法——約束的處理2/36020——特殊的編碼和遺傳策略：使用特殊的編碼策略，在編碼時(shí)就充分考慮約束問(wèn)題，在編碼時(shí)產(chǎn)生的都是符合約束的染色體。為了使染色體在遺傳操作后仍然保持可行性，也有使用特殊的遺傳策略，使遺傳操作后染色體仍然保持可行。3.2遺傳算法——約束的處理

3/3612023/10/3——特殊的編碼和遺傳策略：3.2遺傳算法——約束的處理3現(xiàn)實(shí)的生產(chǎn)和生活中人們常常遇到存在的目標(biāo)超過(guò)一個(gè)，并且需要同時(shí)處理的情況，而這些不同的目標(biāo)又往往是相互沖突的，這就是多目標(biāo)優(yōu)化(MultiobjectiveOptimization)問(wèn)題。具有p個(gè)目標(biāo)的多目標(biāo)問(wèn)題的一般形式為：3.2遺傳算法——多目標(biāo)的處理1/4622023/10/3現(xiàn)實(shí)的生產(chǎn)和生活中人們常常遇到存在的目標(biāo)超過(guò)一個(gè)，并且需要同在大多數(shù)情況下，各個(gè)目標(biāo)函數(shù)間可能是沖突的。這就使得多目標(biāo)優(yōu)化問(wèn)題不存在唯一的全局最優(yōu)解，使所有目標(biāo)函數(shù)同時(shí)最優(yōu)。但是，可以存在這樣的解：對(duì)一個(gè)或幾個(gè)目標(biāo)函數(shù)不可能進(jìn)一步優(yōu)化，而對(duì)其他目標(biāo)函數(shù)不至于劣化，這樣的解稱(chēng)之為非劣最優(yōu)解，也稱(chēng)有效解，或Pareto最優(yōu)解。遺傳算法種群進(jìn)化特征使其適合于這樣的問(wèn)題。處理多目標(biāo)問(wèn)題時(shí)，遺傳算法遇到的一個(gè)主要問(wèn)題是如何根據(jù)多個(gè)目標(biāo)函數(shù)值來(lái)確定個(gè)體的適應(yīng)值，即適應(yīng)值分配機(jī)制。3.2遺傳算法——多目標(biāo)的處理2/4632023/10/3在大多數(shù)情況下，各個(gè)目標(biāo)函數(shù)間可能是沖突的。這就使得多目標(biāo)優(yōu)——向量評(píng)價(jià)方法：采用向量形式評(píng)價(jià)的適應(yīng)值度量來(lái)產(chǎn)生下一代，而不是使用標(biāo)量適應(yīng)值度量方式來(lái)評(píng)價(jià)染色體。對(duì)于有p個(gè)目標(biāo)的給定問(wèn)題，每代中的選擇過(guò)程是一個(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/4642023/10/3——向量評(píng)價(jià)方法：3.2遺傳算法——多目標(biāo)的處理3/46——基于Pareto的方法：有兩種基于Pareto的方法：Pareto排序和Pareto競(jìng)爭(zhēng)。——妥協(xié)方法：通過(guò)某種距離的度量來(lái)確定與理想解最近的解。——目標(biāo)規(guī)劃方法：采用基于排序的適應(yīng)值分配方法來(lái)判斷個(gè)體的價(jià)值。具體過(guò)程為：根據(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ī)對(duì)其進(jìn)行排序。然后采用從最好到最差的指數(shù)插值進(jìn)行個(gè)體的適應(yīng)值分配。3.2遺傳算法——多目標(biāo)的處理4/4652023/10/3——基于Pareto的方法：3.2遺傳算法——多目標(biāo)的處理GADS這個(gè)是Matlab7.0版本自帶的工具箱，全名叫GeneticAlgorithmandDirectSearchToolbox。在Matlab7.0的Help里面有對(duì)這個(gè)工具箱的詳細(xì)介紹，還有很多例子作演示。它還提供了一個(gè)圖形用戶(hù)界面的工具，名為“GeneticAlgorithmTool”，有了這個(gè)工具就可以不必輸入繁瑣的命令行參數(shù)，能方便而且直觀(guān)的觀(guān)察算法的運(yùn)行過(guò)程。在命令行里輸入“gatool”，就可以進(jìn)入該圖形用戶(hù)界面。3.2遺傳算法——MATLAB遺傳算法工具箱662023/10/3GADS這個(gè)是Matlab7.0版本自帶的工具箱，全名叫G[xfval]=ga(@fitnessfun,nvars,options)Where@fitnessfunisahandletothefitnessfunction.nvarsisthenumberofindependentvariablesforthefitnessfunction.optionsisastructurecontainingoptionsforthegeneticalgorithm.Ifyoudonotpassinthisargument,gausesitsdefaultoptions.Theresultsaregivenby:x—Pointatwhichthefinalvalueisattainedfval—Finalvalueofthefitnessfunction3.2遺傳算法——MATLAB遺傳算法工具箱—命令行函數(shù)672023/10/3[xfval]=ga(@fitnessfun,nva3.2遺傳算法——MATLAB遺傳算法工具箱—圖形用戶(hù)界面682023/10/33.2遺傳算法——MATLAB遺傳算法工具箱—圖形用戶(hù)界面求下列函數(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í)例692023/10/3求下列函數(shù)的最小值：建立適應(yīng)函數(shù)FitFun.m文件：3.2適應(yīng)度函數(shù)的文件名待尋優(yōu)變量的個(gè)數(shù)變量的下邊界和上邊界3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例702023/10/3適應(yīng)度函數(shù)的文件名待尋優(yōu)變量的個(gè)數(shù)變量的下邊界和上邊界3.2尋優(yōu)結(jié)果優(yōu)化參數(shù)迭代次數(shù)3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例712023/10/3尋優(yōu)結(jié)果優(yōu)化參數(shù)迭代次數(shù)3.2遺傳算法——MATLAB遺傳該例題的理論最小值為0.436，且在(x1,x2,x3,x4,x5)=(1,1,1,1,1)時(shí)取到。從結(jié)果的比較可以看出，遺傳算法求出的結(jié)果精度是很高的。3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例722023/10/3該例題的理論最小值為0.436，且在(x1,x2,x3,x4建立適應(yīng)函數(shù)FitFun.m文件：functiony=FitFun(x)y=x(1)^2+2*x(2)^2-4*x(1)-8*x(2)+15;建立非線(xiàn)性約束函數(shù)NonCon.m文件：function[c,ceq]=NonCon(x)c=x(1)^2+x(2)^2-9;ceq=[];3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例732023/10/3建立適應(yīng)函數(shù)FitFun.m文件：建立非線(xiàn)性約束函數(shù)NonC非線(xiàn)性約束函數(shù)Nonlinearconstraintfunctiondefinesthenonlinearconstraints.Specifythefunctionasananonymousfunctionorasafunctionhandleoftheform@nonlcon,wherenonlcon.misanM-filethatreturnsthevectorscandceq.Thenonlinearequalitiesareoftheformceq=0,andthenonlinearinequalitiesareoftheformc

0.線(xiàn)性等式和不等式約束3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例742023/10/3非線(xiàn)性約束函數(shù)Nonlinearconstraintfu此例題的理論最小值為3，在(x1,x2)=(2,2)時(shí)取得。從結(jié)果可以看出，結(jié)果精度是很高的。3.2遺傳算法——MATLAB遺傳算法工具箱—應(yīng)用實(shí)例752023/10/3此例題的理論最小值為3，在(x1,x2)=(2,2)時(shí)取得。如果雙親的基因非常相近，所產(chǎn)生的后代相對(duì)于雙親也必然比較接近。這樣所期待的性能改善也必然較小。類(lèi)似于“近親繁殖”。所以基因模式的單一性不僅減慢進(jìn)化歷程，而且可能導(dǎo)致進(jìn)化停滯，過(guò)早地收斂于局部的極值解。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è)體被淘汰。3.2遺傳算法——改進(jìn)—自適應(yīng)遺傳算法762023/10/3如果雙親的基因非常相近，所產(chǎn)生的后代相對(duì)于雙親也必然比較接近因此，自適應(yīng)遺傳算法能夠提供相對(duì)某個(gè)解的最佳交叉概率和變異概率。自適應(yīng)遺傳算法中交叉概率和變異概率的計(jì)算公式為：3.2遺傳算法——改進(jìn)—自適應(yīng)遺傳算法772023/10/3因此，自適應(yīng)遺傳算法能夠提供相對(duì)某個(gè)解的最佳交叉概率和變異概設(shè)PG為上一代進(jìn)化到下一代時(shí)被替換的個(gè)體的比例，則按此比例，部分個(gè)體被新的個(gè)體所取代，而其他部分的個(gè)體則直接進(jìn)入下一代。PG越大，進(jìn)化得越快，但算法的穩(wěn)定性和收斂性將受到影響；而PG越小，算法的穩(wěn)定性越好，但進(jìn)化速度將變慢?？梢?jiàn)，應(yīng)該尋求運(yùn)行速度與穩(wěn)定性、收斂性之間的協(xié)調(diào)平衡。3.2遺傳算法——改進(jìn)—部分替代法782023/10/3設(shè)PG為上一代進(jìn)化到下一代時(shí)被替換的個(gè)體的比例，則按此比例，這種方法對(duì)于每代中一定數(shù)量的最優(yōu)個(gè)體，使之直接進(jìn)入下一代。這樣可以防止優(yōu)秀個(gè)體由于復(fù)制、交叉或變異中的偶然因素而被破壞掉。這是增強(qiáng)算法穩(wěn)定性和收斂性的有效方法。但同時(shí)也可能使遺傳算法陷入局部的極值范圍。3.2遺傳算法——改進(jìn)—優(yōu)秀個(gè)體保護(hù)法792023/10/3這種方法對(duì)于每代中一定數(shù)量的最優(yōu)個(gè)體，使之直接進(jìn)入下一代。這該方法將一個(gè)總的群體分為若干個(gè)子群，各子群將具有略微不同的基因模式，它們各自的遺傳過(guò)程具有相對(duì)的獨(dú)立性和封閉性，因而進(jìn)化的方向也略有差異，從而保證了搜索的充分性及收斂結(jié)果的全局最優(yōu)性。另一方面，在各子群之間又以一定的比例定期地進(jìn)行優(yōu)良個(gè)體的遷移，即每個(gè)子群將其中最優(yōu)的幾個(gè)個(gè)體輪流送到其他子群中。這樣做的目的是期望使各子群能共享優(yōu)良的基因模式以防止某些子群向局部最優(yōu)方向收斂。分布式遺傳算法模擬了生物進(jìn)化過(guò)程中的基因隔離和基因遷移，即各子群之間有相關(guān)的封閉性，又有必要的交流和溝通。研究表明，在總的種群個(gè)數(shù)相同的情況下，分布式遺傳算法可以得到比單一種群遺傳算法更好的效果。3.2遺傳算法——改進(jìn)—分布式遺傳算法802023/10/3該方法將一個(gè)總的群體分為若干個(gè)子群，各子群將具有略微不同的基其它改進(jìn)

——順序選擇遺傳算法

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

——大變異遺傳算法

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

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

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

ij

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

ij(t)

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

ij(0)＝C。n：城市數(shù)目3.3蟻群算法——應(yīng)用于TSP問(wèn)題的基本算法—基本符號(hào)992023/10/3bi(t)(i=1,2,,n)：在t時(shí)刻城市i的螞蟻數(shù)螞蟻k(k=1,2,

,m)在運(yùn)動(dòng)過(guò)程中，根據(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問(wèn)題的基本算法—基本符號(hào)1002023/10/3螞蟻k(k=1,2,,m)在運(yùn)動(dòng)過(guò)程中，根據(jù)各條路徑上積tabuk(k=1,2,

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

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

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

<1來(lái)避免路徑上信息素的無(wú)限累加。3.3蟻群算法——應(yīng)用于TSP問(wèn)題的基本算法—基本符號(hào)1022023/10/3為了避免信息素過(guò)多而淹沒(méi)啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛲瓿蓪?duì)根據(jù)信息素更新策略的不同，DorigoM提出了三種不同的基本蟻群算法模型，分別稱(chēng)為蟻周模型、蟻量模型和蟻密模型。三種模型的差別在于求法不同。3.3蟻群算法——應(yīng)用于TSP問(wèn)題的基本算法—信息素修改ant-cyclealgorithm（蟻環(huán)算法）蟻環(huán)算法（蟻周算法）的特點(diǎn)是行走的路徑越短，對(duì)應(yīng)保存的信息素的值就越大。1032023/10/3根據(jù)信息素更新策略的不同，DorigoM提出了三種不同的基ant-quantityalgorithm（蟻量算法）ant-densityalgorithm（蟻密算法）信息濃度會(huì)因?yàn)槌鞘芯嚯x的減小而增大。3.3蟻群算法——應(yīng)用于TSP問(wèn)題的基本算法—信息素修改1042023/10/3ant-quantityalgorithm（蟻量算法）an蟻周模型利用整體信息，螞蟻完成一個(gè)循環(huán)后才更新所有路徑上的信息。蟻量和蟻密模型利用局部信息，螞蟻每走一步就要更新路徑上的信息素。蟻周模型在求解TSP問(wèn)題時(shí)效果較好，應(yīng)用也比較廣泛。3.3蟻群算法——應(yīng)用于TSP問(wèn)題的基本算法—信息素修改1052023/10/3蟻周模型利用整體信息，螞蟻完成一個(gè)循環(huán)后才更新所有路徑上的信（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ì)算各螞蟻的路徑長(zhǎng)度Lk；記錄當(dāng)前最好解。（4）修改信息素。（5）tt+1。（6）若t<預(yù)定的迭代次數(shù)，且無(wú)退化行為（即找到的都是相同的解），則轉(zhuǎn)步驟2。（7）輸出目前最好解。3.3蟻群算法——應(yīng)用于TSP問(wèn)題的基本算法1062023/10/3（1）t0（t為迭代步數(shù)或搜索次數(shù)）；參數(shù)初始化。3.33.3蟻群算法——應(yīng)用于TSP問(wèn)題的基本算法1072023/10/33.3蟻群算法1072023/8/1ACO蟻環(huán)算法偽代碼：begin初始化過(guò)程：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中；}