《遺傳算法畢業(yè)論文遺傳算法在實(shí)際數(shù)值函數(shù)優(yōu)化問(wèn)題中的應(yīng)用研究其中以解決函數(shù)問(wèn)題為例》由會(huì)員分享，可在線閱讀，更多相關(guān)《遺傳算法畢業(yè)論文遺傳算法在實(shí)際數(shù)值函數(shù)優(yōu)化問(wèn)題中的應(yīng)用研究其中以解決函數(shù)問(wèn)題為例（36頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、蘇州大學(xué)自學(xué)考試畢業(yè)論文（設(shè)計(jì)） 遺傳算法求 中文摘要： 本文首先介紹遺傳算法的歷史背景，基本思想，對(duì)遺傳算法的常見(jiàn)的編碼解碼方法進(jìn)行了深入的闡述，并對(duì)算子選擇方法進(jìn)行深入分析和對(duì)比，在此基礎(chǔ)上把遺傳算法應(yīng)用于求解復(fù)雜函數(shù)的極值計(jì)算。最后在MATLAB語(yǔ)言環(huán)境下編寫(xiě)程序，對(duì)求解函數(shù)的最大值進(jìn)行了仿真，并對(duì)調(diào)試的結(jié)果進(jìn)行了分析，得出了部分結(jié)論。 關(guān)鍵詞：遺傳算法 最優(yōu)解 算子選擇 復(fù)雜函數(shù) 作者：xx xx

2、 指導(dǎo)老師：xxxx xx Using Genetic Algorithm to Solve Extreme Problem of Complex Function Abstract Firstly, the historical background and basic idea of genetic algorithm are introduced in this paper. The common coding and decoding met

3、hod of genetic algorithm are discussed too. Secondly, the selection method of genetic operator is analyzed and compared deeply, based on which genetic algorithm is used to solve extreme problem of complex function. Finally, with MATLAB software, the program is compiled and the maximum is sought ou

4、t. At the end of the paper, the debugging result is analyzed and the conclusion is given. Keywords: Genetic Algorithm Optimal Solution Operator Selection Complex Function Written by : xx xx Supervised by

5、: xxxx xx 目 錄 第一章 緒論……………………………………………………………………………… (5) 1.1 遺傳算法生物學(xué)背景………………………………………………………………(5) 1.1.1 遺傳與變異…………………………………………………………………………(5) 1.1.2 進(jìn)化………………………………………………………………………………… (5) 1.2 本文主要內(nèi)容……………………………………………………………………… (5) 第二章 遺傳算法簡(jiǎn)介………………………………………………………………… (6) 2.1 遺傳算法歷史和發(fā)

6、展………………………………………………………………(6) 2.2 遺傳算法的基本原理………………………………………………………………(6) 2.3 遺傳算法的特點(diǎn)……………………………………………………………………(7) 2.4 遺傳算法的目的……………………………………………………………………(7) 2.5 遺傳算法應(yīng)用………………………………………………………………………(8) 第三章 遺傳算法的參數(shù)和算子選擇………………………………………………(10) 3.1 遺傳算法的數(shù)學(xué)理論……………………………………………………………(10) 3.2 編碼………………

7、…………………………………………………………………(11) 3.2.1 編碼方法………………………………………………………………………… (11) 3.2.2 編碼原則………………………………………………………………………… (13) 3.3 個(gè)體適應(yīng)度函數(shù)………………………………………………………………… (13) 3.3.1 評(píng)價(jià)個(gè)體適應(yīng)…………………………………………………………………… (13) 3.2.2 適應(yīng)度尺度變換…………………………………………………………………(14) 3.3 算子選擇……………………………………………………………………………(1

8、4) 3.3.1 選擇運(yùn)算………………………………………………………………………… (14) 3.3.2 交叉運(yùn)算……………………………………………………………………………(16) 3.3.3 變異運(yùn)算……………………………………………………………………………(18) 3.4 其他運(yùn)行參數(shù)……………………………………………………………………… (18) 第四章 遺傳算法求解復(fù)雜函數(shù)極值問(wèn)題………………………………………… (20) 4.1 遺傳算法的求解步驟………………………………………………………………(20) 4.2 算例驗(yàn)證………………………………………………

9、…………………………… (24) 第五章 結(jié)論………………………………………………………………………………(28) 參考文獻(xiàn)……………………………………………………………………………………(28) 附錄（程序）………………………………………………………………………………(29) 第一章 緒 論 1.1遺傳算法生物學(xué)背景 生物的進(jìn)化是一個(gè)奇妙的優(yōu)化過(guò)程，它通過(guò)選擇淘

10、汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。 1.1.1 遺傳與變異 1、遺傳 世間的生物從其親代繼承特性或性狀，這種生命現(xiàn)象叫遺傳，研究這種生命現(xiàn)象的科學(xué)叫做遺傳學(xué)。遺傳信息是由基因組成的，生物的各種性狀由其相應(yīng)基因來(lái)控制，基因是遺傳的基本單位。細(xì)胞分裂具有自我復(fù)制的能力，在細(xì)胞分裂的過(guò)程中，其遺傳基因也同時(shí)被復(fù)制到下一代，從而其性狀也被下一代所繼承。 2、變異 細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過(guò)復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞的基因，在進(jìn)行細(xì)胞復(fù)制時(shí)，雖然概率很小，但也有可能產(chǎn)生某些復(fù)制差

11、錯(cuò)，從而使DNA發(fā)生某種變異產(chǎn)生出新的染色體，從而表現(xiàn)出新的性狀。 1.1.2 進(jìn)化 生物在其延續(xù)生存的過(guò)程中，逐漸適應(yīng)于其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種現(xiàn)象叫做進(jìn)化。新的基因依據(jù)其與環(huán)境的適應(yīng)程度決定其增殖能力，有利于生存環(huán)境的基因逐漸增加，而不利于生存環(huán)境的基因逐漸減少，通過(guò)這種自然的選擇，物種漸漸的向適應(yīng)于生存環(huán)境的方向進(jìn)化，從而產(chǎn)生優(yōu)良的物種。 1.2 本文主要內(nèi)容 本文主要討論遺傳算法在實(shí)際數(shù)值函數(shù)優(yōu)化問(wèn)題中的應(yīng)用，即對(duì)實(shí)際問(wèn)題建模后求函數(shù)最大值的問(wèn)題。遺傳算法通過(guò)對(duì)群體所施加的迭代進(jìn)化過(guò)程，不斷的將當(dāng)前群體中具有較高適應(yīng)度的個(gè)體遺傳到下一代群體中，

