前言：我們精心挑選了數篇優質遺傳算法論文文章，供您閱讀參考。期待這些文章能為您帶來啟發，助您在寫作的道路上更上一層樓。

第1篇

論文摘要：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問題的限定條件下進行繁衍,然后保留適應度高的染色體種群,達到優化的目的。單親演化算法的基因重組操作包括基因換位、基因段錯位和基因段倒轉三種操作來實現。基因換位操作是將親代的染色體基因進行對換后,形成子代,其換位又分為單基因換位和基因段換位兩種方式。基因段錯位操作是隨機確定基因段,也隨機選定錯位位置,整段錯移。基因段倒轉操作則是隨機地確定倒轉基因段的起止位置,倒轉操作是對該段內基因按中垂線作鏡面反射,若段內基因數為奇數時,則中位基因不變。單親演化時可以是單個操作用于單個父代,也可以是幾種操作同時采用。為了編程方便,文中采用基因段倒轉操作。

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結束語

第2篇

遺傳算法就是一種以事物的自然屬性和遺傳屬性為基礎，通過計算機對生物進化規律進行模擬以尋優的一種算法，將尋優的范圍與遺傳空間相對應，把每一種可能的值通過二進制碼進行編碼，如同染色體一樣，形成的字符串相當于基因，然后按預期的結果對每一組編碼進行評價，選出最合適的一個值。算法一開始是提出一些問題的解，然后根據要求對這些解進行選擇，重新拆解組合，去掉不合適的，留下最優值，由此形成的便是新值，如此往復，繼承與改良，這便是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算法結果的權威性和有效性，太小則不能提供足夠的采樣點，結果的多樣性將會打折扣，太大則會增加計算量，拖長搜索時間，通暢將規模控制在40～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結語

第3篇

假設所用的計算機傳輸介質兩節點之間不多于一條直線的鏈接路，所用計算機網絡就可以運用數學圖G=（N,L）來進行描述。而且網絡的節點不會出現任何的故障，網絡鏈接介質的可靠和自身的長度沒有關系，網絡鏈接路與網絡只有兩種狀態存在：正常工作和故障。而當所有的計算機網絡用戶都相互聯通時，則可組成G圖的一棵生成樹，并且全部的結點都處于正常。那么無論在什么時刻，可能只有L種的子集（L）是正常狀態，全部結點都是正常狀態。因此，整個計算機網絡的可靠度都可使用數學建模來進行運算。

2遺傳算法在計算機網絡可靠度優化計算中的應用研究

2.1遺傳運算方法

在計算機網絡中遺傳運算主要是以變異和交叉這兩種方式進行。交叉主要是通過在網絡結點的范圍（[1，N]）之間的隨機數，以此作為基因交叉位置的設置且一次只可以操作一個結點。這樣能夠最大程度地確保網絡的連通性，但也有可能出現錯的連通結構，所以進行調整操作；變異則是先確定基因的變異和數目，然后再根據范圍來選擇新的基因段替換舊基因段生成后代。一般變異率都在0.001到0.01內，如是變異出現了錯誤的網絡連通結構基因，就必須進行相應的調整。

2.2算法的調整與仿真實例