1、中中南南民民族族大大學(xué)學(xué) 畢畢業(yè)業(yè)論論文文 ( (設(shè)設(shè)計計) ) 學(xué)學(xué)院院: : 計計算算機機科科學(xué)學(xué)學(xué)學(xué)院院 專專業(yè)業(yè): : 軟軟件件工工程程 年年級級: : 2 20 00 08 8 題題目目: : 基基于于云云遺遺傳傳算算法法的的函函數(shù)數(shù)優(yōu)優(yōu)化化 學(xué)學(xué)生生姓姓名名 : : 謝謝勁勁 學(xué)學(xué)號號: : 0 08 80 06 65 50 05 58 8 指指導(dǎo)導(dǎo)教教師師姓姓名名 : :林紀漢林紀漢職職稱稱: :高級工程師高級工程師 2 20 01 12 2 年年 5 5 月月 7 7 日日 目目 錄錄 摘要.1 abstract.1 引言.2 1 遺傳算法.2 1.1 遺傳算法概述 .2 1.

2、2 遺傳算法的基本步驟 .3 1.3 遺傳算法的特點 .4 2 云模型.4 2.1 云與云滴 .4 2.2 云的性質(zhì) .4 2.3 云的數(shù)字特征 .5 2.4 正態(tài)云發(fā)生器 .6 2.5 云模型在遺傳算法中的應(yīng)用 .6 3 函數(shù)優(yōu)化實現(xiàn).6 3.1 編碼 .6 3.2 選擇 .7 3.3 交叉和交叉概率 .7 3.4 變異和變異概率 .10 3.5 產(chǎn)生下一代 .11 3.6 適應(yīng)函數(shù)的計算 .12 3.7 實驗結(jié)果 .12 結(jié)論.13 致 謝.13 參考文獻.13 1 基于云遺傳算法的函數(shù)優(yōu)化基于云遺傳算法的函數(shù)優(yōu)化 摘要：摘要：遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，可以不用依賴

3、于問題的具體領(lǐng)域， 對解決問題的種類有很強的魯棒性，所以應(yīng)用廣泛。其中函數(shù)優(yōu)化是對遺傳算法進行性能評價的常 用算例，可以用各種各樣的函數(shù)來驗證遺傳算法的性能。本文介紹了遺傳算法和云模型的基本原理， 在 vc 環(huán)境下，結(jié)合正態(tài)云模型云滴的隨機性和穩(wěn)定傾向性，由正態(tài)云發(fā)生器產(chǎn)生自適應(yīng)交叉概率 和變異概率，實現(xiàn)了函數(shù)優(yōu)化。實驗結(jié)果表明，云遺傳算法只需要較少的進化代數(shù)就可以收斂，收 斂速度快于標準遺傳算法。 關(guān)鍵詞關(guān)鍵詞：遺傳算法；云模型；函數(shù)優(yōu)化；vc 2 the function optimization based on cloud genetic algorithm abstract: gen

4、etic algorithm provides commonly used framework that can solve complex problem of system optimization. that framework is widely used because it does not rely on the specific areas of the problem, and because of its strong robustness to the species of problem. to evaluate performance of genetic algor

5、ithm we often come up with all kinds of function optimization. this paper introduces the basic principle of cloud model and the genetic algorithm. on vc platform, combined with normal cloud model droplets randomness and stable tendentiousness and probabilities of crossover and mutation which are pro

6、duced by normal clouds generator to realize function optimization. the experimental results show that compared with standard genetic algorithm, cloud genetic algorithm can converge through less evolution generation, which enhances the convergence speed. key words: genetic algorithm; cloud model; fun

7、ction optimization; visual c+ 3 引言引言 （1） 遺傳算法生物學(xué)背景 生物的進化是一個奇妙的優(yōu)化過程，他通過遺傳、選擇淘汰、突然變異等產(chǎn)生適應(yīng)環(huán)境變化的 優(yōu)良物種。行為主義學(xué)派模擬這種物競天擇、適者生存的生物群體進化過程，提出了演化計算 （evolutionary computation,ec）的方法。遺傳算法（genetic algorithm）是模擬達爾文生物進化論 的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的 方法，它最初由美國michigan大學(xué)j.holland教授于1975年首先提出來的，并出版了頗有影響的專

