數(shù)學(xué)建模專題之遺傳算法

1、數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法v 重慶理工大學(xué)重慶理工大學(xué)v 主講：肖漢光主講：肖漢光v Email:數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法Contents遺傳算法概述遺傳算法概述1標(biāo)準(zhǔn)遺傳標(biāo)準(zhǔn)遺傳算法算法2遺傳算法簡(jiǎn)單舉例：函數(shù)極值遺傳算法簡(jiǎn)單舉例：函數(shù)極值3遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)遺傳算法優(yōu)化神經(jīng)網(wǎng)絡(luò)5遺傳算法求解遺傳算法求解TSP問(wèn)題問(wèn)題4遺傳算法的實(shí)現(xiàn)遺傳算法的實(shí)現(xiàn)6數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法Contents of Section 11.4什么是遺傳算法什么是遺傳算法1.11.21.3遺傳算法的特點(diǎn)遺傳算法的特點(diǎn)遺傳算法的發(fā)展歷程遺傳算法的發(fā)展歷程遺傳

2、算法的研究和應(yīng)用領(lǐng)域遺傳算法的研究和應(yīng)用領(lǐng)域1 遺傳算法概述遺傳算法概述數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法1 遺傳算法概述遺傳算法概述1.1 遺傳算法（遺傳算法（Genetic Algorithm, GA）一種仿生全局優(yōu)化算法一種仿生全局優(yōu)化算法模仿生物的遺傳進(jìn)化原理（模仿生物的遺傳進(jìn)化原理（Darwins theory of evolution & Mendels law of inheritance)，通過(guò)選擇（，通過(guò)選擇（Selection）、）、交叉（交叉（Crossover）與變異（）與變異（Mutation）等操作機(jī)制，使種群中個(gè)體的適應(yīng)性等操作機(jī)制，使種群中個(gè)體的適應(yīng)性

3、（Fitness）不斷提高）不斷提高核心思想：物競(jìng)天擇，適者生存核心思想：物競(jìng)天擇，適者生存 （“天天”適應(yīng)度函數(shù)，適應(yīng)度函數(shù)，F(xiàn)itness Function)數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法1 遺傳算法概述遺傳算法概述1.2 遺傳算法的特點(diǎn)遺傳算法的特點(diǎn)四大優(yōu)點(diǎn)：四大優(yōu)點(diǎn)：良好的并行性（操作對(duì)象是一組可行解；搜索軌良好的并行性（操作對(duì)象是一組可行解；搜索軌道有多條）道有多條）強(qiáng)大的通用性（只需利用目標(biāo)的取值信息，無(wú)需強(qiáng)大的通用性（只需利用目標(biāo)的取值信息，無(wú)需梯度等高價(jià)值信息）梯度等高價(jià)值信息）良好的全局優(yōu)化性和魯棒性良好的全局優(yōu)化性和魯棒性良好的可操作性良好的可操作性兩個(gè)缺點(diǎn)：

4、兩個(gè)缺點(diǎn)： 未成熟收斂問(wèn)題未成熟收斂問(wèn)題 收斂速度較慢，算法實(shí)時(shí)性欠佳收斂速度較慢，算法實(shí)時(shí)性欠佳數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法1 遺傳算法概述遺傳算法概述1.3 遺傳算法的發(fā)展歷史遺傳算法的發(fā)展歷史年份年份貢獻(xiàn)者貢獻(xiàn)者內(nèi)容內(nèi)容1962Holland程序漫游元胞計(jì)算機(jī)自適應(yīng)系統(tǒng)框架程序漫游元胞計(jì)算機(jī)自適應(yīng)系統(tǒng)框架1968Holland模式定理的建立模式定理的建立1971Hollstein具有交配和選擇規(guī)則的二維函數(shù)優(yōu)化具有交配和選擇規(guī)則的二維函數(shù)優(yōu)化1972BosworthFoo, Zeigler提出具有復(fù)雜變異、類似于遺傳算法的基因操作提出具有復(fù)雜變異、類似于遺傳算法的基因操作

5、1972Frantz位置非線性和倒位操作研究位置非線性和倒位操作研究1973Holland遺傳算法中試驗(yàn)的最優(yōu)配置和雙臂強(qiáng)盜問(wèn)題遺傳算法中試驗(yàn)的最優(yōu)配置和雙臂強(qiáng)盜問(wèn)題1973Martin類似遺傳算法的概率算法理論類似遺傳算法的概率算法理論1975De Jong用于用于5個(gè)測(cè)試函數(shù)的研究基本遺傳短發(fā)基準(zhǔn)參數(shù)個(gè)測(cè)試函數(shù)的研究基本遺傳短發(fā)基準(zhǔn)參數(shù)1975Holland出版開(kāi)創(chuàng)性著作出版開(kāi)創(chuàng)性著作Adaptation in Natural and Artificial Systems表表1.1 遺傳算法理論的經(jīng)典研究成果遺傳算法理論的經(jīng)典研究成果第一階段：第一階段：20世紀(jì)世紀(jì)60年代至年代至70年代

6、中期年代中期（萌芽期）（萌芽期）數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法1 遺傳算法概述遺傳算法概述年份年份貢獻(xiàn)者貢獻(xiàn)者內(nèi)容內(nèi)容1981Bethke應(yīng)用應(yīng)用Walsh函數(shù)分析模式函數(shù)分析模式1981Brindle研究遺傳算法中的選擇和支配問(wèn)題研究遺傳算法中的選擇和支配問(wèn)題1983Pettit, Swigger遺傳算法應(yīng)用于非穩(wěn)定問(wèn)題的粗略研究遺傳算法應(yīng)用于非穩(wěn)定問(wèn)題的粗略研究1983Wetzel用遺傳算法解決旅行商問(wèn)題（用遺傳算法解決旅行商問(wèn)題（TSP)1984Mauldin基本遺傳算法中用啟發(fā)知識(shí)維持遺傳多樣性基本遺傳算法中用啟發(fā)知識(shí)維持遺傳多樣性1985Baker試驗(yàn)基于排序的選擇方法

7、試驗(yàn)基于排序的選擇方法1985Booker建議采用部分分配計(jì)分、分享操作和交配限制法建議采用部分分配計(jì)分、分享操作和交配限制法1985Goldberg, LingleTSP問(wèn)題中采用部分匹配交叉問(wèn)題中采用部分匹配交叉1985Grefenstette, Fitzpattrick對(duì)含噪聲的函數(shù)進(jìn)行測(cè)試對(duì)含噪聲的函數(shù)進(jìn)行測(cè)試1985Schaffer多種群遺傳算法解決多目標(biāo)優(yōu)化問(wèn)題多種群遺傳算法解決多目標(biāo)優(yōu)化問(wèn)題續(xù)表續(xù)表1.1數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法1 遺傳算法概述遺傳算法概述年份年份貢獻(xiàn)者貢獻(xiàn)者內(nèi)容內(nèi)容1986Goldberg最優(yōu)種群大小估計(jì)最優(yōu)種群大小估計(jì)1986Grefens

