畢業(yè)設計（論文）遺傳算法求復雜函數(shù)極值問題

1、遺傳算法求復雜函數(shù)極值問題中文摘要：本文首先介紹遺傳算法的歷史背景，基本思想，對遺傳算法的常見的編碼解碼方法進行了深入的闡述，并對算子選擇方法進行深入分析和對比，在此基礎上把遺傳算法應用于求解復雜函數(shù)的極值計算。最后在matlab語言環(huán)境下編寫程序，對求解函數(shù)的最大值進行了仿真，并對調試的結果進行了分析，得出了部分結論。關鍵詞：遺傳算法 最優(yōu)解 算子選擇 復雜函數(shù) 作者：xx xx 指導老師：xxxx xxusing genetic algorithm to solve extreme problem of complex function abstractfirstly, the histo

2、rical 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 solve extrem

3、e 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 by : xx

4、xx supervised by: xxxx xx 目 錄第一章 緒論 (5)1.1 遺傳算法生物學背景(5)1.1.1 遺傳與變異(5)1.1.2 進化 (5)1.2 本文主要內容 (5)第二章 遺傳算法簡介 (6)2.1 遺傳算法歷史和發(fā)展(6)2.2 遺傳算法的基本原理(6)2.3 遺傳算法的特點(7)2.4 遺傳算法的目的(7)2.5 遺傳算法應用(8)第三章 遺傳算法的參數(shù)和算子選擇(10)3.1 遺傳算法的數(shù)學理論(10)3.2 編碼(11)3.2.1 編碼方法 (11)3.2.2 編碼原則 (13)3.3 個體適應度函數(shù) (13)3.3.1 評價個體適應 (13)3.2.2 適應

5、度尺度變換(14)3.3 算子選擇(14)3.3.1 選擇運算 (14)3.3.2 交叉運算(16)3.3.3 變異運算(18)3.4 其他運行參數(shù) (18)第四章 遺傳算法求解復雜函數(shù)極值問題 (20)4.1 遺傳算法的求解步驟(20)4.2 算例驗證 (24)第五章 結論(28)參考文獻(28)附錄（程序）(29) 第一章 緒 論1.1遺傳算法生物學背景生物的進化是一個奇妙的優(yōu)化過程，它通過選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進化思想而啟發(fā)得出的一種全局優(yōu)化算法。1.1.1 遺傳與變異1、遺傳世間的生物從其親代繼承特性或性狀，這種生命現(xiàn)象叫遺傳，

6、研究這種生命現(xiàn)象的科學叫做遺傳學。遺傳信息是由基因組成的，生物的各種性狀由其相應基因來控制，基因是遺傳的基本單位。細胞分裂具有自我復制的能力，在細胞分裂的過程中，其遺傳基因也同時被復制到下一代，從而其性狀也被下一代所繼承。2、變異 細胞在分裂時，遺傳物質dna通過復制而轉移到新產(chǎn)生的細胞中，新細胞就繼承了舊細胞的基因，在進行細胞復制時，雖然概率很小，但也有可能產(chǎn)生某些復制差錯，從而使dna發(fā)生某種變異產(chǎn)生出新的染色體，從而表現(xiàn)出新的性狀。1.1.2 進化 生物在其延續(xù)生存的過程中，逐漸適應于其生存環(huán)境，使得其品質不斷得到改良，這種現(xiàn)象叫做進化。新的基因依據(jù)其與環(huán)境的適應程度決定其增殖能力，有利

7、于生存環(huán)境的基因逐漸增加，而不利于生存環(huán)境的基因逐漸減少，通過這種自然的選擇，物種漸漸的向適應于生存環(huán)境的方向進化，從而產(chǎn)生優(yōu)良的物種。1.2 本文主要內容 本文主要討論遺傳算法在實際數(shù)值函數(shù)優(yōu)化問題中的應用，即對實際問題建模后求函數(shù)最大值的問題。遺傳算法通過對群體所施加的迭代進化過程，不斷的將當前群體中具有較高適應度的個體遺傳到下一代群體中，并且不斷的淘汰掉適應度較低的個體，從而最終尋求出適應度最大的個體。這個適應度最大的個體經(jīng)解碼處理之后所對應的個體表現(xiàn)型即為實際問題最優(yōu)解或是最近似最優(yōu)解第二章 遺傳算法簡介 2.1 歷史與發(fā)展二十世紀六十年代，i.rechenberg在他的演化戰(zhàn)略中第一