8、著 adaptation in natural and artificial systems，ga這個名稱才逐漸為人所知，j.holland教授所提 出的ga通常為簡單遺傳算法（sga）1。 （2）論文主要研究內(nèi)容 本文主要討論遺傳算法在實際數(shù)值函數(shù)優(yōu)化問題中的應(yīng)用，即對實際問題建模后求函數(shù)最大值 的問題。主要內(nèi)容包括以下幾個方面： 1）對遺傳算法的基本原理和方法進行闡述，并針對算法的局限性，對其操作過程進行改進。 2）函數(shù)最大值模型的建立。以x的值為設(shè)計變量，在滿足相關(guān)約束條件的前提下，建立了以 函數(shù)值最大為目標函數(shù)的優(yōu)化設(shè)計模型。 3）應(yīng)用改進遺傳算法進行函數(shù)最大值優(yōu)化設(shè)計。在算法操作過程

9、中，把目標函數(shù)轉(zhuǎn)換為對應(yīng) 的適應(yīng)函數(shù)，給出了約束條件的處理方法，使部分約束條件自動得到滿足。操作過程中針對各變量 均為離散型變量只采用了整數(shù)編碼。 4）在前面理論研究工作的基礎(chǔ)上，采用軟件工程學(xué)方法在vc編程環(huán)境下將問題的模型建立， 求解過程給予計算機實現(xiàn)，最終得出函數(shù)最優(yōu)解或近似函數(shù)最優(yōu)解，并對結(jié)果進行了討論。 1 1 遺傳算法遺傳算法 1.1 遺傳算法概述遺傳算法概述 以模擬自然界生物遺傳和進化過程形式的遺傳算法，是依據(jù)生物進化以集團的形式即群體共同 進化的。組成群體的單個生物稱為個體基本特征的遺傳繼承，由個體性質(zhì)的染色體所決定。具有遺 傳基因染色體的個體對環(huán)境有不同的適應(yīng)性。遺傳算法正是

10、基于自然界生物“物竟天澤，適者生存” 的進化思想構(gòu)造的一類算法，算法將保持一個競爭的解群體，經(jīng)過雜交和（或）變異等遺傳操作而 更新?lián)Q代，從而使待求的解逐步優(yōu)化，最終找到問題的最優(yōu)解或次優(yōu)解2。 遺傳算法的術(shù)語來源于自然遺傳學(xué)。1975 年由美國 j.holland 教授提出的遺傳算法（genetic algorithm，簡稱 ga）是基于自然選擇原理、自然遺傳機制和自適應(yīng)搜索（尋優(yōu)）的算法3。 j.holland 教授的adaptation in natural and artificial systems一書的問世標志著遺傳算法的誕生。 ga 啟迪于生物學(xué)的新達爾文主義（達爾文的進化論、魏茨

11、曼的物種選擇學(xué)說和孟德爾的基因?qū)W說） ， 模仿物竟天演、優(yōu)勝劣汰、適者生存的生物遺傳和進化的規(guī)律性。1989 年美國伊利諾大學(xué)的 david e.goldberg 博士出版的專著genetic algorithm in search，optimization and machine learning是 遺傳算法發(fā)展過程中的又一個里程碑，這本書全面地闡述了遺傳算法的發(fā)展歷程、現(xiàn)狀、各種算法 和應(yīng)用實例，并附有 pascal 源程序，從而使得廣大工程技術(shù)人員得以進行實際的應(yīng)用，在全世界掀 起了關(guān)于遺傳算法的研究和應(yīng)用熱潮。 在進化論中，每一物種在不斷的發(fā)展過程中都是越來越適應(yīng)環(huán)境，物種的每個個體的

12、基本特征 被后代所繼承，但后代又不完全等同于父代，這些新的變化若適應(yīng)環(huán)境則被保留下來，否則就將被 淘汰。在遺傳學(xué)中認為，遺傳是作為一種指令遺傳密碼封裝在每個細胞中，并以基因的形式包含在 4 染色體中，每個基因有特殊的位置并控制某個特殊的性質(zhì)。每個基因產(chǎn)生的個體對環(huán)境有一定的適 應(yīng)性4。基因雜交和基因突變可能產(chǎn)生對環(huán)境適應(yīng)性強的后代，通過優(yōu)勝劣汰的自然選擇，適應(yīng)值 高的基因結(jié)構(gòu)就保存下來。遺傳算法就是模仿了生物的遺傳、進化原理，并引用了隨機統(tǒng)計理論而 形成的。在求解過程中，遺傳算法從一個初始變量群體開始，一代一代地尋找問題的最優(yōu)解，直到 滿足收斂叛據(jù)或預(yù)先設(shè)定的迭代次數(shù)為止。它借助選擇、交叉、變