8、tette元級(jí)遺傳算法控制的遺傳算法元級(jí)遺傳算法控制的遺傳算法1987Baker選擇中隨機(jī)誤差的較少方法選擇中隨機(jī)誤差的較少方法1987Goldberg復(fù)制和交叉時(shí)最小欺騙問(wèn)題（復(fù)制和交叉時(shí)最小欺騙問(wèn)題（MDP）1987Goldberg, Richardson借助分享函數(shù)的小生境和物種歸納法借助分享函數(shù)的小生境和物種歸納法1987Goldberg, Segrest復(fù)制和交叉的有限馬爾科夫鏈復(fù)制和交叉的有限馬爾科夫鏈1987Goldberg, Smith雙倍染色體遺傳算法應(yīng)用于非穩(wěn)定函數(shù)優(yōu)化雙倍染色體遺傳算法應(yīng)用于非穩(wěn)定函數(shù)優(yōu)化1987Oliver, Smith, Holland排列重組算子的模

9、擬和分析排列重組算子的模擬和分析1987Schaffer, Morishima串編碼自適應(yīng)交叉試驗(yàn)串編碼自適應(yīng)交叉試驗(yàn)1987Whitley子孫測(cè)試應(yīng)用于遺傳算法的選擇操作子孫測(cè)試應(yīng)用于遺傳算法的選擇操作續(xù)表續(xù)表1.1第二階段：第二階段：20世紀(jì)世紀(jì)80年代（蓬勃發(fā)展期）年代（蓬勃發(fā)展期）數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法1 遺傳算法概述遺傳算法概述1.4 遺傳算法的應(yīng)用領(lǐng)域遺傳算法的應(yīng)用領(lǐng)域（1）函數(shù)優(yōu)化（經(jīng)典應(yīng)用）函數(shù)優(yōu)化（經(jīng)典應(yīng)用）（2）組合優(yōu)化（旅行商問(wèn)題）組合優(yōu)化（旅行商問(wèn)題已成為衡量算法優(yōu)劣的標(biāo)準(zhǔn)、背包問(wèn)已成為衡量算法優(yōu)劣的標(biāo)準(zhǔn)、背包問(wèn)題、裝箱問(wèn)題等）題、裝箱問(wèn)題等）（3

10、）生產(chǎn)調(diào)度問(wèn)題）生產(chǎn)調(diào)度問(wèn)題（4）自動(dòng)控制（如航空控制系統(tǒng)的優(yōu)化設(shè)計(jì)、模糊控制器優(yōu)化設(shè)計(jì)和）自動(dòng)控制（如航空控制系統(tǒng)的優(yōu)化設(shè)計(jì)、模糊控制器優(yōu)化設(shè)計(jì)和在線修改隸屬度函數(shù)、人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)和調(diào)整人工神在線修改隸屬度函數(shù)、人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)和調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)等優(yōu)化問(wèn)題）經(jīng)網(wǎng)絡(luò)的連接權(quán)等優(yōu)化問(wèn)題）（5）機(jī)器人智能控制（如移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡）機(jī)器人智能控制（如移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解等）規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解等）（6）圖像處理和模式識(shí)別（如圖像恢復(fù)、圖像邊緣特征提取、幾何形）圖像處理和模式識(shí)別（如圖像恢復(fù)、圖像邊緣特征提取

11、、幾何形狀識(shí)別等）狀識(shí)別等）（7）機(jī)器學(xué)習(xí)（將）機(jī)器學(xué)習(xí)（將GA用于知識(shí)獲取，構(gòu)建基于用于知識(shí)獲取，構(gòu)建基于GA的機(jī)器學(xué)習(xí)系統(tǒng)）的機(jī)器學(xué)習(xí)系統(tǒng)） 此外，遺傳算法在人工生命、遺傳程序設(shè)計(jì)、社會(huì)和經(jīng)濟(jì)領(lǐng)域等此外，遺傳算法在人工生命、遺傳程序設(shè)計(jì)、社會(huì)和經(jīng)濟(jì)領(lǐng)域等方面的應(yīng)用盡管不是很成熟，但還是取得了一定的成功。在日后，必方面的應(yīng)用盡管不是很成熟，但還是取得了一定的成功。在日后，必定有更深入的發(fā)展。定有更深入的發(fā)展。Hotspot數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法Contents of Section 22.4遺傳算法的生物學(xué)基礎(chǔ)遺傳算法的生物學(xué)基礎(chǔ)2.12.22.32.5遺傳算法的基本流

12、程遺傳算法的基本流程遺傳算法的若干基本概念遺傳算法的若干基本概念遺傳算法的應(yīng)用步驟遺傳算法的應(yīng)用步驟欺騙問(wèn)題和未成熟收斂問(wèn)題欺騙問(wèn)題和未成熟收斂問(wèn)題數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.1 遺傳算法的生物學(xué)基礎(chǔ)遺傳算法的生物學(xué)基礎(chǔ)細(xì)胞（細(xì)胞（Cell）染色體染色體（Chromosome） 脫氧核糖核酸脫氧核糖核酸（Deoxyribonucleic Acid，DNA） 基因（基因（Gene）、）、等位基因（等位基因（Allele） 基因型基因型（Genotype） 表現(xiàn)型表現(xiàn)型（Phenotype） 復(fù)制（復(fù)制（Reproduction）交叉（交叉（Cros

13、sover）變異（變異（Mutation）對(duì)環(huán)境的適應(yīng)性對(duì)環(huán)境的適應(yīng)性“種瓜得瓜，種瓜得瓜，種豆得豆種豆得豆”數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.1 遺傳算法的生物學(xué)基礎(chǔ)遺傳算法的生物學(xué)基礎(chǔ)個(gè)體個(gè)體（Individual） 種群種群（Population） 適應(yīng)度適應(yīng)度（Fitness） 進(jìn)化進(jìn)化（Evolution） 生存（生存（Survival） LowHigh“物競(jìng)天擇，適者生存物競(jìng)天擇，適者生存”死亡死亡（Death） 滅絕滅絕（Extinction） 數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.2 標(biāo)準(zhǔn)遺傳算法的

