基于遺傳算法的TSP問題優(yōu)化方法

陳洋卓 李青青 羅天揚 朱林丹 肖奇

摘 要：針對傳統(tǒng)遺傳算法在巡回商旅問題優(yōu)化計算中存在的弊端——收斂速度慢，迭代次數(shù)多。在傳統(tǒng)遺傳算法基礎上，設計出一種加入人工選擇和定向突變的優(yōu)化改進算法。該優(yōu)化算法通過人工方法保存具有有利變異個體和淘汰具有不利變異個體，有利變異個體進行雜交和變異，從而提高遺傳算法的收斂速度，減少遺傳算法的迭代次數(shù)。同時針對遺傳算法易陷入局部最優(yōu)解的情況，在優(yōu)化算法中引入自適應參數(shù)算法，針對遺傳算法的不同階段，實現(xiàn)雜交概率和變異概率的自適應調節(jié)，防止算法陷入局部最優(yōu)解。最后，采用國際標準的TSP測試集（TSPLIB）對優(yōu)化算法的優(yōu)良性進行驗證，實驗表明，對比其他算法，該優(yōu)化算法在TSP最優(yōu)解的質量上提高10%左右。

關鍵詞：TSP；遺傳算法；人工選擇；定向突變；自適應算法

中圖分類號：TP3-05 文獻標識碼：A

1 緒論

旅行商問題（Traveling Salesman Problem，）是路徑規(guī)劃和組合優(yōu)化領域中著名的NP-hard問題[1，2]，網(wǎng)絡路由的大規(guī)模優(yōu)化[3]、超遠距離泵送混凝土造價控制技術[4]、車輛路線設計[5]等均是典型的TSP。目前，求解TSP的算法可分為精確算法（exact algorithm）和近似算法（approximation algorithm）兩類。Wang等在分析基于智能算法的TSP求解方法優(yōu)缺點[6，7]的基礎上，指出遺傳算法受參數(shù)選擇和數(shù)據(jù)集分布結構的影響最小，陷入局部最優(yōu)的概率最小。

遺傳算法是以適應度[8]為依據(jù)的逐代搜索過程。傳統(tǒng)的遺傳算法，往往存在諸多問題，如收斂速度慢，最優(yōu)解質量差，容易陷入局部最優(yōu)等。針對傳統(tǒng)遺傳算法在旅行商問題求解中存在的弊端，本文對傳統(tǒng)遺傳算法的幾個步驟進行優(yōu)化，提出改進的遺傳算法——在原有的基礎上加入新型的進化策略，從而提升最優(yōu)解的質量，降低最優(yōu)解的誤差率，有效控制遺傳算法早熟收斂性。

2 遺傳算法優(yōu)化改進

2.1 人工選擇法

傳統(tǒng)遺傳算法[9]雜交過程的實現(xiàn)往往是從上一代種群中隨機選擇兩個個體進行雜交，對于雜交生成的子代，采取直接替代父代的方法，但是在替代的過程中存在子代的適應度低于父代，出現(xiàn)劣勢個體的情況，使整個算法的收斂速度變慢，在遺傳代數(shù)一定的條件下，最終解的誤差率上升。

針對上述情況，本文在傳統(tǒng)雜交過程和變異基礎上進行優(yōu)化。我們對雜交生成的四個子代個體的適應度進行重新排序，選擇其中最優(yōu)秀的兩個個體進入下一代種群，同時在變異過程中也進行人工選擇，變異前后的兩個個體選擇出適應度高的進入下一代群體。人工選擇會使種群總體的進化向著適應度不斷提高的方向進行，盡可能保證群體中的優(yōu)勢不會在變異過程中淘汰掉，使群體優(yōu)秀基因能夠遺傳下去，整個遺傳算法的收斂速度得到提高。

2.2 定向突變法

Fmax代表了群體當中的最大適應度值，F(xiàn)avg代表了群體當中的平均適應度值。由上式可知，群體最大適應度和平均適應度差值越大，Pc和Pm的值相應會越小，而K1和K2在這個過程代表著自適應調節(jié)力度的大小。通過自適應參數(shù)算法的引入，在遺傳過程根據(jù)實際情況及時調整Pm和Pc，遺傳算法將具有更好的靈活性，收斂速度提高，并且陷入局部最優(yōu)解的可能性降低。