12、并且不斷的淘汰掉適應(yīng)度較低的個(gè)體，從而最終尋求出適應(yīng)度最大的個(gè)體。這個(gè)適應(yīng)度最大的個(gè)體經(jīng)解碼處理之后所對(duì)應(yīng)的個(gè)體表現(xiàn)型即為實(shí)際問(wèn)題最優(yōu)解或是最近似最優(yōu)解 第二章 遺傳算法簡(jiǎn)介 2.1 歷史與發(fā)展 二十世紀(jì)六十年代，I.Rechenberg在他的《演化戰(zhàn)略》中第一次引入了進(jìn)化算法的思想（起初稱之為Evolutionsstragegie）。他的這一思想逐漸被其他一些研究者發(fā)展。遺傳算法（Genetic Algorithms） 是John Holland 發(fā)明的，后來(lái)他和他的學(xué)生及他的同事又不斷發(fā)展了它。終于，在1975年John Holland 出版了專著《自然系統(tǒng)和人工系統(tǒng)中的

13、自適應(yīng)》（Adaption In Natural and Artificial Systems）。 1992年，John Koza 曾經(jīng)使用遺傳算法編出新的程序去做一些具體的工作。他稱他的這種方法為“進(jìn)化規(guī)劃”（Genetic Programming，簡(jiǎn)稱GP）。其中使用了LISP規(guī)劃方法，這是因?yàn)檫@種語(yǔ)言中的程序被表示為“分析樹(shù)”（Parse Tree），而這種遺傳算法就是以這些分析樹(shù)為對(duì)象的。 2.2 遺傳算法的基本原理： 遺傳算法GA把問(wèn)題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置

14、于問(wèn)題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問(wèn)題的最優(yōu)解。 這里所指的某種結(jié)束準(zhǔn)則一般是指?jìng)€(gè)體的適應(yīng)度達(dá)到給定的閥值；或者個(gè)體的適應(yīng)度的變化率為零。 圖2-1中表示了遺傳算法的執(zhí)行過(guò)程。 圖2-1 遺傳算法基本原理 2.3 遺傳算法特點(diǎn)： （1） 遺傳算法的操作對(duì)象是一組可行解，而非單個(gè)可行解；搜索軌道有多條，而非單條，因此具有良好的并行性。 （2） 遺傳算法只需利用目標(biāo)函數(shù)取值信息，而無(wú)須梯度等高價(jià)信息，

15、因而實(shí)用用于大規(guī)模高度非線形的不連續(xù)多峰值函數(shù)的優(yōu)化以及無(wú)解析表達(dá)式的目標(biāo)函數(shù)的優(yōu)化，具有很強(qiáng)的通用性。 （3） 遺傳算法的擇優(yōu)機(jī)制是一種“軟“策略，加上其良好的并行性使其具有良好的全局優(yōu)化性能和穩(wěn)健性魯棒性。 （4） 遺傳算法的可行解集是經(jīng)過(guò)編碼的，目標(biāo)函數(shù)可解釋為編碼化個(gè)體的適應(yīng)值因而具有良好的可操作性與簡(jiǎn)單性。 2.4 遺傳算法的目的 典型的遺傳算法CGA(Canonical Genetic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問(wèn)題： 考慮對(duì)于一群長(zhǎng)度為L(zhǎng)的二進(jìn)制編碼bi，i＝1，2，…，n；有 bi∈{0,1}L 給定目標(biāo)函數(shù)f，有f(bi)，并且76

16、 0 同時(shí) f(bi)≠f(bi+1) 求滿足下式 max{f(bi)|bi∈{0,1}L} 的bi。 很明顯，遺傳算法是一種最優(yōu)化方法，它通過(guò)進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串bi處，即求出最優(yōu)解。 2.5 遺傳算法的應(yīng)用 遺傳算法已經(jīng)在很多復(fù)雜問(wèn)題（比如說(shuō)NP-難題）、機(jī)器學(xué)習(xí)和簡(jiǎn)單的進(jìn)化規(guī)劃中得到了使用。遺傳算法在一些藝術(shù)領(lǐng)域也取得了很大成就，比如說(shuō)進(jìn)化圖片和進(jìn)化音樂(lè)。 遺傳算法的優(yōu)勢(shì)在于他的并行性。遺傳算法在搜索空間中非常獨(dú)立地移動(dòng)（按照基因型而不是表現(xiàn)型），所以它幾乎不可能像其它

17、算法那樣“粘”在局部極值點(diǎn)。 遺傳算法更容易實(shí)現(xiàn)。一旦你有了一個(gè)遺傳算法的程序，如果你想解決一個(gè)新的問(wèn)題，你只需要針對(duì)新的問(wèn)題重新進(jìn)行基因編碼就行。如果編碼方法也相同，那你只需要改變一下適應(yīng)度函數(shù)就可以了。當(dāng)然，選擇編碼方法和適應(yīng)度函數(shù)是一件非常難的問(wèn)題。 遺傳算法的缺點(diǎn)是它的計(jì)算時(shí)間太長(zhǎng)。它們可能比其他任何算法需要的時(shí)間都長(zhǎng)。當(dāng)然，對(duì)于今天的高速計(jì)算機(jī)來(lái)說(shuō)，這已經(jīng)不是個(gè)大問(wèn)題了。 為了讓讀者更好地了解遺傳算法所解決的問(wèn)題,這里有一個(gè)關(guān)于遺傳算法應(yīng)用的小列表: （1）非線性動(dòng)態(tài)系統(tǒng)——預(yù)測(cè)，數(shù)據(jù)分析； （2）神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和權(quán)重設(shè)計(jì)； （3）自動(dòng)控制導(dǎo)彈的軌道設(shè)

18、計(jì)； （4）進(jìn)化LISP規(guī)劃（遺傳規(guī)劃）； （5）戰(zhàn)略計(jì)劃； （6）蛋白質(zhì)分子的形狀的尋找； （7）旅行商問(wèn)題和時(shí)間序列排序問(wèn)題； 第三章 遺傳算法的主要參數(shù)及算子選擇 3.1 遺傳算法的數(shù)學(xué)理論 3.1.1 模式定理 遺傳算法中，在選擇，交叉和變異算子的作用下，具有低階，短的定義長(zhǎng)度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按指數(shù)級(jí)增加。 其中： (1) 模式表示一些相似的模塊，它描述了在某些位置上具有相似結(jié)構(gòu)特

19、征的個(gè)體編碼串的一個(gè)子集。 (2) 在模式H中具有確定基因值的位置數(shù)目叫做該模式的模式階。 (3) 模式H中第一個(gè)確定基因值的位置和最后一個(gè)確定基因值的位置之間的距離稱為該模式的模式定義長(zhǎng)度。 模式定理闡述了遺傳算法的理論基礎(chǔ)，它說(shuō)明了模式的增加規(guī)律，同時(shí)也給遺傳算法的應(yīng)用提供了指導(dǎo)作用。 3.1.2 積木塊假設(shè) 模式定理說(shuō)明了具有某種結(jié)構(gòu)特征的模式在遺傳進(jìn)化過(guò)程中其樣本數(shù)將按指數(shù)級(jí)增加，這種模式具有低階，短的定義長(zhǎng)度，且平均適應(yīng)度高于群體平均適應(yīng)度的模式。這種模式被稱為積木塊。 模式定理說(shuō)明了積木塊的樣本數(shù)呈指數(shù)級(jí)增長(zhǎng)，也說(shuō)明了用遺傳算法尋求最優(yōu)化樣本的可能性

20、，但它并未指明遺傳算法一定能夠?qū)で蟮阶顑?yōu)樣本而積木塊假設(shè)卻說(shuō)明了遺傳算法的這種能力。 定義：個(gè)體的基因塊通過(guò)選擇，交叉，變異等遺傳算子的作用，能夠相互連接在一起，形成適應(yīng)度更高的個(gè)體編碼串。 作用：積木塊假設(shè)說(shuō)明了用遺傳算法求解各類問(wèn)題的基本思想，即通過(guò)基因塊之間的相互拼接能夠產(chǎn)生出問(wèn)題更好的解?；谀Ｊ蕉ɡ砗头e木塊假設(shè)，就使得我們能夠在很多應(yīng)用問(wèn)題中廣泛的使用遺傳算法的思想。 3.2 編碼 定義：遺傳算法中如何描述問(wèn)題的可行解，即把一個(gè)問(wèn)題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱為編碼 作用： 編碼是應(yīng)用遺傳算法時(shí)要解決的首要問(wèn)題，也是設(shè)計(jì)遺傳算