13、異等操作，使所要解決的問題一 步步地逼近最優(yōu)解。與其他優(yōu)化方法相比，遺傳算法以單一的字符串形式描述所研究的問題，只需 要利用適應(yīng)函數(shù)值來進行優(yōu)化計算，而不需要函數(shù)導(dǎo)數(shù)等其他輔助信息。目前，隨著計算機技術(shù)的 發(fā)展，遺傳算法越來越得到人們的重視，并在機器學(xué)習、模式識別、神經(jīng)網(wǎng)絡(luò)、優(yōu)化控制、組合優(yōu) 化等領(lǐng)域得到了成功應(yīng)用5。 遺傳算法一般由 4 個部分組成：編碼與解碼、適應(yīng)函數(shù)、遺傳算子和控制參數(shù)： （1）由設(shè)計空間向遺傳算法編碼空間的映射稱為編碼；而由編碼空間向設(shè)計空間的映射稱為 解碼。用遺傳算法求解最優(yōu)化問題時，必須先建立設(shè)計變量與染色體之間的對應(yīng)關(guān)系，即確定編碼 與解碼的規(guī)則。 （2）適應(yīng)函數(shù)

14、是用以描述個體適應(yīng)環(huán)境的程度，也是生物進化中決定哪些染色體可以產(chǎn)生優(yōu) 良后代的依據(jù)。一般是，個體的適應(yīng)函數(shù)值愈大，則個體性能愈好，生存可能性愈大；反之，若個 體的適應(yīng)函數(shù)值愈小，則個體的性能愈差，淘汰愈有可能。 （3）遺傳算子包括復(fù)制算子、交配算子和變異算子。復(fù)制算子是根據(jù)個體的優(yōu)劣程度決定在 下一代是被淘汰還是被復(fù)制。交配是指兩個相互配對的染色體按某種方式相互交換其部分基因而生 成兩個新的個體。變異是將個體染色體編碼字符中的某些基因用其他等位基因來替換，從而生成一 個新的染色體。這三個算子一般都按一定的種群選擇概率、交配概率和變異概率隨機地進行，造成 遺傳中的子代和父代的不同和差異。 （4）

15、算法的控制參數(shù)包括種群的規(guī)模 n、交配率 pc 和變異率 pm。 迄今為止，有關(guān)遺傳算法的理論研究還相當不完善，特別是有關(guān)遺傳算法的收斂性研究，以及 如何提高算法的收斂速度和計算的穩(wěn)定性等，這些都是目前具有重要研究價值的問題6。 1.2 遺傳算法的基本步驟遺傳算法的基本步驟 遺傳算法是一類隨機優(yōu)化算法，標準遺傳算法（sga）的主要步驟： （1）選擇優(yōu)化問題求解的一種編碼。 （2）隨機產(chǎn)生 n 個染色體的初始群體。 0popkk ， （3）對群體中的每個染色體 popi(k)計算適應(yīng)函數(shù) （2-1） kf ii popfitness （4）若滿足終止規(guī)則，則轉(zhuǎn)向（9） ，否則計算概率 , （2-

16、2） n i i i f f p i 1 ni, 2 , 1 （5）以概率從中隨機選一些染色體構(gòu)成一個新群體（其中可以重復(fù)選中的 i p kpop kpop 元素） （2-3） nikk i , 2 , 1pop1newpop （6）通過交配，按交配概率得到一個有 n 個染色體的交配群體。 c p1crosspopk 5 （7）以一個較小的變異概率，得到一個染色體的一個基因發(fā)生變異，形成變異群體 m p 。 1mutpopk （8）令和，返回（3） 。 1 kk 1mutpoppopkk （9）終止計算，輸出最優(yōu)結(jié)果7。 當參數(shù)滿足：交叉概率，變異概率，則簡單遺傳算法不收斂到全局最優(yōu) 10 c