8、次引入了進化算法的思想（起初稱之為evolutionsstragegie）。他的這一思想逐漸被其他一些研究者發(fā)展。遺傳算法（genetic algorithms） 是john holland 發(fā)明的，后來他和他的學生及他的同事又不斷發(fā)展了它。終于，在1975年john holland 出版了專著自然系統(tǒng)和人工系統(tǒng)中的自適應（adaption in natural and artificial systems）。1992年，john koza 曾經(jīng)使用遺傳算法編出新的程序去做一些具體的工作。他稱他的這種方法為“進化規(guī)劃”（genetic programming，簡稱gp）。其中使用了lisp規(guī)劃

9、方法，這是因為這種語言中的程序被表示為“分析樹”（parse tree），而這種遺傳算法就是以這些分析樹為對象的。2.2 遺傳算法的基本原理： 遺傳算法ga把問題的解表示成“染色體”，在算法中也即是以二進制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設解。然后，把這些假設解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應環(huán)境的“染色體”進行復制，再通過交叉，變異過程產(chǎn)生更適應環(huán)境的新一代“染色體”群。這樣，一代一代地進化，最后就會收斂到最適應環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。這里所指的某種結束準則一般是指個體的適應度達到給定的閥值；或者個體的適應度的變化

10、率為零。圖2-1中表示了遺傳算法的執(zhí)行過程。圖2-1 遺傳算法基本原理2.3 遺傳算法特點：（1） 遺傳算法的操作對象是一組可行解，而非單個可行解；搜索軌道有多條，而非單條，因此具有良好的并行性。（2） 遺傳算法只需利用目標函數(shù)取值信息，而無須梯度等高價信息，因而實用用于大規(guī)模高度非線形的不連續(xù)多峰值函數(shù)的優(yōu)化以及無解析表達式的目標函數(shù)的優(yōu)化，具有很強的通用性。（3） 遺傳算法的擇優(yōu)機制是一種“軟“策略，加上其良好的并行性使其具有良好的全局優(yōu)化性能和穩(wěn)健性魯棒性。（4） 遺傳算法的可行解集是經(jīng)過編碼的，目標函數(shù)可解釋為編碼化個體的適應值因而具有良好的可操作性與簡單性。2.4 遺傳算法的目的典型