21、法時(shí)的一個(gè)關(guān)鍵步驟。編碼方法除了決定了個(gè)體的染色體排列形式之外還決定個(gè)體從搜索空間的基因型變換到解空間的表現(xiàn)性時(shí)的解碼方法，編碼方法也影響到交叉算子和變異算子的遺傳算法的運(yùn)算方法。由此看見(jiàn)，編碼方法在很大程度上決定了如何進(jìn)行群體的遺傳化運(yùn)算及遺傳進(jìn)化運(yùn)算效率。 3.2.1編碼方法 1、二進(jìn)制編碼方法 定義：二進(jìn)制編碼方法是遺傳算法中最常見(jiàn)的一種編碼方法，它使用的編碼符號(hào)集是由二進(jìn)制符號(hào)0和1所組成的二值符號(hào)集｛0，1｝，它所構(gòu)成的基因型是一個(gè)二進(jìn)制符號(hào)串。 在使用二進(jìn)制編碼時(shí)，每一個(gè)基因就是一個(gè)由0或者1組成的字符串。 表 3-1二進(jìn)制編碼的基因 基因A 101100101

22、100101011100101 基因B 111111100000110000011111 使用二進(jìn)制編碼時(shí)，即使等位基因的數(shù)量不大，我們也可以得到很多種可能的基因。另一方面，這種方法對(duì)于很多問(wèn)題來(lái)都很不自然，所以有時(shí)候在交叉和變異結(jié)束后還要做一些調(diào)整。 2、格雷碼編碼方法 定義：格雷碼是這樣的一種編碼方法，其連續(xù)2個(gè)整數(shù)所對(duì)應(yīng)的編碼值之間僅僅只有一個(gè)碼位是不相同的，其余碼位都相同。 假設(shè)有一個(gè)二近制編碼為B=bmbm-1…b2b1,其對(duì)應(yīng)的格雷碼為G=gmgm-1..g2g1。 由二進(jìn)制編碼到格雷碼換算公式為：

23、 公式(3-1) 由格雷碼到二進(jìn)制轉(zhuǎn)換公式為： 公式(3-2) 格雷碼優(yōu)點(diǎn)： （1） 便于提高遺傳算法的局部搜索能力 （2） 交叉，變異等遺傳操作便于實(shí)現(xiàn) （3） 符合最小字符串編碼原則 （4） 便于利用模式定理對(duì)算法進(jìn)行理論分析 3、浮點(diǎn)數(shù)編碼方法 定義：所謂浮點(diǎn)數(shù)編碼方法是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。 例如：若一個(gè)優(yōu)化問(wèn)題含有5個(gè)變量xi ( I=1,2,…5)每個(gè)變量都有其對(duì)應(yīng)的上下限[Umin,Umax],則: X: 5.80 6.

24、90 3.50 3.80 5.00 就表示一個(gè)體的基因型。其對(duì)應(yīng)的表現(xiàn)型是：X =[5.80 , 6.90 , 3.50 , 3.80 , 5.00]T 浮點(diǎn)數(shù)編碼方法有下面幾個(gè)優(yōu)點(diǎn)： （1） 適合于在遺傳算法中表示范圍較大的數(shù)。 （2） 適合于精度要求較高的遺傳算法 （3） 便于較大空間的遺傳搜索 （4） 改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算效率 （5） 便于遺傳算法和經(jīng)典油畫(huà)方法的混合使用 （6） 便于設(shè)計(jì)針對(duì)問(wèn)題的專門知識(shí)的知識(shí)型遺傳算子 （7） 便于處理復(fù)雜的決策變量約束條件 4、值編碼（Value Encoding） 在很多問(wèn)題中我們還可以采用直接的

25、值編碼,也就是說(shuō)用一些比較復(fù)雜的數(shù)來(lái)編碼,比如說(shuō)實(shí)數(shù)。因?yàn)槎M(jìn)制編碼在這類問(wèn)題中不好用。 在值編碼中，每個(gè)基因就是一串取值。這些取值可以是與問(wèn)題有關(guān)任何值：整數(shù)，實(shí)數(shù)，字符或者其他一些更復(fù)雜的東西。 表3-2值編碼串 基因A 1.2324 5.3243 0.4556 2.3293 2.4545 基因B ABDJEIFJDHDIERJFDLDF 基因C （back）, (back), (right), (forward), (left) 3.2.2 編碼原則 （1） 應(yīng)使用能易于產(chǎn)生所求問(wèn)題相關(guān)的且具有低階短定義長(zhǎng)度模式的編碼方案。 （2

