序言：寫作是分享個人見解和探索未知領域的橋梁，我們?yōu)槟x了8篇的建模藝術論文樣本，期待這些樣本能夠為您提供豐富的參考和啟發(fā)，請盡情閱讀。

第1篇

論文關鍵詞：遺傳算法

 

1 引言

“物競天擇，適者生存”是達爾文生物進化論的基本原理，揭示了物種總是向著更適應自然界的方向進化的規(guī)律?？梢?，生物進化過程本質上是一種優(yōu)化過程，在計算科學上具有直接的借鑒意義。在計算機技術迅猛發(fā)展的時代，生物進化過程不僅可以在計算機上模擬實現，而且還可以模擬進化過程，創(chuàng)立新的優(yōu)化計算方法，并應用到復雜工程領域之中，這就是遺傳算法等一類進化計算方法的思想源泉。

2 遺傳算法概述

遺傳算法是將生物學中的遺傳進化原理和隨[1]優(yōu)化理論相結合的產物，是一種隨機性的全局優(yōu)算法。遺傳算法不但具有較強的全局搜索功能和求解問題的能力，還具有簡單通用、魯棒性強、適于并行處理等特點數學建模論文，是一種較好的全局優(yōu)化搜索算法。在遺傳算法的應用中，由于編碼方式和遺傳算子的不同，構成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點，即通過對生物遺傳和進化過程中選擇、交叉、變異機理的模仿，來完成對問題最優(yōu)解的自適應搜索過程?；谶@個共同點，Holland的遺傳算法常被稱為簡單遺傳算法（簡記SGA），簡單遺傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎，這種改進的或變形的遺傳算法，都是以其為基礎[1]。

2.1遺傳算法幾個基本概念

個體(IndividualString)：個體是遺傳算法中用來模擬生物染色體的一定數目的二進制串，該二進制串用來表示優(yōu)化問題的滿意解。

種群(population)：包含一組個體的群體，是問題解的集合。

基因模式(Sehemata)：基因模式是指二進制位串表示的個體中，某一個或某些位置上具有相似性的個體組成的集合，也稱模式。

適應度(Fitness)：適應度是以數值方式來描述個體優(yōu)劣程度的指標，由評價函數F計算得到。F作為求解問題的目標函數，求解的目標就是該函數的最大值或最小值。

遺傳算子(genetic operator)：產生新個體的操作，常用的遺傳算子有選擇、交叉和變異。

選擇(Reproduetion)：選擇算子是指在上一代群體中按照某些指標挑選出的，參與繁殖下一代群體的一定數量的個體的一種機制龍源期刊。個體在下一代種群中出現的可能性由個體的適應度決定，適應度越高的個體，產生后代的概率就越高。

交叉(erossover)：交叉是指對選擇后的父代個體進行基因模式的重組而產生后代個體的繁殖機制。在個體繁殖過程中，交叉能引起基因模式的重組，從而有可能產生含優(yōu)良性能的基因模式的個體。交叉可以發(fā)生在染色體的一段基因串或者多段基因串。交叉概率（Pc）決定兩個個體進行交叉操作的可能性數學建模論文，交叉概率太小時難以向前搜索，太大則容易破壞高適應度的個體結構，一般Pc取0.25~0.75

變異(Mutation)：變異是指模擬生物在自然的遺傳環(huán)境中由于某種偶然因素引起的基因模式突變的個體繁殖方式。在變異算子中，常以一定的變異概率（Pm）在群體中選取個體，隨機選擇個體的二進制串中的某些位進行由概率控制的變換（0與1互換）從而產生新的個體[2]。如果變異概率太小，就難以產生新的基因結構，太大又會使遺傳算法成了單純的隨機搜索，一般取Pm=0.1~0.2。在遺傳算法中，變異算子增加了群體中基因模式的多樣性，從而增加了群體進化過程中自然選擇的作用，避免早熟現象的出現。

2.2基本遺傳算法的算法描述

用P(t)代表第t代種群，下面給出基本遺傳算法的程序偽代碼描述：

