遺傳算法論文答辯專家講座

遺傳算法及其應(yīng)用

姓名：車少帥專業(yè)：信息與計(jì)算科學(xué)指導(dǎo)教師：武斌

遺傳算法論文答辯專家講座第1頁(yè)論文章節(jié)結(jié)論遺傳算法求解函數(shù)優(yōu)化問題

遺傳算法實(shí)現(xiàn)技術(shù)

遺傳算法基本概念與原理

研究目標(biāo)與意義遺傳算法論文答辯專家講座第2頁(yè)論文主要工作第1章第2章第3章結(jié)論應(yīng)用遺傳算法來處理幾個(gè)函數(shù)優(yōu)化問題以及用MATLAB編程來實(shí)現(xiàn)遺傳算法處理函數(shù)優(yōu)化實(shí)例認(rèn)識(shí)遺傳算法基本概念，個(gè)體與種群、適應(yīng)度與適應(yīng)度函數(shù)、染色體與基因、選擇、交叉、變異等概念，掌握基本遺傳算法基本原理與步驟研究一些遺傳算法基本實(shí)現(xiàn)技術(shù)，如編碼方法，適應(yīng)度函數(shù)，選擇算子，交叉算子，變異算子等對(duì)整個(gè)畢業(yè)設(shè)計(jì)進(jìn)行全方面總結(jié)，提出本人對(duì)設(shè)計(jì)過程中各個(gè)方面看法、提議與心得體會(huì)。遺傳算法論文答辯專家講座第3頁(yè)論文研究背景、目標(biāo)與意義研究背景:

90年代，遺傳算法迎來了興盛發(fā)展時(shí)期，不論是理論研究還是應(yīng)用研究都成了十分熱門課題。尤其是遺傳算法應(yīng)用研究格外活躍，不但它應(yīng)用領(lǐng)域擴(kuò)大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)能力也顯著提升，同時(shí)產(chǎn)業(yè)應(yīng)用方面研究也在探索之中。遺傳算法論文答辯專家講座第4頁(yè)目標(biāo)與意義：

遺傳算法提供了一個(gè)求解復(fù)雜系統(tǒng)問題通用框架，它不依賴于問題詳細(xì)領(lǐng)域，對(duì)問題種類有很強(qiáng)魯棒性，所以GA在函數(shù)優(yōu)化，組合優(yōu)化、生產(chǎn)調(diào)度問題、自動(dòng)控制、機(jī)器人學(xué)、圖象處理、人工生命、遺傳編碼和機(jī)器學(xué)習(xí)等方面取得了廣泛利用。從遺傳算法理論和技術(shù)兩方面概述當(dāng)前研究現(xiàn)實(shí)狀況；描述遺傳算法主要特點(diǎn)、基本原理；應(yīng)用遺傳算法來處理函數(shù)優(yōu)化、組合優(yōu)化等方面案例。