14、基本流程標(biāo)準(zhǔn)遺傳算法的基本流程實(shí)際問(wèn)題參數(shù)集實(shí)際問(wèn)題參數(shù)集參數(shù)編碼成為染色體參數(shù)編碼成為染色體初始化群體初始化群體計(jì)算每一個(gè)體的計(jì)算每一個(gè)體的適應(yīng)度適應(yīng)度對(duì)染色體進(jìn)行解對(duì)染色體進(jìn)行解碼碼滿足終止?jié)M足終止條件？條件？得到問(wèn)題最優(yōu)解得到問(wèn)題最優(yōu)解進(jìn)行遺傳操作進(jìn)行遺傳操作群體群體新群體新群體P(t)P(t+1)1、選擇、選擇2、交叉、交叉3、變異、變異數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.3 遺傳算法的若干概念遺傳算法的若干概念p 個(gè)體個(gè)體(Individual) 稱稱 為個(gè)體空間，個(gè)體空間的元為個(gè)體空間，個(gè)體空間的元素素 稱為個(gè)體，它是染色體帶有特征的實(shí)稱為個(gè)

15、體，它是染色體帶有特征的實(shí)體。分量體。分量 稱為基因，正整數(shù)稱為基因，正整數(shù) 稱為個(gè)體的基因長(zhǎng)稱為個(gè)體的基因長(zhǎng)度。度。 0,1lS 011laa aaS 0,1ja lp種群種群(Population) 稱個(gè)體空間稱個(gè)體空間S中中N個(gè)個(gè)體組成的一個(gè)子個(gè)個(gè)體組成的一個(gè)子集（個(gè)體允許重復(fù)）稱為一個(gè)種群，記為：集（個(gè)體允許重復(fù)）稱為一個(gè)種群，記為：其中其中 ，N稱為種群規(guī)模。稱為種群規(guī)模。12(,)NAA AA(1,2,)jAjNS數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.3 遺傳算法的若干概念遺傳算法的若干概念p適應(yīng)度適應(yīng)度（Fitness） 在研究自然界中生物的

16、遺傳和進(jìn)化在研究自然界中生物的遺傳和進(jìn)化現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)度量某個(gè)物種對(duì)現(xiàn)象時(shí)，生物學(xué)家使用適應(yīng)度這個(gè)術(shù)語(yǔ)來(lái)度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種于生存環(huán)境的適應(yīng)程度。對(duì)生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物將獲得更多的繁殖機(jī)會(huì)，而對(duì)生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕。在遺傳算種，其繁殖機(jī)會(huì)就會(huì)相對(duì)較少，甚至逐漸滅絕。在遺傳算法中，一般通過(guò)適應(yīng)度函數(shù)法中，一般通過(guò)適應(yīng)度函數(shù)（Fitness function）來(lái)衡量某來(lái)衡量某一個(gè)體的適應(yīng)度高低。一個(gè)體的適應(yīng)度高低。 數(shù)學(xué)建模專題之?dāng)?shù)學(xué)

17、建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法p解碼解碼（Decoding） 解碼是將遺傳算法所搜索到的最優(yōu)個(gè)解碼是將遺傳算法所搜索到的最優(yōu)個(gè)體的染色體轉(zhuǎn)換成待求解問(wèn)題的實(shí)際最優(yōu)解的過(guò)程，即編碼體的染色體轉(zhuǎn)換成待求解問(wèn)題的實(shí)際最優(yōu)解的過(guò)程，即編碼的逆過(guò)程。的逆過(guò)程。 2.3 遺傳算法的若干概念遺傳算法的若干概念p編碼編碼（Coding） 將一個(gè)待求解的問(wèn)題的實(shí)際可行解從其將一個(gè)待求解的問(wèn)題的實(shí)際可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間（即個(gè)體空間）解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間（即個(gè)體空間）的過(guò)程，就稱為編碼。的過(guò)程，就稱為編碼。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳

18、算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法p 選擇操作（選擇操作（Selection） 根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一根據(jù)各個(gè)個(gè)體的適應(yīng)度，按照一定的規(guī)則，從第定的規(guī)則，從第t代群體代群體P(t)中選擇出一些優(yōu)良的個(gè)體遺傳中選擇出一些優(yōu)良的個(gè)體遺傳到下一代群體到下一代群體P(t+1)中。一般地，選擇操作通過(guò)選擇算子中。一般地，選擇操作通過(guò)選擇算子（Selection Operator）進(jìn)行。）進(jìn)行。 2.3 遺傳算法的若干概念遺傳算法的若干概念p 交叉操作交叉操作（Crossover） 將群體將群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對(duì)，對(duì)每一對(duì)個(gè)體，以某個(gè)概率（稱為交叉概率，配成對(duì)，對(duì)每一對(duì)

19、個(gè)體，以某個(gè)概率（稱為交叉概率，Crossover Rate）遵循某一種規(guī)則）遵循某一種規(guī)則交換它們之間的部分染交換它們之間的部分染色體。色體。p 變異操作（變異操作（Mutation） 對(duì)群體對(duì)群體P(t)中的每一個(gè)個(gè)體，以某中的每一個(gè)個(gè)體，以某一概率（稱為變異概率，一概率（稱為變異概率，Mutation Rate）改變某一個(gè)或某）改變某一個(gè)或某一些基因座上的基因值為其他的等位基因。一些基因座上的基因值為其他的等位基因。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.4 遺傳算法的應(yīng)用步驟遺傳算法的應(yīng)用步驟（1）確定決策變量及各種約束條件，即確定出個(gè)體的表現(xiàn)型）確

20、定決策變量及各種約束條件，即確定出個(gè)體的表現(xiàn)型X和問(wèn)題的解空和問(wèn)題的解空間。間。（2）建立優(yōu)化模型，確定出目標(biāo)函數(shù)的類型及其數(shù)學(xué)描述形式或量化方法。）建立優(yōu)化模型，確定出目標(biāo)函數(shù)的類型及其數(shù)學(xué)描述形式或量化方法。（3）確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型）確定表示可行解的染色體編碼方法，即確定出個(gè)體的基因型X*，及遺，及遺傳算法的搜索空間。傳算法的搜索空間。 編碼是遺傳算法解決問(wèn)題的先決條件和關(guān)鍵步驟編碼是遺傳算法解決問(wèn)題的先決條件和關(guān)鍵步驟:不僅決定個(gè)體基因的排列形式（不僅決定個(gè)體基因的排列形式（從而決定選擇與繁殖等操作的作用方式從而決定選擇與繁殖等操作的作用方式），），而且