26、） 應(yīng)使用能使問(wèn)題得到自然表示和描述的具有最小字符的編碼方案。 3.3 求適應(yīng)度函數(shù) 3.3.1 評(píng)價(jià)個(gè)體適應(yīng)度 定義：遺傳算法中使用適應(yīng)度這個(gè)概念來(lái)衡量群體中各個(gè)個(gè)體在優(yōu)化計(jì)算中有可能達(dá)到或接近或有助于找到最優(yōu)解的優(yōu)良程度。適應(yīng)度較高的個(gè)體遺傳到下一代的概率教大，反之遺傳到下一代的概率相對(duì)小一些。度量個(gè)體適應(yīng)度的函數(shù)叫做適應(yīng)度函數(shù)。 評(píng)價(jià)個(gè)體適應(yīng)度的一般過(guò)程： （1） 對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體表現(xiàn)型。 （2） 由個(gè)體表現(xiàn)型可計(jì)算出對(duì)應(yīng)個(gè)體的目標(biāo)函數(shù)值。 （3） 根據(jù)最優(yōu)化問(wèn)題的類型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。 3.3.2 適應(yīng)度尺度

27、變換 在遺傳算法中各個(gè)個(gè)體被遺傳到下一代群體中的概率由該個(gè)體的適應(yīng)度來(lái)決定。如何確定適應(yīng)度對(duì)遺傳算法的性能有很大的影響。在遺傳算法運(yùn)行的初期階段，算法能夠?qū)σ? 些適應(yīng)度教高的個(gè)體進(jìn)行控制，降低其適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，從而限制其復(fù)制數(shù)量，以維護(hù)群體的多樣性。我們希望在遺傳算法運(yùn)行的后期階段，算法能夠?qū)€(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)姆糯?，擴(kuò)大最佳個(gè)體適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，以提高個(gè)體之間的競(jìng)爭(zhēng)性。 適應(yīng)度尺度變換方法： （1） 線性尺度變換 公式為： F’’=aF+b

28、 （3－2） 其中，F(xiàn)為原適應(yīng)度，F(xiàn)”為新適應(yīng)度，a,b為系數(shù)。 線性尺度變換的選取條件： a.尺度變換后全個(gè)體的新適應(yīng)度的平均值F’avg要等于原適應(yīng)度平均值Favg。 b.尺度變換后群體中新的最大適應(yīng)度F’max要等于原平均適應(yīng)度Favg的指定倍數(shù)。 （2） 乘冪尺度變換 公式為： F’=FK （3-3） 冪指數(shù)K與所求解的問(wèn)題有關(guān)，并且在算法的執(zhí)行中需要不斷對(duì)其進(jìn)行修正才能使尺度變換滿足一定的伸縮要求。 （3） 指數(shù)尺度變換 公式為：

29、 F’=exp(-βF) （3-4） 其中β決定了選擇的強(qiáng)制性，β越小，原有適應(yīng)度較高的個(gè)體的新適應(yīng)度就越與其他個(gè)體的新適應(yīng)度相差越大，亦即越增加了選擇該個(gè)體的強(qiáng)制性。 3.4算子選擇 遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中一種遺傳運(yùn)算。選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上，選擇操作的目的是為了避免基因缺失，提高全局收斂性和計(jì)算效率。 3.4.1 選擇運(yùn)算 （1） 比例選擇方法：是一種回放式隨機(jī)采樣方法。各個(gè)個(gè)體被選中的概率

30、與其適應(yīng)度大小成正比。 設(shè)群體大小為M,個(gè)體I的適應(yīng)度為Fi則個(gè)體被選種的概率Pis為： pis=Fi/∑Fi (I=1,2….M) （3-5） 由此可見(jiàn)，適應(yīng)度越高的個(gè)體被選種的概率也越大，反之適應(yīng)度越低的個(gè)體被選種的概率也越小。 （2） 最優(yōu)保存策略：當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，而是 它來(lái)替代掉本代群體中經(jīng)過(guò)交叉變異等遺傳操作后所產(chǎn)生適應(yīng)度最低的個(gè)體。我們希望適應(yīng)度最好的個(gè)體要盡可能保留到下一代群體中。 最優(yōu)保存策略進(jìn)化模型的具體操作過(guò)程是： a. 找出當(dāng)前群體中適應(yīng)度最高的個(gè)體和適應(yīng)度最低的個(gè)體。

31、 b. 若當(dāng)前群體中最佳個(gè)體的適應(yīng)度比總的迄今為止的最好個(gè)體適應(yīng)度還要高，則以當(dāng)前群體中的最佳個(gè)體做為新的迄今為止的最好個(gè)體。 c. 用迄今為止的最好個(gè)體替換掉當(dāng)前群體中最差個(gè)體。 作用： 該策略的實(shí)施可保證迄今為止所得到的最優(yōu)個(gè)體不會(huì)被交叉，變異等遺傳運(yùn)算所破壞，它遺傳算法收斂性的一個(gè)重要保證條件。 （3） 排序選擇 主要思想是：對(duì)群體中所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)個(gè)體被選中的概率，具體操作過(guò)如下： a. 對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行降序排序。 b. 根據(jù)具體問(wèn)題，設(shè)計(jì)一個(gè)概率分配表將各個(gè)概率值按上述排列次序分配給各個(gè)個(gè)體。 c.

32、以各個(gè)分配到的概率值做為其能夠遺傳到下一代的概率，基于這些概率值用比例選擇（賭輪選擇）的方法產(chǎn)生下一代群體。 （4）輪盤賭選擇方法（Roulette Wheel Selection） 父代的選擇是根據(jù)他們的適應(yīng)度做出的?；蛟绞沁m應(yīng)環(huán)境，那么它被選擇到的機(jī)會(huì)就越大。想像一個(gè)輪盤賭的機(jī)器上放置了種群中所有的基因。每一個(gè)基因所占的地方的大小和它的適應(yīng)度成正比。如下圖所示： 圖3-1 賭輪算法示意圖 然后開(kāi)始扔彈子，扔到那個(gè)地方就把對(duì)應(yīng)的基因拿出來(lái)。顯然，適應(yīng)度越大的基因被選到的機(jī)會(huì)就越大。 這個(gè)過(guò)程可以被下面的這個(gè)算法來(lái)模擬： 1．［求和］ 計(jì)算所有種群的適應(yīng)度的和S