11、的遺傳算法cga(canonical genetic algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問題：考慮對于一群長度為l的二進制編碼bi，i1，2，n；有 bi0,1l給定目標函數(shù)f，有f(bi)，并且760f(bi) 同時 f(bi)f(bi+1)求滿足下式maxf(bi)|bi0,1l 的bi。很明顯，遺傳算法是一種最優(yōu)化方法，它通過進化和遺傳機理，從給出的原始解群中，不斷進化產(chǎn)生新的解，最后收斂到一個特定的串bi處，即求出最優(yōu)解。2.5 遺傳算法的應用 遺傳算法已經(jīng)在很多復雜問題（比如說np-難題）、機器學習和簡單的進化規(guī)劃中得到了使用。遺傳算法在一些藝術領域也取得了很大成

12、就，比如說進化圖片和進化音樂。 遺傳算法的優(yōu)勢在于他的并行性。遺傳算法在搜索空間中非常獨立地移動（按照基因型而不是表現(xiàn)型），所以它幾乎不可能像其它算法那樣“粘”在局部極值點。 遺傳算法更容易實現(xiàn)。一旦你有了一個遺傳算法的程序，如果你想解決一個新的問題，你只需要針對新的問題重新進行基因編碼就行。如果編碼方法也相同，那你只需要改變一下適應度函數(shù)就可以了。當然，選擇編碼方法和適應度函數(shù)是一件非常難的問題。 遺傳算法的缺點是它的計算時間太長。它們可能比其他任何算法需要的時間都長。當然，對于今天的高速計算機來說，這已經(jīng)不是個大問題了。 為了讓讀者更好地了解遺傳算法所解決的問題,這里有一個關于遺傳算法應用

13、的小列表: （1）非線性動態(tài)系統(tǒng)預測，數(shù)據(jù)分析； （2）神經(jīng)網(wǎng)絡的結構和權重設計； （3）自動控制導彈的軌道設計； （4）進化lisp規(guī)劃（遺傳規(guī)劃）； （5）戰(zhàn)略計劃； （6）蛋白質分子的形狀的尋找； （7）旅行商問題和時間序列排序問題； 第三章 遺傳算法的主要參數(shù)及算子選擇3.1 遺傳算法的數(shù)學理論3.1.1 模式定理 遺傳算法中，在選擇，交叉和變異算子的作用下，具有低階，短的定義長度，并且平均適應度高于群體平均適應度的模式將按指數(shù)級增加。其中：(1) 模式表示一些相似的模塊，它描述了在某些位置上具有相似結構特征的個體編碼串的一個子集。(2) 在模式h中具有確定基因值的位置數(shù)目叫做該模式的

14、模式階。(3) 模式h中第一個確定基因值的位置和最后一個確定基因值的位置之間的距離稱為該模式的模式定義長度。模式定理闡述了遺傳算法的理論基礎，它說明了模式的增加規(guī)律，同時也給遺傳算法的應用提供了指導作用。3.1.2 積木塊假設 模式定理說明了具有某種結構特征的模式在遺傳進化過程中其樣本數(shù)將按指數(shù)級增加，這種模式具有低階，短的定義長度，且平均適應度高于群體平均適應度的模式。這種模式被稱為積木塊。 模式定理說明了積木塊的樣本數(shù)呈指數(shù)級增長，也說明了用遺傳算法尋求最優(yōu)化樣本的可能性，但它并未指明遺傳算法一定能夠尋求到最優(yōu)樣本而積木塊假設卻說明了遺傳算法的這種能力。定義：個體的基因塊通過選擇，交叉，變

15、異等遺傳算子的作用，能夠相互連接在一起，形成適應度更高的個體編碼串。作用：積木塊假設說明了用遺傳算法求解各類問題的基本思想，即通過基因塊之間的相互拼接能夠產(chǎn)生出問題更好的解?；谀Ｊ蕉ɡ砗头e木塊假設，就使得我們能夠在很多應用問題中廣泛的使用遺傳算法的思想。3.2 編碼定義：遺傳算法中如何描述問題的可行解，即把一個問題的可行解從其解空間轉換到遺傳算法所能處理的搜索空間的轉換方法就稱為編碼作用： 編碼是應用遺傳算法時要解決的首要問題，也是設計遺傳算法時的一個關鍵步驟。編碼方法除了決定了個體的染色體排列形式之外還決定個體從搜索空間的基因型變換到解空間的表現(xiàn)性時的解碼方法，編碼方法也影響到交叉算子和變

16、異算子的遺傳算法的運算方法。由此看見，編碼方法在很大程度上決定了如何進行群體的遺傳化運算及遺傳進化運算效率。3.2.1編碼方法1、二進制編碼方法定義：二進制編碼方法是遺傳算法中最常見的一種編碼方法，它使用的編碼符號集是由二進制符號0和1所組成的二值符號集0，1，它所構成的基因型是一個二進制符號串。在使用二進制編碼時，每一個基因就是一個由0或者1組成的字符串。 表 3-1二進制編碼的基因 基因a 101100101100101011100101 基因b 111111100000110000011111 使用二進制編碼時，即使等位基因的數(shù)量不大，我們也可以得到很多種可能的基因。另一方面，這種方法對

17、于很多問題來都很不自然，所以有時候在交叉和變異結束后還要做一些調整。 2、格雷碼編碼方法定義：格雷碼是這樣的一種編碼方法，其連續(xù)2個整數(shù)所對應的編碼值之間僅僅只有一個碼位是不相同的，其余碼位都相同。假設有一個二近制編碼為b=bmbm-1b2b1,其對應的格雷碼為g=gmgm-1.g2g1。由二進制編碼到格雷碼換算公式為： 公式(3-1)由格雷碼到二進制轉換公式為： 公式(3-2)格雷碼優(yōu)點：（1） 便于提高遺傳算法的局部搜索能力（2） 交叉，變異等遺傳操作便于實現(xiàn)（3） 符合最小字符串編碼原則（4） 便于利用模式定理對算法進行理論分析3、浮點數(shù)編碼方法定義：所謂浮點數(shù)編碼方法是指個體的每個基因

18、值用某一范圍內的一個浮點數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)。例如：若一個優(yōu)化問題含有5個變量xi ( i=1,2,5)每個變量都有其對應的上下限umin,umax,則:x: 5.80 6.90 3.50 3.80 5.00就表示一個體的基因型。其對應的表現(xiàn)型是：x =5.80 , 6.90 , 3.50 , 3.80 , 5.00t浮點數(shù)編碼方法有下面幾個優(yōu)點：（1） 適合于在遺傳算法中表示范圍較大的數(shù)。（2） 適合于精度要求較高的遺傳算法（3） 便于較大空間的遺傳搜索（4） 改善了遺傳算法的計算復雜性，提高了運算效率（5） 便于遺傳算法和經(jīng)典油畫方法的混合使用（6） 便于設計針對問

