利用遺傳算法求解圓排列問題①

徐小平,朱秋秋,邰會強(西安理工大學 理學院,西安 70048)(西安理工大學 機械與精密儀器工程學院,西安 70048)

?

利用遺傳算法求解圓排列問題①

徐小平1,朱秋秋1,邰會強2
1(西安理工大學 理學院,西安 710048)
2(西安理工大學 機械與精密儀器工程學院,西安 710048)

摘 要:圓排列問題是一個典型的組合優化問題,也是一個NP完全問題.遺傳算法是根據自然界生物學進化而發展起來的一種進化方法,其具有簡單、易行、抽象性與魯棒性特征,已成功地解決了許多工程優化問題.給出基于改進遺傳算法給出求解圓排列問題的新方法.首先,分析了圓排列問題與旅行商問題之間的關系.然后,將圓排列問題轉化為旅行商問題.接著,利用所給改進遺傳算法進行了求解.最后,在仿真實驗中,與已有算法進行了比較,結果表明,所給算法是一種能夠簡單有效地求解圓排列問題的新方法.

關鍵詞:圓排列問題; 組合優化; 遺傳算法; 進化算法

圓排列問題是一個典型的組合優化問題,也是NP-hard問題[1].它不僅具有組合優化問題的典型特征,并且其描述簡單.因此,許多學者將圓排列問題的算例作為算法研究的公共實例[2,3].目前,圓排列研究的最多的問題是如何求解最小長度,即就是說,要求從n個圓的所有排列中找出有最小長度的圓排列.它有很強的應用背景,比如包裝問題[4]、農機作業優化[5]、物流配送問題[6]等等問題,都可以被轉化為圓排列問題.因此,對圓排列問題的研究具有重要的現實意義.

遺傳算法(Genetic Algorithm,GA)是一種模仿生物自然進化過程的、自適應啟發式的全局優化算法[7].它不存在求導和函數連續性的限定、具有內在的隱并行性和優秀的全局尋優能力,能自動獲取和指導優化的搜索空間,自適應地調整搜索方向,且求解問題時僅需要很少的輔助信息,容易與其他領域的知識相結合,所以在自動組卷問題[8]、車輛路徑問題[9]、儲層識別技術[10]、本體映射技術[11]等領域已得到了廣泛的應用.當然,它也為解決圓排列問題提供了一種有效工具.

本文嘗試利用GA對圓排列問題進行求解.首先,敘述了圓排列問題和旅行商問題之間的關系.接著,將圓排列問題轉化為旅行商問題.然后,利用一種改進遺傳算法給出了圓排列問題的有效求解.在選擇、交叉和變異之后,引進連續多次的進化逆轉操作,有效的加快了算法的收斂速度.最后,通過仿真實驗結果說明該方法是有效的.

1　問題的描述

實際工程中經常涉及到把一個矩形鋼板切割成半徑不等的圓,盡可能節省材料的圓排列問題.即就是說,給定n個大小不等的圓c1,c2,…,cn,現要將這n個圓排進到一個矩形框中,并且要求與矩形的底邊相切.本文首先將圓排列問題轉化為旅行商問題,然后用改進GA對其進行求解.

已知圓ci的半徑ri(i=1,2,…,n),假如排列方式為i1,i2,…,in,則長度為

旅行商問題具體是指有n個城市,城市i,j之間的距離為dij,一個旅行商從城市1出發到其他每個城市去一次且只去一次,最后回到城市1,旅行商問題要求從2～n個城市的所有排列中找出總路線最短的路線.

假設把1～n個圓分別放置在1～n個城市中,城市i和城市j之間的距離dij(i= 1,2,L ,n;j=1,2,…,n)為.再增加一個城市0,它與城市j的距離d0j(j=1,2,…,n)為d0j=rj.因此,圓排列問題與旅行商問題等價[12].也就是說,一個旅行商從城市0出發到其他每個城市去一次且只去一次,最后回到城市0,而旅行商問題要求從1～n個城市的所有排列中找出總路線最短的路線.所以,求解圓排列問題就可以變為求解旅行商問題.

2　改進的隨機松弛法求解TSP

