遺傳算法天津大學(xué)課件

智能計(jì)算的國(guó)際期刊IEEETransactionsonEvolutionaryComputationAppliedSoftComputingSoftComputingIEEETransactionsonSystems,ManandCyberneticsIEEETransactionsonNeuralNetworksArtificialIntelligence

IEEEComputationalIntelligenceMagazine

IEEETransactionsonComputationalIntelligenceandAIinGamesNeuralNetworksExpertSystemswithApplicationsMachineLearningComputersandOperationsResearchOperationsResearch智能計(jì)算的國(guó)際期刊IEEETransactionson12參考書

[1]李敏強(qiáng)，寇紀(jì)淞，林丹，李書全著.遺傳算法的基本理論與應(yīng)用.北京：科學(xué)出版社，2004.[2]邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法.北京:清華大學(xué)出版社,2005.[3]王凌.智能優(yōu)化算法及其應(yīng)用.北京:清華大學(xué)出版社,2001.2參考書23[4]王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn).西安:西安交通大學(xué)出版社,2002.[5]黃席樾等.現(xiàn)代智能算法理論及應(yīng)用.北京：科學(xué)出版社,2005.[6]高尚,楊靜宇.群智能算法及其應(yīng)用.北京:中國(guó)水利水電出版社,2006.3[4]王小平,曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)34授課方式教師講授專題報(bào)告學(xué)生討論教師講授：(專題報(bào)告+學(xué)生討論)=2：1考試：閉卷、開卷或者大作業(yè)成績(jī)=平時(shí)（30%）+考試（70%）4授課方式教師講授45學(xué)生報(bào)告及討論（每人15+5分鐘）遺傳算法3次（基本+高級(jí)+應(yīng)用）模擬退火1次（基本原理）禁忌搜索1次（基本原理）模擬退火和禁忌搜索算法應(yīng)用1次蟻群算法1次（基本原理）粒子群優(yōu)化1次（基本原理）蟻群算法和粒子群優(yōu)化應(yīng)用1次5學(xué)生報(bào)告及討論（每人15+5分鐘）遺傳算法356內(nèi)容安排遺傳算法模擬退火禁忌搜索蟻群算法粒子群優(yōu)化6內(nèi)容安排遺傳算法67智能計(jì)算的基本思想智能計(jì)算（軟計(jì)算）就是借用自然界生物規(guī)律的啟迪，根據(jù)其原理，模仿設(shè)計(jì)求解問題的算法。人工神經(jīng)網(wǎng)絡(luò)技術(shù)、遺傳算法、進(jìn)化規(guī)劃、模擬退火技術(shù)和群智能技術(shù)等?！胺律鷮W(xué)”在計(jì)算智能的發(fā)展中起到了很大的推動(dòng)作用（鋸子）。從自然的規(guī)律中得到啟迪,利用其原理進(jìn)行算法設(shè)計(jì)，就是智能計(jì)算的思想。模仿海豚皮而構(gòu)造的“海豚皮游泳衣”；依照鯨魚皮構(gòu)造，造成一個(gè)薄膜蒙在飛機(jī)的表面(節(jié)能3%)；依照蜘蛛的行走發(fā)明液壓步行機(jī)。7智能計(jì)算的基本思想智能計(jì)算（軟計(jì)算）就是借用自然界生物規(guī)律78智能優(yōu)化算法及其特點(diǎn)智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)、且適合于并行處理的算法。這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗(yàn)，理論上可以在一定的時(shí)間內(nèi)找到最優(yōu)解或近似最優(yōu)解。它們的共同特點(diǎn)：都是從任一解出發(fā)，按照某種機(jī)制，以一定的概率在整個(gè)求解空間中探索最優(yōu)解。由于它們可以把搜索空間擴(kuò)展到整個(gè)問題空間，因而具有全局優(yōu)化性能。8智能優(yōu)化算法及其特點(diǎn)智能優(yōu)化算法又稱為現(xiàn)代啟發(fā)式算法，是89第一章導(dǎo)言一.最優(yōu)化的重要性二.傳統(tǒng)優(yōu)化方法的基本步驟——三步曲三.傳統(tǒng)優(yōu)化方法的局限性四.實(shí)際問題中對(duì)最優(yōu)化方法的要求五.智能優(yōu)化算法的產(chǎn)生與發(fā)展六.應(yīng)用前景局限性和研究方向、注意事項(xiàng)9第一章導(dǎo)言一.最優(yōu)化的重要性910人類的一切活動(dòng)都是認(rèn)識(shí)世界和改造世界的過程即：認(rèn)識(shí)世界→ 改造世界 ↓ ↓ (建模)(優(yōu)化)例：水電站建設(shè)