33、； 2．［選擇］ 在區(qū)間（0，S）上隨機(jī)的產(chǎn)生一個(gè)數(shù)r； 3．［循環(huán)］ 從某個(gè)基因開(kāi)始，逐一取出基因來(lái)，把它的適應(yīng)度加到s上去（s開(kāi)始為0），如果s大于r，則停止循環(huán)并返回當(dāng)前基因； 當(dāng)然，第一步在計(jì)算中只需要執(zhí)行一次。 3.4.2交叉算子 遺傳算法中的所謂交叉運(yùn)算，是指對(duì)兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成2個(gè)新的個(gè)體，交叉運(yùn)算是遺傳算法區(qū)別其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法。 交叉算子的設(shè)計(jì)過(guò)程： 1如何確定交叉點(diǎn)的位置 2如何進(jìn)行部分基因交換 最常用的交叉算子是單點(diǎn)交叉算子。下面介紹集中適

34、合于二進(jìn)制編碼個(gè)體或浮點(diǎn)數(shù)編碼個(gè)體的交叉算子： （1） 單點(diǎn)交叉：它是指?jìng)€(gè)體編碼串中只隨即設(shè)置一個(gè)交叉點(diǎn)然后在該點(diǎn)相互交換2個(gè)配 對(duì)個(gè)體的部分染色體。 特點(diǎn)：假如鄰接基因座之間的關(guān)系能夠提供比較好的個(gè)體性狀和較高的個(gè)體適應(yīng)度的話則這個(gè)單點(diǎn)交叉操作破壞這種個(gè)體性狀和降低個(gè)體適應(yīng)度的可能性最小。 （2） 雙點(diǎn)交叉和多點(diǎn)交叉：是指定個(gè)體編碼串中隨機(jī)設(shè)置2個(gè)或多個(gè)交叉點(diǎn)然后進(jìn)行部分基因交換。 具體操作過(guò)程： 1在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置2個(gè)交叉點(diǎn) 2交換2個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體。 例如： A: x x | x x x x x | x x x -

35、-----A’: x x | y y y y y| x x x B: y y | y y y y y | y y y------B’: y y | x x x x x| y y y 交叉點(diǎn)1 交叉點(diǎn)2 雙點(diǎn)交叉示意圖 11001011 + 11011111 = 11011111 圖（3-2） 均勻交叉算子 (Uniform Crossover):子代基因的每一個(gè)位點(diǎn)是隨機(jī)地來(lái)自于兩個(gè)父代基因中的一個(gè)的; 均勻交叉示意圖 11001011 + 11011101 = 11011111

36、 圖（3-3） 3.4.3 變異算子 遺傳算法中所謂變異運(yùn)算是指?jìng)€(gè)體染色體編碼串中某些基因座上的基因值用該基因座的其他等位基因替換，從而形成新個(gè)體。 位點(diǎn)轉(zhuǎn)換算子（Bit Inversion）：選擇一些位點(diǎn)然后將這些地方的0，1互換； 圖（3-4） 在遺傳算法中使用變異算子的目的： 1 改善遺傳算法局部搜索能力 2維持群體多樣性，防止出現(xiàn)早熟現(xiàn)象 變異算子的常用方法： a、基本位變異：指對(duì)個(gè)體基因串以變異概率隨機(jī)指定某一位或幾位基因座上的基因值做變異運(yùn)算 b、均勻變異：指分別用符合某一范圍內(nèi)隨機(jī)數(shù)，以某一較小概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因

37、值。 c、 邊界變異：邊界變異是上述均勻變異操作的一個(gè)變形遺傳算法。在進(jìn)行邊界變異操作時(shí)，隨機(jī)的取基因座的2個(gè)對(duì)應(yīng)邊界基因值之一去替換原來(lái)的基因值。 d、非均勻變異：對(duì)每個(gè)基因座都以相同的概率進(jìn)行變異運(yùn)算之后相當(dāng)于整個(gè)解向量在解空間中，作了一個(gè)輕微的變動(dòng)。 3.5 遺傳算法的其他運(yùn)行參數(shù) （1） 編碼串長(zhǎng)度L：使用二進(jìn)制來(lái)表示個(gè)體時(shí)，編碼串長(zhǎng)度L的選取與問(wèn)題所要求的求解精度有關(guān)。 （2） 群體大小M：表示群體中所含個(gè)體的數(shù)量。M取值越小可提運(yùn)算速度但降低群體多樣性。容易引起遺傳算法的早熟現(xiàn)象，而當(dāng)M取值較大時(shí)降低了遺傳算法的運(yùn)行效率。一般建議范圍20-100。 （3） 交叉概

38、率Pc。交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法，一般建議范圍是 0.4-0.99。隨著遺傳算法在線性能的提高可以增大交叉概率的取值。 （4） 變異概率Pm。一般建議范圍是0.0001~0.1，隨著遺傳算法在線性能的下降，可以減小變異概率的取值 （5） 終止帶寬T它表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行并將最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。建議范圍是100~1000 （6） 代溝G：表示每一代群體中被替換掉的個(gè)體在全部個(gè)體中所占的百分比。

39、 第四章：用遺傳算法求解復(fù)雜函數(shù)極值問(wèn)題 本課題采用遺傳算法求解函數(shù)最大值問(wèn)題，應(yīng)用常規(guī)的二進(jìn)度編碼，利用賭輪算法選擇最憂群體，進(jìn)行交叉變異等遺傳操作，最終求出所求函數(shù)最大值即最憂解，最后在MATLAB語(yǔ)言環(huán)境下進(jìn)行調(diào)試，更改相關(guān)參數(shù)，得出幾組最憂解圖象并進(jìn)行對(duì)比分析。 所求問(wèn)題為f(x)=x+9*sin(4x)+8*cos(3x)的最大值，其中定義域?yàn)?<=x<=12，采用二進(jìn)制編碼，選取種群個(gè)體數(shù)目為20，設(shè)定二進(jìn)制編碼長(zhǎng)度為10，交叉概率為0.8，變異概率是0.01。 4.1 本算例的求解步驟 （1） 確定決策變量和約束條