21、也決定從搜索空間的基因型到解空間的表現(xiàn)型的解碼方式（而且也決定從搜索空間的基因型到解空間的表現(xiàn)型的解碼方式（從而決定對(duì)從而決定對(duì)GA所獲解的翻譯與理解所獲解的翻譯與理解）；）；決定決定GA搜索的困難度與復(fù)雜性；搜索的困難度與復(fù)雜性；決定對(duì)問(wèn)題的求解精度。決定對(duì)問(wèn)題的求解精度。 常用的遺傳算法編碼方法主要有：二進(jìn)制編碼、浮點(diǎn)數(shù)編碼等?？梢猿Ｓ玫倪z傳算法編碼方法主要有：二進(jìn)制編碼、浮點(diǎn)數(shù)編碼等。可以證明，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼搜索能力強(qiáng)，但浮點(diǎn)數(shù)編碼比二進(jìn)制編碼在證明，二進(jìn)制編碼比浮點(diǎn)數(shù)編碼搜索能力強(qiáng)，但浮點(diǎn)數(shù)編碼比二進(jìn)制編碼在變異操作上能夠保持更好的種群多樣性。變異操作上能夠保持更好的種群多樣性

22、。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.4 遺傳算法的應(yīng)用步驟遺傳算法的應(yīng)用步驟（4）確定解碼方法，即確定出由個(gè)體基因型）確定解碼方法，即確定出由個(gè)體基因型X*，到個(gè)體表現(xiàn)型，到個(gè)體表現(xiàn)型X的對(duì)應(yīng)關(guān)的對(duì)應(yīng)關(guān)系和轉(zhuǎn)換方法。系和轉(zhuǎn)換方法。 標(biāo)準(zhǔn)遺傳算法多采用二進(jìn)制編碼方法，將決策變量用二進(jìn)制字符串表標(biāo)準(zhǔn)遺傳算法多采用二進(jìn)制編碼方法，將決策變量用二進(jìn)制字符串表示，二進(jìn)制編碼串的長(zhǎng)度由所求精度決定。然后將各決策變量的二進(jìn)制編示，二進(jìn)制編碼串的長(zhǎng)度由所求精度決定。然后將各決策變量的二進(jìn)制編碼串連接在一起，構(gòu)成一個(gè)染色體。碼串連接在一起，構(gòu)成一個(gè)染色體。 例如：變量例

23、如：變量x的定義域?yàn)榈亩x域?yàn)?2，3，要求其精度為，要求其精度為10-5，則需要將，則需要將-2，3分成至少分成至少500 000個(gè)等長(zhǎng)小區(qū)域，而每個(gè)小區(qū)域用一個(gè)二進(jìn)制串表示。于個(gè)等長(zhǎng)小區(qū)域，而每個(gè)小區(qū)域用一個(gè)二進(jìn)制串表示。于是有，是有，2L=500 000，即，即2log 50000018.93向上取整，可得到向上取整，可得到L=19。即可用。即可用19位二進(jìn)制串位二進(jìn)制串a(chǎn)18a17a0 來(lái)表示。來(lái)表示。 例如：對(duì)于二進(jìn)制編碼，其解碼過(guò)程如下：若例如：對(duì)于二進(jìn)制編碼，其解碼過(guò)程如下：若X*的取值范圍為的取值范圍為Xl,Xr，參數(shù)的二進(jìn)制編碼碼長(zhǎng)為參數(shù)的二進(jìn)制編碼碼長(zhǎng)為L(zhǎng)，碼串對(duì)應(yīng)的十進(jìn)制

24、整數(shù)為，碼串對(duì)應(yīng)的十進(jìn)制整數(shù)為k，則解碼公式為，則解碼公式為:式中，式中， Xl,Xr參數(shù)最小、最大值；參數(shù)最小、最大值； L參數(shù)編碼長(zhǎng)度；參數(shù)編碼長(zhǎng)度； k二進(jìn)制串對(duì)應(yīng)的實(shí)數(shù)值。二進(jìn)制串對(duì)應(yīng)的實(shí)數(shù)值。()(21)rllLXXkXX102Liiika21rlLXX數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法（5）確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，就是確定出由目標(biāo)函數(shù)值到個(gè)）確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法，就是確定出由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度的轉(zhuǎn)換規(guī)則。標(biāo)準(zhǔn)遺傳算法的適應(yīng)度函數(shù)常用一下三種：體適應(yīng)度的轉(zhuǎn)換規(guī)則。標(biāo)準(zhǔn)遺傳算法的適應(yīng)度函數(shù)常用一下三種：2.4 遺傳算法的應(yīng)用步驟遺