論文研究背景、目標(biāo)與意義遺傳算法論文答辯專家講座第5頁(yè)主要內(nèi)容：認(rèn)識(shí)遺傳算法基本概念，掌握基本步驟。學(xué)習(xí)基本實(shí)現(xiàn)技術(shù)，應(yīng)用遺傳算法來處理函數(shù)優(yōu)化問題。論文研究背景、目標(biāo)與意義遺傳算法論文答辯專家講座第6頁(yè)遺傳算法基本概念與原理遺傳算法是模擬達(dá)爾文遺傳選擇和自然淘汰生物進(jìn)化過程計(jì)算模型，它是由美國(guó)Michigan大學(xué)J.Holland教授于1975年首先提出．遺傳算法作為一個(gè)新全局優(yōu)化搜索算法，以其簡(jiǎn)單通用、魯棒性強(qiáng)、適于并行處理及應(yīng)用范圍廣等顯著特點(diǎn)，奠定了它作為21世紀(jì)關(guān)鍵智能計(jì)算之一地位。遺傳算法論文答辯專家講座第7頁(yè)遺傳算法基本概念與原理遺傳算法基本思想正是基于模仿生物界遺傳學(xué)遺傳過程．它把問題參數(shù)用基因代表，把問題解用染色體代表（在計(jì)算機(jī)里用二進(jìn)制碼表示），從而得到一個(gè)由含有不一樣染色體個(gè)體組成群體．這個(gè)群體在問題特定環(huán)境里生存競(jìng)爭(zhēng)，適者有最好機(jī)會(huì)生存和產(chǎn)生后代．后代隨機(jī)化地繼承了父代最好特征，并也在生存環(huán)境控制支配下繼續(xù)這一過程。遺傳算法論文答辯專家講座第8頁(yè)遺傳算法基本概念與原理序號(hào)遺傳學(xué)概念遺傳算法概念數(shù)學(xué)概念1個(gè)體要處理基本對(duì)象、結(jié)構(gòu)也就是可行解2群體個(gè)體集合被選定一組可行解3染色體個(gè)體表現(xiàn)形式可行解編碼4基因染色體中元素編碼中元素5基因位某一基因在染色體中位置元素在編碼中位置6適應(yīng)值個(gè)體對(duì)于環(huán)境適應(yīng)程度，或在環(huán)境壓力下生存能力可行解所對(duì)應(yīng)適應(yīng)函數(shù)值7種群被選定一組染色體或個(gè)體依據(jù)入選概率定出一組可行解8選擇從群體中選擇優(yōu)勝個(gè)體，淘汰劣質(zhì)個(gè)體操作保留或復(fù)制適應(yīng)值大可行解，去掉小可行解9交叉一組染色體上對(duì)應(yīng)基因段交換依據(jù)交叉標(biāo)準(zhǔn)產(chǎn)生一組新解10交叉概率染色體對(duì)應(yīng)基因段交換概率（可能性大?。╅]區(qū)間[0,1]上一個(gè)值，普通為0.65~0.9011變異染色體水平上基因改變編碼一些元素被改變12變異概率染色體上基因改變概率（可能性大?。╅_區(qū)間(0,1)內(nèi)一個(gè)值,普通為0.001~0.0113進(jìn)化、適者生存?zhèn)€體進(jìn)行優(yōu)勝劣汰進(jìn)化，一代又一代地優(yōu)化目標(biāo)函數(shù)取到最大值，最優(yōu)可行解遺傳算法論文答辯專家講座第9頁(yè)遺傳算法基本概念與原理1.個(gè)體與種群●個(gè)體就是模擬生物個(gè)體而對(duì)問題中對(duì)象（普通就是問題解）一個(gè)稱呼，一個(gè)個(gè)體也就是搜索空間中一個(gè)點(diǎn)?！穹N群(population)就是模擬生物種群而由若干個(gè)體組成群體,它普通是整個(gè)搜索空間一個(gè)很小子集。遺傳算法論文答辯專家講座第10頁(yè)遺傳算法基本概念與原理2.適應(yīng)度與適應(yīng)度函數(shù)●適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境適應(yīng)程度,而對(duì)問題中個(gè)體對(duì)象所設(shè)計(jì)表征其優(yōu)劣一個(gè)測(cè)度?！襁m應(yīng)度函數(shù)(fitnessfunction)就是問題中全體個(gè)體與其適應(yīng)度之間一個(gè)對(duì)應(yīng)關(guān)系該函數(shù)就是遺傳算法中指導(dǎo)搜索評(píng)價(jià)函數(shù)。

遺傳算法論文答辯專家講座第11頁(yè)遺傳算法基本概念與原理3.染色體與基因染色體（chromosome）就是問題中個(gè)體某種字符串形式編碼表示。字符串中字符也就稱為基因（gene）。比如：

個(gè)體染色體9----1001

（2，5，6）----010101110遺傳算法論文答辯專家講座第12頁(yè)遺傳算法基本概念與原理4.遺傳操作亦稱遺傳算子(geneticoperator)，就是關(guān)于染色體運(yùn)算。遺傳算法中有三種遺傳操作:選擇-復(fù)制,交叉(亦稱交換、交配或雜交),變異(亦稱突變)。遺傳算法論文答辯專家講座第13頁(yè)

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