3 性能分析與實驗結果

基于上述分析，采用C語言對求解TSP問題的改進遺傳算法進行設計實現(xiàn)，為了驗證算法的正確性和有效性，本文選取了國際標準的TSPLIB測試集中的兩組數(shù)據(jù)，將本文算法求解得到的最優(yōu)路線與文獻[12]中得到的最優(yōu)解進行比對，結果如下圖1，圖2所示。

由以上兩組對比可知，在最優(yōu)路線的求解上，本文算法相比較于文獻[12]中的算法具有一定優(yōu)勢，驗證了本文算法的優(yōu)勢性。

4 結語

本文針對TSP問題的求解在傳統(tǒng)遺傳算法的基礎上引入人工選擇，定向突變，和自適應參數(shù)算法，設計出一套優(yōu)化算法。優(yōu)化算法具有快速的收斂能力，能大幅改善種群的質量，極大程度降低所得解的誤差率，并能動態(tài)調節(jié)雜交概率參數(shù)和變異概率參數(shù)，防止算法陷入局部最優(yōu)解。實驗結果表明，與其他四種算法進行比較，本文算法在解的誤差率上具有很大優(yōu)勢。

當然，本文提出的算法還需要做進一步的優(yōu)化工作。在種群規(guī)模迅速擴大的時候，算法的運行時間也會變長，程序會容易陷入局部最優(yōu)解當中，這些都需要在以后的研究工作中加以改進。

參考文獻：

[1]張芳琴.改進遺傳算法在TSP組合優(yōu)化問題中的應用[J].高師理科學刊，2014，34（05）：1-4.（ZHANG F Q.Application of improved genetic algorithm to TSP combinatorial optimization problem[J].Science of Science，2014，34（05）：1-4.）

[2]杜立智，陳和平，符海東.NP完全問題研究及前景剖析[J].武漢工程大學學報，2015，37（10）：73-78.

[3]徐津.基于遺傳免疫粒群優(yōu)化的網(wǎng)絡擁塞控制方法[D].鄭州大學，2012.（XU J.Network congestion control based on genetic immune particle swarm optimization[D].Zhengzhou University，2012.）

[4]馬行耀.遺傳算法用于超遠距離泵送混凝土造價控制技術分析[J].混凝土，2018（05）：94-97.

[5]李珍萍，胡娩霞，吳凌云.基于遺傳算法的成品油二次配送車輛路徑問題研究[J].數(shù)學的實踐與認識，2018，48（09）：189-198.

[6]WANGJ，ERSOYO，HEM，et al.Multi-offspring genetic algorithm and its application to the traveling salesman problem[J].Applied Soft Computing，2016，43：415-423.

[7]TOBIASM，OLA S.Removing and adding edges for the traveling salesmen problem[J].Journal of theACM，2016，63（1）：2-29.

[8]張大科，錢謙.一種新型自適應遺傳算法在多峰函數(shù)優(yōu)化中的應用[J].軟件導刊，2018，17（06）：85-87+91.

[9]鄧先習.遺傳算法求解 TSP 問題的研究與改進[D].沈陽：東北大學信息科學與工程學院，2008.（DENG X X.Genetic.algorithm to solve TSP research and improvement[D].Shenyang：Northeastern University，School of Information Science and Engineering，2008.）

[10]Zu Yun-xiao and Zhou Jie.Multi-user cognitive radio network resource allocation based on the adaptive niche immune genetic algorithm[J].Chinese Physics B，2012，21（1）.

[11]Jianfeng Yu，Yuehong Yin.Assembly line balancing based on an adaptive genetic algorithm[J].The International Journal of Advanced Manufacturing Technology，2010，48（1-4）：347-354.

[12]于瑩瑩，陳燕，李桃迎.改進的遺傳算法求解旅行商問題[J].控制策，2014，（8）：1483-1488.（YU Y Y，CHEN Y，LI T Y.An improved genetic algorithm for traveling salesman problem[J].Control Strategy，2014，（8）：1483-1488.

作者簡介：陳洋卓（1987-），男，碩士，實驗師，研究領域為智能優(yōu)化算法；李青青（1998-），女，本科；羅天揚（1997-），男，本科；朱林丹（1998-），女，本科；肖奇（1996-），男，本科。