25、傳算法的應(yīng)用步驟直接以待求解的目標(biāo)函數(shù)為適應(yīng)度函數(shù)直接以待求解的目標(biāo)函數(shù)為適應(yīng)度函數(shù) 若目標(biāo)函數(shù)為最大值問(wèn)題，則若目標(biāo)函數(shù)為最大值問(wèn)題，則Fit(f(X)=f(X) 若目標(biāo)函數(shù)為最小值問(wèn)題，則若目標(biāo)函數(shù)為最小值問(wèn)題，則Fit(f(X)=f(X)界限構(gòu)造法界限構(gòu)造法優(yōu)點(diǎn)：簡(jiǎn)單直觀；優(yōu)點(diǎn)：簡(jiǎn)單直觀；缺點(diǎn)：其一，可能不滿足非負(fù)的要求；其二，某些代求解的函數(shù)值分布相差很缺點(diǎn)：其一，可能不滿足非負(fù)的要求；其二，某些代求解的函數(shù)值分布相差很大，由此得到的平均適應(yīng)度可能不利于體現(xiàn)種群的平均性能。大，由此得到的平均適應(yīng)度可能不利于體現(xiàn)種群的平均性能。 若目標(biāo)函數(shù)為最大值問(wèn)題，則若目標(biāo)函數(shù)為最大值問(wèn)題，則max

26、max+ ( ),( )( ()0,cf xf xcFit f X其它Cmax為為f(x)的最大的最大值估計(jì)。值估計(jì)。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法 倒數(shù)法倒數(shù)法 若目標(biāo)函數(shù)為最小值問(wèn)題，則若目標(biāo)函數(shù)為最小值問(wèn)題，則minmin( ),( )( ()0,f xcf xcFit f X其它2.4 遺傳算法的應(yīng)用步驟遺傳算法的應(yīng)用步驟該方法是第一種方法的改進(jìn)，但有時(shí)存在界限值預(yù)先估計(jì)困難或估計(jì)該方法是第一種方法的改進(jìn)，但有時(shí)存在界限值預(yù)先估計(jì)困難或估計(jì)不精確等問(wèn)題。不精確等問(wèn)題。Cmin為為f(x)的最小的最小值估計(jì)。值估計(jì)。 若目標(biāo)函數(shù)為最小值問(wèn)題，則若

27、目標(biāo)函數(shù)為最小值問(wèn)題，則1( ()0,( )01()Fit f Xccf xcf X 若目標(biāo)函數(shù)為最大值問(wèn)題，則若目標(biāo)函數(shù)為最大值問(wèn)題，則1( ()0,( )01()Fit f Xccf xcf X C為目標(biāo)函數(shù)界限的保守估計(jì)值。為目標(biāo)函數(shù)界限的保守估計(jì)值。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法（6）確定各遺傳具體操作方法。）確定各遺傳具體操作方法。2.4 遺傳算法的應(yīng)用步驟遺傳算法的應(yīng)用步驟選擇算子和選擇操作選擇算子和選擇操作個(gè)體選擇概率的常用分配方法有以下兩種：個(gè)體選擇概率的常用分配方法有以下兩種：A 按比例的適應(yīng)度分配（按比例的適應(yīng)度分配（Proport

28、ional Fitness Assignment） 亦可稱為選擇的蒙特亦可稱為選擇的蒙特卡羅方法，是利用比例于各個(gè)個(gè)體適應(yīng)度的概率決定其子孫的遺留可能性。若某個(gè)卡羅方法，是利用比例于各個(gè)個(gè)體適應(yīng)度的概率決定其子孫的遺留可能性。若某個(gè)個(gè)體個(gè)體i，其適應(yīng)度為，其適應(yīng)度為fi，則其被選取的概率表示為，則其被選取的概率表示為, 顯然選擇概率大的個(gè)體，能多次被選中，它的遺傳因子就會(huì)在種群中擴(kuò)大。顯然選擇概率大的個(gè)體，能多次被選中，它的遺傳因子就會(huì)在種群中擴(kuò)大。1MiiiiPffB 基于排序的適應(yīng)度分配（基于排序的適應(yīng)度分配（Rank-based Fitness Assignment） 在基于排序的適在基

29、于排序的適應(yīng)度分配中，種群按目標(biāo)值進(jìn)行排序。適應(yīng)度僅僅取決于個(gè)體在種群中的序位，而應(yīng)度分配中，種群按目標(biāo)值進(jìn)行排序。適應(yīng)度僅僅取決于個(gè)體在種群中的序位，而不是實(shí)際的目標(biāo)值。不是實(shí)際的目標(biāo)值。 排序方法比比例方法表現(xiàn)出更好的魯棒性，它能在一定程度上克服了比例適應(yīng)排序方法比比例方法表現(xiàn)出更好的魯棒性，它能在一定程度上克服了比例適應(yīng)度計(jì)算的尺度問(wèn)題和過(guò)早收斂問(wèn)題。度計(jì)算的尺度問(wèn)題和過(guò)早收斂問(wèn)題。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.5 遺傳算法的應(yīng)用步驟遺傳算法的應(yīng)用步驟另外，還可采用以下的幾種提高遺傳算法性能的選擇方法：另外，還可采用以下的幾種提高遺傳算法性能

30、的選擇方法：穩(wěn)態(tài)繁殖（穩(wěn)態(tài)繁殖（Steady State Reproduction） 在迭代過(guò)在迭代過(guò)程中用部分優(yōu)質(zhì)新子個(gè)體來(lái)更新群體中部分父?jìng)€(gè)體，作為程中用部分優(yōu)質(zhì)新子個(gè)體來(lái)更新群體中部分父?jìng)€(gè)體，作為下一代種群。下一代種群。沒(méi)有重串的穩(wěn)態(tài)繁殖（沒(méi)有重串的穩(wěn)態(tài)繁殖（Steady State Reproduction without Duplicates） 在穩(wěn)態(tài)繁殖的基礎(chǔ)上，形成下一在穩(wěn)態(tài)繁殖的基礎(chǔ)上，形成下一代新種群時(shí)，使其中的個(gè)體不重復(fù)。代新種群時(shí)，使其中的個(gè)體不重復(fù)。 個(gè)體選擇概率確定后，可以選用的常用選擇算法有輪盤賭選擇法（個(gè)體選擇概率確定后，可以選用的常用選擇算法有輪盤賭選擇法（Ro

31、ulette Wheel Selection）、隨機(jī)遍歷抽樣法（、隨機(jī)遍歷抽樣法（Stochastic Universal Sampling）、局）、局部選擇法（部選擇法（Local Selection）、截?cái)噙x擇法（）、截?cái)噙x擇法（Truncation Selection）和錦標(biāo)賽）和錦標(biāo)賽選擇法（選擇法（Tournament Selection）等。標(biāo)準(zhǔn)遺傳算法常用的輪盤賭選擇法的原）等。標(biāo)準(zhǔn)遺傳算法常用的輪盤賭選擇法的原理如右下圖所示。理如右下圖所示。1()niiSf X()iif XpSpointer1kkjjqp關(guān)于選擇算子：關(guān)于選擇算子：如果對(duì)解的質(zhì)量要求不高，要求收如果對(duì)解的質(zhì)量

32、要求不高，要求收斂快，可取較高的選擇強(qiáng)度；反之，斂快，可取較高的選擇強(qiáng)度；反之，可取較低的選擇強(qiáng)度。標(biāo)準(zhǔn)遺傳算可取較低的選擇強(qiáng)度。標(biāo)準(zhǔn)遺傳算法達(dá)到收斂的世代數(shù)與選擇強(qiáng)度成法達(dá)到收斂的世代數(shù)與選擇強(qiáng)度成反比。反比。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法 交叉率及交叉操作交叉率及交叉操作 交叉，也可以稱為基因重組（交叉，也可以稱為基因重組（Recombination），是遺傳算法獲），是遺傳算法獲取新的優(yōu)良個(gè)體的最重要的手段，決定了遺傳算法的全局搜索能力。取新的優(yōu)良個(gè)體的最重要的手段，決定了遺傳算法的全局搜索能力。 一般地，當(dāng)隨機(jī)產(chǎn)生的概率大于交叉率，遺傳算法就會(huì)

33、按一定規(guī)一般地，當(dāng)隨機(jī)產(chǎn)生的概率大于交叉率，遺傳算法就會(huì)按一定規(guī)則選擇兩個(gè)個(gè)體，執(zhí)行交叉操作。則選擇兩個(gè)個(gè)體，執(zhí)行交叉操作。交叉率的選擇決定了交叉的頻率，交叉率的選擇決定了交叉的頻率，較大的交叉率使各代充分交叉，但群體中的優(yōu)良模式遭到破壞的可能較大的交叉率使各代充分交叉，但群體中的優(yōu)良模式遭到破壞的可能性增大，以致產(chǎn)生較大的代溝，從而使搜索走向隨機(jī)化；交叉率越低，性增大，以致產(chǎn)生較大的代溝，從而使搜索走向隨機(jī)化；交叉率越低，產(chǎn)生的代溝越小，就會(huì)使得更多的個(gè)體直接復(fù)制到下一代，遺傳搜索產(chǎn)生的代溝越小，就會(huì)使得更多的個(gè)體直接復(fù)制到下一代，遺傳搜索可能陷入停滯狀態(tài)，一般建議取值范圍可能陷入停滯狀態(tài)，

34、一般建議取值范圍0.40.9。對(duì)于二進(jìn)制編碼，常用的交叉方法有：?jiǎn)吸c(diǎn)交叉、多點(diǎn)交叉和均勻交對(duì)于二進(jìn)制編碼，常用的交叉方法有：?jiǎn)吸c(diǎn)交叉、多點(diǎn)交叉和均勻交叉等。一個(gè)單點(diǎn)交叉的例子如下圖所示。叉等。一個(gè)單點(diǎn)交叉的例子如下圖所示。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法變異率及變異操作變異率及變異操作 變異本身是一種局部隨機(jī)搜索，使遺傳算法具有局部的隨機(jī)搜索能變異本身是一種局部隨機(jī)搜索，使遺傳算法具有局部的隨機(jī)搜索能力；同時(shí)使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。力；同時(shí)使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。 一般地，隨機(jī)產(chǎn)生的概率大于變異率就

