改進(jìn)遺傳算法解決TSP問題

陳林 潘大志

摘要：針對基本遺傳算法收斂速度慢，易早熟等問題，提出一種改進(jìn)的遺傳算法。新算法利用貪婪思想產(chǎn)生初始種群來加快尋優(yōu)速度，用貪婪思想來引導(dǎo)交叉操作，在交叉操作之前，把當(dāng)前較差的一半種群替換成隨機(jī)種群，最后用改進(jìn)的變異算子和進(jìn)化逆轉(zhuǎn)操作進(jìn)行尋優(yōu)，利用新的遺傳算法求解基本的旅行商問題。仿真結(jié)果表明，改進(jìn)的遺傳算法具有全局搜索能力強(qiáng)、收斂速度快的特點(diǎn)，優(yōu)化質(zhì)量和尋優(yōu)效率都較好。

關(guān)鍵詞：遺傳算法；貪婪思想；進(jìn)化逆轉(zhuǎn)；旅行商問題

中圖分類號： TP18 文獻(xiàn)標(biāo)識碼： A

0引言

遺傳算法（GA）是一種進(jìn)化算法，其基本原理是仿效生物界中的“物競天擇、適者生存”的演化法則。最早是由美國密歇根大學(xué)Holland教授提出，在20世紀(jì)80年代左右得到了進(jìn)一步發(fā)展。遺傳算法是把問題參數(shù)編碼為染色體，再利用迭代的方式進(jìn)行選擇、交叉以及變異等運(yùn)算來交換種群中染色體的信息，最終生成符合優(yōu)化目標(biāo)的染色體。目前遺傳算法主要多用于優(yōu)化問題[1]、圖像處理[2]、通訊工程[3]等領(lǐng)域。

旅行商問題（TSP）是典型的組合優(yōu)化問題，求解TSP問題傳統(tǒng)的算法有：窮舉法、分支限界法、動(dòng)態(tài)規(guī)劃法[4-5]等。高海昌等[6] 對蟻群算法、遺傳算法、模擬退火算法、禁忌搜索、神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法、免疫算法等進(jìn)行了論述。隨著研究的深入，許多改進(jìn)的算法不斷涌現(xiàn)，李瑋[7]采用矩陣編碼、交叉、變異的遺傳算法來解決TSP問題，雷玉梅[8]提出了一種分而治之的遺傳算法思想，姚明海[9]采用遺傳算法與其他智能算法結(jié)合的思想來解決問題。遺傳算法因其高效的搜索能力成為了解決TSP問題的有效方法之一。雖然遺傳算法能夠較為成功地求解TSP問題，但也存在搜索較慢的問題，特別是遺傳算法在解決TSP問題時(shí)容易出現(xiàn)早熟的問題。因此本文在交叉操作之前，將一半的當(dāng)前種群替換成隨機(jī)種群來防止早熟，再融合貪婪思想產(chǎn)生的初始群體[10]和貪婪思想引導(dǎo)的交叉算子[11]來加快收斂速度，用改進(jìn)的變異算子[12]進(jìn)行操作，由此而得到最優(yōu)解。

5 結(jié)束語

文章在基本的遺傳算法基礎(chǔ)上提出一定改進(jìn)，引用貪婪思想產(chǎn)生質(zhì)量相對較好的初始種群，同時(shí)又在貪婪思想引導(dǎo)的交叉操作操作之前，把當(dāng)前較差的一半種群替換成隨機(jī)種群，二者結(jié)合來提升收斂速度又防止了陷入局部最優(yōu)。實(shí)驗(yàn)證明，本文研發(fā)的改進(jìn)遺傳算法較好地解決了TSP問題中收斂速度和早熟的問題，且具有較強(qiáng)的魯棒性，通用于類似的組合優(yōu)化問題。

參考文獻(xiàn)：

[1]袁滿，劉耀林.基于多智能體遺傳算法的土地利用優(yōu)化配置[J].農(nóng)業(yè)工程學(xué)報(bào)， 2014，30（1）： 191-199.

[2]門慧勇.基于遺傳算法的圖像分割優(yōu)化研究[D].長春：東北師范大學(xué)，2012.

[3]陳俠.基于改進(jìn)的遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化方法研究[D].武漢：華中科技大學(xué)，2012.

[4]周康，強(qiáng)小利，同小軍，等.求解TSP算法[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（29）：43-47，85.

[5]趙頌華.城市公共資源監(jiān)管設(shè)計(jì)新思維[J].科技資訊，2015（15）：31-32.

[6]高海昌，馮博琴，朱利.智能優(yōu)化算法求解TSP問題[J].控制與決策，2006，21（3）：241-247，252.

[7]李瑋.關(guān)于旅行商問題的改進(jìn)遺傳算法[D].重慶：重慶大學(xué)，2004.

[8]雷玉梅.基于改進(jìn)遺傳算法的大規(guī)模TSP問題求解方案[J].計(jì)算機(jī)與現(xiàn)代化，2015（2）：34-39.

[9]姚明海，王娜，趙連朋.改進(jìn)的模擬退火和遺傳算法求解TSP問題[J].計(jì)算機(jī)工程與應(yīng)用，2013， 49（14）：60-65.

[10]于瑩瑩，陳燕，李桃迎.改進(jìn)的遺傳算法求解旅行商問題[J].控制與決策，2014，29（8）： 1483-1488.

[11]謝勝利，唐敏，董金祥.求解TSP問題的一種改進(jìn)的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2002， 38（8）： 58-60，245.

[12]黃立君，許永花.遺傳算法和蟻群算法融合求解TSP[J].東北農(nóng)業(yè)大學(xué)學(xué)報(bào)，2008，39（4）： 109-113.

[13]郁磊，史峰.MATLAB智能算法30個(gè)案例分析[M].北京：北京航空航天大學(xué)出版社，2015： 38-39.