一.最優(yōu)化的重要性（1）10一.最優(yōu)化的重要性（1）1011一切學(xué)科都是建模與優(yōu)化在某個(gè)特定領(lǐng)域中的應(yīng)用 概念模型(定性)→結(jié)構(gòu)模型(圖)→ →數(shù)學(xué)模型→智能模型

一.最優(yōu)化的重要性（2）11一.最優(yōu)化的重要性（2）1112最優(yōu)化理論的發(fā)展極值理論；運(yùn)籌學(xué)的興起(OperationResearch)；數(shù)學(xué)規(guī)劃：線性規(guī)劃(LP)；非線性規(guī)劃(NLP)；動(dòng)態(tài)規(guī)劃(PP)；馬爾托夫規(guī)劃(MDP)；排隊(duì)輪；決策論；存儲(chǔ)論。最優(yōu)化理論在國(guó)民經(jīng)濟(jì)中的廣泛應(yīng)用 一.最優(yōu)化的重要性（3）12最優(yōu)化理論的發(fā)展一.最優(yōu)化的重要性（3）1213停機(jī)選擇一個(gè)初始解停止準(zhǔn)則向改進(jìn)方向移動(dòng)啟動(dòng)YN二.傳統(tǒng)優(yōu)化方法的基本步驟13停機(jī)選擇一個(gè)初始解停止準(zhǔn)則向改進(jìn)方向移動(dòng)啟動(dòng)YN二.傳統(tǒng)1314對(duì)問題中目標(biāo)函數(shù)、約束函數(shù)有很高的要求——有顯式表達(dá)，線性、連續(xù)、可微，且高階可微;只從一個(gè)初始點(diǎn)出發(fā)，難以進(jìn)行并行、網(wǎng)絡(luò)計(jì)算，難以提高計(jì)算效率；最優(yōu)性達(dá)到的條件太苛刻——問題的函數(shù)為凸，可行域?yàn)橥?；在非雙凸條件下，沒有跳出局部最優(yōu)解的能力。