17、 p10 m p 解。而在以下幾種改進中收斂到最優(yōu)解： （1）每次記錄下當前最優(yōu)解并將群體狀態(tài)最前面增加一維存放當前最優(yōu)解。 （2）按交叉、變異、種群選取之后，更新當前最優(yōu)染色體的進化循環(huán)過程。 （3）按交叉、變異后就更新當前最優(yōu)染色體，之后再進行種群選取的進化循環(huán)過程。 1.3 遺傳算法的特點遺傳算法的特點 遺傳算法不同于傳統(tǒng)的優(yōu)化算法，它是利用生物進化和遺傳的思想實現(xiàn)優(yōu)化過程的，因此它具 有如下幾個優(yōu)點： （1）遺傳算法是通過對優(yōu)化問題的變量（或參數(shù)）編碼成“染色體”后進行操作的，而不是對 變量本身，因此這個不受變量性質(zhì)（如連續(xù)、離散等）的限制，而且對多變量、多目標的優(yōu)化問題 也是一種很適

18、用的方法，遺傳算法也是一種隨機搜索的數(shù)值求解方法，由于在求解過程中記錄下一 個群體，因而可提供多個解，而且在求解過程中無需提供其他如導(dǎo)數(shù)等一類信息8。 （2）遺傳算法的求解是從一個群體開始的，并在求解過程中記錄下一個群體。因此具有隱含 并行搜索的特性，從而大大減小了陷入局部最優(yōu)解的可能性。 （3）遺傳算法對優(yōu)化問題的變量編碼后，其計算過程比較簡單，且可以較快地得到一個滿意 解。由于算法本身與其它啟發(fā)式算法具有較強的兼容性，所以可以用其他算法產(chǎn)生初始群體，亦可 以對每一群體用其他算法產(chǎn)生下一代新群體。 遺傳算法也還可以存在一些不足或是需要進一步深入研究的問題，如編碼不規(guī)范性以及編碼存 在表示的不

19、準確性、編碼不能全面地表示出約束以及保證收斂到最優(yōu)解等。 2 2 云模型云模型 云模型是建立在隨機數(shù)學(xué)和模糊數(shù)學(xué)上的一種定量到定性之間的轉(zhuǎn)換模型，用來統(tǒng)一刻畫語言 值中大量存在的隨機性、模糊性以及兩者之間的關(guān)聯(lián)性。云方法提出用 3 個數(shù)字特征(期望值, 熵, 超熵) 來描述整個云團, 實現(xiàn)定性和定量之間的轉(zhuǎn)換9。 2.1 云與云滴云與云滴 設(shè) u 是一個用精確數(shù)值表示的定量論域（一維的、二維的或多維的） ，c 是 u 上的定性概念， 對于論域中的任意一個元素 x，且 x 是定性概念 c 的一次隨機實現(xiàn)，x 對 c 的確定度 (x)0,1是 有穩(wěn)定傾向的隨機數(shù)，則 x 在論域 u 上的分布稱為云

20、模型，簡稱為云，每一個 x 稱為一個云滴10。 2.2 云的性質(zhì)云的性質(zhì) 論域 u 可以是一維的，也可以是多維的。 定義中提及的隨機實現(xiàn)，是概率意義下的實現(xiàn)；定義中提及的確定度，是模糊集意義下的隸屬 度，同時又具有概率意義下的分布。所有這些都體現(xiàn)了模糊性和隨機性的關(guān)聯(lián)性11。 對于任意一個 xu，x 到0，1上的映射是一對多的變換，x 對 c 的確定度是一個概率分布， 而不是一個固定的數(shù)值。 6 云由云滴組成，云滴之間的無次序性，一個云滴是定性概念在數(shù)量上的一次實現(xiàn)，云滴越多， 越能反映這個定性概念的整體特征。 云滴出現(xiàn)的概率大，云滴的確定度大，則云滴對概念的貢獻大。 2.3 云的數(shù)字特征云的

