【正文】 制編碼時，即使等位基因的數(shù)量不大，我們也可以得到很多種可能的基因。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 11 二進(jìn)制編碼方法 定義：二進(jìn)制編碼方法是遺傳算法中最常見的一種編碼方法，它使用的編碼符號集是由二進(jìn)制符號 0 和 1 所組成的二值符號集｛ 0， 1｝，它所構(gòu)成的基因型是一個二進(jìn)制符號串。編碼方法除了決定了個體的染色體排列形式之外還決定個體從搜索空間的基因型變換到解空間的表現(xiàn)性時的解碼方法，編碼方法也影響到交叉算子和變異算子的遺傳算法的運(yùn)算方法。基于模式定理和積木塊假設(shè)，就使得我們能夠在很多應(yīng)用問題中廣泛的使用遺傳算法的思想。 定義：個體的基因塊通過選擇，交叉，變異等遺傳算子的作用，能夠相互連接在一起，形成適應(yīng)度更高的個體編碼串。這種模式被稱為積木塊。 模式定理闡述了遺傳算法的理論基礎(chǔ)，它說明了模式的增加規(guī)律，同時也給遺傳算法的應(yīng)用提供了指導(dǎo)作用。 (2) 在模式 H 中具有確定基因值的位置數(shù)目叫做該模式的模式階。 為了讓讀者更好地了解遺傳算法所解決的問題 ,這里有一個關(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è)計； （ 4） 進(jìn)化 LISP規(guī)劃（遺傳規(guī)劃）； （ 5） 戰(zhàn)略計劃； （ 6） 蛋白質(zhì)分子的形狀的尋找； （ 7） 旅行商問題和時間序列排序問題； 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 9 第三章 遺傳算法的主要參數(shù)及算子選擇 遺傳算法的數(shù)學(xué)理論 模式定理 遺傳算法中，在選擇，交叉和變異算子的作用下，具有低階，短的定義長度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按指數(shù)級增加。它們可能比其他任何算法需要的時間都長。當(dāng)然，選擇編碼方法和適應(yīng)度函數(shù)是一件非常難的問 題。一旦你有了一個遺傳算法的程序，如果你想解決一個新的問題，你只需要針對新的問題重新進(jìn)行基因編碼就行。遺傳算法在搜索空間中非常獨(dú)立地移動（按照基因型而不是表現(xiàn)型），所以它幾乎不可能像其它算法那樣“粘”在局部極值點。遺傳算法在一些藝術(shù)領(lǐng)域也取得了很大成就，比如說進(jìn)化圖片和進(jìn)化音樂。 很明顯，遺傳算法是一種最優(yōu)化方法，它通過進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個特定的串 bi 處，即求出最優(yōu)解。 （ 4） 遺傳算法的可行解集是經(jīng)過編碼的，目標(biāo)函數(shù)可解釋為編碼化個體的適應(yīng)值因而具有良好的可操作性與簡單性。 （ 2） 遺傳算法只需利用目標(biāo)函數(shù)取值信息，而無須梯度等高價信息，因而實用用于大規(guī)模高度非線形的不連續(xù)多峰值函數(shù)的優(yōu)化以及無解析表達(dá)式的目標(biāo)函數(shù)的優(yōu)化，具有很強(qiáng)的通用性。 圖 21 中表示了遺傳算法的執(zhí)行過程。這樣，一代一代地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境的一個 “染色體 ”上，它就是問題的最優(yōu)解。并且，在執(zhí)行遺傳算法之前，給出一群 “染色體 ”，也即是假設(shè)解。其中使用了 LISP規(guī)劃方法，這是因為這種語言中的程序被表示為“分析樹”（ Parse Tree），而這種遺傳算法就是以這些分析樹為對象的。 1992年， John Koza 曾經(jīng)使用遺傳算法編出新的程序去做一些具體的工作。遺傳算法（ Geic Algorithms） 是 John Holland 發(fā)明的，后來他和他的學(xué)生及他的同事又不斷發(fā)展了它。這個適應(yīng)度最大的個體經(jīng)解碼處理之后所對應(yīng)的個體表現(xiàn)型即為實際問題最優(yōu)解或是最近似最優(yōu)解 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 6 第二章 遺傳算法簡介 歷史與發(fā)展 二十世紀(jì)六十年代 ， 《演化戰(zhàn)略》中第一次引入了進(jìn)化算法的思想 （ 起初稱之為 Evolutionsstragegie） 。 本文主要內(nèi)容 本文主要討論遺傳算法在實際數(shù)值函數(shù)優(yōu)化問題中的應(yīng)用，即對實際問題建模后求函數(shù)最大值的問題。 進(jìn)化 生物在其延續(xù)生存的過程中，逐漸適應(yīng)于其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種現(xiàn)象叫做進(jìn)化。細(xì)胞分裂具有自我復(fù)制的能力，在細(xì)胞分裂的過程中，其遺傳基因也同時被復(fù)制到下一代，從而其性狀也被下一代所繼承。 遺傳與變異 遺傳 世間的生物從其親代繼承特性或性狀，這種生命現(xiàn)象叫遺傳，研究這種生命現(xiàn)象的科學(xué)叫做遺傳學(xué)。 關(guān)鍵詞：遺傳算法 最優(yōu)解 算子 選擇 復(fù)雜函數(shù) 作者： xx xx 指導(dǎo)老師： xxxx xx 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 2 Using Geic Algorithm to Solve Extreme Problem of Complex Function Abstract Firstly, the historical background and basic idea of geic algorithm are introduced in this paper. The mon coding and decoding method of geic algorithm are discussed too. Secondly, the selection method of geic operator is analyzed and pared deeply, based on which geic algorithm is used to solve extreme problem of plex function. Finally, with MATLAB software, the program is piled and the maximum is sought out. At the end of the paper, the debugging result is analyzed and the conclusion is given. Keywords: Geic Algorithm Optimal Solution Operator Selection Complex Function Written by : xx xx Supervised by: xxxx xx 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 3 目 錄 第一章 緒論 ???????????????????????????? ?? (5) 遺傳算法生物學(xué)背景 ???????????????????????? (5) 遺傳與變異 ????????????????? ????????? ? ? (5) 進(jìn)化 ????????????????????????????? ?? (5) 本文主要內(nèi)容 ?????????????????????????? ? (5) 第二章 遺傳算法簡介 ?????????????????????? ??? (6) 遺傳算法歷史和發(fā)展 ???????????????????????? (6) 遺傳算法的基本原理 ???????????????????????? (6) 遺傳算法的特點 ????????????????? ????????? (7) 遺傳算法的目的 ?????????????????????????? (7) 遺傳算法應(yīng)用 ??????????????????????????? (8) 第三章 遺傳算法的參數(shù)和算子選擇 ????????????????? ? (10) 遺傳算法的數(shù)學(xué)理論 ?????????????????????? ? (10) 編碼 ??????????????????????????????? (11) 編碼方法 ?????????????????????? ?????? (11) 編碼原則 ???????????????????????????? (13) 個體適應(yīng)度函數(shù) ????????????????????????? (13) 評價個體適應(yīng) ?????????????????????????? (13) 適應(yīng)度尺度變換 ????????????????????????? (14) 算子選擇 ???????????????????????????? ? (14) 選擇運(yùn)算 ??????????? ????????????????? (14) 交叉運(yùn)算 ????????????????????????????? (16) 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 4 變異運(yùn)算 ????????????????????????????? (18) 其他運(yùn) 行參數(shù) ??????????????????????????? (18) 第四章 遺傳算法求解復(fù)雜函數(shù)極值問題 ??????????????? ? (20) 遺傳算法的求解步驟 ??????????????????????? ? (20) 算例驗證 ?????? ??????????????????????? (24) 第五章 結(jié)論 ????????????????????????????? ? (28) 參考文獻(xiàn) ???????????????????????????????? (28) 附錄（程序） ????????????????????????????? ? (29) 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 5 第一章 緒 論 遺傳算法生物學(xué)背景 生物的進(jìn)化是一個奇妙的優(yōu)化過程，它通過選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應(yīng)環(huán)境變化的優(yōu)良物種。蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 1 遺傳算法求 中文摘要 ： 本文首先介紹遺傳算法的歷史背景，基本思想，對遺傳算法的常見的編碼解碼方法進(jìn)行了深入的 闡述，并對算子選擇方法進(jìn)行深入分析和對比，在此基礎(chǔ)上把遺傳算法 應(yīng)用于求解復(fù)雜函數(shù)的極值計算。最后在 MATLAB 語言環(huán)境下編寫程序，對求解函數(shù)的最大值進(jìn)行了仿真，并對調(diào)試的結(jié)果進(jìn)行了分析，得出了部分結(jié)論。遺傳算法是根據(jù)生物進(jìn)化思想而啟發(fā)得出的一種全局優(yōu)化算法。遺傳信息是由基因組成的，生物的各種性狀由其相應(yīng)基因來控制，基因是遺傳的基本單位。 變異 細(xì)胞在分裂時，遺傳物質(zhì) DNA 通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞的基因，在進(jìn)行細(xì)胞復(fù)制時，雖然概率很小，但也有可能產(chǎn)生某些復(fù)制差錯，從而使 DNA 發(fā)生某種變異產(chǎn)生出新的染色體，從而表現(xiàn)出新的性狀。新的基因依據(jù)其與環(huán)境的適應(yīng)程度決定其增殖能力，有利于生存環(huán)境的基因逐漸增加，而不利于生存環(huán)境的基因逐漸減少，通過這種自然的選擇，物種漸漸的向適應(yīng)于生存環(huán)境的方向進(jìn)化，從而產(chǎn)生優(yōu)良的物種。遺傳算法通過對群體所施加的迭代進(jìn)化過程，不斷的將當(dāng)前群體中具有較高適應(yīng)度的個體遺傳到下一代群體中，并且不斷的淘汰掉適應(yīng)度較低的個體，從而最終尋求出適應(yīng)度最大的個體。他的這一思想逐漸被其他一些研究者發(fā)展。終于，在 1975年 John Holland 出版了專著《自然系統(tǒng)和人工系統(tǒng)中的自適應(yīng)》（ Adaption In Natural and Artificial Systems）。他稱他的這種方法為“進(jìn)化規(guī)劃”（ Geic Programming，簡稱 GP）。 遺傳算法的基本原理 ： 遺傳算法 GA 把問題的解表示成 “染色體 ”，在算法中也即是以二進(jìn)制編碼的串。然后，把這些假設(shè)解置于問題的 “環(huán)境 ”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的 “染色體 ”進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代 “染色體 ”群。 這里所指的某種結(jié)束準(zhǔn)則一般是指個體的適應(yīng)度達(dá)到給定的閥值；或者個體的適應(yīng)度的變化率為零。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計） 7 圖 21 遺傳算法 基本 原理 遺傳算法特點 ： （ 1） 遺傳算法的操作對象是一組可行解 ，而非單個可行解；搜索軌道有多條，而非單條，因此具有良好的并行性。 （ 3） 遺傳算法的擇優(yōu)機(jī)制是一種 “ 軟“策略，加上其良好的并行性使其具有良好的全局優(yōu)化性能和穩(wěn)健性魯棒性。 遺傳算法的目的 典型的遺傳算法 CGA(Canonical Geic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問題 ：