三.傳統(tǒng)優(yōu)化方法的局限性14三.傳統(tǒng)優(yōu)化方法的局限性1415對(duì)問題的描述要寬松(目標(biāo)和約束函數(shù))—— 可以用一段程序來描述(程序中帶判斷、循環(huán))，函數(shù)可以非連續(xù)、非凸、非可微、非顯式；并不苛求最優(yōu)解——通常滿意解、理想解就可以了；計(jì)算快速、高效,可隨時(shí)終止(根據(jù)時(shí)間定解的質(zhì)量)；能夠處理數(shù)據(jù)、信息的不確定性(如數(shù)據(jù)的模糊性，事件的隨機(jī)性)。四.實(shí)際問題中對(duì)最優(yōu)化方法的要求15對(duì)問題的描述要寬松(目標(biāo)和約束函數(shù))——四.實(shí)際問題15161975年holland提出遺傳算法(GeneticAlgorithm)1977年Glouer提出禁忌搜索算法(TabuSearch) 1982年Kirkpatrick提出模擬退火算法(SimulatedAnnealing)人工神經(jīng)元網(wǎng)絡(luò)（NeuralNetwork）1995年Dorigo提出蟻群算法（AntColonyOptimization)五.智能優(yōu)化算法的產(chǎn)生與發(fā)展（1）161975年holland提出遺傳算法(GeneticA16171995年Kennedy&Eherhart提出粒子群優(yōu)化(ParticleSwarmOptimization)其它文化算法(CulturalAlgorithm)人工生命算法(Artificial-LifeAlgorithm)五.智能優(yōu)化算法的產(chǎn)生與發(fā)展（2）171995年Kennedy&Eherhart提出粒子群1718我們統(tǒng)稱以上算法為人工生命計(jì)算(ArtificialLifeComputation)人工生命計(jì)算+模糊邏輯(FuzzyLogic)= 軟計(jì)算(SoftComputation)人工生命計(jì)算+進(jìn)化編程= 進(jìn)化算法(Evolutionarycomputation)五.智能優(yōu)化算法的產(chǎn)生與發(fā)展（3）18我們統(tǒng)稱以上算法為人工生命計(jì)算五.智能優(yōu)化算法的產(chǎn)1819應(yīng)用前景十分廣闊——國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域局限性——不能保證最優(yōu)解，理論上不完備六.應(yīng)用前景局限性和研究方向、注意事項(xiàng)19應(yīng)用前景十分廣闊——國(guó)民經(jīng)濟(jì)的各個(gè)領(lǐng)域六.應(yīng)用前景局限性1920研究方向及注意事項(xiàng)以應(yīng)用為主，擴(kuò)大面向新問題的應(yīng)用；不要刻意做理論研究;算法改進(jìn)表現(xiàn)在以下幾個(gè)方面：?jiǎn)栴}的描述、編碼方法、算法構(gòu)造及可行性修復(fù)策略;要進(jìn)行大量的上機(jī)計(jì)算；算例的選取，以下算例的說服力降序排列：網(wǎng)上的測(cè)試用例、文獻(xiàn)中的例子、實(shí)際例子、隨機(jī)產(chǎn)生的例子、自己編的例子;如何檢驗(yàn)算法的好壞：比較計(jì)算速度、可解規(guī)模、(從不同的隨機(jī)種子出發(fā))達(dá)優(yōu)率。六.應(yīng)用前景局限性和研究方向、注意事項(xiàng)20研究方向及注意事項(xiàng)六.應(yīng)用前景局限性和研究方向、注意事項(xiàng)2021個(gè)人介紹本科畢業(yè)設(shè)計(jì)內(nèi)容是什么？研究生期間的主要學(xué)術(shù)工作、解決思路？對(duì)智能計(jì)算方法的掌握程度如何？21個(gè)人介紹本科畢業(yè)設(shè)計(jì)內(nèi)容是什么？21第二章遺傳算法進(jìn)化計(jì)算基本遺傳算法遺傳算法應(yīng)用案例遺傳算法的特點(diǎn)和優(yōu)勢(shì)遺傳算法原理第二章遺傳算法進(jìn)化計(jì)算222.1進(jìn)化計(jì)算進(jìn)化計(jì)算簡(jiǎn)介

進(jìn)化計(jì)算是研究仿照生物進(jìn)化自然選擇過程中所表現(xiàn)出來的優(yōu)先規(guī)律和方法，它用來解決，對(duì)復(fù)雜的工程技術(shù)領(lǐng)域或其他領(lǐng)域提出的而傳統(tǒng)優(yōu)化理論和方法又難以解決的優(yōu)化問題。進(jìn)化計(jì)算包括四個(gè)方面內(nèi)容：遺傳算法（GeneticAlgorithm）進(jìn)化規(guī)則（Evolutionaryprogramming）進(jìn)化策略（EvolutionaryStrategy）遺傳規(guī)劃樹圖結(jié)構(gòu)編碼2.1進(jìn)化計(jì)算進(jìn)化計(jì)算簡(jiǎn)介23遺傳算法天津大學(xué)ppt課件24從進(jìn)化算法對(duì)決策變量編碼方案的不同來看，可以有固定長(zhǎng)度的編碼（靜態(tài)編碼）和可變長(zhǎng)度的編碼（動(dòng)態(tài)編碼）從進(jìn)化算法對(duì)決策變量編碼方案的不同來看，可以有固定長(zhǎng)252.1進(jìn)化計(jì)算進(jìn)化計(jì)算的誕生（1）1990年，遺傳算法開始與進(jìn)化規(guī)劃和進(jìn)化策略有所交流。（2）1992年，進(jìn)化規(guī)劃和進(jìn)化策略這兩個(gè)不同領(lǐng)域的研究人員首次接觸到對(duì)方的研究工作，提出了“進(jìn)化計(jì)算”（EC）的方法。（3）1993年，進(jìn)化計(jì)算這一專業(yè)領(lǐng)域的第一份國(guó)際性雜志《進(jìn)化計(jì)算》在美國(guó)問世。（4）1994年，IEEE神經(jīng)網(wǎng)絡(luò)委員會(huì)主持召開了第一屆進(jìn)化計(jì)算國(guó)際會(huì)議，以后每年舉行一次。此外，此會(huì)每三年與IEEE神經(jīng)網(wǎng)絡(luò)國(guó)際會(huì)議、IEEE模糊系統(tǒng)國(guó)際會(huì)議在同一地點(diǎn)先后連續(xù)舉行，共同稱為IEEE計(jì)算智能國(guó)際會(huì)議。2.1進(jìn)化計(jì)算進(jìn)化計(jì)算的誕生26進(jìn)化計(jì)算的理論研究與應(yīng)用現(xiàn)狀由于Holland及其同事的長(zhǎng)期努力，在遺傳算法的數(shù)學(xué)基礎(chǔ)方面做了許多工作，如提出了“模式定理”，證明了一些遺傳算法的收斂性等；因此遺傳算法的理論研究成果相對(duì)成熟些。建立進(jìn)化計(jì)算的數(shù)學(xué)模型，奠定進(jìn)化計(jì)算的理論基礎(chǔ)，更深刻地認(rèn)識(shí)進(jìn)化計(jì)算的本質(zhì)。

