蟻群和遺傳算法在旅行路線規(guī)劃中的研究

陳春燕，彭陽，許環(huán)梓，何宇佳，石苗

蟻群和遺傳算法在旅行路線規(guī)劃中的研究

陳春燕，彭陽，許環(huán)梓，何宇佳，石苗

（湘南學(xué)院 數(shù)學(xué)與金融學(xué)院，湖南 郴州 423000）

隨著國家經(jīng)濟(jì)迅速的發(fā)展，旅游成為了大部分人生活中必不可少的部分，經(jīng)濟(jì)式出行旅游規(guī)劃中最重要的是最優(yōu)路線的選擇．以郴州旅游行業(yè)為研究背景，把旅行最優(yōu)路線規(guī)劃問題看成旅行商問題，建立蟻群算法和遺傳算法模型．通過使用Matlab軟件研究旅行問題，找出最優(yōu)路線，并且通過比較選擇出更合適的一種算法來解決商業(yè)上路線的問題．旅游行業(yè)可以通過使用這個最優(yōu)算法建立一個智能旅游出行規(guī)劃系統(tǒng)，來彌補(bǔ)旅游市場行程規(guī)劃系統(tǒng)的缺陷，為游客提供最為經(jīng)濟(jì)、便利的旅行規(guī)劃．

最優(yōu)路線規(guī)劃；旅行商問題；蟻群算法；遺傳算法

郴州有著“林邑郴州”“林中之城，休閑之都”的稱號，其自然型、生態(tài)型旅游資源和歷史文化資源豐富，地理位置優(yōu)越，是中國優(yōu)秀旅游城市．郴州的旅游業(yè)雖起步晚，但是發(fā)展較快，目前已經(jīng)初步形成規(guī)模．

隨著國家經(jīng)濟(jì)的迅速發(fā)展，旅游成為人們休閑生活的重要方式之一．出行的旅游規(guī)劃就變得尤為重要．在旅游規(guī)劃中，旅游路線的選擇直接影響到旅行者在旅行中金錢消費(fèi)和時間消費(fèi)，所以在出行旅游的規(guī)劃中選擇最優(yōu)的路線尤為重要．目前，出行旅游的路線多數(shù)是單一的路線，一天到一個景點(diǎn)，不能多個景點(diǎn)，耗費(fèi)很多的時間和金錢，造成這樣的結(jié)果主要?dú)w結(jié)于沒有選擇一條好的路線，現(xiàn)有的單一旅行路線已經(jīng)不能滿足市場大部分用戶的需求，最優(yōu)路線的選擇對旅游市場的推廣有著不可替代的作用．從郴州旅游現(xiàn)狀看，由于地域差距較為突出，交通等基礎(chǔ)設(shè)施較為落后，為郴州旅游業(yè)的發(fā)展帶來了一定的影響．本文提出旅游出行最優(yōu)路線問題，同時把旅游出行最優(yōu)路線的選擇問題看成旅行商問題來進(jìn)行研究，研究旅行商問題的算法分別有線性規(guī)劃法、蟻群算法[1]、貪心算法[2]、遺傳算法[3]、動態(tài)規(guī)劃法[4]、模擬退火法[5]等，本文從中選擇蟻群算法和遺傳算法對其進(jìn)行研究．

1 TSP最優(yōu)路線研究現(xiàn)狀分析

TSP問題又稱旅行商問題，是典型的所有非確定型多項式時間可解的判定問題，也是組合優(yōu)化問題．早期的研究者使用分支定界法、線性規(guī)劃法、動態(tài)規(guī)劃法等精確的算法來進(jìn)行研究，但是隨著數(shù)量的增大，實現(xiàn)很復(fù)雜，這些算法也都無能為力．隨后，許多國外研究者著重使用遺傳算法、蟻群算法、模擬退火法、貪婪算法和神經(jīng)網(wǎng)絡(luò)等近似算法或者啟發(fā)式算法．針對旅行商問題的算法主要是蟻群算法和遺傳算法，這2種算法又稱為智能算法．蟻群算法是模擬螞蟻，根據(jù)螞蟻分泌的信息素的濃度為依據(jù)來迭代搜索，遺傳算法是依據(jù)適應(yīng)度來迭代搜索．2種算法都有相同的群體特點(diǎn)，也同樣有著收斂速度慢和迭代次數(shù)多的缺陷，對于這2點(diǎn)的缺陷，近年國內(nèi)的學(xué)者對蟻群算法和遺傳算法進(jìn)行了優(yōu)化[6]．這2種算法哪個更適合于旅行商問題中的最優(yōu)路線，并且把這種算法應(yīng)該于旅行商業(yè)上，這是我們需要研究的．