19、題的專門知識的知識型遺傳算子（7） 便于處理復雜的決策變量約束條件4、值編碼（value encoding） 在很多問題中我們還可以采用直接的值編碼,也就是說用一些比較復雜的數(shù)來編碼,比如說實數(shù)。因為二進制編碼在這類問題中不好用。 在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關任何值：整數(shù)，實數(shù)，字符或者其他一些更復雜的東西。 表3-2值編碼串基因a 1.2324 5.3243 0.4556 2.3293 2.4545 基因b abdjeifjdhdierjfdldf 基因c （back）, (back), (right), (forward), (left) 3.2.2 編碼原則

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

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

22、尺度變換后全個體的新適應度的平均值favg要等于原適應度平均值favg。b.尺度變換后群體中新的最大適應度fmax要等于原平均適應度favg的指定倍數(shù)。（2） 乘冪尺度變換公式為： f=fk （3-3）冪指數(shù)k與所求解的問題有關，并且在算法的執(zhí)行中需要不斷對其進行修正才能使尺度變換滿足一定的伸縮要求。（3） 指數(shù)尺度變換公式為： f=exp(-f) （3-4）其中決定了選擇的強制性，越小，原有適應度較高的個體的新適應度就越與其他個體的新適應度相差越大，亦即越增加了選擇該個體的強制性。3.4算子選擇 遺傳算法中的選擇操作就是用來確定如何從父代群體中按某種方法選取哪些個體遺傳到下一代群體中一種遺傳

23、運算。選擇操作建立在對個體的適應度進行評價的基礎之上，選擇操作的目的是為了避免基因缺失，提高全局收斂性和計算效率。3.4.1 選擇運算（1） 比例選擇方法：是一種回放式隨機采樣方法。各個個體被選中的概率與其適應度大小成正比。設群體大小為m,個體i的適應度為fi則個體被選種的概率pis為：pis=fi/fi (i=1,2.m) （3-5）由此可見，適應度越高的個體被選種的概率也越大，反之適應度越低的個體被選種的概率也越小。（2） 最優(yōu)保存策略：當前群體中適應度最高的個體不參與交叉運算和變異運算，而是 它來替代掉本代群體中經(jīng)過交叉變異等遺傳操作后所產(chǎn)生適應度最低的個體。我們希望適應度最好的個體要盡

24、可能保留到下一代群體中。最優(yōu)保存策略進化模型的具體操作過程是：a. 找出當前群體中適應度最高的個體和適應度最低的個體。b. 若當前群體中最佳個體的適應度比總的迄今為止的最好個體適應度還要高，則以當前群體中的最佳個體做為新的迄今為止的最好個體。c. 用迄今為止的最好個體替換掉當前群體中最差個體。作用： 該策略的實施可保證迄今為止所得到的最優(yōu)個體不會被交叉，變異等遺傳運算所破壞，它遺傳算法收斂性的一個重要保證條件。（3） 排序選擇主要思想是：對群體中所有個體按其適應度大小進行排序，基于這個排序來分配各個個體被選中的概率，具體操作過如下：a. 對群體中的所有個體按其適應度大小進行降序排序。b. 根據(jù)

25、具體問題，設計一個概率分配表將各個概率值按上述排列次序分配給各個個體。c. 以各個分配到的概率值做為其能夠遺傳到下一代的概率，基于這些概率值用比例選擇（賭輪選擇）的方法產(chǎn)生下一代群體。（4）輪盤賭選擇方法（roulette wheel selection） 父代的選擇是根據(jù)他們的適應度做出的?；蛟绞沁m應環(huán)境，那么它被選擇到的機會就越大。想像一個輪盤賭的機器上放置了種群中所有的基因。每一個基因所占的地方的大小和它的適應度成正比。如下圖所示：圖3-1 賭輪算法示意圖然后開始扔彈子，扔到那個地方就把對應的基因拿出來。顯然，適應度越大的基因被選到的機會就越大。這個過程可以被下面的這個算法來模擬：1求

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

27、個體的交叉算子：（1） 單點交叉：它是指個體編碼串中只隨即設置一個交叉點然后在該點相互交換2個配對個體的部分染色體。特點：假如鄰接基因座之間的關系能夠提供比較好的個體性狀和較高的個體適應度的話則這個單點交叉操作破壞這種個體性狀和降低個體適應度的可能性最小。（2） 雙點交叉和多點交叉：是指定個體編碼串中隨機設置2個或多個交叉點然后進行部分基因交換。具體操作過程：1在相互配對的兩個個體編碼串中隨機設置2個交叉點2交換2個個體在所設定的兩個交叉點之間的部分染色體。例如： a: x x | x x x x x | x x x -a: x x | y y y y y| x x x b: y y | y