■進(jìn)化算法的理論研究有關(guān)進(jìn)化計(jì)算的理論基礎(chǔ)主要研究以下一些問題：①進(jìn)化計(jì)算的數(shù)學(xué)模型和理論基礎(chǔ)，如算法的復(fù)雜性分析、算法的收斂性和收斂速度等。②確定特別適合采用進(jìn)化計(jì)算方法求解的問題類型，以及采用進(jìn)化計(jì)算方法求解效果不太明顯的問題類型。進(jìn)化計(jì)算的理論研究與應(yīng)用現(xiàn)狀由于Holland及27③從理論上和實(shí)際計(jì)算效果兩方面比較進(jìn)化計(jì)算方法與其他優(yōu)化方法的計(jì)算效果。④進(jìn)化計(jì)算方法與其他優(yōu)化方法結(jié)合，提出新的混合算法。⑤探索在非優(yōu)化類問題中如何使用進(jìn)化計(jì)算方法。⑥從生物進(jìn)化或自然界的各種現(xiàn)象中獲得新的啟發(fā)，提出新的方法，或?qū)ΜF(xiàn)有的進(jìn)化計(jì)算方法進(jìn)行改進(jìn)。⑦進(jìn)化計(jì)算方法在計(jì)算機(jī)上的有效實(shí)施方案，如進(jìn)化計(jì)算的并行算法等。

■進(jìn)化算法的實(shí)際應(yīng)用研究進(jìn)化計(jì)算的一些典型的應(yīng)用領(lǐng)域如下：③從理論上和實(shí)際計(jì)算效果兩方面比較進(jìn)化計(jì)算方法與28①?gòu)?fù)雜的非線性最優(yōu)化問題：對(duì)具有多個(gè)局部極值的非線性最優(yōu)化問題。普通的優(yōu)化方法一般難以找到全局最優(yōu)解，而進(jìn)化計(jì)算方法可以克服這一缺點(diǎn)，找到全局最優(yōu)解。②復(fù)雜的組合規(guī)劃或整數(shù)規(guī)劃問題：大多數(shù)組合規(guī)劃或整數(shù)規(guī)劃問題屬于NP問題，難以找到有效的求解方法；進(jìn)化計(jì)算方法廣泛用于求解這類問題，在可以承受的計(jì)算時(shí)間內(nèi)求得滿意的近似解如旅行商問題、裝箱問題等。③生物學(xué)：進(jìn)化計(jì)算起源于對(duì)生物現(xiàn)象的模擬，現(xiàn)在又反過來用于生物學(xué)的研究，如利用進(jìn)化算法研究小生境理論和生物物種的形成等。④計(jì)算機(jī)科學(xué)：進(jìn)化算法廣泛用于計(jì)算機(jī)科學(xué)的研究，如用于圖像處理和自動(dòng)識(shí)別以及文檔自動(dòng)處理等。①?gòu)?fù)雜的非線性最優(yōu)化問題：對(duì)具有多個(gè)局部極值的非29⑤工程應(yīng)用：進(jìn)化算法越來越多地用于工程實(shí)際，如通訊網(wǎng)絡(luò)的優(yōu)化設(shè)計(jì)、超大規(guī)模集成電路的布線、飛機(jī)外形的設(shè)計(jì)等。⑥社會(huì)科學(xué)：進(jìn)化計(jì)算在社會(huì)科學(xué)的許多領(lǐng)域也有廣泛應(yīng)用，如人類行為規(guī)范進(jìn)化過程的模擬、人口遷移模型的建立等。⑤工程應(yīng)用：進(jìn)化算法越來越多地用于工程實(shí)際，如通30一般來說，進(jìn)化計(jì)算的求解過程應(yīng)包括以下幾個(gè)步驟：給定一組初始解；評(píng)價(jià)當(dāng)前這組解的性能(即對(duì)目標(biāo)滿足的優(yōu)劣程度如何)；按②的解的性能從當(dāng)前這組解中選擇一定數(shù)量的解作為迭代后解的基礎(chǔ)；④對(duì)③所得到的解進(jìn)行操作(如基因重組和突變)，作為迭代后的解；若這些解已滿足要求，則停止；否則，將這些迭代得到的解作為當(dāng)前解，返回②。

