序言：寫作是分享個(gè)人見(jiàn)解和探索未知領(lǐng)域的橋梁，我們?yōu)槟x了8篇的建模藝術(shù)論文樣本，期待這些樣本能夠?yàn)槟峁┴S富的參考和啟發(fā)，請(qǐng)盡情閱讀。

第1篇

論文關(guān)鍵詞：遺傳算法

 

1 引言

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

2 遺傳算法概述

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

2.1遺傳算法幾個(gè)基本概念

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

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

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

適應(yīng)度(Fitness)：適應(yīng)度是以數(shù)值方式來(lái)描述個(gè)體優(yōu)劣程度的指標(biāo)，由評(píng)價(jià)函數(shù)F計(jì)算得到。F作為求解問(wèn)題的目標(biāo)函數(shù)，求解的目標(biāo)就是該函數(shù)的最大值或最小值。

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

選擇(Reproduetion)：選擇算子是指在上一代群體中按照某些指標(biāo)挑選出的，參與繁殖下一代群體的一定數(shù)量的個(gè)體的一種機(jī)制龍?jiān)雌诳€(gè)體在下一代種群中出現(xiàn)的可能性由個(gè)體的適應(yīng)度決定，適應(yīng)度越高的個(gè)體，產(chǎn)生后代的概率就越高。

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

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

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

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

基本操作：

InitPop（）

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

Selection（）

初始條件：種群已存在。

操作結(jié)果：對(duì)當(dāng)前種群進(jìn)行交叉操作。

Crossover（）

初始條件：種群已存在。

操作結(jié)果：對(duì)當(dāng)前種群進(jìn)行交叉操作。

Mutation（）

初始條件：種群已存在。

對(duì)當(dāng)前種群進(jìn)行變異操作。

PerformEvolution（）

初始條件：種群已存在且當(dāng)前種群不是第一代種群。

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

Output（）

初始條件：當(dāng)前種群是最后一代種群。

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

3 遺傳算法的缺點(diǎn)及改進(jìn)

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

3.1編碼方案

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

3.2 適應(yīng)度函數(shù)

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

（1）

3.3 選擇交叉和變異

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

（2）

（3）

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

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

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

(4)

(5)

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

3.4 種群的進(jìn)化與進(jìn)化終止條件

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

(6)

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

[3]李敏強(qiáng),寇紀(jì)淞,林丹,李書(shū)全.遺傳算法的基本理論與應(yīng)用[M].科學(xué)出版社, 2002:1-16.

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

[5]陳瑋,周激,流程進(jìn),陳莉.一種改進(jìn)的兩代競(jìng)爭(zhēng)遺傳算法[J].四川大學(xué)學(xué)報(bào):自然科學(xué)版,2003.040(002):273-277.

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

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

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