28、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 圖（3-3）3.4.3 變異算子遺傳算法中所謂變異運算是指個體染色體編碼串中某些基因座上的基因值用該基因座的其他等位基因替換，從而形成新個體。 位點轉換算子（bit inversion）：選擇一些位點然后將這些地方的

29、0，1互換； 圖（3-4）在遺傳算法中使用變異算子的目的：1 改善遺傳算法局部搜索能力2維持群體多樣性，防止出現(xiàn)早熟現(xiàn)象變異算子的常用方法：a、基本位變異：指對個體基因串以變異概率隨機指定某一位或幾位基因座上的基因值做變異運算b、均勻變異：指分別用符合某一范圍內隨機數(shù)，以某一較小概率來替換個體編碼串中各個基因座上的原有基因值。c、 邊界變異：邊界變異是上述均勻變異操作的一個變形遺傳算法。在進行邊界變異操作時，隨機的取基因座的2個對應邊界基因值之一去替換原來的基因值。d、非均勻變異：對每個基因座都以相同的概率進行變異運算之后相當于整個解向量在解空間中，作了一個輕微的變動。3.5 遺傳算法的其他運

30、行參數(shù)（1） 編碼串長度l：使用二進制來表示個體時，編碼串長度l的選取與問題所要求的求解精度有關。（2） 群體大小m：表示群體中所含個體的數(shù)量。m取值越小可提運算速度但降低群體多樣性。容易引起遺傳算法的早熟現(xiàn)象，而當m取值較大時降低了遺傳算法的運行效率。一般建議范圍20-100。（3） 交叉概率pc。交叉操作是遺傳算法中產(chǎn)生新個體的主要方法，一般建議范圍是0.4-0.99。隨著遺傳算法在線性能的提高可以增大交叉概率的取值。（4） 變異概率pm。一般建議范圍是0.00010.1，隨著遺傳算法在線性能的下降，可以減小變異概率的取值（5） 終止帶寬t它表示遺傳算法運行到指定的進化代數(shù)之后就停止運行并

31、將最佳個體作為所求問題的最優(yōu)解輸出。建議范圍是1001000（6） 代溝g：表示每一代群體中被替換掉的個體在全部個體中所占的百分比。 第四章：用遺傳算法求解復雜函數(shù)極值問題本課題采用遺傳算法求解函數(shù)最大值問題，應用常規(guī)的二進度編碼，利用賭輪算法選擇最憂群體，進行交叉變異等遺傳操作，最終求出所求函數(shù)最大值即最憂解，最后在matlab語言環(huán)境下進行調試，更改相關參數(shù)，得出幾組最憂解圖象并進行對比分析。 所求問題為f(x)=x+9*sin(4x)+8*cos(3x)的最大值，其中定義域為5=x=12，采用二進制編碼，選取種群個體數(shù)目為20，設定二進制編碼長度為10，交叉概率為0.8，變異概率是0.0

32、1。4.1 本算例的求解步驟（1） 確定決策變量和約束條件【問題】求f(x)= 11*sin(6*x)+7*cos(5*x)的最大值，其中0=x 2 (個體表現(xiàn)型)00000000 (個體基因型) - 0 (個體表現(xiàn)型)111111111+00000000=11011111 (產(chǎn)生的新個體)種群的各個個體兩兩配對后以交叉概率pc=0.8隨機指定各個基因位進行交叉運算即生成新個體種群。假如鄰接基因座之間的關系能夠提供比較好的個體性狀和較高的個體適應的話則這個單點交叉操作破壞這種個體性狀和降低個體適應度的可能性最小變異運算使用第三章的基本位變異算子確定遺根據(jù)生物遺傳中基因變異的原理，以變異概率pm

33、對某些個體的某些位執(zhí)行變異。在變異時，對執(zhí)行變異的串的對應位求反，即把1變?yōu)?，把0變?yōu)?。變異概率pm與生物變異極小的情況一致，所以，pm的取值較小，一般取0.01-0.2。 經(jīng)交叉運算得到的新個體基因串種群以變異概率pm=0.01隨機指定有一位或幾位基因座上的基因值進行變異操作.11011111-11101011 (生成的新個體)以變異概率分別對每個或者幾個基因位做變異操作就可以生成新的種群個體。單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進化的單一群體。因為在所有的個體一樣時，交叉是無法產(chǎn)生新的個體的，這時只能靠變異產(chǎn)生新的個體。也就是說，變異增加了全局優(yōu)化的特質。遺傳算法的運行參數(shù)群體大小：m （20-1