進(jìn)化算法的一般框架一般來說，進(jìn)化計(jì)算的求解過程應(yīng)包括以下幾個(gè)步驟：進(jìn)化算法31進(jìn)化算法它是一種具有“魯棒性”的方法，它能適應(yīng)不同的環(huán)境、不同的問題，并且在大多數(shù)情況下都能得到比較滿意解。古典搜索方法主要有以下3類：①基于導(dǎo)數(shù)的方法：包括直接法(如爬山法等)和間接法(即求導(dǎo)數(shù)為零的點(diǎn)）。這類方法首先要求導(dǎo)數(shù)存在并容易得到；其次，這類方法一般是一種局部搜索方法，而不是一種全局搜索方法。②枚舉法：包括完全枚舉法、隱式枚舉法(分枝定界法)、動(dòng)態(tài)規(guī)劃法等。③隨機(jī)搜索方法：在問題空間中隨機(jī)選定一定數(shù)量的點(diǎn)，從中選優(yōu)。

進(jìn)化算法的特點(diǎn)及與古典搜索方法的比較進(jìn)化算法它是一種具有“魯棒性”的方法，它能適應(yīng)不同的環(huán)322.2基本遺傳算法遺傳算法（geneticalgorithms，GA）：一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法,非常適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性優(yōu)化問題。遺傳算法可廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制、規(guī)劃設(shè)計(jì)和人工生命等領(lǐng)域。2.2基本遺傳算法遺傳算法（geneticalgorit33遺傳算法的發(fā)展歷史1962年，F(xiàn)raser提出了自然遺傳算法。1965年，Holland首次提出了人工遺傳操作的重要性。1967年，Bagley首次提出了遺傳算法這一術(shù)語(yǔ)。1970年，Cavicchio把遺傳算法應(yīng)用于模式識(shí)別中。1971年，Hollstien在論文《計(jì)算機(jī)控制系統(tǒng)中人工遺傳自適應(yīng)方法》中闡述了遺傳算法用于數(shù)字反饋控制的方法。1975年，美國(guó)J.Holland出版了《自然系統(tǒng)和人工系統(tǒng)的適配》；DeJong完成了重要論文《遺傳自適應(yīng)系統(tǒng)的行為分析》。20世紀(jì)80年代以后，遺傳算法進(jìn)入興盛發(fā)展時(shí)期。遺傳算法的發(fā)展歷史1962年，F(xiàn)raser提出了自然遺傳算法34遺傳算法的基本原則

適用性：算法所能適用的問題種類。可靠性：算法對(duì)于所設(shè)計(jì)的問題，以適當(dāng)?shù)木惹蠼馄渲写蠖鄶?shù)問題的能力。收斂性：算法能否收斂到全局最優(yōu)。穩(wěn)定性：算法對(duì)其控制參數(shù)及問題數(shù)據(jù)的敏感度。生物類比：通過類比的方法引入，在生物界被認(rèn)為是有效的方法及操作。