35、會(huì)觸發(fā)變異操作。一般地，隨機(jī)產(chǎn)生的概率大于變異率就會(huì)觸發(fā)變異操作。變異率一變異率一般可取般可取0.0010.1。變異率。變異率不能取得太大，如果大于不能取得太大，如果大于0.5，遺傳算法就退化，遺傳算法就退化為隨機(jī)搜索，為隨機(jī)搜索，而遺傳算法的一些重要的數(shù)學(xué)特性和搜索能力也不復(fù)存在而遺傳算法的一些重要的數(shù)學(xué)特性和搜索能力也不復(fù)存在了。了。 常用的變異操作方法有：實(shí)值變異法和二進(jìn)制變異法等。常用的變異操作方法有：實(shí)值變異法和二進(jìn)制變異法等。實(shí)值變實(shí)值變異法異法0.5XXL10( )2mia i a(i)以概率以概率1/m取值取值1，以概，以概率率1-1/m取值取值0，通常，通常m=20 此外，還

36、有部分匹配交叉（此外，還有部分匹配交叉（Partially Matched Crossover）、順序）、順序交叉（交叉（Ordered Crossover）、洗牌交叉（）、洗牌交叉（Shuffle Crossover）等等。）等等。二進(jìn)制二進(jìn)制變異法變異法數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法（7）確定遺傳算法的有關(guān)運(yùn)行參數(shù)，包括群體規(guī)模確定遺傳算法的有關(guān)運(yùn)行參數(shù)，包括群體規(guī)模(Population Size)、迭、迭代次數(shù)（一般取為代次數(shù)（一般取為100500）、選擇算子、交叉率、變異率等等）、選擇算子、交叉率、變異率等等。（8）初始化群體。）初始化群體。

37、l初始群體一般隨機(jī)產(chǎn)生初始群體一般隨機(jī)產(chǎn)生l初始值最好能在解空間中均勻采樣（初始值最好能在解空間中均勻采樣（收斂速度比較快收斂速度比較快 ）l對(duì)于非二進(jìn)制編碼，還要考慮所生成的染色體是否在可行區(qū)域內(nèi)。對(duì)于非二進(jìn)制編碼，還要考慮所生成的染色體是否在可行區(qū)域內(nèi)。（9）計(jì)算群體中個(gè)體解碼后的適應(yīng)值。）計(jì)算群體中個(gè)體解碼后的適應(yīng)值。（10）按照遺傳策略，運(yùn)用所選定的選擇、交叉和變異算子作用于群體，生）按照遺傳策略，運(yùn)用所選定的選擇、交叉和變異算子作用于群體，生成下一代群體。成下一代群體。（11）判斷群體性能是否滿足某一指標(biāo)或是否完成預(yù)定迭代次數(shù)，不滿足則）判斷群體性能是否滿足某一指標(biāo)或是否完成預(yù)定迭代

38、次數(shù)，不滿足則返回（返回（9）。）。popsize取值較取值較小時(shí)小時(shí)提高運(yùn)算和收提高運(yùn)算和收斂速度斂速度卻降低了群體多樣性，卻降低了群體多樣性，可能引起早熟現(xiàn)象可能引起早熟現(xiàn)象取值較取值較大時(shí)大時(shí)含有較多模式，可含有較多模式，可提高提高GA搜索質(zhì)量搜索質(zhì)量但計(jì)算量增大，但計(jì)算量增大，收斂速度降低收斂速度降低一般取為一般取為20100數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法2.6 欺騙問(wèn)題和未成熟收斂問(wèn)題欺騙問(wèn)題和未成熟收斂問(wèn)題2.6.1 欺騙問(wèn)題（欺騙問(wèn)題（Deceptive Problem）競(jìng)爭(zhēng)模式：若模式競(jìng)爭(zhēng)模式：若模式H與與H中，中，*的位置完全一致，但

39、任一確定位的編碼的位置完全一致，但任一確定位的編碼均不一樣，則稱均不一樣，則稱H與與H互為競(jìng)爭(zhēng)模式?；楦?jìng)爭(zhēng)模式。欺騙性：假設(shè)欺騙性：假設(shè)f(X)的最大值對(duì)應(yīng)的的最大值對(duì)應(yīng)的X集合為集合為X*，H為一包含為一包含X*的的m階模階模式。式。H的競(jìng)爭(zhēng)模式為的競(jìng)爭(zhēng)模式為H，而且，而且f(H)f(H)，則，則f為為m階欺騙。階欺騙。欺騙問(wèn)題：在遺傳算法中，將所有妨礙評(píng)價(jià)值高的個(gè)體生成從而影響欺騙問(wèn)題：在遺傳算法中，將所有妨礙評(píng)價(jià)值高的個(gè)體生成從而影響遺傳算法正常工作的問(wèn)題統(tǒng)稱為欺騙問(wèn)題。遺傳算法正常工作的問(wèn)題統(tǒng)稱為欺騙問(wèn)題。 如對(duì)于一個(gè)如對(duì)于一個(gè)2位二進(jìn)制編碼的模式，如果位二進(jìn)制編碼的模式，如果f(1

40、1) 為最大值，則以下不為最大值，則以下不等式任意一個(gè)成立，則存在欺騙性問(wèn)題：等式任意一個(gè)成立，則存在欺騙性問(wèn)題： f(*1) f(*0) ， f(*1) f(0*) ，f(1*) f (0*) ， f(1*) f(*0) 欺騙性問(wèn)題的產(chǎn)生往往與基因編碼方法、適應(yīng)度函數(shù)的確定和調(diào)整等欺騙性問(wèn)題的產(chǎn)生往往與基因編碼方法、適應(yīng)度函數(shù)的確定和調(diào)整等因素相關(guān)，一般可以相應(yīng)地采用不同的編碼方法或者調(diào)整適應(yīng)度函數(shù)因素相關(guān)，一般可以相應(yīng)地采用不同的編碼方法或者調(diào)整適應(yīng)度函數(shù)等方法來(lái)化解。等方法來(lái)化解。數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法（1）未成熟收斂現(xiàn)象未成熟收斂現(xiàn)象