這里選擇概率P(xi)計(jì)算公式為遺傳算法基本概念與原理遺傳算法論文答辯專家講座第14頁(yè)

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

s1′=01000101,s2′=10011011能夠看做是原染色體s1和s2子代染色體。

比如,設(shè)染色體s1=01001011,s2=10010101,交換其后4位基因,即遺傳算法基本概念與原理遺傳算法論文答辯專家講座第15頁(yè)變異就是改變?nèi)旧w某個(gè)(些)位上基因。比如,設(shè)染色體s=11001101將其第三位上0變?yōu)?,即s=11001101→11101101=s′。s′也能夠看做是原染色體s子代染色體。遺傳算法基本概念與原理遺傳算法論文答辯專家講座第16頁(yè)

遺傳算法基本流程框圖生成初始種群計(jì)算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束遺傳算法基本概念與原理遺傳算法論文答辯專家講座第17頁(yè)

基本遺傳算法步驟步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(x)；步4若終止條件滿足，則取S中適應(yīng)度最大個(gè)體作為所求結(jié)果，算法結(jié)束。

遺傳算法基本概念與原理遺傳算法論文答辯專家講座第18頁(yè)

步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；遺傳算法基本概念與原理遺傳算法論文答辯專家講座第19頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)編碼方法:二進(jìn)制編碼方法是遺傳算法中最慣用一個(gè)編碼方法，它使用編碼符號(hào)集是由二進(jìn)制符號(hào)0和1組成二值符號(hào)集，它所組成個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)串。格雷碼，連續(xù)兩個(gè)整數(shù)所對(duì)應(yīng)編碼值之間只有一個(gè)碼位不相同。格雷碼有這么一個(gè)特點(diǎn)：任意兩個(gè)整數(shù)差是這兩個(gè)整數(shù)所對(duì)應(yīng)海明距離。這個(gè)特點(diǎn)是遺傳算法中使用格雷碼進(jìn)行個(gè)體編碼主要原因。遺傳算法論文答辯專家講座第20頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)符點(diǎn)數(shù)編碼方法:指?jìng)€(gè)體每個(gè)基因值用某一范圍內(nèi)一個(gè)浮點(diǎn)數(shù)來表示個(gè)體編碼長(zhǎng)度等于其決議變量個(gè)數(shù)，個(gè)體變量長(zhǎng)度等于去決議變量真實(shí)值，所以也叫真值編碼方法.符號(hào)編碼方法是指?jìng)€(gè)體染色體編碼串中基因值取自一個(gè)無數(shù)值含義，而只有代碼含義符號(hào)集。這個(gè)符號(hào)集能夠是一個(gè)字母表，如{A,B,C,D,…}；也能夠是一個(gè)數(shù)宇序號(hào)表，如{1,2,3,4,5,…}；還能夠是一個(gè)代碼表，如{Al,A2,A3,A4,A5,…}等等。遺傳算法論文答辯專家講座第21頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)適應(yīng)度函數(shù):適應(yīng)度較高個(gè)體遺傳到下一代概率就相對(duì)大一些；而適應(yīng)度較低個(gè)體遺傳到下一代概率就相對(duì)較小一些。度量個(gè)體適應(yīng)度函數(shù)就稱為適應(yīng)度函數(shù)。依據(jù)個(gè)體適應(yīng)值，就可決定在此環(huán)境下生存能力。個(gè)體適應(yīng)度大小決定該個(gè)體被遺傳到下一代群體中概率。遺傳算法僅使用所求問題目標(biāo)函數(shù)值就能夠得到下一步相關(guān)搜索信息。目標(biāo)函數(shù)值使用是經(jīng)過評(píng)價(jià)個(gè)體適應(yīng)度來表達(dá)。遺傳算法論文答辯專家講座第22頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)選擇算子:選擇算子（也叫復(fù)制算子ReproductionOperator）來對(duì)群體中個(gè)體進(jìn)行優(yōu)勝劣汰操作：適應(yīng)度較高個(gè)體被遺傳到下一代概率較大；適應(yīng)度較低個(gè)體被遺傳到下一代概率較小。選擇操作建立在對(duì)個(gè)體適應(yīng)度進(jìn)行評(píng)價(jià)基礎(chǔ)上。選擇主要目標(biāo)為了防止基因缺失、提升全局收斂性和計(jì)算效率。遺傳算法論文答辯專家講座第23頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)輪盤賭選擇方法實(shí)現(xiàn)步驟：（1）計(jì)算群體中全部個(gè)體適應(yīng)度函數(shù)值（需要解碼）；（2）利用百分比選擇算子公式，計(jì)算每個(gè)個(gè)體被選中遺傳到下一代群體概率；（3）采取模擬賭盤操作（即生成0到1之間隨機(jī)數(shù)與每個(gè)個(gè)體遺傳到下一代群體概率進(jìn)行匹配）來確定各個(gè)個(gè)體是否遺傳到下一代群體中。遺傳算法論文答辯專家講座第24頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)最優(yōu)保留策略選擇：在遺傳算法運(yùn)行過程中，經(jīng)過對(duì)個(gè)體進(jìn)行交叉、變異等遺傳操作而不停產(chǎn)生新個(gè)體，即使伴隨群體進(jìn)化過程會(huì)產(chǎn)生出越來越多優(yōu)良個(gè)體，但因?yàn)檫z傳操作隨機(jī)性，它們也有可能破壞掉當(dāng)前群體中適應(yīng)度最好個(gè)體。我們希望適應(yīng)度最好個(gè)體要盡可能保留到下一代群體中，為到達(dá)這個(gè)目標(biāo)我們使用最優(yōu)保留策略進(jìn)化模型。遺傳算法論文答辯專家講座第25頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)詳細(xì)操作過程：（1）找出當(dāng)前群體中適應(yīng)度最高個(gè)體和適應(yīng)度最低個(gè)體。（2）若當(dāng)前群體中最正確個(gè)體適應(yīng)度比總迄今為止最好個(gè)體適應(yīng)度還高，則以當(dāng)前種群中最正確個(gè)體作為新迄今為止最好個(gè)體。（3）用迄今為止最好個(gè)體替換掉當(dāng)前群體中最差個(gè)體。遺傳算法論文答辯專家講座第26頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)交叉算子:所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配正確染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個(gè)新個(gè)體。交叉運(yùn)算是遺傳算法區(qū)分于其它進(jìn)化算法主要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體主要方法。SGA中交叉算子采取單點(diǎn)交叉算子。