2 TSP的蟻群算法和遺傳算法

旅行規(guī)劃的最優(yōu)路線問題看成旅行商問題，通過用Matlab智能算法（蟻群算法 遺傳算法[7]）得出最優(yōu)路線值．

2.1 蟻群算法

用螞蟻的行走路徑表示待優(yōu)化問題的可行解，整個螞蟻群體的所有路徑構(gòu)成待優(yōu)化問題的解空間．路徑較短的螞蟻釋放的信息素量較多，隨著時間的推進(jìn)，較短的路徑上累積的信息素濃度逐漸增高，選擇該路徑的螞蟻個數(shù)也愈來愈多，從而得出最優(yōu)路線（即待優(yōu)化問題的最優(yōu)解）．

2.2 遺傳算法

遺傳操作是模擬生物基因遺傳的做法[8]．在遺傳算法中，通過編碼組成初始群體后，遺傳操作的任務(wù)就是對群體的個體按照它們對環(huán)境適應(yīng)度（適應(yīng)度評估）施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進(jìn)化過程．從優(yōu)化搜索的角度而言，遺傳操作可使問題的解，一代又一代地優(yōu)化，并逼近最優(yōu)解．可以把這個思想轉(zhuǎn)化為旅行商的思想，從而得出最優(yōu)路線.

3 Matlab建立的最優(yōu)路線模型和運(yùn)行結(jié)果

3.1 Matlab 蟻群算法

算法理念：從郴州一個起點(diǎn)出發(fā)，每個景點(diǎn)均僅經(jīng)過一次，最終回到起點(diǎn)的最優(yōu)路線．

數(shù)學(xué)規(guī)劃模型為：

建立數(shù)學(xué)模型

給出10個景點(diǎn)的坐標(biāo)，螞蟻為30，迭代次數(shù)200次，求出最優(yōu)路線值和最優(yōu)路線．

圖1 蟻群算法的適應(yīng)度進(jìn)化曲線

蟻群算法所得的結(jié)果見圖1，其縱坐標(biāo)的目標(biāo)函數(shù)值表示的是最優(yōu)距離，即最短距離．從圖1中可以看出，總共迭代了200次，蟻群算法迭代2次就可以達(dá)到最優(yōu)解．

蟻群算法的平均距離和最短距離見圖2．從圖2可以看到最大距離與最短距離和不確定性的路況距離的波動性，從而讓旅行者在選擇適合的路徑時考慮到不確定因素的影響．

蟻群算法在旅行商問題優(yōu)化的結(jié)果見圖3．從圖3可以看到景點(diǎn)坐落的坐標(biāo)點(diǎn)，把10個景點(diǎn)坐標(biāo)按照輸入從1~10排序，運(yùn)行的結(jié)果可以得出最優(yōu)路線．

最優(yōu)路線為Shortest_Route = 4 5 6 7 8 9 10 2 3 1

最短距離為Shortest_Length = 2.690 7．

圖2 蟻群算法的平均距離和最短距離

圖3 蟻群算法在旅行商問題優(yōu)化的結(jié)果

3.2 Matlab 遺傳算法

數(shù)學(xué)規(guī)劃模型：

給出10個景點(diǎn)的坐標(biāo)（10個景點(diǎn)坐標(biāo)與蟻群算法的坐標(biāo)相同），初始種群為30，迭代次數(shù)200次，求出最優(yōu)路線值和最優(yōu)路線．

遺傳算法的平均距離和最短距離見圖4．從圖4中可以看到遺傳算法迭代多少次達(dá)到最優(yōu)解，也可以知道在不確定因素下的最大距離．

遺傳算法在旅行商問題優(yōu)化的結(jié)果見圖5．從圖5可以看到遺傳算法需迭代12次，才能達(dá)到最優(yōu)函數(shù)值，其得到的最優(yōu)路線與蟻群算法的相同．

最優(yōu)路線為Shortest_Route =4 5 6 7 8 9 10 2 3 1

最短距離為Shortest_Length = 2.690 7．

圖4 遺傳算法所得的結(jié)果

圖5 遺傳算法在旅行商問題優(yōu)化的結(jié)果

4 結(jié)語