基本操作：

InitPop（）

操作結果：產生初始種群，初始化種群中的個體，包括生成個體的染色體值、計算適應度、計算對象值。

Selection（）

初始條件：種群已存在。

操作結果：對當前種群進行交叉操作。

Crossover（）

初始條件：種群已存在。

操作結果：對當前種群進行交叉操作。

Mutation（）

初始條件：種群已存在。

對當前種群進行變異操作。

PerformEvolution（）

初始條件：種群已存在且當前種群不是第一代種群。

操作結果：如果當前種群的最優(yōu)個體優(yōu)于上一代的最優(yōu)本，則將其賦值給bestindi，否則不進行任何操作。

Output（）

初始條件：當前種群是最后一代種群。

操作結果：輸出bestindi的表現型以及對象值。

3 遺傳算法的缺點及改進

遺傳算法有兩個明顯的缺點：一個原因是出現早熟往往是由于種群中出現了某些超級個體，隨著模擬生物演化過程的進行，這些個體的基因物質很快占據種群的統(tǒng)治地位，導致種群中由于缺乏新鮮的基因物質而不能找到全局最優(yōu)值；另一個主要原因是由于遺傳算法中選擇及雜交變異等算子的作用，使得一些優(yōu)秀的基因片段過早丟失，從而限制了搜索范圍，使得搜索只能在局部范圍內找到最優(yōu)值，而不能得到滿意的全局最優(yōu)值[3]。為提高遺傳算法的搜索效率并保證得到問題的最優(yōu)解，從以下幾個方面對簡單遺傳算法進行改進。

3.1編碼方案

因實數編碼方案比二進制編碼策略具有精度高、搜索范圍大、表達自然直觀等優(yōu)點數學建模論文，并能夠克服二進制編碼自身特點所帶來的不易求解高精度問題、不便于反應所求問題的特定知識等缺陷，所以確定實數編碼方案替代SGA中采用二進制編碼方案[4]。

3.2 適應度函數

采用基于順序的適應度函數，基于順序的適應度函數最大的優(yōu)點是個體被選擇的概率與目標函數的具體值無關，僅與順序有關[5]。構造方法是先將種群中所有個體按目標函數值的好壞進行排序，設參數β∈(0,1)，基于順序的適應度函數為：

（1）

3.3 選擇交叉和變異

在遺傳算法中，交叉概率和變異概率的選取是影響算法行為和性能的關鍵所在，直接影響算法的收斂性。在SGA中，交叉概率和變異概率能夠隨適應度自動調整，在保持群體多樣性的同時保證了遺傳算法的收斂性。在自適應基本遺傳算法中，pc和pm按如下公式進行自動調整：

（2）

（3）

式中：fmax為群體中最大的適應度值；fave為每代群體的平均適應度值；f′為待交叉的兩個個體中較大的適應度值；f為待變異個體的適應度值；此處，只要設定k1、k2、k3、k4為（0，1）之間的調整系數，Pc及Pm即可進行自適應調整。本文對標準的遺傳算法進行了改進，改進后的遺傳算法對交叉概率采用與個體無關，變異概率與個體有關。交叉算子主要作用是產生新個體，實現了算法的全局搜索能力。從種群整體進化過程來看，交叉概率應該是一個穩(wěn)定而逐漸變小，到最后趨于某一穩(wěn)定值的過程；而從產生新個體的角度來看，所有個體在交叉操作上應該具有同等地位，即相同的概率，從而使GA在搜索空間具有各個方向的均勻性。對公式（2)和（3）進行分析表明，適應度與交叉率和變異率呈簡單的線性映射關系。當適應度低于平均適應度時，說明該個體是性能不好的個體數學建模論文，對它就采用較大的交叉率和變異率；如果適應度高于平均適應度，說明該個體性能優(yōu)良，對它就根據其適應度值取相應的交叉率和變異率龍源期刊。