41、未成熟收斂現(xiàn)象是遺傳算法中的特有現(xiàn)象，且十分常見(jiàn)。它是指，未成熟收斂現(xiàn)象是遺傳算法中的特有現(xiàn)象，且十分常見(jiàn)。它是指，當(dāng)遺傳算法還沒(méi)找到全局最優(yōu)解或滿意解時(shí)，群體中不能再產(chǎn)生性能超當(dāng)遺傳算法還沒(méi)找到全局最優(yōu)解或滿意解時(shí)，群體中不能再產(chǎn)生性能超過(guò)父代的后代，群體中的各個(gè)個(gè)體非常相似。未成熟收斂的重要特征是過(guò)父代的后代，群體中的各個(gè)個(gè)體非常相似。未成熟收斂的重要特征是群體中個(gè)體結(jié)構(gòu)的多樣性急劇減少。群體中個(gè)體結(jié)構(gòu)的多樣性急劇減少。2.6.2 未成熟收斂問(wèn)題（未成熟收斂問(wèn)題（Premature Convergence）（2）未成熟收斂產(chǎn)生的原因）未成熟收斂產(chǎn)生的原因理論上考慮的選擇、交叉、變異操作都是

42、絕對(duì)精確的，他們相互協(xié)理論上考慮的選擇、交叉、變異操作都是絕對(duì)精確的，他們相互協(xié)調(diào)，能搜索到整個(gè)解空間，但實(shí)際不然；調(diào)，能搜索到整個(gè)解空間，但實(shí)際不然；存在隨機(jī)誤差（主要包括取樣誤差和選擇誤差）；存在隨機(jī)誤差（主要包括取樣誤差和選擇誤差）；所求解的問(wèn)題是遺傳算法欺騙問(wèn)題。所求解的問(wèn)題是遺傳算法欺騙問(wèn)題。（3）未成熟收斂的防止）未成熟收斂的防止重新啟動(dòng)法重新啟動(dòng)法替代策略（替代策略（Replacement Strategies ）重組策略（重組策略（Recombination Strategies ）匹配策略（匹配策略（Mating Strategies）提高多樣性提高多樣性數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建

43、模專題之遺傳算法遺傳算法v遺傳算法具體步驟選擇選擇編碼編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；定義適應(yīng)度定義適應(yīng)度函數(shù)，便于計(jì)算適應(yīng)值；函數(shù)，便于計(jì)算適應(yīng)值；確定遺傳策略，包括選擇群體大小，確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法選擇、交叉、變異方法以及以及確定交叉概率、變異概率等確定交叉概率、變異概率等遺傳參數(shù)遺傳參數(shù)；隨機(jī)產(chǎn)生隨機(jī)產(chǎn)生初始化群體初始化群體；計(jì)算群體中的個(gè)體或染色體計(jì)算群體中的個(gè)體或染色體解碼后的適應(yīng)值解碼后的適應(yīng)值；按照遺傳策略，運(yùn)用按照遺傳策略，運(yùn)用選擇、交叉和變異算子選擇、交叉和變異算子作用于群

44、體，形成下作用于群體，形成下一代群體；一代群體； 判斷群體性能是否判斷群體性能是否滿足某一指標(biāo)滿足某一指標(biāo)，或者已完成預(yù)定的，或者已完成預(yù)定的迭代次數(shù)迭代次數(shù)，不滿足則返回第五步，或者修改遺傳策略再返回第六步不滿足則返回第五步，或者修改遺傳策略再返回第六步2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法2 標(biāo)準(zhǔn)遺傳算法標(biāo)準(zhǔn)遺傳算法v程序流程圖程序流程圖開(kāi)開(kāi)始始Gen=0編碼編碼隨機(jī)產(chǎn)生隨機(jī)產(chǎn)生M個(gè)初始個(gè)體個(gè)初始個(gè)體滿足終止條件滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)度計(jì)算群體中各個(gè)體適應(yīng)度從左至右依次執(zhí)行遺傳算子從左至右依次執(zhí)行遺傳算子j = 0j = 0j = 0根據(jù)適應(yīng)度

45、選擇復(fù)制個(gè)體根據(jù)適應(yīng)度選擇復(fù)制個(gè)體選擇兩個(gè)交叉?zhèn)€體選擇兩個(gè)交叉?zhèn)€體選擇個(gè)體變異點(diǎn)選擇個(gè)體變異點(diǎn)執(zhí)行變異執(zhí)行變異執(zhí)行交叉執(zhí)行交叉執(zhí)行復(fù)制執(zhí)行復(fù)制將復(fù)制的個(gè)體添入將復(fù)制的個(gè)體添入新群體中新群體中將交叉后的兩個(gè)新個(gè)體將交叉后的兩個(gè)新個(gè)體添入新群體中添入新群體中將變異后的個(gè)體添入將變異后的個(gè)體添入新群體中新群體中j = j+1j = j+2j = j+1 j = M? j = pcM? j = pmLM?Gen=Gen+1輸出結(jié)果輸出結(jié)果終終止止YNYYYNNNpcpm數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法例例1 利用遺傳算法求解區(qū)間利用遺傳算法求解區(qū)間0,31上的二次函數(shù)上的二次函數(shù)y=x2的

46、最大值，精度要求達(dá)到個(gè)位。的最大值，精度要求達(dá)到個(gè)位。y=x2 31 XY3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法 分析 原問(wèn)題可轉(zhuǎn)化為在區(qū)間0, 31中搜索能使y取最大值的點(diǎn)a的問(wèn)題。那么，0, 31 中的點(diǎn)x就是個(gè)體, 函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間0, 31就是一個(gè)(解)空間 。這樣, 只要能給出個(gè)體x的適當(dāng)染色體編碼, 該問(wèn)題就可以用遺傳算法來(lái)解決。3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法(1) 設(shè)定種群規(guī)模設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。編

47、碼染色體，產(chǎn)生初始種群。 將種群規(guī)模設(shè)定為將種群規(guī)模設(shè)定為4；用；用5位二進(jìn)制數(shù)編碼染色體；取位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群下列個(gè)體組成初始種群S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定義適應(yīng)度函數(shù)定義適應(yīng)度函數(shù), 取適應(yīng)度函數(shù)：取適應(yīng)度函數(shù)：f (x)=x2 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法(3) 計(jì)算各代種群中的各個(gè)體的適應(yīng)度, 并對(duì)其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。