GA由美國Michigan大學J.Holland教授于1975年提出[14],它通過模擬生物進化過程搜索最優解,且與傳統優化算法相比,其具有高魯棒性、全局搜索性、內在并行性等優點[15].因此,其受到人們的普遍關注,且已被廣泛應用到各個領域.

GA的基本步驟如下:

步驟1.隨機產生初始種群,并設置好初始的參數.

步驟2.進行迭代.

步驟3.執行選擇算子,選擇優良的個體,并淘汰適應度低的個體.

步驟4.執行交叉算子.

步驟 5.執行變異算子.

步驟 6.計算每個個體的適應度.

步驟 7.如果邏輯條件滿足,結束迭代.否則,轉到步驟2.

3　改進遺傳算法求解圓排列問題

本文針對基本遺傳算法易陷入局部極小值,較難快速穩定地找到最優值的缺點,在選擇、交叉和變異之后,引進連續多次的進化逆轉操作對遺傳算法進行改進,使算法的每一代都能從父代繼承更多的基因,從而提高算法的局部搜索能力.改進后的算法可以跳出局部極小值,快速穩定地尋找到最優值.這樣就能夠有效的加快算法的收斂速度,同時使得尋優結果會更加令人滿意.以下為利用改進GA求解圓排列問題的實現步驟.

Step 1.編碼: 采用整數排列編碼方法.對于n個圓的排列問題,染色體分為n段,其中每一段為對應圓的編號,比如,對10個圓的排列問題{1,2,3,4,5,6,7,8,9,10},則|1|10|2|4|5|6|8|7|9|3就是一個合法的染色體.

Step 2.種群初始化: 在完成染色體編碼以后,必須產生一個初始種群作為初始解,所以首先需要決定初始化種群的數目.初始化種群的數目一般根據經驗得到,且一般情況下種群的數量視圓規模的大小而決定.

Step 3.確定適應度函數: 假設k1|k2|…|ki|…|kn|為一個采用整數編碼的染色體,為圓ki到圓kj的距離,則該個體的適應度函數為

即就是說,適應度函數為恰好走遍n個圓的距離的倒數.優化的目標就是選擇適應度函數值盡可能大的染色體,適應度函數值越大的染色體越優質,反之越惡劣.

Step 4.選擇操作: 從舊群體中以一定概率選擇個體到新群體中,個體被選中的概率跟適應度函數值有關,個體適應度值越大,被選中的概率越大.

Step 5.交叉操作: 采用部分映射雜交,確定交叉操作的父代,將父代樣本兩兩分組,每組重復以下過程(假定圓的個數為10).

Substep 1.產生兩個[1,10]區間內的隨機整數r1和r2,確定兩個位置,對兩位置的中間數據進行交叉,比如,當r1=4,r2= 7時

對其交叉后為

Substep 2.交叉后,同一個個體中有重復的圓的編號,不重復的數字保留,有沖突的數字(帶*位置)采用部分映射的方法消除沖突,即就是,利用中間段的對應關系進行映射,其結果為

Step 6.變異操作: 變異策略采取隨機選取兩個點,將其對換位置.產生兩個[1,10]范圍內的隨機整數r1和r2,確定兩個位置,將其對換位置,比如,當r1=4,r2= 7時,

對其變異后為

Step 7.進化逆轉操作: 為改善遺傳算法的局部搜索能力,在選擇、交叉和變異之后引進連續多次的進化逆轉操作.這里的“進化”是指逆轉算子的單方面性,即就是說,只有經過逆轉后,適應度值有所提高的才接受下來,否則逆轉無效.即產生兩個[1,10]區間內的隨機整數r1和r2,確定兩個位置,將其對換位置,比如,當r1=4,r2= 7時

對其進化逆轉后為

對每個個體進行交叉變異,然后帶入適應度函數進行評估,選擇出適應度值大的個體進行下一代的交叉和變異以及進化逆轉操作.

Step 8.判斷操作: 如果滿足設定的最大遺傳代數的話,則終止程序; 否則,轉到Step 3.

5　仿真實驗