40、件 【問(wèn)題】求f(x)= 11*sin(6*x)+7*cos(5*x)的最大值，其中0<=x<=2*pi 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為20，二進(jìn)制編碼長(zhǎng)度為10，交叉概率為0.8,變異概率為0.01 （2） 確定編碼方法 用長(zhǎng)度為十的二進(jìn)制編碼串來(lái)分別表示兩個(gè)決策變量Umax(2π) Umin(0)。10位二進(jìn)制 編碼串可以表示為0到1023之間的1024個(gè)不同的數(shù)，故將Umax Umin的定義域離散為1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有1024個(gè)不同的離散點(diǎn)。從離散點(diǎn)Umin到Umax，依次讓它們分別對(duì)應(yīng)從0000000000（0）到1111111111

41、（1023）之間的二進(jìn)制編碼。再將分別表示Umax Umin的二進(jìn)制編碼串聯(lián)在一起，組成一個(gè)20位長(zhǎng)的二進(jìn)制編碼串，它構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間具有一一對(duì)應(yīng)的關(guān)系。 例如：就表示為一個(gè)個(gè)體的基因型，其中前十位表示Umax 后十位表示Umin X: 11111111 00000000 2π 0 00000000…00000000=0 ----- Umin 00000000…00000001=1 ---- Umin+￡ … … … 11111111

42、…11111111=2^l-1 ---- Umax 則二進(jìn)制編碼精度為： ￡=Umax-Umin/2^l-1 公式（4-1） 假設(shè)某一個(gè)個(gè)體編碼是 X: blbl-1bl-2…b2b1 確定解碼方法 Xi=Umin+ L ∑ bi* 2^( i-1) * Umax-Umin/2^l -1 i=1 公式（4-2） 解碼時(shí)需先將20位長(zhǎng)的

43、二進(jìn)制編碼串切斷為兩個(gè)10位長(zhǎng)的二進(jìn)制編碼串，然后分別將他們轉(zhuǎn)化為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為Y1 Y2。根據(jù)前述個(gè)體編碼方法和定義域的離散化方法可知，將代碼Yi轉(zhuǎn)換為變量Xi的解碼公式為： （3） 確定個(gè)體評(píng)價(jià)方法 在遺傳算法中，以個(gè)體適應(yīng)度的大小來(lái)確定該個(gè)體被遺傳到下一代群體中的概率?；具z傳算法使用比例選擇算子來(lái)確定群體中各個(gè)個(gè)體遺傳到下一代群體中的數(shù)量。為正確計(jì)算不同情況下各個(gè)個(gè)體的遺傳概率，要求所有個(gè)體的適應(yīng)度必須為整數(shù)或者是零，不能是負(fù)數(shù) 為滿足適應(yīng)度取非負(fù)值的要求，基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)f(x)變換為個(gè)體適應(yīng)度F(X) 方法一：對(duì)

