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

?

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

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

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

關(guān)鍵詞:圓排列問題; 組合優(yōu)化; 遺傳算法; 進化算法

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

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

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

1　問題的描述

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

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

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

假設(shè)把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出發(fā)到其他每個城市去一次且只去一次,最后回到城市0,而旅行商問題要求從1～n個城市的所有排列中找出總路線最短的路線.所以,求解圓排列問題就可以變?yōu)榍蠼饴眯猩虇栴}.

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

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

GA的基本步驟如下:

步驟1.隨機產(chǎn)生初始種群,并設(shè)置好初始的參數(shù).

步驟2.進行迭代.

步驟3.執(zhí)行選擇算子,選擇優(yōu)良的個體,并淘汰適應(yīng)度低的個體.

步驟4.執(zhí)行交叉算子.

步驟 5.執(zhí)行變異算子.

步驟 6.計算每個個體的適應(yīng)度.

步驟 7.如果邏輯條件滿足,結(jié)束迭代.否則,轉(zhuǎn)到步驟2.

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

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

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

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

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

即就是說,適應(yīng)度函數(shù)為恰好走遍n個圓的距離的倒數(shù).優(yōu)化的目標就是選擇適應(yīng)度函數(shù)值盡可能大的染色體,適應(yīng)度函數(shù)值越大的染色體越優(yōu)質(zhì),反之越惡劣.

Step 4.選擇操作: 從舊群體中以一定概率選擇個體到新群體中,個體被選中的概率跟適應(yīng)度函數(shù)值有關(guān),個體適應(yīng)度值越大,被選中的概率越大.

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

Substep 1.產(chǎn)生兩個[1,10]區(qū)間內(nèi)的隨機整數(shù)r1和r2,確定兩個位置,對兩位置的中間數(shù)據(jù)進行交叉,比如,當r1=4,r2= 7時

對其交叉后為

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

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

對其變異后為

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

對其進化逆轉(zhuǎn)后為

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

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

5　仿真實驗

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

表1　設(shè)置控制參數(shù)

當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.

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

這樣,得到的最優(yōu)路線為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 .

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

圖1　隨機路線

圖2　優(yōu)化過程

圖3　最優(yōu)路線

當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.

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

圖4　隨機路線

圖5　優(yōu)化過程

圖6　最優(yōu)路線

這樣,得到的最優(yōu)路線為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.此時,最優(yōu)路線的總距離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.

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

這樣,得到的最優(yōu)路線為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.此時,最優(yōu)路線的總距離為8004.4,算法的運行時間為0.89s.

圖7　隨機路線

圖8　優(yōu)化過程

圖9　最優(yōu)路線

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

表2　實驗結(jié)果

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

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

6　結(jié)束語

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15張愉,婁卉芳,文良浩,等.一種改進的遺傳算法交叉策略.湖南科技大學(xué)學(xué)報(自然科學(xué)版),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

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

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