本文提出的進化逆轉操作,對于圓排列問題,就調整前后引起的圓排列圈的長度變化而言,用于最細微的調整,因而局部優化的精度較高.為了說明本文所給方法的合理性和可行性,這里考慮了對當圓排列問題n取30,50,100,ri= i( i= 1,2,…,n).利用文中所給改進GA算法對該問題分別進行了求解,并且算法參數的設置均相同,具體如下表1所示.

表1　設置控制參數

當n取30時,首先,隨機選擇種群中的一個初始隨機路線為 19→21→24→10→18→16→15→22→29 →3→6→2→8→30→20→17→27→25→12→13→5→2 8→9→7→11→14→1→26→4→23.

然后,經計算得到的初始隨機路線的總距離為836.8342.最后,利用所給方法進行一次求解時的相應隨機路線,優化過程和最優路線分別如圖1,圖2和圖3所示.

這樣,得到的最優路線為18→12→20→10→22→8→24→6→26→4→28→2→30 →1→29→3→27→5→25→7→23→9→21→11→19→1 3→17→15→16→14 .

此時,最優路線的總距離為750.9867,算法的運行時間為0.25s.

圖1　隨機路線

圖2　優化過程

圖3　最優路線

當n取50時,首先,隨機選擇種群中的一個初始隨機路線為27→16→45→31→30→47→22→8→48→

15→38→44→35→28→33→26→42→24→20→36→2 →50→14→19→21→37→1→18→6→43→46→34→3 2→3→40→10→9→17→5→49→29→41→25→12→1 1→7→39→13→23→4.

然后,經計算得到的初始隨機路線的總距離為2253.9.最后,利用所給方法進行一次求解時的相應隨機路線,優化過程和最優路線如圖4,圖5和圖6.

圖4　隨機路線

圖5　優化過程

圖6　最優路線

這樣,得到的最優路線為30→20→32→18 →34→16→36→14→38→12→40→10→42→8→44→6 →46→4→48→2→50→1→49→3→47→5→45→7→43 →9→41→11→39→13→37→15→35→17→33→19→3 1→21→29→23→27→25→26→24→28→22.此時,最優路線的總距離2038.1,算法的運行時間0.48s.

當n取100時,首先,隨機選擇種群中的一個初始隨機路線為37→65→35→67→50→51→49→53→47 →55→45→57→43→59→41→61→39→63→33→69→31→71→29→73→27→75→25→77→23→79→21→81 →19→83→17→85→15→87→13→89→11→91→9→9 3→7→95→5→97→3→99→1→100→2→98→4→96→6→94→8→92→10→90→12→88→14→86→16→84→18→82→20→80→22→78→24→76→26→74→28→72 →30→70→32→68→34→66→36→64→38→62→40→60→42→58→44→56→46→54→48→52.

然后,經計算得到的初始隨機路線的總距離為8007.5.最后,利用所給方法進行一次求解時的相應隨機路線,優化過程和最優路線分別如圖7,圖8和圖9所示.

這樣,得到的最優路線為50→51→49→53→47→55→45→57→43→61→37→63→39→62→38→65→35 →67→33→69→31→71→29→73→27→75→25→77→23→79→21→81→19→83→17→85→15→87→13→89 →11→91→9→93→7→95→5→97→3→99→1→100→2→98→4→96→6→94→8→92→10→90→12→88→14 →86→16→84→18→82→20→80→22→78→24→76→26→74→28→72→30→70→32→68→34→66→36→64 →41→60→40→59→42→58→44→56→46→54→48→52.此時,最優路線的總距離為8004.4,算法的運行時間為0.89s.

圖7　隨機路線

圖8　優化過程

圖9　最優路線

為了進一步說明本文方法(即利用改進GA)的有效性,對上述n取30,50和100時,利用本文方法分別進行多次求解后,將其結果的平均值、最好解、最差解和平均所用時間均羅列在表2中.并且分別利用基本GA和文獻[12]中的蟻群模擬退火算法分別對n取30,50和100進行多次求解,其相應結果也羅列在表2 中.

表2　實驗結果

30 　770.43 　758.73 　777.79 　0.28 50 　2045.6 　2038.1 　2059.91 　0.55基本GA 100 　8032.6 　8024.8 　8076.0 　1.01 30 　765.78 　750.75 　770.459 　0.67 50 　2041.5 　2037.5 　2045.5 　0.98文獻[12] 100 　8023.1 　8019.8 　8049.7 　1.05 30 　787.469 784.417 792.951 　0.0546 50 　2224.82 2218.76 2238.61 　0.2815文獻[13] 100 8843.46 8821.88 　8867.7 　2.2734