遺傳算法論文答辯專家講座第27頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)單點(diǎn)交叉運(yùn)算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000遺傳算法論文答辯專家講座第28頁(yè)遺傳算法實(shí)現(xiàn)技術(shù)變異算子：所謂變異運(yùn)算，是指依據(jù)變異概率Pm將個(gè)體編碼串中一些基因值用其它基因值來替換，從而形成一個(gè)新個(gè)體。遺傳算法中變異運(yùn)算是產(chǎn)生新個(gè)體輔助方法，它決定了遺傳算法局部搜索能力，同時(shí)保持種群多樣性。交叉運(yùn)算和變異運(yùn)算相互配合，共同完成對(duì)搜索空間全局搜索和局部搜索。SGA中變異算子采取基本位變異算子。

遺傳算法論文答辯專家講座第29頁(yè)Matlab遺傳算法GUI求函數(shù)最大值函數(shù)：遺傳算法論文答辯專家講座第30頁(yè)Matlab遺傳算法GUI求函數(shù)最大值步驟：首先編寫目標(biāo)函數(shù)M文件并以文件名myfun存盤。functiony=myfun(x)ifx(:,1)<=2&x(:,1)>=-1y=-(x*sin(10*pi*x)+2.0);elsey=0end然后，在MATLAB工作窗口>>gatool打開遺傳算法GUI，在“fitnessfunct