48、首先計(jì)算種群S1中各個(gè)體 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的適應(yīng)度f(wàn) (si) 。容易求得： f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 3613、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法再計(jì)算種群S1中各個(gè)體的選擇概率。NjjiixfxfxP1)()()(選擇概率的計(jì)算公式為選擇概率的計(jì)算公式為 由此

49、可求得由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.313、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法 輪盤賭選擇示意圖s40.31s20.49s10.14s30.063、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法選擇-復(fù)制 染色體染色體 適應(yīng)度適應(yīng)度選擇概率選擇概率選中次數(shù)選中次數(shù)s1=01101 169 0.14 1s2=11000 576 0.49 2s

50、3=01000 64 0.06 0s4=10011 361 0.31 1于是，經(jīng)選擇復(fù)制得群體： s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19） 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法交叉 設(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）3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)

51、單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法變異 設(shè)變異率pm=0.001。這樣，群體S1中共有 540.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。 于是，得到第二代種群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法 第二代種群第二代種群S2中各染色體的情況中各染色體的情況 染色體染色體 適應(yīng)度適應(yīng)度選擇概率選擇概率 估計(jì)的估計(jì)的選中次數(shù)選中次數(shù)s1=11001 625

52、0.36 1s2=01100 144 0.08 0s3=11011 729 0.41 2s4=10000 256 0.15 13、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中個(gè)染色體都被選中，則得到群體： s1=11001（25）, s2= 11011（27） s3=11011（27）, s4= 10000（16） 做交叉運(yùn)算，讓s1與s2，s3與s4 分別交換后三位基因，得 s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011

53、（19） 這一輪仍然不會(huì)發(fā)生變異。 于是，得第三代種群S3： s1=11100（28）, s2=01001（9） s3=11000（24）, s4=10011（19） 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法 第三代種群第三代種群S3中各染色體的情況中各染色體的情況 染色體染色體 適應(yīng)度適應(yīng)度選擇概率選擇概率 估計(jì)的估計(jì)的選中次數(shù)選中次數(shù)s1=11100 784 0.44 2s2=01001 81 0.04 0s3=11000 576 0.32 1s4=10011 361 0.20 13、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例

54、：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法 設(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ā)生變異。 于是，得第四代種群S4： s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16） 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)

55、建模專題之遺傳算法遺傳算法 顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。 將31代入函數(shù)y=x2中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961。 3、遺傳算法簡(jiǎn)單舉例：函數(shù)極值、遺傳算法簡(jiǎn)單舉例：函數(shù)極值數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法YYy=x2 8 13 19 24 X第一代種群及其適應(yīng)度y=x2 12 16 25 27 XY第二代種群及其適應(yīng)度y=x2 9 19 24 28 XY第三代種群及其適應(yīng)度y=x2 16 24 28

56、31 X第四代種群及其適應(yīng)度數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法課堂練習(xí)課堂練習(xí)v 求一元函數(shù)求一元函數(shù)f(x)的最大值：的最大值： 要求求解精度到要求求解精度到6位小數(shù)位小數(shù)2 , 1 0 . 2)10sin()(xxxxf數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法v 編碼 表現(xiàn)型：x 基因型：二進(jìn)制編碼（串長(zhǎng)取決于求解精度） 按編碼原理：假設(shè)要求求解精度到6位小數(shù)，區(qū)間長(zhǎng)度為2-(-1)3，即需將區(qū)間分為3/0.000001=3106等份。 所以編碼的二進(jìn)制串長(zhǎng)應(yīng)為22位。419430423000000220971522221數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法v 產(chǎn)生初

57、始種群 產(chǎn)生的方式：隨機(jī) 產(chǎn)生的結(jié)果：長(zhǎng)度為22的二進(jìn)制串 產(chǎn)生的數(shù)量：種群的大?。ㄒ?guī)模），如30，50 1111010011100001011000 1100110011101010101110 1010100011110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法v 計(jì)算適應(yīng)度直接用目標(biāo)函數(shù)作為適應(yīng)度函數(shù) 解碼：將個(gè)體s轉(zhuǎn)化為-1,2區(qū)間的實(shí)數(shù)： s= x=0.637197 計(jì)算x的函數(shù)值（適應(yīng)度）： f(x)=xsin(10 x)+

58、2.0=2.586345數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法v 遺傳操作 選擇：比例選擇法； 交叉：?jiǎn)吸c(diǎn)交叉； 變異：小概率變異數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法v 模擬結(jié)果 設(shè)置的參數(shù)： 種群大小50；交叉概率0.75；變異概率0.05；最大代數(shù)200。 得到的最佳個(gè)體： smax=; xmax=1.8506; f(xmax)=3.8503;數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法v 模擬結(jié)果 進(jìn)化的過(guò)程：世代數(shù)世代數(shù)自變量自變量適應(yīng)度適應(yīng)度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8

59、503801.85063.85031201.85063.85032001.85063.8503數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法v考慮問(wèn)題：能否用遺傳算法解決以下問(wèn)題考慮問(wèn)題：能否用遺傳算法解決以下問(wèn)題1、2、3、 , 1 , 0)(, 1 , 0)()( iiijiuxlnjxhmixgxfMinimize2 , 1 0 . 2)(10sin()y(m22yxexyxxfaxy， , 1 , 0)(, 1 , 0)()(,),(),( 21iiijikuxlnjxhmixgxfxfxfMinimize數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法Contents of Section

60、 4巡回旅行商問(wèn)題巡回旅行商問(wèn)題4.14.24.3基本操作基本操作計(jì)算仿真結(jié)果計(jì)算仿真結(jié)果4 4 遺傳算法求解巡回旅行商問(wèn)題遺傳算法求解巡回旅行商問(wèn)題數(shù)學(xué)建模專題之?dāng)?shù)學(xué)建模專題之遺傳算法遺傳算法4 遺傳算法求解巡回旅行商問(wèn)題遺傳算法求解巡回旅行商問(wèn)題4.1 巡回旅行商問(wèn)題巡回旅行商問(wèn)題City5City1City2City3City4 巡回旅行商問(wèn)題（巡回旅行商問(wèn)題（Traveling salesman problem, TSP）可描述如下：）可描述如下：已知已知N個(gè)城市之間的相互距離，現(xiàn)有一推銷員必須遍歷這個(gè)城市之間的相互距離，現(xiàn)有一推銷員必須遍歷這N個(gè)城市，并且個(gè)城市，并且每個(gè)城市只能訪問(wèn)