44、于求目標(biāo)函數(shù)最大值的優(yōu)化問(wèn)題，變換方法為： F(X)={ F(X) + Cmin, if f(x)+ Cmin>0 0, if f(x)+Cmin≤0 公式（4-3） 式中，Cmin為一個(gè)適當(dāng)?shù)叵鄬?duì)比較小的數(shù)，它可用下面幾種方法之一來(lái)選取。 （一）預(yù)先指定一個(gè)較小的數(shù)。 （二）進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。 （三）當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。 方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，變換方法為： F(X)={ Cmax-f (X) , if f (X)

45、 0, if f(x)≥Cmax 公式（4-4） 式中，Cmax位為一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可用下面幾種方法之一來(lái)選取。 （一）預(yù)先指定一個(gè)較大的數(shù)。 （二）進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。 （三）當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值 根據(jù)適者生存原則選擇下一代的個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。 給出目標(biāo)函數(shù)f，則f(bi)稱為個(gè)體bi的適應(yīng)度。以 (3-86) 為選中bi為下一代個(gè)體的次數(shù)。 顯然．從式(3—86)可知： a、適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。

46、 b、適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。 這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。對(duì)于問(wèn)題求解角度來(lái)講，就是選擇出和最優(yōu)解較接近的中間解。 （4） 設(shè)計(jì)遺傳算子 選擇運(yùn)算 a. 使用第三章的賭輪選擇算法,求解最佳適應(yīng)度種群： b. 分別求出20個(gè)初始種群中每個(gè)種群個(gè)體的適應(yīng)度函數(shù)，并計(jì)算所有種群的和S。 c. 在區(qū)間（0，S）上隨機(jī)的產(chǎn)生一個(gè)數(shù)r從某個(gè)基因開(kāi)始，逐一取出基因來(lái)，把它的適應(yīng)度加到s上去（s開(kāi)始為0），如果s大于r，則停止循環(huán)并返回當(dāng)前基因； 當(dāng)然，第一步在計(jì)算中只需要執(zhí)行一次 因此基因越是適應(yīng)環(huán)境那么它被選擇到的機(jī)會(huì)就越大。 交

47、叉運(yùn)算 使用第三章的單點(diǎn)交叉算子 對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率P。在選中的位置實(shí)行交換。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合也即產(chǎn)生新的個(gè)體。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。 本例選用單點(diǎn)交叉法： 從選擇運(yùn)算求出適應(yīng)度較高的種群，從該種群種隨機(jī)抽出2個(gè)個(gè)體基因型編碼進(jìn)行配對(duì)交叉 111111111 (個(gè)體基因型) ---------> 2π (個(gè)體表現(xiàn)型) 00000000 (個(gè)體基因型) ---------> 0 (個(gè)體表現(xiàn)型) 111111111+00000000=11011111 (產(chǎn)生的

48、新個(gè)體) 種群的各個(gè)個(gè)體兩兩配對(duì)后以交叉概率Pc=0.8隨機(jī)指定各個(gè)基因位進(jìn)行交叉運(yùn)算即生成新個(gè)體種群。 假如鄰接基因座之間的關(guān)系能夠提供比較好的個(gè)體性狀和較高的個(gè)體適應(yīng)的話則這個(gè)單點(diǎn)交叉操作破壞這種個(gè)體性狀和降低個(gè)體適應(yīng)度的可能性最小 變異運(yùn)算 使用第三章的基本位變異算子確定遺根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。 經(jīng)交叉運(yùn)算得到的新個(gè)體基因串種群以變異概率Pm=0.01隨機(jī)指定有一位

49、或幾位基因座上的基因值進(jìn)行變異操作. 11011111------->11101011 (生成的新個(gè)體) 以變異概率分別對(duì)每個(gè)或者幾個(gè)基因位做變異操作就可以生成新的種群個(gè)體。單靠變異不能在求解中得到好處。但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說(shuō)，變異增加了全局優(yōu)化的特質(zhì)。 遺傳算法的運(yùn)行參數(shù) 群體大?。篗 （20-100） 終止代數(shù)：T （100-500） 交叉概率：Pc （0.4-0.99） 變異概率：Pm (0.0001-0.1) 4.2

50、 算例驗(yàn)證 【問(wèn)題】求f(x)= 11*sin(6*x)+7*cos(5*x)的最大值，其中0<=x<=2*pi 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為20，二進(jìn)制編碼長(zhǎng)度為10，交叉概率為0.8,變異概率為0.01 X（個(gè)體表現(xiàn)型值）: 1.2805 1.2708 1.261 1.261 1.2805 1.3587 1.3392 1.261 1.3685 1.261 1.261 1.1926 1.1632 1.3587 2.4145 2.3754 1.2512 1.3294 1.2317 1.2121 Y（目標(biāo)函數(shù)值）: 17.79 17.694 17.545

51、 17.545 17.79 16.621 17.232 17.545 16.239 17.545 17.545 15.067 13.306 16.621 16.497 16.328 17.343 17.459 16.783 16.021 FINAL(最優(yōu)解)= 16.0208 由圖可見(jiàn)，遺傳代數(shù)較小時(shí)，交叉概率較大時(shí)圖象局部最優(yōu)解分散，全局最優(yōu)解緩慢收斂。 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為20，二進(jìn)制編碼長(zhǎng)度為10，交叉概率為0.6,變異概率為0.04 X（個(gè)體表現(xiàn)型值）: 1.3099 1.3099 1.3099 1.3587 1.280

52、5 1.2805 2.3851 2.3851 2.3558 1.2805 1.2805 1.2805 1.3196 1.3001 1.3392 1.3392 1.2805 1.2708 1.3099 1.2414 Y（目標(biāo)函數(shù)值）: 17.753 17.753 17.753 16.621 17.79 17.79 16.446 16.446 15.94 17.79 17.79 17.79 17.633 17.82 17.232 17.232 17.79 17.694 17.753 17.089 FINAL(最優(yōu)解)= 17.0886 由圖可見(jiàn)，當(dāng)交叉概率變小變異概率變大

53、，局部最憂解減少，全局最優(yōu)解明顯。 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為50，二進(jìn)制編碼長(zhǎng)度為10，交叉概率為0.5,變異概率為0.08 X（個(gè)體表現(xiàn)型值）: 1.2805 1.2805 1.2805 1.3099 1.3099 1.3099 1.3099 1.3099 1.3294 1.261 1.3001 1.3099 1.3099 1.3099 1.2708 1.2708 1.3099 1.2708 1.2903 1.2512 Y（目標(biāo)函數(shù)值）: 17.79 17.79 17.79 17.753 17.753 17.753

54、17.753 17.753 17.459 17.545 17.82 17.753 17.753 17.753 17.694 17.694 17.753 17.694 17.832 17.343 FINAL(最優(yōu)解)= 17.3431 由圖可見(jiàn)，遺傳代數(shù)增加，變異概率增加，全局最憂解收斂性最優(yōu)。 程序調(diào)試總結(jié)： (1) 群體大小M較小時(shí)可以提高遺傳算法的運(yùn)行速度,但是降低了群體的多樣性有可能引起算法的早熟現(xiàn)象，當(dāng)M較大時(shí)使得運(yùn)行效率降低，一般建議范圍為(20~100)最佳。 (2) 交叉操作是產(chǎn)生新個(gè)體的主要方法一般應(yīng)取值較大，但太大會(huì)破壞群體的優(yōu)良

55、模型，對(duì)進(jìn)化產(chǎn)生不利影響。取值太小產(chǎn)生新個(gè)體速度又較慢，一般建議范圍(0.4~0.99) (3) 變異概率Pm較大時(shí)雖能產(chǎn)生比較多的新個(gè)體，但有可能破壞掉較好的模型使得遺傳算法的性能近似于隨機(jī)搜索算法性能，Pm太小變異操作產(chǎn)生新個(gè)體和抑制早熟的能力較差，最佳范圍(0.0001~0.1) 第五章 結(jié)論 本文首先介紹遺傳算法歷史發(fā)展基本原理方法對(duì)遺傳算法的編碼，解碼方法進(jìn)行深入分析，從而確定了用二進(jìn)制編碼方法來(lái)求解復(fù)雜函數(shù)優(yōu)化問(wèn)題，通過(guò)選澤，交叉，變異等遺傳操作，最后用M

56、ATLAB語(yǔ)言進(jìn)行調(diào)試，改變遺傳算法相關(guān)參數(shù)求出函數(shù)最優(yōu)解并進(jìn)行對(duì)比分析。得出遺傳算法不僅可求解簡(jiǎn)單函數(shù)最值問(wèn)題，而且可以優(yōu)化許多復(fù)雜系統(tǒng)函數(shù)問(wèn)題，它提供了一種系統(tǒng)優(yōu)化函數(shù)的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類具有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多科學(xué)領(lǐng)域。 參考文獻(xiàn) [1]《遺傳算法原理及應(yīng)用》/周明，孫樹(shù)棟編著 北京國(guó)防工業(yè)出版社，1999。6 [2]《MATLAB語(yǔ)言》/張陪強(qiáng) 主編 合肥中國(guó)科學(xué)技術(shù)出版社 1995年11月 [3]《遺傳算法的基本理論與應(yīng)用》/李敏強(qiáng) 寇紀(jì)淞 科

57、學(xué)出版社 2003.3 [4]《MATLAB 語(yǔ)言及實(shí)踐教程》/肖燕彩 清華大學(xué)出版社 2004年5月 附 錄 % f(x)=11*sin(6x)+7*cos(5x) x∈[0,2*pi] % 2.8 主程序 %遺傳算法主程序 clear clf popsize=20; %設(shè)置初始參數(shù)，群體大小 chromlength=8; %字符串長(zhǎng)度（個(gè)體長(zhǎng)度），染色體長(zhǎng)度 pc=0.8; %設(shè)置交叉概率，本例中交叉概率是定值，若想設(shè)置變化的交叉概率可用表達(dá)式表示，或從寫(xiě)一個(gè) %交叉概率函數(shù)，

58、例如用神經(jīng)網(wǎng)絡(luò)訓(xùn)練得到的值作為交叉概率 pm=0.01; %設(shè)置變異概率，同理也可設(shè)置為變化的 pop=initpop(popsize,chromlength); %運(yùn)行初始化函數(shù)，隨機(jī)產(chǎn)生初始群體 for i=1:20%20為迭代次數(shù) [objvalue]=calobjvalue(pop);%計(jì)算目標(biāo)函數(shù) fitvalue=calfitvalue(objvalue); %計(jì)算群體中每個(gè)個(gè)體的適應(yīng)度 [newpop]=selection(pop,fitvalue); %復(fù)制 [newpop]=crossover(pop,pc); %交叉 [newpop]=mutation(

59、pop,pc);%變異 [bestindividual,bestfit]=best(pop,fitvalue);%求出群體中適應(yīng)值最大的個(gè)體及其適應(yīng)值 y(i)=max(bestfit); n(i)=i; pop5=bestindividual; x(i)=decodechrom(pop5,1,chromlength)*10/1023; pop=newpop; end y(i) fplot(11*sin(6*x)+7*cos(5*x),[0 2*pi]) grid on hold on plot(x,y,r*) hold off % 2.1初始化(編碼) %

60、initpop.m函數(shù)的功能是實(shí)現(xiàn)群體的初始化，popsize表示群體的大小，chromlength表示染色體的長(zhǎng)度(二值數(shù)的長(zhǎng)度)， % 長(zhǎng)度大小取決于變量的二進(jìn)制編碼的長(zhǎng)度(在本例中取8位)。 %遺傳算法子程序 %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand隨機(jī)產(chǎn)生每個(gè)單元為 {0,1} 行數(shù)為popsize，列數(shù)為chromlength的矩陣， %roud對(duì)矩陣的每個(gè)單元進(jìn)行圓整。這樣產(chǎn)生的初始種群 % 2.2 計(jì)算目標(biāo)函數(shù)值 %

61、2.2.1 將二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)(1) %遺傳算法子程序 %產(chǎn)生 [2^n 2^(n-1) ... 1] 的行向量，然后求和，將二進(jìn)制轉(zhuǎn)化為十進(jìn)制 function pop2=decodebinary(pop) [px,py]=size(pop); %求pop行和例數(shù) for i=1:py pop1(:,i)=2.^(py-1).*pop(:,i); %pop的每一個(gè)行向量（二進(jìn)制表示），for循環(huán)語(yǔ)句將每個(gè)二進(jìn)制行向量按位置 py=py-1; % 乘上權(quán)重 end