遺傳算法的基本原則適用性：算法所能適用的問題種類。35編碼方案：編碼表示方式。適應(yīng)度函數(shù)：目標(biāo)函數(shù)。選擇策略：優(yōu)勝劣汰。控制參數(shù)：種群的規(guī)模、算法執(zhí)行的最大代數(shù)、執(zhí)行不同遺傳操作的概率等。遺傳算子：選擇(selection)；交叉(crossover)；變異(mutation)。算法的終止準(zhǔn)則：規(guī)定一個(gè)最大的演化代數(shù)，或算法在連續(xù)多少代以后解的適應(yīng)值沒有改進(jìn)。遺傳算法設(shè)計(jì)的基本內(nèi)容編碼方案：編碼表示方式。遺傳算法設(shè)計(jì)的基本內(nèi)容36

基本概念

1.個(gè)體與種群

●個(gè)體就是模擬生物個(gè)體而對(duì)問題中的對(duì)象（一般就是問題的解）的一種稱呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。

●

種群(population)就是模擬生物種群而由若干個(gè)體組成的群體,它一般是整個(gè)搜索空間的一個(gè)很小的子集?；靖拍?7

2.適應(yīng)度與適應(yīng)度函數(shù)

●

適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度,而對(duì)問題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度。

●適應(yīng)度函數(shù)(fitnessfunction)就是問題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。

2.適應(yīng)度與適應(yīng)度函數(shù)383.染色體與基因

染色體（chromosome）就是問題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如：個(gè)體染色體

9----

1001（2，5，6）----0101011103.染色體與基因394.遺傳操作

亦稱遺傳算子(geneticoperator)，就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作:

●

選擇-復(fù)制(selection-reproduction)

●

交叉(crossover，亦稱交換、交配或雜交)

●

變異(mutation，亦稱突變)

4.遺傳操作40

選擇-復(fù)制通常做法是：對(duì)于一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xi∈S的選擇概率P(xi)所決定的選中機(jī)會(huì),分N次從S中隨機(jī)選定N個(gè)染色體,并進(jìn)行復(fù)制。

這里的選擇概率P(xi)的計(jì)算公式為選擇-復(fù)制通常做法是：對(duì)于一個(gè)規(guī)模為N的種群S,按每個(gè)41得到選擇概率后，我們采用旋輪法(RouletteWheel)令，隨機(jī)產(chǎn)生當(dāng)，選擇個(gè)體

轉(zhuǎn)輪NP次NP*次做交叉；NP*次做變異；NP*(1--)不變得到選擇概率后，我們采用旋輪法(Roulette轉(zhuǎn)輪NP次42如下圖所示:注：優(yōu)良種得到較多的繁殖機(jī)會(huì)，后代很像；而很可能失去繁殖的機(jī)會(huì)。

如下圖所示:43

交叉就是互換兩個(gè)染色體某些位上的基因。

s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。

例如,設(shè)染色體s1=01001011,s2=10010101,交換其后4位基因,即交叉就是互換兩個(gè)染色體某些位上的基因。44交叉(Crossover)單切點(diǎn)交叉隨機(jī)產(chǎn)生一個(gè)斷點(diǎn)(CuttingPoint)［1，n-1］例：

011|0011101|

0110011|0110101|

0011單切點(diǎn)交叉交叉(Crossover)011|0011101|045雙切點(diǎn)交叉(交換中間段)

例：不是所有點(diǎn)都交叉，設(shè)定一個(gè)交叉概率，一般為0.9011|00|11101|

01|10011|01|

11101|

00|

10雙切點(diǎn)交叉雙切點(diǎn)交叉(交換中間段)011|00|11101|46

變異就是改變?nèi)旧w某個(gè)(些)位上的基因。例如,設(shè)染色體s=11001101將其第三位上的0變?yōu)?,即s=11001101→11101101=s′。s′也可以看做是原染色體s的子代染色體。變異就是改變?nèi)旧w某個(gè)(些)位上的基因。472.2基本遺傳算法

遺傳算法基本流程框圖生成初始種群計(jì)算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束2.2基本遺傳算法遺傳算法基本流程框圖生成初始種群計(jì)48