從以上結果可以看出,利用文中所提方法得到的結果優,用時較短,而且隨著n的增大,優勢更為明顯.從而可以看出文中所給方法是合理有效的.

6　結束語

本文給出了基于一種改進遺傳算法求解圓排列問題的新方法.首先,將圓排列問題與旅行商問題進行了對比分析.然后,將圓排列問題轉化為旅行商問題,從而得出一個相應的組合優化問題.接著,利用具有良好收斂性的改進遺傳算法給出了該問題的求解.最后,利用仿真結果說明了所給方法是可行的.

參考文獻

1Applegate DL,Bixby RE,Chvatal V,et al.The Traveling Salesman Problem: A Computational Study.Princeton: Princeton University Press,2011.

2麻存瑞,馬昌喜.不確定旅行商問題的魯棒模型與算法.計算機應用,2014,34(7):2090–2092.

3王慶,劉學鵬.基于流水算法的旅行商問題求解.預測,2014,33(1):65–69.

4楊金勇,宋海洲.圓排列包裝問題最優解解析.華僑大學學報,2013,34(2):221–224.

5楊巍,劉占良.農機作業路徑優化的研究—基于旅行商問題新算法.農機化研究,2014,(6):55–57.

6樂國友.基于節約算法的旅行商問題配送線路優化.物流技術,2013,33(2):241–244.

7Holland JH.Adaptation in Natural and Artificial Systems.Ann Arbor: University of Michigan Press,1975.

8劉召華,李建良.自動組卷中簡單遺傳算法的應用.卷宗,2014,(3):186.

9劉俐.基于遺傳算法的車輛路徑問題研究.中國電子商務,2014,(4):81.

10李鐵軍,薛玲,郭大立,杜國鋒,許江文.基于粗糙集與遺傳算法的儲層識別技術.斷塊油氣田,2014,21(2):196–200.

11薛興思.基于遺傳算法的本體映射技術.福建工程學院學報,2014,12(1):74–77.

12高尚,楊靜宇,吳小俊,等.圓排列問題的蟻群模擬退火算法.系統工程理論與實踐,2004,8 (8):102–106.

13章義剛,王會穎.改進蟻群算法求解圓排列問題.機電工程,2008,25(5):92–95.

14劉曉霞,竇明鑫.一種改進的自適應遺傳算法.合作經濟與科技,2012,(5):127–128.

15張愉,婁卉芳,文良浩,等.一種改進的遺傳算法交叉策略.湖南科技大學學報(自然科學版),2012,27(1):94–97.

Solving Circle Permutation Problem Using Improved Genetic Algorithm

XU Xiao-Ping1,ZHU Qiu-Qiu1,TAI Hui-Qiang2
1(School of Sciences,Xi’an University of Technology,Xi’an 710048,China)
2(School of Mechanical and Precision Instrument Engineering,Xi’an University of Technology,Xi’an 710048,China)

Abstract:Circle permutation problem is a typical combinatorial optimization problem; moreover,it is a NP complete problem.Genetic algorithm is a kind of evolutionary method based on natural biological evolution.It is simple and easy,and has characteristics of abstraction and robustness.which has been successfully applied to many engineering optimization problems.A new method based on improved genetic algorithm is presented for solving circle permutation problem.Firstly,the relationship between circular permutation problem and the traveling salesman problem is analyzed,and then circular permutation problem is translated into traveling salesman problem.Next,it is solved by the improved genetic algorithm.Finally,in the simulation experiments,compared with the existing algorithm,the proposed method is a simple and effective algorithm for solving circle permutation problem.

Key words:circle permutation problem; combinatorial optimization; genetic algorithm; evolutionary algorithm

基金項目:①國家自然科學基金(61273127);陜西省自然科學基礎研究計劃(2014JM8325);陜西省教育廳科研計劃(14JK1538)

收稿時間:2015-07-06;收到修改稿時間:2015-09-28