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

第1篇

論文關鍵詞：遺傳算法

 

1 引言

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

2 遺傳算法概述

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

2.1遺傳算法幾個基本概念

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

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

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

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

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

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

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

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

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

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

基本操作：

InitPop（）

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

Selection（）

初始條件：種群已存在。

操作結(jié)果：對當前種群進行交叉操作。

Crossover（）

初始條件：種群已存在。

操作結(jié)果：對當前種群進行交叉操作。

Mutation（）

初始條件：種群已存在。

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

PerformEvolution（）

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

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

Output（）

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

操作結(jié)果：輸出bestindi的表現(xiàn)型以及對象值。

3 遺傳算法的缺點及改進

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

3.1編碼方案

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

3.2 適應度函數(shù)

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

（1）

3.3 選擇交叉和變異

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

（2）

（3）

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

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

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

(4)

(5)

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

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

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

(6)

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

3.5 重要參數(shù)的選擇

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

4 結(jié)束語

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

參考文獻

[1]邢文訓,謝金星.現(xiàn)代優(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