蟻群算法和遺傳算法都是智能隨機(jī)算法[9-10]，從運(yùn)行結(jié)果來看（圖3與圖5），最優(yōu)路線和最優(yōu)路線值是一致的[11}；從運(yùn)行的速度來看（圖1與圖5），蟻群算法迭代的次數(shù)要小于遺傳算法，所有蟻群算法的收斂速度要優(yōu)于遺傳算法；從最優(yōu)路線的波動性來看（圖2與圖4），蟻群算法不確定因素下的最大距離要小于遺傳算法，遺傳算法的搜索能力要比蟻群算法強(qiáng)．綜上所述，可以知道蟻群算法有較強(qiáng)的魯棒性、并行求解質(zhì)量好，同時也有較強(qiáng)的全局優(yōu)化能力，收斂的速度也比遺傳算法的要快．雖然遺傳算法有比較強(qiáng)的全局搜索能力，但是從旅行商業(yè)角度來看，算法中迭代的次數(shù)越多，消費(fèi)成本可能就越高，所以蟻群算法更適合旅行商業(yè)中解決旅游路線規(guī)劃問題，可以考慮利用蟻群算法建立一個智能旅游出行規(guī)劃系統(tǒng)，為游客提供最為合適的旅行路線．

[1] 劉中強(qiáng)，游曉明，劉升．一種啟發(fā)式動態(tài)信息素更新策略的蟻群算法[J]．計算機(jī)工程與應(yīng)用，2018（20）：20-27

[2] 畢龍閣．貪心算法和線性規(guī)劃[J]．計算機(jī)產(chǎn)品與流通，2017（11）：239，251

[3] 胡士娟，魯海燕，黃洋，等．求解工作量平衡多旅行商問題的改進(jìn)遺傳算法[J]．計算機(jī)工程與應(yīng)用，2019（17）：150-155，231

[4] 呂丹，楊子寒，周君．動態(tài)規(guī)劃算法在生活中的應(yīng)用[J]．電腦知識與技術(shù)，2018，14（17）：253-255，268

[5] 馮玉蓉．模擬退火算法的研究及其應(yīng)用[D]．昆明：昆明理工大學(xué)，2005

[6] 陳洋卓，李青青，羅天揚(yáng)，等．基于遺傳算法的TSP問題優(yōu)化方法[J]．科技風(fēng)，2019（1）：59-60

[7] 史小明．淺談MATLAB下的遺傳算法優(yōu)化軟件設(shè)計[J]．?dāng)?shù)學(xué)技術(shù)與應(yīng)用，2019（1）：59-60

[8] 蔣然．改進(jìn)遺傳算法在TSP問題中的應(yīng)用[J]．軟件導(dǎo)刊，2016（12）：44-45

[9] 武海峰．基于Matlab的遺傳算法程序設(shè)計探討[J]．電腦迷，2017（1）：38-39

[10] 杜洋．遺傳算法的原理及應(yīng)用[J]．才智，2010（9）：49

[11] 陳少杰，麻莉娜．蟻群算法基本原理及綜述[J]．科技創(chuàng)新與應(yīng)用，2016（11）：62-64

Study on ant colony and genetic algorithm in traveling route planning

CHEN Chunyan，PENG Yang，XU Huanzi，HE Yujia，SHI Miao

（School of Mathematics and Finance，Xiangnan University，Chenzhou 423000，China）

With the rapid development of the national economy，travelling has become an indispensable part of most people′ s life．The most significant thing of economical travel plans is to choose the best route．Takes the Chenzhou tourist industry as background，comparing the best travel route planning to the traveling salesman problem（TSP）to find the best travel route by using Matlab to establish the model of ant colony optimization（ACO）and genetic algorithm（GA），and get the most suitable way to settle commercial routine issues．The tourist industry will establish a intelligent travel planning system to perfect the defect of the formal travel planning system and provide tourists with the most economical and convenient travel planning．

optimal route planning；traveling salesman problem（TSP）；ant colony optimization（ACO）；genetic algorithm（GA）

1007-9831（2020）07-0033-04

TP18

A

10.3969/j.issn.1007-9831.2020.07.008

2020-02-27

湘南學(xué)院2018年度校級大學(xué)生研究性學(xué)習(xí)和創(chuàng)新性項目（第29項）；2017年湘南學(xué)院校級教改項目（第31項）

陳春燕（1998-），女，湖南永州人，在讀本科生．

石苗（1981-），女，湖南常德人，講師，從事最優(yōu)化算法研究．E-mail：jingui0531@126.com