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

1、蘇州大學(xué)自學(xué)考試畢業(yè)論文（設(shè)計） 遺傳算法求 中文摘要： 本文首先介紹遺傳算法的歷史背景，基本思想，對遺傳算法的常見的編碼解碼方法進行了深入的闡述，并對算子選擇方法進行深入分析和對比，在此基礎(chǔ)上把遺傳算法應(yīng)用于求解復(fù)雜函數(shù)的極值計算。最后在MATLAB語言環(huán)境下編寫程序，對求解函數(shù)的最大值進行了仿真，并對調(diào)試的結(jié)果進行了分析，得出了部分結(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 進化………………………………………………………………………………… (5) 1.2 本文主要內(nèi)容……………………………………………………………………… (5) 第二章 遺傳算法簡介………………………………………………………………… (6) 2.1 遺傳算法歷史和發(fā)

6、展………………………………………………………………(6) 2.2 遺傳算法的基本原理………………………………………………………………(6) 2.3 遺傳算法的特點……………………………………………………………………(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 個體適應(yīng)度函數(shù)………………………………………………………………… (13) 3.3.1 評價個體適應(yīng)…………………………………………………………………… (13) 3.2.2 適應(yīng)度尺度變換…………………………………………………………………(14) 3.3 算子選擇……………………………………………………………………………(1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、值編碼,也就是說用一些比較復(fù)雜的數(shù)來編碼,比如說實數(shù)。因為二進制編碼在這類問題中不好用。 在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關(guān)任何值：整數(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)生所求問題相關(guān)的且具有低階短定義長度模式的編碼方案。 （2

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

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

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

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

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

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

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

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

34、合于二進制編碼個體或浮點數(shù)編碼個體的交叉算子： （1） 單點交叉：它是指個體編碼串中只隨即設(shè)置一個交叉點然后在該點相互交換2個配 對個體的部分染色體。 特點：假如鄰接基因座之間的關(guān)系能夠提供比較好的個體性狀和較高的個體適應(yīng)度的話則這個單點交叉操作破壞這種個體性狀和降低個體適應(yīng)度的可能性最小。 （2） 雙點交叉和多點交叉：是指定個體編碼串中隨機設(shè)置2個或多個交叉點然后進行部分基因交換。 具體操作過程： 1在相互配對的兩個個體編碼串中隨機設(shè)置2個交叉點 2交換2個個體在所設(shè)定的兩個交叉點之間的部分染色體。 例如： 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 交叉點1 交叉點2 雙點交叉示意圖 11001011 + 11011111 = 11011111 圖（3-2） 均勻交叉算子 (Uniform Crossover):子代基因的每一個位點是隨機地來自于兩個父代基因中的一個的; 均勻交叉示意圖 11001011 + 11011101 = 11011111

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

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

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

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

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

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

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

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

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

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

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

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

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

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

50、 算例驗證 【問題】求f(x)= 11*sin(6*x)+7*cos(5*x)的最大值，其中0<=x<=2*pi 【分析】選擇二進制編碼，種群中的個體數(shù)目為20，二進制編碼長度為10，交叉概率為0.8,變異概率為0.01 X（個體表現(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（目標函數(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 由圖可見，遺傳代數(shù)較小時，交叉概率較大時圖象局部最優(yōu)解分散，全局最優(yōu)解緩慢收斂。 【分析】選擇二進制編碼，種群中的個體數(shù)目為20，二進制編碼長度為10，交叉概率為0.6,變異概率為0.04 X（個體表現(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（目標函數(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 由圖可見，當交叉概率變小變異概率變大

53、，局部最憂解減少，全局最優(yōu)解明顯。 【分析】選擇二進制編碼，種群中的個體數(shù)目為50，二進制編碼長度為10，交叉概率為0.5,變異概率為0.08 X（個體表現(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（目標函數(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 由圖可見，遺傳代數(shù)增加，變異概率增加，全局最憂解收斂性最優(yōu)。 程序調(diào)試總結(jié)： (1) 群體大小M較小時可以提高遺傳算法的運行速度,但是降低了群體的多樣性有可能引起算法的早熟現(xiàn)象，當M較大時使得運行效率降低，一般建議范圍為(20~100)最佳。 (2) 交叉操作是產(chǎn)生新個體的主要方法一般應(yīng)取值較大，但太大會破壞群體的優(yōu)良

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

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

57、學(xué)出版社 2003.3 [4]《MATLAB 語言及實踐教程》/肖燕彩 清華大學(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; %字符串長度（個體長度），染色體長度 pc=0.8; %設(shè)置交叉概率，本例中交叉概率是定值，若想設(shè)置變化的交叉概率可用表達式表示，或從寫一個 %交叉概率函數(shù)，

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

59、pop,pc);%變異 [bestindividual,bestfit]=best(pop,fitvalue);%求出群體中適應(yīng)值最大的個體及其適應(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ù)的功能是實現(xiàn)群體的初始化，popsize表示群體的大小，chromlength表示染色體的長度(二值數(shù)的長度)， % 長度大小取決于變量的二進制編碼的長度(在本例中取8位)。 %遺傳算法子程序 %初始化 function pop=initpop(popsize,chromlength) pop=round(rand(popsize,chromlength)); % rand隨機產(chǎn)生每個單元為 {0,1} 行數(shù)為popsize，列數(shù)為chromlength的矩陣， %roud對矩陣的每個單元進行圓整。這樣產(chǎn)生的初始種群 % 2.2 計算目標函數(shù)值 %

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

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

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

64、e(pop) temp1=decodechrom(pop,1,8);%將pop每行轉(zhuǎn)化成十進制數(shù) x=temp1*10/1023;%將二值域 中的數(shù)轉(zhuǎn)化為變量域 的數(shù) objvalue=11*sin(6*x)+7*cos(5*x);%計算目標函數(shù)值 % 2.3 計算個體的適應(yīng)值 %遺傳算法子程序 %計算個體的適應(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ù)制操作是決定哪些個體可以進入下一代。程序中采用賭輪盤選擇法選擇，這種方法較易實現(xiàn)。 % 根據(jù)方程 pi=fi/∑fi=fi/fsum ，選擇步驟： % 1）在第 t 代，由（1）式計算 fsum 和 pi % 2）產(chǎn)生 {0,1} 的隨機數(shù) rand( .)，求 s=rand( .)*fsum % 3）求 ∑fi≥s 中最小的 k ，則第 k 個個體被選中 % 4）進行 N 次2）

66、、3）操作，得到 N 個個體，成為第 t=t+1 代種群 %遺傳算法子程序 %選擇復(fù)制 function [newpop]=selection(pop,fitvalue) totalfit=sum(fitvalue);%求適應(yīng)值之和 fitvalue=fitvalue/totalfit;%單個個體被選擇的概率 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)生的一列隨機數(shù)變成輪盤賭形式的表示方法，由小到大排列 fitin=1; %fivalue是一向量，fitin代表向量中元素位，即fitvalue(fitin)代表第fitin個個體的單個個體被選擇的概率 newin=1; %同理 while newin<=px if(ms(newin))