算法中的一些控制參數(shù)：

■

種群規(guī)模

■

最大代數(shù)

■

交叉率(crossoverrate)就是參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.4～0.99。

■

變異率(mutationrate)是指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001～0.1。算法中的一些控制參數(shù)：49基本遺傳算法

步1在搜索空間U上定義一個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；

步2隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1,s2,…,sN，組成初始種群S={s1,s2,…,sN}，置代數(shù)計(jì)數(shù)器t=1；

步3計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f()；

步4若終止條件滿足，則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束?；具z傳算法50

步5按選擇概率P(xi)所決定的選中機(jī)會(huì)，每次從S中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個(gè)染色體組成群體S1；

步6按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對(duì)進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；步5按選擇概率P(xi)所決定的選51

步7按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；

步8

將群體S3作為新一代種群，即用S3代替S，t=t+1，轉(zhuǎn)步3；

步7按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定52解空間與編碼空間的轉(zhuǎn)換 遺傳運(yùn)算是對(duì)編碼空間操作的，所以要進(jìn)行兩個(gè)空間的轉(zhuǎn)換。

解空間編碼編碼空間011001100011110011遺傳運(yùn)算后代011000000011110001解空間選擇解碼計(jì)算適值，評(píng)估適值解空間與編碼空間的轉(zhuǎn)換解空間編碼編碼空間0110011000532.3遺傳算法應(yīng)用舉例

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

y=x2

31

XY2.3遺傳算法應(yīng)用舉例例2.1利用遺傳算法求解區(qū)間54

分析

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

解

(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

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

解56

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

(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對(duì)其染色體進(jìn)57首先計(jì)算種群S1中各個(gè)體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應(yīng)度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361首先計(jì)算種群S1中各個(gè)體58再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31再計(jì)算種群S1中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為由此59賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法賭輪選擇示意s4s2s1s30.06●賭輪選擇60

在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計(jì)算公式為在算法中賭輪選擇法可用下面的子過程來模擬:①在［61選擇-復(fù)制

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

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

染色體適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001選擇-復(fù)制設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù)如62于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）于是，經(jīng)復(fù)制得群體：63交叉

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

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

交叉64變異設(shè)變異率pm=0.001。這樣，群體S1中共有5×4×0.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。變異65

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

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

s3=11011（27）,s4=10000（16）遺傳算法天津大學(xué)ppt課件66

第二代種群S2中各染色體的情況

染色體適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001第二代種群S2中各染色體的情況染色體適應(yīng)度選擇概67

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：

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

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

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

分別交換后三位基因，得

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

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

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

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的s1’=1168于是，得第三代種群S3：s1=11100（28）,s2=01001（9）

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

于是，得第三代種群S3：69第三代種群S3中各染色體的情況

染色體適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001第三代種群S3中各染色體的情況染色體適應(yīng)度選70設(shè)這一輪的選擇-復(fù)制結(jié)果為：s1’=11100（28）,s2’=11100（28）

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

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

分別交換后兩位基因，得

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

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

這一輪仍然不會(huì)發(fā)生變異。設(shè)這一輪的選擇-復(fù)制結(jié)果為：做交叉運(yùn)算，71于是，得第四代種群S4：

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

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

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

顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=73YYy=x2

8131924

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

12162527

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

9192428

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

16242831

X第四代種群及其適應(yīng)度YYy=x2813192474

例2.2用遺傳算法求解TSP。分析

由于其任一可能解——一個(gè)合法的城市序列，即n個(gè)城市的一個(gè)排列，都可以事先構(gòu)造出來。于是，我們就可以直接在解空間（所有合法的城市序列）中搜索最佳解。這正適合用遺傳算法求解。例2.2用遺傳算法求解TSP。75

（1）定義適應(yīng)度函數(shù)我們將一個(gè)合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作為一個(gè)個(gè)體。這個(gè)序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個(gè)體s的適應(yīng)度，從而適應(yīng)度函數(shù)就是（1）定義適應(yīng)度函數(shù)76

（2）對(duì)個(gè)體s=（c1,c2,…,cn,cn+1）進(jìn)行編碼。但對(duì)于這樣的個(gè)體如何編碼卻不是一件直截了當(dāng)?shù)氖虑?。因?yàn)槿绻幋a不當(dāng)，就會(huì)在實(shí)施交叉或變異操作時(shí)出現(xiàn)非法城市序列即無效解。例如，對(duì)于5個(gè)城市的TSP，我們用符號(hào)A、B、C、D、E代表相應(yīng)的城市，用這5個(gè)符號(hào)的序列表示可能解即染色體。（2）對(duì)個(gè)體s=（c1,c2,…,cn,cn+1）77然后進(jìn)行遺傳操作。設(shè)s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）實(shí)施常規(guī)的交叉或變異操作，如交換后三位，得s1’=（A,C,B,C,B,A），s2’=（A,E,D,E,D,A）或者將染色體s1第二位的C變?yōu)镋，得s1’’=（A,E,B,E,D,A）可以看出，上面得到的s1’，s2’和s1’’都是非法的城市序列。然后進(jìn)行遺傳操作。設(shè)78為此，對(duì)TSP必須設(shè)計(jì)合適的染色體和相應(yīng)的遺傳運(yùn)算。事實(shí)上，人們針對(duì)TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異等等。從而巧妙地用遺傳算法解決了TSP。為此，對(duì)TSP必須設(shè)計(jì)合適的染色體和相應(yīng)的遺792.4遺傳算法的特點(diǎn)與優(yōu)勢(shì)