62、 pop2=sum(pop1,2); %求pop1的每行之和，即得到每行二進(jìn)制表示變?yōu)槭M(jìn)制表示值，實(shí)現(xiàn)二進(jìn)制到十進(jìn)制的轉(zhuǎn)變 % 2.2.2 將二進(jìn)制編碼轉(zhuǎn)化為十進(jìn)制數(shù)(2) %函數(shù)的功能是將染色體(或二進(jìn)制編碼)轉(zhuǎn)換為十進(jìn)制，參數(shù)spoint表示待解碼的二進(jìn)制串的起始位置 % (對(duì)于多個(gè)變量而言，如有兩個(gè)變量，采用20為表示，每個(gè)變量10為，則第一個(gè)變量從1開(kāi)始，另一個(gè)變量從11開(kāi)始。本例為1)， % 參數(shù)1ength表示所截取的長(zhǎng)度（本例為8）。 %遺傳算法子程序 %將二進(jìn)制編碼轉(zhuǎn)換成十進(jìn)制 function pop2=decodech

63、rom(pop,spoint,length) pop1=pop(:,spoint:spoint+length-1); %將從第“spoint”位開(kāi)始到第“spoint+length-1”位（這段碼位表示一個(gè)參數(shù)）取出 pop2=decodebinary(pop1); %利用上面函數(shù)“decodebinary(pop)”將用二進(jìn)制表示的個(gè)體基因變?yōu)槭M(jìn)制數(shù) % 2.2.3 計(jì)算目標(biāo)函數(shù)值 %函數(shù)的功能是實(shí)現(xiàn)目標(biāo)函數(shù)的計(jì)算，其公式采用本文示例仿真，可根據(jù)不同優(yōu)化問(wèn)題予以修改。 %遺傳算法子程序 %實(shí)現(xiàn)目標(biāo)函數(shù)的計(jì)算 function [objvalue]=calobjvalu

64、e(pop) temp1=decodechrom(pop,1,8);%將pop每行轉(zhuǎn)化成十進(jìn)制數(shù) x=temp1*10/1023;%將二值域 中的數(shù)轉(zhuǎn)化為變量域 的數(shù) objvalue=11*sin(6*x)+7*cos(5*x);%計(jì)算目標(biāo)函數(shù)值 % 2.3 計(jì)算個(gè)體的適應(yīng)值 %遺傳算法子程序 %計(jì)算個(gè)體的適應(yīng)值 function fitvalue=calfitvalue(objvalue) global Cmin; Cmin=0; [px,py]=size(objvalue); for i=1:px if objvalue(i)+Cmin>0 temp=Cmi

65、n+objvalue(i); else temp=0.0; end fitvalue(i)=temp; end fitvalue=fitvalue; % 2.4 選擇復(fù)制 % 選擇或復(fù)制操作是決定哪些個(gè)體可以進(jìn)入下一代。程序中采用賭輪盤選擇法選擇，這種方法較易實(shí)現(xiàn)。 % 根據(jù)方程 pi=fi/∑fi=fi/fsum ，選擇步驟： % 1）在第 t 代，由（1）式計(jì)算 fsum 和 pi % 2）產(chǎn)生 {0,1} 的隨機(jī)數(shù) rand( .)，求 s=rand( .)*fsum % 3）求 ∑fi≥s 中最小的 k ，則第 k 個(gè)個(gè)體被選中 % 4）進(jìn)行 N 次2）

66、、3）操作，得到 N 個(gè)個(gè)體，成為第 t=t+1 代種群 %遺傳算法子程序 %選擇復(fù)制 function [newpop]=selection(pop,fitvalue) totalfit=sum(fitvalue);%求適應(yīng)值之和 fitvalue=fitvalue/totalfit;%單個(gè)個(gè)體被選擇的概率 fitvalue=cumsum(fitvalue); %如 fitvalue=[1 2 3 4]，則 cumsum(fitvalue)=[1 3 6 10] [px,py]=size(pop); ms=sort(rand(px,1)); %從小到大排列，將"rand(px,1)"產(chǎn)生的一列隨機(jī)數(shù)變成輪盤賭形式的表示方法，由小到大排列 fitin=1; %fivalue是一向量，fitin代表向量中元素位，即fitvalue(fitin)代表第fitin個(gè)個(gè)體的單個(gè)個(gè)體被選擇的概率 newin=1; %同理 while newin<=px if(ms(newin))