《遺傳算法畢業(yè)論文遺傳算法在實(shí)際數(shù)值函數(shù)優(yōu)化問題中的應(yīng)用研究其中以解決函數(shù)問題為例》由會員分享，可在線閱讀，更多相關(guān)《遺傳算法畢業(yè)論文遺傳算法在實(shí)際數(shù)值函數(shù)優(yōu)化問題中的應(yīng)用研究其中以解決函數(shù)問題為例（36頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、蘇州大學(xué)自學(xué)考試畢業(yè)論文（設(shè)計(jì)）遺傳算法求中文摘要：本文首先介紹遺傳算法的歷史背景，基本思想，對遺傳算法的常見的編碼解碼方法進(jìn)行了深入的闡述，并對算子選擇方法進(jìn)行深入分析和對比，在此基礎(chǔ)上把遺傳算法應(yīng)用于求解復(fù)雜函數(shù)的極值計(jì)算。最后在MATLAB語言環(huán)境下編寫程序，對求解函數(shù)的最大值進(jìn)行了仿真，并對調(diào)試的結(jié)果進(jìn)行了分析，得出了部分結(jié)論。關(guān)鍵詞：遺傳算法 最優(yōu)解 算子選擇 復(fù)雜函數(shù) 作者：xx xx 指導(dǎo)老師：xxxx xxUsing Genetic Algorithm to Solve Extreme Problem of Complex Function AbstractFirstly, t
2、he historical background and basic idea of genetic algorithm are introduced in this paper. The common coding and decoding method 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 solv
3、e extreme problem of complex function.Finally, with MATLAB software, the program is compiled and the maximum is sought out. 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
4、by : xx xx Supervised by: xxxx xx 目 錄第一章 緒論 (5)1.1 遺傳算法生物學(xué)背景(5)1.1.1 遺傳與變異(5)1.1.2 進(jìn)化 (5)1.2 本文主要內(nèi)容 (5)第二章 遺傳算法簡介 (6)2.1 遺傳算法歷史和發(fā)展(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 編碼(11)3.2.1 編碼方法 (11)3.2.2 編碼原則 (13)3.3 個體適應(yīng)度函數(shù) (13)3.3.1 評價(jià)個體適應(yīng) (13)
5、3.2.2 適應(yīng)度尺度變換(14)3.3 算子選擇(14)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ù)極值問題 (20)4.1 遺傳算法的求解步驟(20)4.2 算例驗(yàn)證 (24)第五章 結(jié)論(28)參考文獻(xiàn)(28)附錄（程序）(29) 第一章 緒 論1.1遺傳算法生物學(xué)背景生物的進(jìn)化是一個奇妙的優(yōu)化過程，它通過選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。1.1.1 遺傳與變異1、遺傳世間的生物從其親代繼承特性或性狀，這種
6、生命現(xiàn)象叫遺傳，研究這種生命現(xiàn)象的科學(xué)叫做遺傳學(xué)。遺傳信息是由基因組成的，生物的各種性狀由其相應(yīng)基因來控制，基因是遺傳的基本單位。細(xì)胞分裂具有自我復(fù)制的能力，在細(xì)胞分裂的過程中，其遺傳基因也同時被復(fù)制到下一代，從而其性狀也被下一代所繼承。2、變異 細(xì)胞在分裂時，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞的基因，在進(jìn)行細(xì)胞復(fù)制時，雖然概率很小，但也有可能產(chǎn)生某些復(fù)制差錯，從而使DNA發(fā)生某種變異產(chǎn)生出新的染色體，從而表現(xiàn)出新的性狀。1.1.2 進(jìn)化 生物在其延續(xù)生存的過程中，逐漸適應(yīng)于其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種現(xiàn)象叫做進(jìn)化。新的基因依據(jù)其與環(huán)境的適應(yīng)程度決定
7、其增殖能力，有利于生存環(huán)境的基因逐漸增加，而不利于生存環(huán)境的基因逐漸減少，通過這種自然的選擇，物種漸漸的向適應(yīng)于生存環(huán)境的方向進(jìn)化，從而產(chǎn)生優(yōu)良的物種。1.2 本文主要內(nèi)容 本文主要討論遺傳算法在實(shí)際數(shù)值函數(shù)優(yōu)化問題中的應(yīng)用，即對實(shí)際問題建模后求函數(shù)最大值的問題。遺傳算法通過對群體所施加的迭代進(jìn)化過程，不斷的將當(dāng)前群體中具有較高適應(yīng)度的個體遺傳到下一代群體中，并且不斷的淘汰掉適應(yīng)度較低的個體，從而最終尋求出適應(yīng)度最大的個體。這個適應(yīng)度最大的個體經(jīng)解碼處理之后所對應(yīng)的個體表現(xiàn)型即為實(shí)際問題最優(yōu)解或是最近似最優(yōu)解第二章 遺傳算法簡介 2.1 歷史與發(fā)展二十世紀(jì)六十年代，I.Rechenberg在他
8、的演化戰(zhàn)略中第一次引入了進(jìn)化算法的思想（起初稱之為Evolutionsstragegie）。他的這一思想逐漸被其他一些研究者發(fā)展。遺傳算法（Genetic Algorithms） 是John Holland 發(fā)明的，后來他和他的學(xué)生及他的同事又不斷發(fā)展了它。終于，在1975年John Holland 出版了專著自然系統(tǒng)和人工系統(tǒng)中的自適應(yīng)（Adaption In Natural and Artificial Systems）。1992年，John Koza 曾經(jīng)使用遺傳算法編出新的程序去做一些具體的工作。他稱他的這種方法為“進(jìn)化規(guī)劃”（Genetic Programming，簡稱GP）。其中使
9、用了LISP規(guī)劃方法，這是因?yàn)檫@種語言中的程序被表示為“分析樹”（Parse Tree），而這種遺傳算法就是以這些分析樹為對象的。2.2 遺傳算法的基本原理： 遺傳算法GA把問題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，一代一代地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。這里所指的某種結(jié)束準(zhǔn)則一般是指個體的適應(yīng)度達(dá)到給定的閥值；或者個
10、體的適應(yīng)度的變化率為零。圖2-1中表示了遺傳算法的執(zhí)行過程。圖2-1 遺傳算法基本原理2.3 遺傳算法特點(diǎn)：（1） 遺傳算法的操作對象是一組可行解，而非單個可行解；搜索軌道有多條，而非單條，因此具有良好的并行性。（2） 遺傳算法只需利用目標(biāo)函數(shù)取值信息，而無須梯度等高價(jià)信息，因而實(shí)用用于大規(guī)模高度非線形的不連續(xù)多峰值函數(shù)的優(yōu)化以及無解析表達(dá)式的目標(biāo)函數(shù)的優(yōu)化，具有很強(qiáng)的通用性。（3） 遺傳算法的擇優(yōu)機(jī)制是一種“軟“策略，加上其良好的并行性使其具有良好的全局優(yōu)化性能和穩(wěn)健性魯棒性。（4） 遺傳算法的可行解集是經(jīng)過編碼的，目標(biāo)函數(shù)可解釋為編碼化個體的適應(yīng)值因而具有良好的可操作性與簡單性。2.4 遺
11、傳算法的目的典型的遺傳算法CGA(Canonical Genetic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問題：考慮對于一群長度為L的二進(jìn)制編碼bi，i1，2，n；有 bi0,1L給定目標(biāo)函數(shù)f，有f(bi)，并且760F(BI) 同時 f(bi)f(bi+1)求滿足下式maxf(bi)|bi0,1L 的bi。很明顯，遺傳算法是一種最優(yōu)化方法，它通過進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個特定的串bi處，即求出最優(yōu)解。2.5 遺傳算法的應(yīng)用 遺傳算法已經(jīng)在很多復(fù)雜問題（比如說NP-難題）、機(jī)器學(xué)習(xí)和簡單的進(jìn)化規(guī)劃中得到了使用。遺傳算法在一些藝術(shù)領(lǐng)
12、域也取得了很大成就，比如說進(jìn)化圖片和進(jìn)化音樂。 遺傳算法的優(yōu)勢在于他的并行性。遺傳算法在搜索空間中非常獨(dú)立地移動（按照基因型而不是表現(xiàn)型），所以它幾乎不可能像其它算法那樣“粘”在局部極值點(diǎn)。 遺傳算法更容易實(shí)現(xiàn)。一旦你有了一個遺傳算法的程序，如果你想解決一個新的問題，你只需要針對新的問題重新進(jìn)行基因編碼就行。如果編碼方法也相同，那你只需要改變一下適應(yīng)度函數(shù)就可以了。當(dāng)然，選擇編碼方法和適應(yīng)度函數(shù)是一件非常難的問題。 遺傳算法的缺點(diǎn)是它的計(jì)算時間太長。它們可能比其他任何算法需要的時間都長。當(dāng)然，對于今天的高速計(jì)算機(jī)來說，這已經(jīng)不是個大問題了。 為了讓讀者更好地了解遺傳算法所解決的問題,這里有一個
13、關(guān)于遺傳算法應(yīng)用的小列表: （1）非線性動態(tài)系統(tǒng)預(yù)測，數(shù)據(jù)分析； （2）神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和權(quán)重設(shè)計(jì)； （3）自動控制導(dǎo)彈的軌道設(shè)計(jì)； （4）進(jìn)化LISP規(guī)劃（遺傳規(guī)劃）； （5）戰(zhàn)略計(jì)劃； （6）蛋白質(zhì)分子的形狀的尋找； （7）旅行商問題和時間序列排序問題； 第三章 遺傳算法的主要參數(shù)及算子選擇3.1 遺傳算法的數(shù)學(xué)理論3.1.1 模式定理 遺傳算法中，在選擇，交叉和變異算子的作用下，具有低階，短的定義長度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按指數(shù)級增加。其中：(1) 模式表示一些相似的模塊，它描述了在某些位置上具有相似結(jié)構(gòu)特征的個體編碼串的一個子集。(2) 在模式H中具有確定基因值的位置
14、數(shù)目叫做該模式的模式階。(3) 模式H中第一個確定基因值的位置和最后一個確定基因值的位置之間的距離稱為該模式的模式定義長度。模式定理闡述了遺傳算法的理論基礎(chǔ)，它說明了模式的增加規(guī)律，同時也給遺傳算法的應(yīng)用提供了指導(dǎo)作用。3.1.2 積木塊假設(shè) 模式定理說明了具有某種結(jié)構(gòu)特征的模式在遺傳進(jìn)化過程中其樣本數(shù)將按指數(shù)級增加，這種模式具有低階，短的定義長度，且平均適應(yīng)度高于群體平均適應(yīng)度的模式。這種模式被稱為積木塊。 模式定理說明了積木塊的樣本數(shù)呈指數(shù)級增長，也說明了用遺傳算法尋求最優(yōu)化樣本的可能性，但它并未指明遺傳算法一定能夠?qū)で蟮阶顑?yōu)樣本而積木塊假設(shè)卻說明了遺傳算法的這種能力。定義：個體的基因塊通
15、過選擇，交叉，變異等遺傳算子的作用，能夠相互連接在一起，形成適應(yīng)度更高的個體編碼串。作用：積木塊假設(shè)說明了用遺傳算法求解各類問題的基本思想，即通過基因塊之間的相互拼接能夠產(chǎn)生出問題更好的解?；谀Ｊ蕉ɡ砗头e木塊假設(shè)，就使得我們能夠在很多應(yīng)用問題中廣泛的使用遺傳算法的思想。3.2 編碼定義：遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱為編碼作用： 編碼是應(yīng)用遺傳算法時要解決的首要問題，也是設(shè)計(jì)遺傳算法時的一個關(guān)鍵步驟。編碼方法除了決定了個體的染色體排列形式之外還決定個體從搜索空間的基因型變換到解空間的表現(xiàn)性時的解碼方法，編碼方法也影
16、響到交叉算子和變異算子的遺傳算法的運(yùn)算方法。由此看見，編碼方法在很大程度上決定了如何進(jìn)行群體的遺傳化運(yùn)算及遺傳進(jìn)化運(yùn)算效率。3.2.1編碼方法1、二進(jìn)制編碼方法定義：二進(jìn)制編碼方法是遺傳算法中最常見的一種編碼方法，它使用的編碼符號集是由二進(jìn)制符號0和1所組成的二值符號集0，1，它所構(gòu)成的基因型是一個二進(jìn)制符號串。在使用二進(jìn)制編碼時，每一個基因就是一個由0或者1組成的字符串。 表 3-1二進(jìn)制編碼的基因 基因A 101100101100101011100101 基因B 111111100000110000011111 使用二進(jìn)制編碼時，即使等位基因的數(shù)量不大，我們也可以得到很多種可能的基因。另一
17、方面，這種方法對于很多問題來都很不自然，所以有時候在交叉和變異結(jié)束后還要做一些調(diào)整。 2、格雷碼編碼方法定義：格雷碼是這樣的一種編碼方法，其連續(xù)2個整數(shù)所對應(yīng)的編碼值之間僅僅只有一個碼位是不相同的，其余碼位都相同。假設(shè)有一個二近制編碼為B=bmbm-1b2b1,其對應(yīng)的格雷碼為G=gmgm-1.g2g1。由二進(jìn)制編碼到格雷碼換算公式為： 公式(3-1)由格雷碼到二進(jìn)制轉(zhuǎn)換公式為： 公式(3-2)格雷碼優(yōu)點(diǎn)：（1） 便于提高遺傳算法的局部搜索能力（2） 交叉，變異等遺傳操作便于實(shí)現(xiàn)（3） 符合最小字符串編碼原則（4） 便于利用模式定理對算法進(jìn)行理論分析3、浮點(diǎn)數(shù)編碼方法定義：所謂浮點(diǎn)數(shù)編碼方法是
18、指個體的每個基因值用某一范圍內(nèi)的一個浮點(diǎn)數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)。例如：若一個優(yōu)化問題含有5個變量xi ( I=1,2,5)每個變量都有其對應(yīng)的上下限Umin,Umax,則:X: 5.80 6.90 3.50 3.80 5.00就表示一個體的基因型。其對應(yīng)的表現(xiàn)型是：X =5.80 , 6.90 , 3.50 , 3.80 , 5.00T浮點(diǎn)數(shù)編碼方法有下面幾個優(yōu)點(diǎn)：（1） 適合于在遺傳算法中表示范圍較大的數(shù)。（2） 適合于精度要求較高的遺傳算法（3） 便于較大空間的遺傳搜索（4） 改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算效率（5） 便于遺傳算法和經(jīng)典油畫方法的混合使用（6）
19、 便于設(shè)計(jì)針對問題的專門知識的知識型遺傳算子（7） 便于處理復(fù)雜的決策變量約束條件4、值編碼（Value Encoding） 在很多問題中我們還可以采用直接的值編碼,也就是說用一些比較復(fù)雜的數(shù)來編碼,比如說實(shí)數(shù)。因?yàn)槎M(jì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.
20、2.2 編碼原則（1） 應(yīng)使用能易于產(chǎn)生所求問題相關(guān)的且具有低階短定義長度模式的編碼方案。（2） 應(yīng)使用能使問題得到自然表示和描述的具有最小字符的編碼方案。3.3 求適應(yīng)度函數(shù)3.3.1 評價(jià)個體適應(yīng)度定義：遺傳算法中使用適應(yīng)度這個概念來衡量群體中各個個體在優(yōu)化計(jì)算中有可能達(dá)到或接近或有助于找到最優(yōu)解的優(yōu)良程度。適應(yīng)度較高的個體遺傳到下一代的概率教大，反之遺傳到下一代的概率相對小一些。度量個體適應(yīng)度的函數(shù)叫做適應(yīng)度函數(shù)。評價(jià)個體適應(yīng)度的一般過程：（1） 對個體編碼串進(jìn)行解碼處理后，可得到個體表現(xiàn)型。（2） 由個體表現(xiàn)型可計(jì)算出對應(yīng)個體的目標(biāo)函數(shù)值。（3） 根據(jù)最優(yōu)化問題的類型，由目標(biāo)函數(shù)值按一
21、定的轉(zhuǎn)換規(guī)則求出個體的適應(yīng)度。3.3.2 適應(yīng)度尺度變換在遺傳算法中各個個體被遺傳到下一代群體中的概率由該個體的適應(yīng)度來決定。如何確定適應(yīng)度對遺傳算法的性能有很大的影響。在遺傳算法運(yùn)行的初期階段，算法能夠?qū)σ恍┻m應(yīng)度教高的個體進(jìn)行控制，降低其適應(yīng)度與其他個體適應(yīng)度之間的差異程度，從而限制其復(fù)制數(shù)量，以維護(hù)群體的多樣性。我們希望在遺傳算法運(yùn)行的后期階段，算法能夠?qū)€體的適應(yīng)度進(jìn)行適當(dāng)?shù)姆糯?，擴(kuò)大最佳個體適應(yīng)度與其他個體適應(yīng)度之間的差異程度，以提高個體之間的競爭性。適應(yīng)度尺度變換方法：（1） 線性尺度變換公式為： F=aF+b （32）其中，F(xiàn)為原適應(yīng)度，F(xiàn)”為新適應(yīng)度，a,b為系數(shù)。線性尺度變換
22、的選取條件：a.尺度變換后全個體的新適應(yīng)度的平均值Favg要等于原適應(yīng)度平均值Favg。b.尺度變換后群體中新的最大適應(yīng)度Fmax要等于原平均適應(yīng)度Favg的指定倍數(shù)。（2） 乘冪尺度變換公式為： F=FK （3-3）冪指數(shù)K與所求解的問題有關(guān)，并且在算法的執(zhí)行中需要不斷對其進(jìn)行修正才能使尺度變換滿足一定的伸縮要求。（3） 指數(shù)尺度變換公式為： F=exp(-F) （3-4）其中決定了選擇的強(qiáng)制性，越小，原有適應(yīng)度較高的個體的新適應(yīng)度就越與其他個體的新適應(yīng)度相差越大，亦即越增加了選擇該個體的強(qiáng)制性。3.4算子選擇 遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下一
23、代群體中一種遺傳運(yùn)算。選擇操作建立在對個體的適應(yīng)度進(jìn)行評價(jià)的基礎(chǔ)之上，選擇操作的目的是為了避免基因缺失，提高全局收斂性和計(jì)算效率。3.4.1 選擇運(yùn)算（1） 比例選擇方法：是一種回放式隨機(jī)采樣方法。各個個體被選中的概率與其適應(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)保存策略：當(dāng)前群體中適應(yīng)度最高的個體不參與交叉運(yùn)算和變異運(yùn)算，而是 它來替代掉本代群體中經(jīng)過交叉變異等遺傳操作后所產(chǎn)生適應(yīng)度最低的個體。我們希望適應(yīng)
24、度最好的個體要盡可能保留到下一代群體中。最優(yōu)保存策略進(jìn)化模型的具體操作過程是：a. 找出當(dāng)前群體中適應(yīng)度最高的個體和適應(yīng)度最低的個體。b. 若當(dāng)前群體中最佳個體的適應(yīng)度比總的迄今為止的最好個體適應(yīng)度還要高，則以當(dāng)前群體中的最佳個體做為新的迄今為止的最好個體。c. 用迄今為止的最好個體替換掉當(dāng)前群體中最差個體。作用： 該策略的實(shí)施可保證迄今為止所得到的最優(yōu)個體不會被交叉，變異等遺傳運(yùn)算所破壞，它遺傳算法收斂性的一個重要保證條件。（3） 排序選擇主要思想是：對群體中所有個體按其適應(yīng)度大小進(jìn)行排序，基于這個排序來分配各個個體被選中的概率，具體操作過如下：a. 對群體中的所有個體按其適應(yīng)度大小進(jìn)行降序
25、排序。b. 根據(jù)具體問題，設(shè)計(jì)一個概率分配表將各個概率值按上述排列次序分配給各個個體。c. 以各個分配到的概率值做為其能夠遺傳到下一代的概率，基于這些概率值用比例選擇（賭輪選擇）的方法產(chǎn)生下一代群體。（4）輪盤賭選擇方法（Roulette Wheel Selection） 父代的選擇是根據(jù)他們的適應(yīng)度做出的。基因越是適應(yīng)環(huán)境，那么它被選擇到的機(jī)會就越大。想像一個輪盤賭的機(jī)器上放置了種群中所有的基因。每一個基因所占的地方的大小和它的適應(yīng)度成正比。如下圖所示：圖3-1 賭輪算法示意圖然后開始扔彈子，扔到那個地方就把對應(yīng)的基因拿出來。顯然，適應(yīng)度越大的基因被選到的機(jī)會就越大。這個過程可以被下面的這個
26、算法來模擬：1求和 計(jì)算所有種群的適應(yīng)度的和S； 2選擇 在區(qū)間（0，S）上隨機(jī)的產(chǎn)生一個數(shù)r； 3循環(huán) 從某個基因開始，逐一取出基因來，把它的適應(yīng)度加到s上去（s開始為0），如果s大于r，則停止循環(huán)并返回當(dāng)前基因； 當(dāng)然，第一步在計(jì)算中只需要執(zhí)行一次。3.4.2交叉算子 遺傳算法中的所謂交叉運(yùn)算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成2個新的個體，交叉運(yùn)算是遺傳算法區(qū)別其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。交叉算子的設(shè)計(jì)過程：1如何確定交叉點(diǎn)的位置2如何進(jìn)行部分基因交換 最常用的交叉算子是單點(diǎn)交叉算子。下面介紹集中適合于二進(jìn)制編碼
27、個體或浮點(diǎn)數(shù)編碼個體的交叉算子：（1） 單點(diǎn)交叉：它是指個體編碼串中只隨即設(shè)置一個交叉點(diǎn)然后在該點(diǎn)相互交換2個配對個體的部分染色體。特點(diǎn)：假如鄰接基因座之間的關(guān)系能夠提供比較好的個體性狀和較高的個體適應(yīng)度的話則這個單點(diǎn)交叉操作破壞這種個體性狀和降低個體適應(yīng)度的可能性最小。（2） 雙點(diǎn)交叉和多點(diǎn)交叉：是指定個體編碼串中隨機(jī)設(shè)置2個或多個交叉點(diǎn)然后進(jìn)行部分基因交換。具體操作過程：1在相互配對的兩個個體編碼串中隨機(jī)設(shè)置2個交叉點(diǎn)2交換2個個體在所設(shè)定的兩個交叉點(diǎn)之間的部分染色體。例如： A: x x | x x x x x | x x x -A: x x | y y y y y| x x x B:
28、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):子代基因的每一個位點(diǎn)是隨機(jī)地來自于兩個父代基因中的一個的; 均勻交叉示意圖11001011 + 11011101 = 11011111 圖（3-3）3.4.3 變異算子遺傳算法中所謂變異運(yùn)算是指個體染色體編碼串中某些基因座上的基因值用該基因座的其他等位基因替換，從而形成新個體。 位點(diǎn)轉(zhuǎn)換算子（Bit Inversion）：選擇一些位點(diǎn)
29、然后將這些地方的0，1互換； 圖（3-4）在遺傳算法中使用變異算子的目的：1 改善遺傳算法局部搜索能力2維持群體多樣性，防止出現(xiàn)早熟現(xiàn)象變異算子的常用方法：a、基本位變異：指對個體基因串以變異概率隨機(jī)指定某一位或幾位基因座上的基因值做變異運(yùn)算b、均勻變異：指分別用符合某一范圍內(nèi)隨機(jī)數(shù)，以某一較小概率來替換個體編碼串中各個基因座上的原有基因值。c、 邊界變異：邊界變異是上述均勻變異操作的一個變形遺傳算法。在進(jìn)行邊界變異操作時，隨機(jī)的取基因座的2個對應(yīng)邊界基因值之一去替換原來的基因值。d、非均勻變異：對每個基因座都以相同的概率進(jìn)行變異運(yùn)算之后相當(dāng)于整個解向量在解空間中，作了一個輕微的變動。3.5
30、遺傳算法的其他運(yùn)行參數(shù)（1） 編碼串長度L：使用二進(jìn)制來表示個體時，編碼串長度L的選取與問題所要求的求解精度有關(guān)。（2） 群體大小M：表示群體中所含個體的數(shù)量。M取值越小可提運(yùn)算速度但降低群體多樣性。容易引起遺傳算法的早熟現(xiàn)象，而當(dāng)M取值較大時降低了遺傳算法的運(yùn)行效率。一般建議范圍20-100。（3） 交叉概率Pc。交叉操作是遺傳算法中產(chǎn)生新個體的主要方法，一般建議范圍是0.4-0.99。隨著遺傳算法在線性能的提高可以增大交叉概率的取值。（4） 變異概率Pm。一般建議范圍是0.00010.1，隨著遺傳算法在線性能的下降，可以減小變異概率的取值（5） 終止帶寬T它表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)
31、之后就停止運(yùn)行并將最佳個體作為所求問題的最優(yōu)解輸出。建議范圍是1001000（6） 代溝G：表示每一代群體中被替換掉的個體在全部個體中所占的百分比。 第四章：用遺傳算法求解復(fù)雜函數(shù)極值問題本課題采用遺傳算法求解函數(shù)最大值問題，應(yīng)用常規(guī)的二進(jìn)度編碼，利用賭輪算法選擇最憂群體，進(jìn)行交叉變異等遺傳操作，最終求出所求函數(shù)最大值即最憂解，最后在MATLAB語言環(huán)境下進(jìn)行調(diào)試，更改相關(guān)參數(shù)，得出幾組最憂解圖象并進(jìn)行對比分析。 所求問題為f(x)=x+9*sin(4x)+8*cos(3x)的最大值，其中定義域?yàn)?=x=12，采用二進(jìn)制編碼，選取種群個體數(shù)目為20，設(shè)定二進(jìn)制編碼長度為10，交叉概率為0.8，
32、變異概率是0.01。4.1 本算例的求解步驟（1） 確定決策變量和約束條件【問題】求f(x)= 11*sin(6*x)+7*cos(5*x)的最大值，其中0=x00, if f(x)+Cmin0 公式（4-3）式中，Cmin為一個適當(dāng)?shù)叵鄬Ρ容^小的數(shù)，它可用下面幾種方法之一來選取。（一）預(yù)先指定一個較小的數(shù)。（二）進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。（三）當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。方法二：對于求目標(biāo)函數(shù)最小值的優(yōu)化問題，變換方法為：F(X)=Cmax-f (X) , if f (X) 2 (個體表現(xiàn)型)00000000 (個體基因型) - 0 (個體表現(xiàn)型)111111111+00
33、000000=11011111 (產(chǎn)生的新個體)種群的各個個體兩兩配對后以交叉概率Pc=0.8隨機(jī)指定各個基因位進(jìn)行交叉運(yùn)算即生成新個體種群。假如鄰接基因座之間的關(guān)系能夠提供比較好的個體性狀和較高的個體適應(yīng)的話則這個單點(diǎn)交叉操作破壞這種個體性狀和降低個體適應(yīng)度的可能性最小變異運(yùn)算使用第三章的基本位變異算子確定遺根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些位執(zhí)行變異。在變異時，對執(zhí)行變異的串的對應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。 經(jīng)交叉運(yùn)算得到的新個體基因串種群以變異概率Pm=0.01隨機(jī)指定有
34、一位或幾位基因座上的基因值進(jìn)行變異操作.11011111-11101011 (生成的新個體)以變異概率分別對每個或者幾個基因位做變異操作就可以生成新的種群個體。單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進(jìn)化的單一群體。因?yàn)樵谒械膫€體一樣時，交叉是無法產(chǎn)生新的個體的，這時只能靠變異產(chǎn)生新的個體。也就是說，變異增加了全局優(yōu)化的特質(zhì)。遺傳算法的運(yùn)行參數(shù)群體大?。篗 （20-100）終止代數(shù)：T （100-500）交叉概率：Pc （0.4-0.99）變異概率：Pm (0.0001-0.1)4.2 算例驗(yàn)證【問題】求f(x)= 11*sin(6*x)+7*cos(5*x)的最大值
35、，其中0=x0temp=Cmin+objvalue(i);elsetemp=0.0;endfitvalue(i)=temp;endfitvalue=fitvalue;% 2.4 選擇復(fù)制% 選擇或復(fù)制操作是決定哪些個體可以進(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）求 fis 中最小的 k ，則第 k 個個體被選中% 4）進(jìn)行 N 次2）、3）操作，得到 N 個個體，成為第
36、 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)生的一列隨機(jī)數(shù)變成輪盤賭形式的表示方法，由小到大排列fitin=1; %fivalue是一向量，fitin代表向量中元素位，即fitvalue(fitin)代表第fitin個個體的單個個體被選擇的概率newin=1; %同理while newin=pxif(ms(newin)fitvalue(fitin)
遺傳算法畢業(yè)論文遺傳算法在實(shí)際數(shù)值函數(shù)優(yōu)化問題中的應(yīng)用研究其中以解決函數(shù)問題為例