◆遺傳算法的主要特點(diǎn)

——遺傳算法一般是直接在解空間搜索,而不像圖搜索那樣一般是在問題空間搜索,最后才找到解?！z傳算法的搜索隨機(jī)地始于搜索空間的一個(gè)點(diǎn)集,而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點(diǎn)或終止節(jié)點(diǎn),所以遺傳算法是一種隨機(jī)搜索算法。

2.4遺傳算法的特點(diǎn)與優(yōu)勢(shì)◆遺傳算法的主要特點(diǎn)80

——遺傳算法總是在尋找優(yōu)解,而不像圖搜索那樣并非總是要求優(yōu)解,而一般是設(shè)法盡快找到解,所以遺傳算法又是一種優(yōu)化搜索算法。——遺傳算法的搜索過程是從空間的一個(gè)點(diǎn)集(種群)到另一個(gè)點(diǎn)集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個(gè)點(diǎn)到另一個(gè)點(diǎn)地搜索。因而它實(shí)際是一種并行搜索,適合大規(guī)模并行計(jì)算,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解?！z傳算法總是在尋找優(yōu)解,而不像圖搜索那樣并非81

——遺傳算法的適應(yīng)性強(qiáng),除需知適應(yīng)度函數(shù)外,幾乎不需要其他的先驗(yàn)知識(shí)。——遺傳算法長(zhǎng)于全局搜索,它不受搜索空間的限制性假設(shè)的約束,不要求連續(xù)性,能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解?！z傳算法的適應(yīng)性強(qiáng),除需知適應(yīng)度函數(shù)外,幾乎不需82◆遺傳算法的應(yīng)用遺傳算法在人工智能的眾多領(lǐng)域便得到了廣泛應(yīng)用。例如，機(jī)器學(xué)習(xí)、聚類、控制（如煤氣管道控制）、規(guī)劃（如生產(chǎn)任務(wù)規(guī)劃）、設(shè)計(jì)（如通信網(wǎng)絡(luò)設(shè)計(jì)、布局設(shè)計(jì)）、調(diào)度（如作業(yè)車間調(diào)度、機(jī)器調(diào)度、運(yùn)輸問題）、配置（機(jī)器配置、分配問題）、組合優(yōu)化（如TSP、背包問題）、函數(shù)的最大值以及圖像處理和信號(hào)處理等等?！暨z傳算法的應(yīng)用83另一方面，人們又將遺傳算法與其他智能算法和技術(shù)相結(jié)合，使其問題求解能力得到進(jìn)一步擴(kuò)展和提高。例如，將遺傳算法與模糊技術(shù)、神經(jīng)網(wǎng)絡(luò)相結(jié)合，已取得了不少成果。

另一方面，人們又將遺傳算法與其他智能算法和技術(shù)相結(jié)合，使其問