時(shí)間：2023-03-22 17:41:41
序論：在您撰寫遺傳算法論文時(shí)，參考他人的優(yōu)秀作品可以開闊視野，小編為您整理的7篇范文，希望這些建議能夠激發(fā)您的創(chuàng)作熱情，引導(dǎo)您走向新的創(chuàng)作高度。
論文關(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ì)淞,林丹,李書全.遺傳算法的基本理論與應(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
論文摘要：TSP是組合優(yōu)化問(wèn)題的典型代表,該文在分析了遺傳算法的特點(diǎn)后,提出了一種新的遺傳算法(GB—MGA),該算法將基因庫(kù)和多重搜索策略結(jié)合起來(lái),利用基因庫(kù)指導(dǎo)單親遺傳演化的進(jìn)化方向,在多重搜索策略的基礎(chǔ)上利用改進(jìn)的交叉算子又增強(qiáng)了遺傳算法的全局搜索能力。通過(guò)對(duì)國(guó)際TSP庫(kù)中多個(gè)實(shí)例的測(cè)試,結(jié)果表明:算法(GB—MGA)加快了遺傳算法的收斂速度,也加強(qiáng)了算法的尋優(yōu)能力。
論文關(guān)鍵詞：旅行商問(wèn)題遺傳算法基因庫(kù)多重搜索策略
TSP(travelingsalesmanproblem)可以簡(jiǎn)述為:有n個(gè)城市1,2,…,n,一旅行商從某一城市出發(fā),環(huán)游所有城市后回到原出發(fā)地,且各城市只能經(jīng)過(guò)一次,要求找出一條最短路線。TSP的搜索空間是有限的,如果時(shí)間不受限制的話,在理論上這種問(wèn)題終會(huì)找到最優(yōu)解,但對(duì)于稍大規(guī)模的TSP,時(shí)間上的代價(jià)往往是無(wú)法接受的。這是一個(gè)典型的組合最優(yōu)化問(wèn)題,已被證明是NP難問(wèn)題,即很可能不存在確定的算法能在多項(xiàng)式時(shí)間內(nèi)求到問(wèn)題的解[1]。由于TSP在工程領(lǐng)域有著廣泛的應(yīng)用,如貨物運(yùn)輸、加工調(diào)度、網(wǎng)絡(luò)通訊、電氣布線、管道鋪設(shè)等,因而吸引了眾多領(lǐng)域的學(xué)者對(duì)它進(jìn)行研究。TSP的求解方法種類繁多,主要有貪婪法、窮舉法、免疫算法[2]、螞蟻算法[3]、模擬退火算法、遺傳算法等。
遺傳算法是一種借鑒生物界自然選擇和遺傳機(jī)制的隨機(jī)化搜索算法,其主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換,搜索不依賴于梯度信息[4]。遺傳算法主要包括選擇、交叉和變異3個(gè)操作算子,它是一種全局化搜索算法,尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問(wèn)題。遺傳算法雖然不能保證在有限的時(shí)間內(nèi)獲得最優(yōu)解,但隨機(jī)地選擇充分多個(gè)解驗(yàn)證后,錯(cuò)誤的概率會(huì)降到可以接受的程度。
用遺傳算法求解TSP能得到令人滿意的結(jié)果,但是其收斂速度較慢,而且種群在交叉算子作用下,會(huì)陷入局部解。采用局部啟發(fā)式搜索算法等,雖然能在很短的時(shí)間內(nèi)計(jì)算出小規(guī)模城市的高質(zhì)量解,一旦城市規(guī)模稍大就容易陷入局部最優(yōu)解。因此,為了能夠加快遺傳算法的收斂速度,又能得到更好的近似最優(yōu)解,該文采納了文[5]中楊輝提出的基因庫(kù)的想法,并結(jié)合文[6]中Cheng-FaTsai提出的多重搜索策略思想,使用單親演化與群體演化相結(jié)合的方式來(lái)求解TSP問(wèn)題。該文根據(jù)文[7]中最小生成樹MST(minimumcostspanningtree)的應(yīng)用,由MST建立TSP的基因庫(kù),保存有希望成為最優(yōu)解的邊,利用基因庫(kù)提高初始群體的質(zhì)量進(jìn)行單親演化,然后利用改進(jìn)后的交叉算子和的多重搜索策略進(jìn)行群體演化。
1單親演化過(guò)程
現(xiàn)有的大多數(shù)演化算法在整個(gè)演化過(guò)程中所涉及的基因,大多來(lái)源于個(gè)體本身,個(gè)體質(zhì)量的高低決定了算法的全局性能,如果群體中初始個(gè)體的適應(yīng)度都較差,肯定要影響算法的收斂速度,對(duì)于規(guī)模稍大的TSP尤其明顯[8]。該文為了克服上述弱點(diǎn),首先利用普里姆算法求出TSP中最小生成樹,并將各個(gè)MST中的每一條邊都保存在一個(gè)n*(n-1)方陣?yán)锩?就構(gòu)成了一個(gè)基因庫(kù),在生成初始群體的時(shí)候盡量使用基因庫(kù)中的基因片段,來(lái)提高整個(gè)初始群體的適應(yīng)度,從而提高算法的效率。
1.1TSP編碼表示
設(shè)n個(gè)城市編號(hào)為1,2,…,n,為一條可行路徑,Pk=Vk1Vk2…Vkn為一條可行路徑,它是1,2,…,n的一個(gè)隨機(jī)排列,其含意是第k條路徑起點(diǎn)城市是Vk1,最后一個(gè)城市是Vkn,則第k條環(huán)路的總長(zhǎng)度可以表示為:
其中,d(Vki,Vkj)表示城市Vki與城市Vkj之間的距離。在算法中環(huán)路Pk的總長(zhǎng)d(Pk)用來(lái)評(píng)價(jià)個(gè)體的好壞[9]。適應(yīng)度函數(shù)取路徑長(zhǎng)度d(Pk)的倒數(shù),f(Pk)=1/d(Pk)。
1.2構(gòu)建TSP基因庫(kù)
對(duì)n個(gè)編號(hào)為1,2,…,n的城市,根據(jù)它們的坐標(biāo)計(jì)算各城市之間的歐氏距離d(i,j),i,j=1,2,…,n,得到一個(gè)n*n的方陣D={d(i,j)}。然后利用普里姆算法求得該TSP的一棵MST,并將這棵MST中的每一條邊e(i,j)對(duì)應(yīng)地存儲(chǔ)在一個(gè)n*(n-1)的方陣M={e(i,j)},即該文的基因庫(kù)。由于一個(gè)TSP可能有多棵MST,操作可以重復(fù)多次,這樣生成的基因庫(kù)中的基因就更多,增強(qiáng)了初始群體的全局性。具體算法如下:
VoidMiniSpanTree—PRIM(MGraphG,VertexTypeu){
Struct{
VertexTypeadjvex;
VRTypelowcost;
}closedge[MAX—VERTEX—NUM];
k=LocateVex(G,u);
for(j=0;j<G.vexnum;++j)
if(j!=k)closedge[j]={u,G.arcs[k][j].adj};
closedge[k].lowcost=0;
for(i=0;i<G.vexnum;++i){
k=minimum(closedge);
printf(closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
for(j=0;j<G.vexnum;++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}
}
1.3單親演化算法
單親演化算法是利用遺傳算法的優(yōu)勝劣汰的遺傳特性,在單個(gè)染色體內(nèi)以基因重組的方式,使子代在滿足TSP問(wèn)題的限定條件下進(jìn)行繁衍,然后保留適應(yīng)度高的染色體種群,達(dá)到優(yōu)化的目的。單親演化算法的基因重組操作包括基因換位、基因段錯(cuò)位和基因段倒轉(zhuǎn)三種操作來(lái)實(shí)現(xiàn)。基因換位操作是將親代的染色體基因進(jìn)行對(duì)換后,形成子代,其換位又分為單基因換位和基因段換位兩種方式?；蚨五e(cuò)位操作是隨機(jī)確定基因段,也隨機(jī)選定錯(cuò)位位置,整段錯(cuò)移?；蚨蔚罐D(zhuǎn)操作則是隨機(jī)地確定倒轉(zhuǎn)基因段的起止位置,倒轉(zhuǎn)操作是對(duì)該段內(nèi)基因按中垂線作鏡面反射,若段內(nèi)基因數(shù)為奇數(shù)時(shí),則中位基因不變。單親演化時(shí)可以是單個(gè)操作用于單個(gè)父代,也可以是幾種操作同時(shí)采用。為了編程方便,文中采用基因段倒轉(zhuǎn)操作。
2群體演化過(guò)程
在單親演化算法求得的初始群體基礎(chǔ)上,再利用多重搜索策略并行地進(jìn)行群體演化,這樣在保證算法的快速收斂的同時(shí)也注重了搜索空間的全局性。
2.1交叉算子
該文算子采用一種與順序交叉OX(ordercrossover)法類似的交叉方法[11],即隨機(jī)在串中選擇一個(gè)區(qū)域,例如以下兩個(gè)父串及區(qū)域選定為:
P1=(12|3456|789)P2=(98|7654|321)
將P2的區(qū)域加到P1的前面或后面,P1的區(qū)域加到P2的前面或后面,得
M1=(7654|123456789)
M2=(3456|987654321)
在M1中自區(qū)域后依次刪除與區(qū)域相同的城市碼,得到最終的兩個(gè)子串:
S1=(765412389)S2=(345698721)
同時(shí)為了能更好地增強(qiáng)算子的全局搜索能力,對(duì)該算子作了如下的改進(jìn)。子代個(gè)體的新邊來(lái)自:隨機(jī)生成和群體中其他個(gè)體,其選擇比例由隨機(jī)數(shù)p和閾值P來(lái)決定。如果隨機(jī)數(shù)p小于閾值P,則子代個(gè)體的新邊來(lái)自隨機(jī)生成,否則就來(lái)自群體中的其他個(gè)體。
這種改進(jìn)后的交叉算子在父串相同的情況下仍能產(chǎn)生一定程度的變異效果,這對(duì)維持群體的多樣化特性有一定的作用。實(shí)驗(yàn)結(jié)果也證實(shí)了這種改進(jìn)算子對(duì)于種群的全局搜索能力有一定的提高,避免搜索陷入局部解。
2.2局部啟發(fā)式算子
為了增強(qiáng)遺傳算法的局部搜索性能,在算法中引入2-Opt局部搜索算子[12]。該算子通過(guò)比較兩條邊并交換路徑以提升算法的局部搜索性能,示例見(jiàn)圖2。
比較子路徑ab+cd和ac+bd,如果ab+cd>ac+bd則交換,否則就不交換?？紤]到程序的運(yùn)行效率,不可能對(duì)每對(duì)邊都做檢查,所以選取染色體中的一定數(shù)量的邊進(jìn)行比較。2-Opt搜索算子實(shí)際上進(jìn)行的相當(dāng)于變異操作,同時(shí)又不僅僅是簡(jiǎn)單的變異,而是提高算法的局部搜索性能的變異操作。
2.3選擇機(jī)制和收斂準(zhǔn)則
為了限制種群的規(guī)模[13],該文采用了聯(lián)賽選擇法的淘汰規(guī)則。聯(lián)賽選擇法就是以各染色體的適應(yīng)度作為評(píng)定標(biāo)準(zhǔn),從群體中任意選擇一定數(shù)目的個(gè)體,稱為聯(lián)賽規(guī)模,其中適應(yīng)度最高的個(gè)體保存到下一代。這個(gè)過(guò)程反復(fù)執(zhí)行,直到保存到下一代的個(gè)體數(shù)達(dá)到預(yù)先設(shè)定的數(shù)目為止。這樣做可能導(dǎo)致種群過(guò)早收斂,因此在收斂準(zhǔn)則上要采取苛刻的要求來(lái)保證搜索的全局性。
遺傳算法求TSP問(wèn)題如果不設(shè)定終止條件,其演化過(guò)程將會(huì)無(wú)限制地進(jìn)行下去。終止條件也稱收斂準(zhǔn)則,因?yàn)槎鄶?shù)最優(yōu)化問(wèn)題事先并不了解最優(yōu)的目標(biāo)函數(shù)值,故無(wú)法判斷尋優(yōu)的精度。該文采用如下兩條收斂準(zhǔn)則:在連續(xù)K1代不再出現(xiàn)更優(yōu)的染色體;優(yōu)化解的染色體占種群的個(gè)數(shù)達(dá)K2的比例以上。當(dāng)兩準(zhǔn)則均滿足時(shí),則終止運(yùn)算,輸出優(yōu)化結(jié)果和對(duì)應(yīng)的目標(biāo)函數(shù)值。由數(shù)值實(shí)驗(yàn)表明,添加第2條準(zhǔn)則之后,全局最優(yōu)解的出現(xiàn)頻率將大為提高。
2.4基于多重搜索策略的群體演化算法
由于基因庫(kù)的引入,可能降低初始種群的多樣性,為避免算法陷入局部最優(yōu)解,因此在群體演化中采取多重搜索策略。由Cheng-FaTsai提出的多重搜索策略[6],就是把染色體集中的染色體分成保守型和探索型兩種不同類型的集合,然后針對(duì)不同類型的染色體集合根據(jù)不同的交叉、變異概率分別進(jìn)行交叉變異操作,對(duì)保守型染色體集合就采用比較低的交叉變異概率,而對(duì)探索型染色體集合就采用比較高的交叉變異概率。這種策略對(duì)保守型染色體集合的操作最大限度地保留了父代的優(yōu)秀基因片段,另一方面對(duì)探索型染色體集合的操作又盡可能地提高了算法的全局搜索能力。為了提高算法的收斂速度,初始染色體集合該文采用了前面單親演化的結(jié)果中的染色體集合,交叉算子則利用的是前面介紹的改進(jìn)后的算子,改進(jìn)后的多重搜索策略見(jiàn)下。
3實(shí)驗(yàn)結(jié)果與分析
該文的GB—MGA算法由C#編程實(shí)現(xiàn),所有的結(jié)果都是在P42.0G微機(jī)上完成,并進(jìn)行通用的TSP庫(kù)實(shí)驗(yàn),選用了具有一定代表性的TSP實(shí)例,并把該算法和其他算法做了一個(gè)對(duì)比。為了減少計(jì)算量,程序中的數(shù)據(jù)經(jīng)過(guò)四舍五入整數(shù)化處理,與實(shí)數(shù)解有一定的偏差,下面給出圖Kroa100的示例。
為了證明該文提出的GB—MGA算法的有效性,將該文算法與典型的遺傳算法GA、單親遺傳算法PGA以及文[5]中楊輝提出的Ge—GA(genepoolgeneticalgorithm)算法和文[12]中提出的MMGA(modifiedmultiple-searchinggeneticalgorithm)算法都進(jìn)行了一個(gè)對(duì)比。
實(shí)驗(yàn)結(jié)果證明,該文算法的求解質(zhì)量要優(yōu)于GA、PGA、MMGA算法,而求解速度方面則優(yōu)于Ge—GA算法,特別是對(duì)于大規(guī)模城市的TSP問(wèn)題求解效果尤其明顯,具有快速收斂的特性。Ge—GA算法對(duì)于中等城市規(guī)模的TSP實(shí)例求解,其運(yùn)算時(shí)間就大幅度增加,如果把該算法用于求解大規(guī)模和超大規(guī)模TSP問(wèn)題,那么時(shí)間上的代價(jià)就讓人無(wú)法忍受。而該文的GB—MGA算法在單親遺傳演化中就使用了基因庫(kù)中的優(yōu)質(zhì)基因,使得單個(gè)個(gè)體的進(jìn)化速度大大提高,從而為進(jìn)一步的演化提供了條件,群體演化過(guò)程的選擇機(jī)制和收斂準(zhǔn)則的恰當(dāng)選取使得算法在注重了求解質(zhì)量的同時(shí)兼顧了算法的效率。
4結(jié)束語(yǔ)
遺傳算法就是一種以事物的自然屬性和遺傳屬性為基礎(chǔ)，通過(guò)計(jì)算機(jī)對(duì)生物進(jìn)化規(guī)律進(jìn)行模擬以尋優(yōu)的一種算法，將尋優(yōu)的范圍與遺傳空間相對(duì)應(yīng)，把每一種可能的值通過(guò)二進(jìn)制碼進(jìn)行編碼，如同染色體一樣，形成的字符串相當(dāng)于基因，然后按預(yù)期的結(jié)果對(duì)每一組編碼進(jìn)行評(píng)價(jià)，選出最合適的一個(gè)值。算法一開始是提出一些問(wèn)題的解，然后根據(jù)要求對(duì)這些解進(jìn)行選擇，重新拆解組合，去掉不合適的，留下最優(yōu)值，由此形成的便是新值，如此往復(fù)，繼承與改良，這便是GA算法。由以上我們可以看出GA算法并不是簡(jiǎn)單的重復(fù)，而是屬于一種螺旋式的上升過(guò)程，是不斷向更好的方向“進(jìn)化”的，在淘汰與擇優(yōu)中趨于穩(wěn)定。
2GA算法的數(shù)學(xué)基礎(chǔ)和算子
2.1GA算法的數(shù)學(xué)基礎(chǔ)
圖式定理是GA算法的數(shù)學(xué)基礎(chǔ)，圖式定理是Holland提出的，它在一定程度上解釋了GA算法強(qiáng)大的數(shù)據(jù)信息處理能力，由定理我們能看出，經(jīng)過(guò)不斷地復(fù)制和交叉變異，在第一代中包含的編碼數(shù)量H可以用如下公式表示：m（H，t+1）≥m（H，t）（N（H）/FAV）[1-PC•（〥（H）/（L-1））-O（H）•Pm]（1）如以遺傳學(xué)講，其中m（H，t）和m（H，t+1）分別代表第t代和第t+1代種群數(shù)量，N代表圖式H中染色體適應(yīng)能力的平均水平，F(xiàn)AV代表種群中包含的染色體的適應(yīng)力的平均水平，交叉比率用PC表示，變異比率用Pm表示，圖式的長(zhǎng)度用〥表示，OH是H的確定參數(shù)，即階，染色體長(zhǎng)度用L表示。
2.2GA算法的算子
GA遺傳算法的基本算子有三個(gè)，分別是選擇、交叉和變異。選擇算子相當(dāng)于生物界優(yōu)勝劣汰，決定物種最終存活的自然選擇，在生物群中選擇一些適應(yīng)力強(qiáng)的生物，將它們的染色體放入基因庫(kù)，是染色體重新交叉組合完成變異的前提，選擇算子的特點(diǎn)是只能在原有的基礎(chǔ)上選擇出優(yōu)良的基因，而無(wú)法重新創(chuàng)造。交叉算子相當(dāng)于自然界生物為完成繁衍生息和進(jìn)化而進(jìn)行的繁殖現(xiàn)象，染色體經(jīng)由交叉，重新組合后形成新的染色體，即從雙親染色體里隨機(jī)地分別選擇一條再重新組合，是染色體的重新創(chuàng)造。變異算子是在選擇和交叉算子完成重組的基礎(chǔ)上使遺傳算法能力的增強(qiáng)，以尋找GA值的最優(yōu)解，如果在整個(gè)GA算法中少了變異操作，就只能在原有基礎(chǔ)上來(lái)回尋找而沒(méi)有新的突破。
3如何實(shí)現(xiàn)遺傳算法
遺傳算法歸根結(jié)底是尋找一個(gè)最優(yōu)的解或者工程中所講的最好的解決方案，從函數(shù)來(lái)講是求如下函數(shù)的最優(yōu)解：F=f（x，y，z），x，y，z∈Ω，F(xiàn)∈R（2）其中x，y，z是自變量，每一組（x，y，z）就是一組解，優(yōu)化目標(biāo)的目的是尋找一組解使得：F=f（x0，y0，z0）=maxf（x，y，z）（3）首先，將公式（2）的各個(gè)參數(shù)通過(guò)二進(jìn)制數(shù)編碼形成字符串，再進(jìn)行鏈接形成所謂的“基因鏈”，據(jù)已有的研究結(jié)果，可以知道字符串長(zhǎng)度不同、碼制不同都將對(duì)最終計(jì)算的結(jié)果的精度產(chǎn)生影響。其次，采用隨機(jī)抽選的方式選擇個(gè)體的初始值，之所以隨機(jī)抽選是因?yàn)檫@樣產(chǎn)生的結(jié)果更具有一般性，能代表尋常情況。最后，確定群體的規(guī)模，即確定基因選擇的目標(biāo)源，在這個(gè)目標(biāo)源中尋找最佳值，規(guī)模的確定決定了GA算法結(jié)果的權(quán)威性和有效性，太小則不能提供足夠的采樣點(diǎn)，結(jié)果的多樣性將會(huì)打折扣，太大則會(huì)增加計(jì)算量，拖長(zhǎng)搜索時(shí)間，通暢將規(guī)模控制在40～200左右為宜，在對(duì)每個(gè)個(gè)體的優(yōu)劣實(shí)施評(píng)價(jià)之后，設(shè)置一個(gè)適應(yīng)度函數(shù)，然后分別確定交叉率和變異率，判斷搜索何時(shí)停止，在本次討論中，判斷標(biāo)準(zhǔn)可以定為搜索所得的解是否達(dá)到了預(yù)期的最大值。
4GA在機(jī)械工程中的應(yīng)用
GA算法的優(yōu)點(diǎn)顯而易見(jiàn)，它在機(jī)械工程中的應(yīng)用是極為廣泛的。在零件的切削中可以對(duì)零部件和切削工具予以優(yōu)化，使得切削參數(shù)的設(shè)置達(dá)到總在工作以最低的成本，實(shí)現(xiàn)最高的效率，最終得到最高的收益的目的，在自動(dòng)化控制的智能制造系統(tǒng)中可以為系統(tǒng)的靜態(tài)動(dòng)態(tài)的配合尋找到最佳契合點(diǎn)，以下對(duì)GA算法在機(jī)械公式和功能中的應(yīng)用以具體實(shí)例加以闡述。
4.1優(yōu)化人工神經(jīng)網(wǎng)
ANN，即人工神經(jīng)網(wǎng)，是一種用于建模和控制的，針對(duì)模型結(jié)構(gòu)不穩(wěn)定的線性系統(tǒng)而設(shè)計(jì)的結(jié)構(gòu)，單次結(jié)構(gòu)目前并不成熟，并沒(méi)有確切的數(shù)據(jù)指導(dǎo)后來(lái)者準(zhǔn)確的使用，處于摸索階段。對(duì)于ANN，目前采用的訓(xùn)練方法是反向傳播算法，大速度比較慢且結(jié)果具有一定的局限性，GA算法可謂使這一問(wèn)題得見(jiàn)柳暗花明。在AN的行學(xué)習(xí)參數(shù)的優(yōu)化工作中，仍用反向傳播，但對(duì)一下因素進(jìn)行編碼操作，包括隱含層數(shù)、隱含層數(shù)的單元數(shù)、勢(shì)態(tài)、網(wǎng)絡(luò)連接方法、迭代數(shù)等，編碼完成后，構(gòu)成ANN基因鏈，把基因鏈的適應(yīng)度函數(shù)定義為10-MSE-隱含單元數(shù)/10-訓(xùn)練跌代數(shù)/1000，MSE是訓(xùn)練好的網(wǎng)絡(luò)對(duì)樣本的方差。
4.2優(yōu)化FLC矩陣的參數(shù)
模糊邏輯控制器，簡(jiǎn)稱FLC，涉及到的概念有控制對(duì)象偏差和動(dòng)作強(qiáng)度，表達(dá)了二者的模糊關(guān)系，現(xiàn)有一延時(shí)二階系統(tǒng)的函數(shù)為GS=exp（-0.4s）/（0.3s+1），要求此系統(tǒng)的輸出值盡量的跟蹤輸入值，采用FLC矩陣進(jìn)行參數(shù)優(yōu)化，取矩陣R=77×11，對(duì)此矩陣的77個(gè)元素以8bit的二進(jìn)制碼表示，基因鏈長(zhǎng)616bit，經(jīng)由GA算法優(yōu)化的FLC控制下，輸出值的效果明顯地優(yōu)于“比例-積分-微分”控制器的效果。
4.3實(shí)現(xiàn)機(jī)床掛最佳組合
機(jī)床掛輪組合的完美與否直接決定了生產(chǎn)線的效率，而這又是一個(gè)極為古老的問(wèn)題，最佳組合最終實(shí)現(xiàn)的是掛輪組的傳動(dòng)比與要求的值誤差達(dá)到最小，本文中，筆者通過(guò)GA算法，以求能找到一個(gè)有效的方案，適合度函數(shù)定義為：F=20-ABS（id）-（A/B）*（C/D）（A，B，C，D）∈Ω其中，A，B，C，D分別代表掛輪齒數(shù)，共計(jì)4個(gè)掛輪，ABS（）表示絕對(duì)值函數(shù)，Ω是掛輪約束條件，需要A+B＞C=d+m，C+D＞B+d+m，d，m分別代表齒輪模、安裝軸徑。筆者在文中采用cenitor算法，對(duì)每個(gè)齒輪用一個(gè)5位二進(jìn)制碼進(jìn)行編碼，代表掛輪表的32個(gè)掛輪，共4個(gè)掛輪故基因碼長(zhǎng)20位，個(gè)體數(shù)為100，經(jīng)過(guò)驗(yàn)證后發(fā)現(xiàn)，如果id為整數(shù)，GA算法只需完成1000次雜交運(yùn)算就可以選出多個(gè)誤差為0的組合，它并非盲目地完成計(jì)算，搜索數(shù)遠(yuǎn)小于問(wèn)題解的數(shù)值。
5結(jié)語(yǔ)
假設(shè)所用的計(jì)算機(jī)傳輸介質(zhì)兩節(jié)點(diǎn)之間不多于一條直線的鏈接路，所用計(jì)算機(jī)網(wǎng)絡(luò)就可以運(yùn)用數(shù)學(xué)圖G=（N,L）來(lái)進(jìn)行描述。而且網(wǎng)絡(luò)的節(jié)點(diǎn)不會(huì)出現(xiàn)任何的故障，網(wǎng)絡(luò)鏈接介質(zhì)的可靠和自身的長(zhǎng)度沒(méi)有關(guān)系，網(wǎng)絡(luò)鏈接路與網(wǎng)絡(luò)只有兩種狀態(tài)存在：正常工作和故障。而當(dāng)所有的計(jì)算機(jī)網(wǎng)絡(luò)用戶都相互聯(lián)通時(shí)，則可組成G圖的一棵生成樹，并且全部的結(jié)點(diǎn)都處于正常。那么無(wú)論在什么時(shí)刻，可能只有L種的子集（L）是正常狀態(tài)，全部結(jié)點(diǎn)都是正常狀態(tài)。因此，整個(gè)計(jì)算機(jī)網(wǎng)絡(luò)的可靠度都可使用數(shù)學(xué)建模來(lái)進(jìn)行運(yùn)算。
2遺傳算法在計(jì)算機(jī)網(wǎng)絡(luò)可靠度優(yōu)化計(jì)算中的應(yīng)用研究
2.1遺傳運(yùn)算方法
在計(jì)算機(jī)網(wǎng)絡(luò)中遺傳運(yùn)算主要是以變異和交叉這兩種方式進(jìn)行。交叉主要是通過(guò)在網(wǎng)絡(luò)結(jié)點(diǎn)的范圍（[1，N]）之間的隨機(jī)數(shù)，以此作為基因交叉位置的設(shè)置且一次只可以操作一個(gè)結(jié)點(diǎn)。這樣能夠最大程度地確保網(wǎng)絡(luò)的連通性，但也有可能出現(xiàn)錯(cuò)的連通結(jié)構(gòu)，所以進(jìn)行調(diào)整操作；變異則是先確定基因的變異和數(shù)目，然后再根據(jù)范圍來(lái)選擇新的基因段替換舊基因段生成后代。一般變異率都在0.001到0.01內(nèi)，如是變異出現(xiàn)了錯(cuò)誤的網(wǎng)絡(luò)連通結(jié)構(gòu)基因，就必須進(jìn)行相應(yīng)的調(diào)整。
2.2算法的調(diào)整與仿真實(shí)例
影響抄板落料特性的主要因素有:抄板的幾何尺寸a和b、圓筒半徑R、圓筒的轉(zhuǎn)速n、抄板安裝角β以及折彎抄板間的夾角θ等［4，9］。在不同的參數(shù)a、β、θ下，抄板的安裝會(huì)出現(xiàn)如圖1所示的情況。圖1描述了不同參數(shù)組合下抄板的落料特性橫截面示意圖。其中，圖1(a)與圖1(b)、圖1(c)、圖1(d)的區(qū)別在于其安裝角為鈍角。當(dāng)安裝角不為鈍角且OB與OC的夾角σ不小于OD與OC夾角ψ時(shí)(即σ≥ψ)，會(huì)出現(xiàn)圖1(b)所示的安裝情況;當(dāng)σ＜ψ時(shí)，又會(huì)出現(xiàn)圖1(c)與圖1(d)所示的情況，而兩者區(qū)別在于，η+θ是否超過(guò)180°，若不超過(guò)，則為圖1(c)情況，反之則為圖1(d)情況。其中，點(diǎn)A為抄板上物料表面與筒壁的接觸點(diǎn)或?yàn)槲锪媳砻媾c抄板橫向長(zhǎng)度b邊的交點(diǎn);點(diǎn)B為抄板的頂點(diǎn);點(diǎn)C為抄板折彎點(diǎn);點(diǎn)D為抄板邊與筒壁的交點(diǎn);點(diǎn)E為OB連線與圓筒內(nèi)壁面的交點(diǎn);點(diǎn)F為OC連線與圓筒內(nèi)壁面的交點(diǎn)。
1．1動(dòng)力學(xué)休止角(γ)［4，10］抄板上的物料表面在初始狀態(tài)時(shí)保持穩(wěn)定，直到物料表面與水平面的夾角大于物料的休止角(最大穩(wěn)定角)時(shí)才發(fā)生落料情況。隨著轉(zhuǎn)筒的轉(zhuǎn)動(dòng)，抄板上物料的坡度會(huì)一直發(fā)生改變。當(dāng)物料的坡度大于最大穩(wěn)定角時(shí)，物料開始掉落。此時(shí)，由于物料的下落，物料表面重新達(dá)到最大穩(wěn)定角開始停止掉落。然而，抄板一直隨著轉(zhuǎn)筒轉(zhuǎn)動(dòng)，使得抄板內(nèi)物料的坡度一直發(fā)生改變，物料坡度又超過(guò)最大休止角。這個(gè)過(guò)程一直持續(xù)到抄板轉(zhuǎn)動(dòng)到一定位置(即抄板位置處于最大落料角δL時(shí))，此時(shí)抄板內(nèi)的物料落空。通常，在計(jì)算抄板持有量時(shí)，會(huì)采用動(dòng)力學(xué)休止角來(lái)作為物料發(fā)生掉落的依據(jù)，即抄板內(nèi)的物料坡度超過(guò)γ時(shí)，物料開始掉落。該角主要與抄板在滾筒中的位置δ、動(dòng)摩擦因數(shù)μ和弗勞德數(shù)Fr等有關(guān)。
1．2抄板持有量的計(jì)算
隨著抄板的轉(zhuǎn)動(dòng)，一般可以將落料過(guò)程劃分為3部分(R－1，R－2，R－3)，如圖1(a)所示。在轉(zhuǎn)動(dòng)過(guò)程中，當(dāng)抄板轉(zhuǎn)角δ超過(guò)動(dòng)力學(xué)休止角γ時(shí)，落料過(guò)程從R－1區(qū)域轉(zhuǎn)變到R－2區(qū)域，在這兩個(gè)區(qū)域內(nèi)，物料不僅受到抄板的作用還受到滾筒壁面的作用。當(dāng)物料表面上的A點(diǎn)與D點(diǎn)重合時(shí)，從R－2區(qū)域轉(zhuǎn)變到R－3區(qū)域，在該區(qū)域內(nèi)，物料僅受抄板作用［4］。然而，抄板情況為圖1(c)、圖1(d)時(shí)只會(huì)經(jīng)歷R－1、R－3區(qū)域。因?yàn)樵谶\(yùn)轉(zhuǎn)過(guò)程中，抄板上物料的A點(diǎn)與D點(diǎn)重合時(shí)抄板的轉(zhuǎn)角不會(huì)超過(guò)動(dòng)力學(xué)休止角γ，所以不會(huì)經(jīng)歷R－2區(qū)域;但是，當(dāng)物料的休止角足夠小時(shí)，由于物料表面只會(huì)與抄板接觸(即A點(diǎn)不會(huì)超出D點(diǎn))，圖1(c)、圖1(d)的抄板落料過(guò)程只會(huì)經(jīng)歷R－3區(qū)域。以下根據(jù)不同的區(qū)域建立了不同組合下抄板持料量的數(shù)學(xué)模型。
2研究結(jié)果與分析
2．1最大落料角結(jié)果分析
通過(guò)MatLab編制以上推導(dǎo)公式的計(jì)算程序，模擬計(jì)算了120種不同組合(β、θ、a不同)下抄板的最大落料角。其中，物料動(dòng)摩擦因數(shù)為0．53［8］，轉(zhuǎn)筒干燥機(jī)半徑為300mm，且其抄板安裝角為10°、30°、50°、70°、90°、110°，抄板間夾角為90°、110°、130°、150°，抄板縱向長(zhǎng)度a為30、45、60、75、90mm，橫向長(zhǎng)度b為60mm。并且，根據(jù)Kelly和O＇Donnell通過(guò)驗(yàn)證得出的公式(1)只適用于Fr小于0．4的情況［4］，此次模擬的轉(zhuǎn)筒干燥機(jī)角速度為0．84rad/s。表1給出了模擬結(jié)果中較為典型的數(shù)據(jù)。從模擬結(jié)果中可以得出，當(dāng)a、θ不變時(shí)，δL隨著安裝角β的增大而增大;當(dāng)a、β不變時(shí)，δL隨著θ的增大而減小。當(dāng)抄板情況如圖1(a)、(b)、(c)時(shí)，且β、θ不變時(shí)，抄板最大落料角隨著長(zhǎng)度a的增大而增大;而圖1(d)情況則反之，并且會(huì)出現(xiàn)最大落料角小于0°的情況，這是由于抄板無(wú)法抄起物料所導(dǎo)致的結(jié)果。另外，在圖1(d)情況下，抄板的最大落料角非常小，這會(huì)使得干燥器的效率很低。因此，在探討抄板優(yōu)化問(wèn)題上，不考慮圖1(d)這種情況下的抄板。
2．2優(yōu)化目標(biāo)與結(jié)果分析
水平直徑上均勻撒料雖好，但是物料應(yīng)與熱氣均勻接觸，如果在路徑長(zhǎng)的地方撒料多些，就可以使熱效率高些。又因?yàn)閳A筒中心熱氣量比邊緣多以及在圓筒下半部分超出干燥圓的區(qū)域存在物料，所以落料均勻度考慮為物料在干燥圓橫截面積上撒料均勻。評(píng)判干燥圓橫截面積上落料均勻的具體方法如下:把干燥圓橫截面積劃分20個(gè)等分，以水平直徑為X軸，鉛垂直徑為Y軸，圓心O為原點(diǎn)，采用定積分方法求解每個(gè)劃分點(diǎn)的x坐標(biāo)，每個(gè)劃分點(diǎn)的鉛垂線與干燥圓壁面(上半部分)有一個(gè)交點(diǎn)，連接圓心與每個(gè)點(diǎn)，可以得出每條連線與X軸的夾角δi(i=1～21，步長(zhǎng)為1，δ1為0°)，如圖2所示。在合理的設(shè)計(jì)下，不僅希望落料過(guò)程中抄板在干燥圓面積上撒料越均勻越好，δL也應(yīng)越接近180°越好。因此，優(yōu)化函數(shù)為最大落料角和抄板在干燥圓而積上落料的均方差。并且，根據(jù)國(guó)內(nèi)外實(shí)際情況，抄板的安裝角一般為90°并且抄板間夾角一般不為銳角，由于機(jī)構(gòu)的限制和不考慮圖1(d)的情況，在研究抄板優(yōu)化問(wèn)題時(shí)只探討安裝角在70°～110°、抄板夾角在90°～130°以及抄板縱向長(zhǎng)度在30～90mm之間的情況。其余參數(shù)同上。采用了線性加權(quán)和法來(lái)求解此多目標(biāo)優(yōu)化結(jié)果。其中，f1為1/δL的最優(yōu)化值，f2為q的最優(yōu)化值;均方差q=(1n∑ni=1(qi－qa)2)12，每相鄰角度落料面積差qi=A(δi)－A(δi+1)，qa為面積差的平均值。當(dāng)δL≤δi+1－δi2，n=i;反之則n=i+1，且δi+1=δL。s1、s2為權(quán)重系數(shù)，由于干燥器的效率主要與抄板的撒料均勻有關(guān)，但是如果落料角很小、撒料很均勻，干燥器效率也不高，綜合考慮下，取s1、s2分別為0．4、0．6。通過(guò)編寫MatLab程序，確定優(yōu)化函數(shù)，然后采用MatLab遺傳算法工具箱進(jìn)行計(jì)算，設(shè)置相關(guān)參數(shù):最大代數(shù)為51，種群規(guī)模為20，交叉概率為0．2，選擇概率為0．5。運(yùn)行算法并顯示結(jié)果，β、θ、a較優(yōu)結(jié)果分別為:1．844rad、1．571rad、51．609mm。
3結(jié)論
關(guān)鍵詞遺傳算法；TSP；交叉算子
1引言
遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。總的說(shuō)來(lái)，遺傳算法是按不依賴于問(wèn)題本身的方式去求解問(wèn)題。它的目標(biāo)是搜索這個(gè)多維、高度非線性空間以找到具有最優(yōu)適應(yīng)值(即最小費(fèi)用的)的點(diǎn)[1]。
基本遺傳算法是一個(gè)迭代過(guò)程，它模仿生物在自然環(huán)境中的遺傳和進(jìn)化機(jī)理，反復(fù)將選擇算子、交叉算子和變異算子作用于種群，最終可得到問(wèn)題的最優(yōu)解和近似最優(yōu)解。
2遺傳算法程序設(shè)計(jì)改進(jìn)比較
2.1基本遺傳算法對(duì)TSP問(wèn)題解的影響
本文研究的遺傳算法及改進(jìn)算法的實(shí)現(xiàn)是以C++語(yǔ)言為基礎(chǔ)，在Windows2000的版本上運(yùn)行，其實(shí)現(xiàn)程序是在MicrosoftVisualStadio6.0上編寫及運(yùn)行調(diào)試的。
1)遺傳算法的執(zhí)行代碼
m_Tsp.Initpop()；//種群的初始化
for(inti=0；i<m_Tsp.ReturnPop()；i++)
m_Tsp.calculatefitness(i)；//計(jì)算各個(gè)個(gè)體的適應(yīng)值
m_Tsp.statistics()；//統(tǒng)計(jì)最優(yōu)個(gè)體
while(entropy>decen||variance>decvar)//m_Tsp.m_gen<100)
{
//將新種群更迭為舊種群，并進(jìn)行遺傳操作
m_Tsp.alternate()；//將新種群付給舊種群
m_Tsp.generation()；//對(duì)舊種群進(jìn)行遺傳操作，產(chǎn)生新種群
m_Tsp.m_gen++；
m_Tsp.statistics()；//對(duì)新產(chǎn)生的種群進(jìn)行統(tǒng)計(jì)
}
2)簡(jiǎn)單的遺傳算法與分支定界法對(duì)TSP問(wèn)題求解結(jié)果的對(duì)比
遺傳算法在解決NPC問(wèn)題的領(lǐng)域內(nèi)具有尋找最優(yōu)解的能力。但隨著城市個(gè)數(shù)的增加，已沒(méi)有精確解，無(wú)法確定遺傳算法求解的精度有多高。一般情況下，當(dāng)?shù)鷶?shù)增大時(shí)，解的精度可能高，但是時(shí)間開銷也會(huì)增大。因此可以通過(guò)改進(jìn)遺傳算法來(lái)提高搜索能力，提高解的精度。
2.2初始化時(shí)的啟發(fā)信息對(duì)TSP問(wèn)題解的影響
1)初始化啟發(fā)信息
在上述實(shí)驗(yàn)算法的基礎(chǔ)上，對(duì)每一個(gè)初始化的個(gè)體的每五個(gè)相鄰城市用分支界定法尋找最優(yōu)子路徑，然后執(zhí)行遺傳算法。
2)遺傳算法與含有啟發(fā)信息的遺傳算法求解結(jié)果的對(duì)比
當(dāng)城市數(shù)增至20個(gè)時(shí)，用分支定界法已經(jīng)不可能在可以接受的時(shí)間內(nèi)得到精確的解了，只能通過(guò)近似算法獲得其可接受的解。試驗(yàn)設(shè)計(jì)中算法的截止條件：固定迭代1000代。表2中的平均最優(yōu)解為經(jīng)過(guò)多次試驗(yàn)(10次以上)得到的最優(yōu)解的平均值，最優(yōu)解的出現(xiàn)時(shí)間為最優(yōu)解出現(xiàn)的平均時(shí)間，交叉操作次數(shù)為最優(yōu)解出現(xiàn)時(shí)交叉次數(shù)的平均值。
表220個(gè)城市的TSP問(wèn)題求解結(jié)果數(shù)據(jù)
算法交叉操作
次數(shù)最優(yōu)解
出現(xiàn)時(shí)間平均
最優(yōu)解
簡(jiǎn)單遺傳算法80244.479.4s1641.8
含初始化啟發(fā)信息的GA79000.237.4s1398.9
從表2中可以看出，當(dāng)初始種群時(shí)引入啟發(fā)信息將提高遺傳算法的尋優(yōu)能力。同時(shí)縮短了遺傳算法的尋優(yōu)時(shí)間和問(wèn)題的求解精度。
2.3交叉算子對(duì)TSP問(wèn)題解的影響
1)循環(huán)貪心交叉算子的核心代碼
for(i=1；i<m_Chrom；i++)
{
flag=0；
city=m_newpop[first].chrom[i-1]；//確定當(dāng)前城市
j=0；
while(flag==0&&j<4)
{
sign=adjcity[city][j]；//adjcity數(shù)組的數(shù)據(jù)為當(dāng)前城市按順序排列的鄰接城市
flag=judge(first，i，sign)；//判斷此鄰接城市是否已經(jīng)存在待形成的個(gè)體中
j++；
}
if(flag==0)//如果所有鄰接城市皆在待擴(kuò)展的個(gè)體中
{
while(flag==0)
{
sign=(int)rand()/(RAND_MAX/(m_Chrom-1))；//隨機(jī)選擇一城市
flag=judge(first，i，sign)；
}
}
if(flag==1)
m_newpop[first].chrom[i]=sign；
}
2)問(wèn)題描述與結(jié)果比較
下面筆者用經(jīng)典的測(cè)試遺傳算法效率的OliverTSP問(wèn)題來(lái)測(cè)試循環(huán)貪心交叉算子的解的精度和解效率。OliverTSP問(wèn)題的30個(gè)城市位置坐標(biāo)如表3所示[2]。
從表4、圖1中可以看到，貪心交叉算子大大提高了遺傳算法的尋優(yōu)能力，同時(shí)也降低了交叉操作次數(shù)。在多次試驗(yàn)中，貪心交叉算子找到的最優(yōu)解與目前記載的最佳數(shù)據(jù)的誤差率為2.7%。而部分匹配交叉算子找到的最優(yōu)解與目前記載的最佳數(shù)據(jù)的誤差率高達(dá)7%。從而可以得到交叉算子對(duì)于遺傳算法
2.4并行遺傳算法消息傳遞實(shí)現(xiàn)的核心代碼
1)主程序代碼
//接收各個(gè)從程序的最優(yōu)個(gè)體
for(i=0；i<slave；i++)
{
MPI_Recv(Rchrom[i]，chrom，MPI_UNSIGNED，MPI_ANY_SOURCE，gen，MPI_COMM_WORLD，&status)；
}
//計(jì)算接收各個(gè)從程序的最優(yōu)個(gè)體的回路距離
for(i=0；i<slave；i++)
{
fitness[i]=0.0；
for(intj=0；j<chrom-1；j++)
fitness[i]=fitness[i]+distance[Rchrom[i][j]][Rchrom[i][j+1]]；
fitness[i]=fitness[i]+distance[Rchrom[i][0]][Rchrom[i][chrom-1]]；
}
//找到最優(yōu)的個(gè)體并把它記錄到文件里
for(i=0；i<slave；i++)
{
if(1/fitness[i]>min)
{
sign=i；
min=1/fitness[i]；
}
}
fwrite(&gen，sizeof(int)，1，out)；
for(i=0；i<chrom；i++)
fwrite(&Rchrom[sign][i]，sizeof(unsigned)，1，out)；
fwrite(&fitness[sign]，sizeof(double)，1，out)；
//每九代向從程序發(fā)送一個(gè)最優(yōu)個(gè)體
if(gen%9==0)
MPI_Bcast(Rchrom[sign]，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；
2)從程序代碼
//將上一代的最優(yōu)個(gè)體傳回主程序
MPI_Send(Rchrom1，chrom，MPI_UNSIGNED，0，gen，MPI_COMM_WORLD)；
//每九代接收一個(gè)最優(yōu)個(gè)體并將其加入種群中替換掉最差個(gè)體
if(gen%9==0)
{
PI_Bcast(Rchrom2，chrom，MPI_UNSIGNED，0，MPI_COMM_WORLD)；
Tsp.IndiAlternate(Rchrom2)；
}
//進(jìn)行下一代的計(jì)算
Tsp.Aternate()；
Tsp.Generation()；
Tsp.Statistics()；
3)并行遺傳算法的性能
筆者在MPI并行環(huán)境下，用C＋＋語(yǔ)言實(shí)現(xiàn)了一個(gè)解決TSP問(wèn)題的粗粒度模型的并行遺傳算法。該程序采用的是主從式的MPI程序設(shè)計(jì)，通過(guò)從硬盤的文件中讀取數(shù)據(jù)來(lái)設(shè)置染色體長(zhǎng)度、種群的規(guī)模、交叉概率和變異概率等參數(shù)。試驗(yàn)環(huán)境為曙光TC1700機(jī)，測(cè)試的對(duì)象是OliverTSP問(wèn)題的30個(gè)城市的TSP問(wèn)題。
正如在測(cè)試串行遺傳算法所提到的數(shù)據(jù)結(jié)果，并行遺傳算法也沒(méi)有達(dá)到目前所記錄的最好解，但是它提高了算法的收斂性，并行遺傳算法的收斂趨勢(shì)如圖2所示[4]。
圖2遺傳算法的收斂過(guò)程
3結(jié)束語(yǔ)
本文通過(guò)對(duì)基本遺傳算法的不斷改進(jìn)，證明了添加啟發(fā)信息、改進(jìn)遺傳算子和利用遺傳算法固有的并行性都可以提高遺傳算法的收斂性，其中對(duì)遺傳算法交叉算子的改進(jìn)可以大大提高遺傳算法的尋優(yōu)能力。
參考文獻(xiàn)
[1]劉勇、康立山，陳毓屏著．非數(shù)值并行算法－遺傳算法．北京：科學(xué)出版社1995.1
[2]IMOliverDJSmithandJRCHolland，Astudyofpermutationcrossoveroperatorsonthetravelingsalesman[C]//ProblemofthesecondInternationalConferenceonGeneticAlgorithmsandTheirApplication，Erlbaum1897：224-230
1．1基因編碼設(shè)計(jì)
編碼就是將遺傳算法中處理不了的空間參數(shù)轉(zhuǎn)換成遺傳空間的由基因組成的染色體或個(gè)體的過(guò)程．其中基因在一定意義上包含了它所代表的問(wèn)題的解．基因的編碼方式有很多，這也取決于要解決的問(wèn)題本身．常見(jiàn)的編碼方式有：二進(jìn)制編碼，基因用0或1表示，通常用于解決01背包問(wèn)題，如基因A：00100011010（代表一個(gè)個(gè)體的染色體）；互換編碼，主要用于解決排序問(wèn)題，如調(diào)度問(wèn)題和旅行商問(wèn)題，用一串基因編碼來(lái)表示遍歷城市順序，如234517986，表示在9個(gè)城市中先經(jīng)過(guò)城市2，再經(jīng)過(guò)城市3，依此類推；樹形編碼，用于遺傳規(guī)劃的演化編程或表示，其編碼的方法就是樹形結(jié)構(gòu)中的一些函數(shù)，本文采用的是樹形編碼．
1．2交叉算子設(shè)計(jì)
交叉運(yùn)算的含義是參照某種方式和交叉概率，將兩組相互配對(duì)的個(gè)體互換部分基因，生成新個(gè)體的過(guò)程．交叉運(yùn)算在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法．交叉操作流程如圖1所示．交叉操作首先判定要交叉的基因是否相同，如果相同進(jìn)行子基因組的交叉，然后再判定交叉是否完成，沒(méi)完成就繼續(xù)，完成就退出；如果交叉的基因不相同，就要選擇是否依據(jù)概率進(jìn)行基因交換，選擇交換就交換其所有的次級(jí)基因結(jié)構(gòu)，然后再判定交叉是否完成，選擇不交換就直接判定交叉是否完成．
1．3變異算子設(shè)計(jì)
變異操作從第i個(gè)子結(jié)構(gòu)開始．依據(jù)變異概率進(jìn)行第i個(gè)基因的變異，如果變異完成，就初始化其所有次級(jí)基因結(jié)構(gòu)，如果變異沒(méi)有完成，就進(jìn)行子基因組的變異操作．重復(fù)操作上面的步驟，直至變異操作結(jié)束．
2遺傳算法在機(jī)械產(chǎn)品設(shè)計(jì)中的應(yīng)用
機(jī)械產(chǎn)品設(shè)計(jì)是在研究人機(jī)協(xié)同方案設(shè)計(jì)的工作機(jī)制上，建立產(chǎn)品的人機(jī)分析、人機(jī)約束模型和協(xié)同方案設(shè)計(jì)求解模型，確立人機(jī)協(xié)同系統(tǒng)的同步與異步交互、任務(wù)協(xié)同、數(shù)據(jù)共享、數(shù)據(jù)可視化、易用性等工作機(jī)制．
2．1基于遺傳算法的數(shù)控車床設(shè)計(jì)
2．1．1數(shù)控車床總體設(shè)計(jì)任務(wù)分解
首先確定數(shù)控車床總體設(shè)計(jì)任務(wù)，然后根據(jù)多層次結(jié)構(gòu)知識(shí)進(jìn)化算法設(shè)計(jì)要求，將數(shù)控車床的總體設(shè)計(jì)任務(wù)分解。
2．1．2數(shù)控車床設(shè)計(jì)的基因編碼表示
依據(jù)數(shù)控車床設(shè)計(jì)任務(wù)分解的結(jié)果，可以得出數(shù)控車床設(shè)計(jì)的基因編碼圖．?dāng)?shù)控車床設(shè)計(jì)任務(wù)按多層次結(jié)構(gòu)劃分為床身、滑臺(tái)、刀架、尾臺(tái)、冷卻、控制器、電機(jī)．每個(gè)結(jié)構(gòu)都包含多個(gè)選擇方案．不同選擇方案的有些結(jié)構(gòu)含有子結(jié)構(gòu)，并且這些子結(jié)構(gòu)還可以進(jìn)一步分解出多種選擇方案．通過(guò)數(shù)控車床設(shè)計(jì)的基因編碼，可看到數(shù)控車床設(shè)計(jì)任務(wù)每一層次的關(guān)系，包括各層次之間的約束關(guān)系．
2．2基于遺傳算法的機(jī)械產(chǎn)品設(shè)計(jì)系統(tǒng)應(yīng)用
