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