21、數(shù)字特征 正態(tài)云模型用相互獨立的一組參數(shù)共同表達一個定性概念的數(shù)字特征, 反映概念的不確定性。 在正態(tài)分布函數(shù)與正態(tài)隸屬函數(shù)基礎(chǔ)上, 這組參數(shù)用期望 ex , 熵 en , 超熵 he 這 3 個數(shù)字特征來 表征，云的數(shù)字特征示意圖如圖 2-1 所示12。 期望 ex：在論域空間中最能夠代表這個定性概念的點, 是這個概念量化的最典型樣本點。 熵 en：代表一個定性概念的可度量粒度, 通常熵越大概念越宏觀。熵還反映了定性概念的不確 定性, 表示在論域空間可以被定性概念接受的取值范圍大小, 即模糊度, 是定性概念亦此亦彼性的 度量，也即云層的陡峭程度，en 越小，云層越陡峭。 超熵 he：熵的不確

22、定性的度量, 它反映代表定性概念值的樣本出現(xiàn)的隨機性, 揭示了模糊性和 隨機性的關(guān)聯(lián)，也即云層的厚度，he 越大云層越厚。 圖 2-1 云的數(shù)字特征示意圖13 設(shè) u 是一個用精確數(shù)值表示的定量論域，c 是 u 上的定性概念，若定量值 x 是定性概念 c 的 一次隨機實現(xiàn)，若 x 滿足 xn(ex，en2)，其中，enn(en，he2)，且 x 對 c 的確定度滿足則 x 在 論域 u 上的分布稱為正態(tài)云。云發(fā)生器通過輸入 3 個數(shù)值特征就形成合乎條件的云滴，從而將一 個定性概念通過不確定性轉(zhuǎn)換模型定量地表示出來。例如十幾公里就是一個不確定的語言值，它 的云模型表示如圖 2-2 所示。 圖 2

23、-2 語言值“十幾公里”云模型示意圖14 7 2.4 正態(tài)云發(fā)生器正態(tài)云發(fā)生器 正向云發(fā)生器是最基本的云算法，實現(xiàn)了語言值表達的定性信息中獲得定量數(shù)據(jù)的范圍和分布 規(guī)律，是表征語言原子最普遍、最重要的工具,是一個前向的、直接的過程。它在表達自然語言中 的基本語言值語言原子時最為有用，因為社會和自然科學(xué)的各個分支都已經(jīng)證明了正態(tài)分布的 普適性。 給定云的三個數(shù)字特征( ex， en， he) ，產(chǎn)生正態(tài)云模型的若干二維點云滴 drop ( xi , i ) ，稱為正向云發(fā)生器。如下圖 2-3 所示： 云滴 drop ( xi , i ) 圖 2-3 正態(tài)云發(fā)生器示意圖15 一維正向云發(fā)生器算法描