當個體適應度值越接近最大適應度值時，交叉概率和變異概率就越小；當等于最大適應度值時，交叉概率和變異概率為零。這種調整方法對于群體處于進化的后期比較合適，這是因為在進化后期，群體中每個個體基本上表現出較優(yōu)的性能，這時不宜對個體進行較大的變化以免破壞了個體的優(yōu)良性能結構；但是這種基本遺傳算法對于演化的初期卻不利，使得進化過程略顯緩慢[6]。因為在演化初期，群體中較優(yōu)的個體幾乎是處于一種不發(fā)生變化的狀態(tài)，而此時的優(yōu)良個體卻不一定是全局最優(yōu)的，這很容易導致演化趨向局部最優(yōu)解。這容易使進化走向局部最優(yōu)解的可能性增加。同時，由于對每個個體都要分別計算Pc和Pm，會影響程序的執(zhí)行效率，不利于實現。

對自適應遺傳算法進行改進，使群體中具有最大適應度值的個體的交叉概率和變異概率不為零，改進后的交叉概率和變異概率的計算公式如式（4）和（5）所示。這樣，經過改進后就相應地提高了群體中性能優(yōu)良個體的交叉概率和變異概率，使它們不會處于一種停滯不前的狀態(tài)，從而使得算法能夠從局部最優(yōu)解中跳出來獲得全局最優(yōu)解[7]。

(4)

(5)

其中：fmax為群體中最大的適應度值；fave為每代群體的平均適應度值；f′為待交叉的兩個個體中較大的適應度值；f為待變異個體的適應度值；pc1為最大交叉概率；pm1為最大變異概率。

3.4 種群的進化與進化終止條件

將初始種群和產生的子代種群放在一起，形成新的種群，然后計算新的種群各個體的適應度，將適應度排在前面的m個個體保留，將適應度排在后面m個個體淘汰數學建模論文，這樣種群便得到了進化[8]。每進化一次計算一下各個個體的目標函數值，當相鄰兩次進化平均目標函數之差小于等于某一給定精度ε時，即滿足如下條件：

(6)

式中，為第t+1次進化后種群的平均目標函數值，為第t次進化后種群的平均目標函數值，此時，可終止進化。

3.5 重要參數的選擇

GA的參數主要有群里規(guī)模n，交叉、變異概率等。由于這些參數對GA性能影響很大，因此參數設置的研究受到重視。對于交叉、變異概率的選擇，傳統(tǒng)選擇方法是靜態(tài)人工設置。現在有人提出動態(tài)參數設置方法，以減少人工選擇參數的困難和盲目性。

4 結束語

遺傳算法作為當前研究的熱點，已經取得了很大的進展。由于遺傳算法的并行性和全局搜索等特點，已在實際中廣泛應用。本文針對傳統(tǒng)遺傳算法的早熟收斂、得到的結果可能為非全局最優(yōu)收斂解以及在進化后期搜索效率較低等缺點進行了改進，改進后的遺傳算法在全局收斂性和收斂速度方面都有了很大的改善，得到了較好的優(yōu)化結果。

參考文獻

[1]邢文訓,謝金星.現代優(yōu)化計算方法[M].北京:清華大學出版社,1999:66-68.

[2]王小平,曹立明.遺傳算法理論[M].西安交通大學出版社,2002:1-50,76-79.

[3]李敏強,寇紀淞,林丹,李書全.遺傳算法的基本理論與應用[M].科學出版社, 2002:1-16.

[4]涂承媛,涂承宇.一種新的收斂于全局最優(yōu)解的遺傳算法[J].信息與控制,2001,30(2):116-138

[5]陳瑋,周激,流程進,陳莉.一種改進的兩代競爭遺傳算法[J].四川大學學報:自然科學版,2003.040(002):273-277.

[6]王慧妮,彭其淵,張曉梅.基于種群相異度的改進遺傳算法及應用[J].計算機應用,2006,26(3):668-669.

[7]金晶,蘇勇.一種改進的自適應遺傳算法[J].計算機工程與應用,2005,41(18):64-69.

[8]陸濤,王翰虎,張志明.遺傳算法及改進[J].計算機科學,2007,34(8):94-96