24、述如下： 輸入：表示定性概念的 a 三個數(shù)字特征值 ex，en，he 和云滴數(shù) n。 輸出：n 個云滴的定量值以及每個云滴代表 a 的確定度。 1）生成以 en 為期望值，he 為標準差的一個正態(tài)隨機數(shù) enn; 2）生成以 ex 為期望值，en 為標準差的正態(tài)隨機數(shù) x； 3）令 x 為定性概念 a 的一次具體量化值，稱為云滴； 4）計算 16； 2 2 ) (2 )( en exf ey 5）令 y 為 x 屬于定性概念 a 的確定度； 6） （x，y）完整的反映了這一次定性定量轉(zhuǎn)換的全部內(nèi)容； 7）重復(fù) 1）6）直到產(chǎn)生 n 個云滴為止。 2.5 云模型在遺傳算法中的應(yīng)用云模型在遺傳算法

25、中的應(yīng)用 圖 2-1 的云模型表示當時其確定度為 1，當時，確定度隨著 x 的增大而減小。 exx exx 要使遺傳算法的收斂速度加快，不易陷入局部極小，得到正確的結(jié)果，必須使適度值小的個體有較 大的交叉概率和變異概率，適度值大的個體有相對較小的交叉概率和變異概率。 從圖 2-1 可以看 出當時云模型具有這一特點，可以將 x 作為遺傳算法中兩交叉?zhèn)€體的最大適應(yīng)度以及變異 exx 個體的適應(yīng)度，確定度作為交叉概率和變異概率，并且云模型中云滴集中在區(qū)間 ，云層厚度為 he，具有很好的隨機性和穩(wěn)定傾向性18。 3,3enexenex 3 3 函數(shù)優(yōu)化實現(xiàn)函數(shù)優(yōu)化實現(xiàn) 目標函數(shù)為： 100/)14(

26、2 100)( x exf 式中 x 的取值范圍是 131，求 f（x）的最大值。 3.1 編碼編碼 遺傳算法的第一步是將 x 編碼為有限長度的串，針對本例中自變量的定義域，考慮采用二進制 8 數(shù)來對二編碼，恰好可用 5 位二進制數(shù)來表示，例如 01001 對應(yīng) x=9，11111 對應(yīng) x=31 17。 void initpop() /初始化種群 int j,j1; srand( (int)time( null ) ); /采用當前時間為隨機種子，保證每次的隨機數(shù)都不一樣 for(j=0;jpopsize;j+) for(j1=0;j1lchrom;j1+) oldpopj.chromj1=

27、(int)(2*rand()/(rand_max+1.0); /*隨機產(chǎn)生染色體二進制 串 */ oldpopj.x=decode(oldpopj.chrom); oldpopj.fitness=objfunc(oldpopj.x); oldpopj.parent1=0; oldpopj.parent2=0; oldpopj.xsite=0; /給結(jié)構(gòu)體其他數(shù)據(jù)（適應(yīng)值，雙親）等賦值 備注：作為遺傳算法的第一步，可以說這是很關(guān)鍵的一步，對于基因位數(shù)的選擇是一個至關(guān)重 要的部分，這里選擇的基因位數(shù)為 5(#define lchrom 5)，之所以選擇 5 有以下兩個原因。其一：為 了程序的方便，

28、使得程序在短時間能夠收斂。其二：五位二進制的范圍031 包括函數(shù)的解 “x14” 。當然基因數(shù)越多，得到的初始值就越多，最后得到的答案也越有說服力。通過各方面 的考慮，這里使用基因數(shù)為 5 并無大礙。 3.2 選擇選擇 考慮到算法的復(fù)雜性，這里選用了輪盤賭這種選擇算法。輪盤賭，就是積累概率來實現(xiàn)的，通 常適應(yīng)度大的被選擇的幾率較高。 程序代碼： int select() double rand1,partsum; int j; partsum=0.0; j=0; rand1=random1()*sumfitness; /得到一個小于 sumfitness 的隨機數(shù) do partsum=par

29、tsum+oldpopj.fitness; j=j+1; while(partsumrand1)/適應(yīng)值大的選中的概率大 return j-1; 3.3 交叉交叉和交叉概率和交叉概率 (1) 交叉 交叉將染色體的基因進行互換，從而產(chǎn)生新的后代，本文采用單點交叉：隨機選取某個基因位， 從此位開始交換兩父本后面的序列，相應(yīng)地產(chǎn)生兩個后代，實例如下： 9 父本 1： 87654321 , 父本 2： 87654321 , 子代 1： 87654321 , 子代 2： 87654321 , 程序中的交叉： int crossover(char *parent1,char *parent2,int k5

30、) /交叉 int j; srand( (int)time( null ) ); if(flipcross(pcross) jcross=(int)(lchrom*rand()/(rand_max+1.0); /得到交叉的位置 jcross ncross=ncross+1; else jcross=lchrom; if(jcross!=lchrom) for(j=0;jjcross;j+) /交叉位置前的不變 f=oldpopmate1.fitness; newpopk5.chromj=mutation(parent1j); f=oldpopmate2.fitness; newpopk5+1.

31、chromj=mutation(parent2j); for(j=jcross;jlchrom;j+) /jcross 后的兩邊互換 f=oldpopmate2.fitness; newpopk5.chromj=mutation(parent2j); f=oldpopmate1.fitness; newpopk5+1.chromj=mutation(parent1j); else /不交叉則直接變成下一代 for(j=0;j=avg) pc=p_1*exp(-(ff-ex)*(ff-ex)/(2*enn*enn);/上式的 pc else pc=p_3; if(pc=probability)

32、return 1; return 0; 3.4 變異變異和變異概率和變異概率 （1） 變異 變異的情況是遺傳算法的三個主要操作之一，符合生物進化的規(guī)律，只有通過變異才能更好的 豐富生物多樣性。 變異作用在單個染色體上，并且產(chǎn)生一個不同于父本的染色體，變異方式有多種，本文采用簡 單變異：簡單變異又稱為點變異或二進制變異，一個個體中任一位按某一概率進行取反運算， m p 即 1 變 0 或 0 變 1。示例如下： 個體：10110011 新個體：10010011 第三位由 1 變?yōu)?0. 程序： int mutation(char ch) /變異 int mutate; mutate=flipmu

33、tate(pmutation); if(mutate) nmutation=nmutation+1; if(ch) ch=0; /如果 ch 是 1 則改成 0 else ch=1; /如果是 0 則改成 1 12 if(ch) return 1; else return 0; （2） 變異概率 變異概率公式如下： m p fx e 1max / )(cffen 2 /cenhe ),(heenrandnen m pffek en exf 2 2 ) (2 )( k ff 函數(shù)程序： int flipmutate(double probability) double pm; srand(uns

34、igned)time(null); enn=(sqrt(-2*log(1.0*rand()/rand_max)*cos(2*pi*1.0*rand()/rand_max)*he+en; if(f=avg) pm=p_2*exp(-(f-ex)*(f-ex)/(2*enn*enn); else pm=p_4; if(pm=probability) return 1; return 0; 3.5 產(chǎn)生下一代產(chǎn)生下一代 void generation() int j; j=0; do mate1=select(); mate2=select(); ff=oldpopmate1.fitness; if

35、(ffoldpopmate2.fitness) ff=oldpopmate2.fitness; crossover(oldpopmate1.chrom,oldpopmate2.chrom,j); newpopj.x=(double)decode(newpopj.chrom); 13 newpopj.fitness=objfunc(newpopj.x); newpopj.parent1=mate1; newpopj.parent2=mate2; newpopj.xsite=jcross; newpopj+1.x=(double)decode(newpopj+1.chrom); newpopj+1

36、.fitness=objfunc(newpopj+1.x); newpopj+1.parent1=mate1; newpopj+1.parent2=mate2; newpopj+1.xsite=jcross; j=j+2; while(jpopsize); 3.6 適應(yīng)函數(shù)的適應(yīng)函數(shù)的計算計算 函數(shù) 100/)14( 2 100)( x exf 本身的值。 程序代碼： double objfunc(double x1) double y; y=-pow(x1-14),2)/100.0; y=100*exp(y); return y; /所求函數(shù)的值 3.7 實驗結(jié)果實驗結(jié)果 在編碼方案、選擇算

37、子、交叉算子、變異算子、適應(yīng)度函數(shù)相同的情況下，分別用固定的交叉 概率和變異概率即標準的遺傳算法以及自適應(yīng)的交叉概率和變異概率即云遺傳算法連續(xù)運行程序 10 次。10 次實驗的進化代數(shù)與收斂值對比結(jié)果如表 1 所示。通過表 1 可以看出，10 次實驗中標準 遺傳算法以及云遺傳算法全部都收斂，其中標準遺傳算法收斂最大值 5 次，局部最大值 5 次。然而 云遺傳情況要好，收斂最大值次數(shù)為 8 次，局部最大值為 2 次，而且在速度上也比標準遺傳算法的 要快。 表 3-1 標準遺傳算法與云遺傳算法對比結(jié)果 標準遺傳算法云遺傳算法 進化代數(shù)收斂值進化代數(shù)收斂值 9010077100 399.005052

38、699.0050 784910015199.0050 15291.3931412100 38971006100 55599.0050595100 1591003100 202699.005027100 1302100178100 9799.00506100 14 結(jié)論結(jié)論 畢業(yè)設(shè)計終于在五月初完整的寫完了，總的體會可以用一句話來表達，紙上得來終覺淺，絕知 此事要躬行！ 以前的課題設(shè)計總是就一個方面來寫，如討論一個算法，或者完成一個功能，而做遺傳算法的 畢業(yè)設(shè)計，它不僅僅是完成一個算法，而是對這個算法的背景，理論原理，應(yīng)用以及改進等多方面 進行探討。對算法的來龍去脈搞得透徹的同時，提出自己的想法。 畢業(yè)設(shè)計是學(xué)生即將完成學(xué)業(yè)的最后一個重要環(huán)節(jié)，它既是對學(xué)校所學(xué)知識的全面總結(jié)和綜合 應(yīng)用，又為今后走向社會的提供實戰(zhàn)演戲的機會。是我們對所學(xué)知識理論的檢驗