改進(jìn)遺傳算法求解文化旅游線路規(guī)劃問題

張瑞姣 陳崇成 黃正睿 方薈

摘 要：針對旅游線路規(guī)劃問題的非確定性多項式難題（nondeterministic polynomially problem，NP）特性，顧及文化旅游景點(diǎn)文化內(nèi)涵的多樣性，提出了一種可有效保持種群多樣性的遺傳算法以求解旅游線路規(guī)劃問題。為了解決傳統(tǒng)遺傳算法的局部最優(yōu)問題，改進(jìn)的算法利用Jaccard系數(shù)產(chǎn)生初始種群以提升種群質(zhì)量;在交叉算子后采用多種變異算子產(chǎn)生多個子代，保留子代與父代中較優(yōu)個體組成新種群，從而保持種群在進(jìn)化過程中的多樣性。實驗結(jié)果表明所提算法能夠更有效求解旅游線路規(guī)劃問題。

關(guān)鍵詞：文化旅游線路規(guī)劃;遺傳算法;Jaccard系數(shù);變異算子;種群多樣性

中圖分類號：TP18;K909

文獻(xiàn)標(biāo)志碼：A

“自由”旅行方式因其能快速推薦旅游行程，輔助游客決策而廣受歡迎。旅游線路規(guī)劃是旅游推薦領(lǐng)域研究的熱點(diǎn)，而旅游線路規(guī)劃問題（tourist trip design problem，TTDP）則是針對有興趣訪問多個興趣點(diǎn)（point of interest，POI）的游客的旅行計劃問題，需要顧及游客偏好，使其滿意度最大化，其本質(zhì)上是帶利益的旅行商問題或者車輛路徑問題[1]，即非確定性多項式難題（nondeterministic polynomially problem，NP）。定向運(yùn)動問題（orienteering problem，OP）是TTDP的一個簡化模型，是指在限定時間內(nèi)訪問具有相關(guān)利潤的多個地點(diǎn)，且每個地點(diǎn)只能訪問一次，使得推薦的旅行線路具有最大的總利潤。針對OP的研究，根據(jù)不同的限制條件發(fā)展了多種變體，如考慮景點(diǎn)開放時間作為限制條件的帶時間窗口的OP問題（OP with time windows，OPTW）[2]等，從而使規(guī)劃的線路更加符合實際?，F(xiàn)有的OP研究大多是面向熱門旅游景點(diǎn)，且僅考慮POI的單個屬性特征作為景點(diǎn)的利益（如評分最大、距離最小、花費(fèi)最小等）來構(gòu)建目標(biāo)函數(shù)，但這并不適用于文化旅游領(lǐng)域。文化旅游中的POI具有許多重要特征（例如文化背景、歷史相關(guān)性等），這些重要特征是文化旅游的核心競爭力。因此，需要將每個特征的分?jǐn)?shù)范圍都與該P(yáng)OI相關(guān)聯(lián)，利用OP建模，為每個POI建模多個分?jǐn)?shù)[3]，從而綜合衡量POI。

目前，TTDP的求解方法主要包括精確算法、啟發(fā)式算法和智能化元啟發(fā)式算法。其中，精確算法雖然能得到精確的解，但其搜索能力較差，只能適用于小規(guī)模的POI規(guī)劃[4]。啟發(fā)式算法能夠在短時間內(nèi)得到可行解，但解的質(zhì)量并不高[5]。智能化元啟發(fā)式算法成為解決該問題的主流算法。元啟發(fā)式算法包括遺傳算法[6]、粒子群算法[7]、蟻群算法[8]、模擬退火算法（simulated annealing algorithm，SAA）[9]等。SAA是一種源于固體退火原理的啟發(fā)式優(yōu)化算法，可以較大概率獲得全局優(yōu)化結(jié)果，廣泛應(yīng)用于優(yōu)化問題、旅行商問題等。遺傳算法（genetic algorithm，GA）源于達(dá)爾文提出的自然進(jìn)化論的思想，遵循競爭的自然法則和優(yōu)勝劣汰的生存法則[4]，因其搜索速度快、隨機(jī)性強(qiáng)、過程簡單、靈活性強(qiáng)的特點(diǎn)而廣泛應(yīng)用于各個領(lǐng)域，例如組合優(yōu)化、生產(chǎn)調(diào)度等。但GA也存在固有的弊端，種群會在進(jìn)化過程中因多樣性的減少而造成過早收斂問題，也稱局部最優(yōu)問題[10]。因此，保證種群多樣性以避免算法陷入局部最優(yōu)。國內(nèi)外學(xué)者對于上述GA問題的解決研究可大致分為兩類：一是提高初始種群質(zhì)量;二是保持進(jìn)化中種群多樣性等。LI等[11]提出了基于信息熵與博弈論的混合GA（hybrid genetic algorithm，HGA），利用信息熵生成初始種群以提升其多樣性，避免算法陷入局部最優(yōu)解。譚文安等[12]利用混沌理論在GA初始種群獲得更優(yōu)秀的初始群體， 從而提高算法效率。SUN等[13]提出了利用余弦相似性理論對相鄰種群間的多樣性和相似性進(jìn)行限定，通過對交叉和變異概率的自適應(yīng)調(diào)整，保持進(jìn)化過程中的種群多樣性，提高算法的收斂和全局最優(yōu)解。WANG等[14]提出了基于多子代的GA（multi-offspring genetic algorithm，MO-GA），利用多個交叉算子產(chǎn)生多個子代種群以提高種群子代的多樣性，解決旅行商問題，使得可行解更加接近最優(yōu)解。王福林等[15]利用兩點(diǎn)交叉算子產(chǎn)生多子代保持種群遺傳進(jìn)化中的生物多樣性，提高遺傳算法的收斂速度。XIN等[16]利用多子代戰(zhàn)略，在傳統(tǒng)遺傳算法之后增加多域倒位遺傳算子，解決旅行商問題，顯著提高種群多樣性，提升算法收斂和魯棒性。

本文在上述研究的基礎(chǔ)上，提出了改進(jìn)的GA以求解文化旅游線路規(guī)劃問題。首先，根據(jù)景點(diǎn)的文化屬性構(gòu)建旅游線路規(guī)劃模型;其次，利用Jaccard系數(shù)和多變異算子提升GA的初始種群和進(jìn)化中種群的多樣性，避免算法的早收斂問題;再次，以長征景點(diǎn)中遵義會議為例，對比提出算法與GA求解模型，證明了所提算法的優(yōu)越性。

1 文化旅游線路規(guī)劃模型

本文借鑒OPTW，即在OP的基礎(chǔ)上考慮POI的到達(dá)時間要在景點(diǎn)的時間窗之內(nèi)，公式如下：

Topentime≤Tarrivetime≤Tclosetime （1）

若Tarrivetime=Tclosetime，則游客不能充分游覽景點(diǎn)造成旅游體驗差。因此，本文將到達(dá)時間與游覽時間相加得到游覽完景點(diǎn)的時間點(diǎn)，使其不得超過景點(diǎn)關(guān)閉時間，并以最大化綜合線路評分為目標(biāo)函數(shù)。

1.1 問題描述

由于景點(diǎn)文本中干擾信息多，涉及文化信息的較少，常用的文本挖掘方法會造成挖掘結(jié)果精度不準(zhǔn)的問題。為此，本文采用正則表達(dá)式來精確表征一組字符串[17]，并以具有重要意義的長征文化為例，通過紅色旅游構(gòu)成要素[18]及長征文化特點(diǎn)，確定待挖掘景點(diǎn)的文化特征，包括人物、事件和類型（如紅軍亭、紅軍橋等）。利用HanLP工具對文本進(jìn)行分詞，然后預(yù)定義文化特征，利用正則表達(dá)式將景點(diǎn)與特征精確匹配。

模型顧及多種限制因素，包括游客需求和景點(diǎn)屬性，其中，游客需求包括游客偏好、起始位置、旅行天數(shù);后者則包括景點(diǎn)的經(jīng)緯度、文化特征、開放時間、評分、游覽時間。為了便于數(shù)學(xué)模型構(gòu)建，對模型涉及的問題進(jìn)行描述，模型涉及到的符號及其含義見表1。

定義1 景點(diǎn)信息。對于每一個景點(diǎn)SiS，Si={tt，l，to，tc，w，r} ，其中r為景點(diǎn)標(biāo)簽集合，r={rp，re，rl}，便于游客選擇感興趣文化主題或景點(diǎn)文化類型。

定義2 POI集合s。s是指游客選擇了感興趣的r后產(chǎn)生的POI集合，s={s1，s2，…，sn}，其中n表示集合中POI的數(shù)量。

定義3 交通時間ttr。ttr為兩部分，分別是ttru和ttrs。對于線路c={s1，s2，…，sk}，k=1，2，…，n，k≤n，則

ttru（ps，si）=D（ps，si）v（2）

ttrs（si，sj）=D（si，sj）v（3）

ttr（ps，si）=ttru（ps，si）+∑k-1i=0ttrs（si，si+1）（4）

定義4 景點(diǎn)到達(dá)時間ta。ta對于不同時段的景點(diǎn)有不同的數(shù)學(xué)表達(dá)式。對于多日旅程，旅行第一天選定的第一景點(diǎn)的到達(dá)時間如式（5）所示，其余旅行新一天中第一個景點(diǎn)的到達(dá)時間如式（6）所示，其余ta則參照式（7）。

ta（si）=ts+ttru（ps，si）（5）

ta（si）=ts+ttrs（si，sj）（6）

ta（sj）=ta（si）+ttrs（si，sj）+tt（si）（7）

定義5 游客總旅行時間T。T由游客的交通時間和景點(diǎn)游覽時間組成，對于線路c={s1，s2，…，sk}，k=1，2，…，n，k≤n，則

T=ttr（ps，si）+∑ki=1tt（si）（8）

定義6 景點(diǎn)綜合評分sw。sw由兩部分組成，即景點(diǎn)評分和景點(diǎn)文化特征，分別對兩者進(jìn)行歸一化處理即可得到景點(diǎn)綜合評分，其中景點(diǎn)文化特征需要每個特征按歸一化過程處理。

sw（si）=w（si）-wminwmax-wmin+rp（si）-rpminrpmax-rpmin+

re（si）-reminremax-remin+rl（si）-rlminrlmax-rlmin（9）

式中：wmin、rpmin、remin、rlmin分別表示Si中評分、人物、事件和文化類型的最小值;wmax、rpmax、remax、rlmax分別對應(yīng)上述最大值。

定義7 線路綜合評分Z。Z即線路包含的景點(diǎn)的綜合評分之和。若對于c={s1，s2，…，sk}，k=1，2，…，n，k≤n，則c的線路綜合評分為

Z=∑ki=1sw（si）（10）

1.2 OPTW模型

OPTW模型以綜合線路評分為目標(biāo)，充分考慮游客偏好、旅游時間等因素，從而求解更為合理的旅游線路。OPTW數(shù)學(xué)模型可以表示為

Max Z=∑ki=1sw（si） （11）

s.t.T<d×t（12）

h（si）=1， si游客已游覽

h（si）=0， si游客未游覽 （13）

to（si）≤ta（si）

ta（si）+tt（si）≤tc（si） （14）

ttru（ps，si）<C，C為常數(shù)（15）

D（ps，sj）=D（si，ps）

D（si，sj）=D（sj，si） （16）

其中：式（11）表示模型的目標(biāo)函數(shù);式（12）表示T要滿足游客的旅行總時間要求;式（13）表示對景點(diǎn)是否游覽標(biāo)注;式（14）表示更為嚴(yán)格的時間窗控制;式（15）表示游客從起始位置到首個景點(diǎn)的交通時間應(yīng)在某個時間段;式（16）表示一個假設(shè)條件，即景點(diǎn)間的往返距離一致。

2 遺傳算法改進(jìn)

2.1 進(jìn)化策略

2.1.1 初始化種群產(chǎn)生方式的改進(jìn)

Jaccard相似系數(shù)可用于比較有限樣本集之間的相似性和差異[19]。本文引入Jaccard相似系數(shù)產(chǎn)生初始種群，利用Jaccard相似度得到個體間的相似性，然后通過Jaccard距離計算個體間的差異。Jaccard相似系數(shù)為

J（pi，pi+1）=|pi∩pi+1||pi∪pi+1|，（1≤i≤M-1）（17）

Jaccard距離為

D（pi，pi+1）=1-J（pi，pi+1）

=|pi∩pi+1||pi∪pi+1|，（1≤i≤M-1）（18）

式中：pi、pi+1分別為初始種群中的個體;M為種群規(guī)模。個體間的Jaccard距離與Jaccard相似度相反：J（pi，pi+1）越大表明個體間基因的重疊率越高，個體越相似，反之則差異越大;而D（pi，pi+1）越大，表明個體間差異越大。

2.1.2 多子代策略

根據(jù)WANG等[14]提出的多子代策略，在交叉算子后增加多個變異算子產(chǎn)生多個子代個體，從父代與子代個體中選擇適應(yīng)度最好的個體組成新種群。突變算子是一種維持從一個種群到下一個種群的遺傳多樣性的操作[20]，則多個突變算子可以增加種群多樣性。本文選擇常用的3種變異算子：倒位變異、多次交換變異和插入變異。其中，倒位變異是指兩變異位置之間的基因倒序排列得到子代的過程;多次交換變異就是多次進(jìn)行交換變異操作，以p1=[1，2，3，4，5，6]兩次交換變異為例，第一次交換2、4，則得到p2=[1，4，3，2，5，6]，第二次交換1、6，則得到最終變異p3=[6，4，3，2，5，1];插入變異是將第2個變異位置的基因插入第1個變異位置基因之后。

2.2 算法流程

綜上所述，本文提出了多變異算子的遺傳算法（Multi-Mution GA，MMGA），算法的流程圖如下：

MMGA的具體步驟如下：

步驟1 初始化種群生成。利用Jaccard產(chǎn)生初始種群，產(chǎn)生過程如下：

1）設(shè)定臨界距離H0。

2）使用隨機(jī)方法產(chǎn)生第1個個體。

3）用同樣的方法生成之后的個體，同時計算新產(chǎn)生的染色體與種群已有個體的Jaccard 距離H。如果滿足H>H0，則該個體添加到新種群;否則，重新生成新的個體，直至滿足H>H0。

4）重復(fù)步驟3，達(dá)到設(shè)定的種群規(guī)模M即可得到初始種群。

步驟2 適應(yīng)度評價。適應(yīng)度評價是根據(jù)目標(biāo)函數(shù)式（11）和各種限制條件，計算個體中滿足約束條件的POI，求解適應(yīng)度。

步驟3 采用賭盤選擇法選取M（種群規(guī)模）個個體組成種群進(jìn)行之后的交叉操作。

步驟4 采用類似于順序交叉的方式，隨機(jī)產(chǎn)生2個交叉點(diǎn)，將一個體基因的第3部分作為開始，將另一個體去除重復(fù)的基因依次插入之后產(chǎn)生一個子代個體，同樣的方式產(chǎn)生另一子代個體。

步驟5 采用倒位變異、多次交換變異和插入變異對父代個體進(jìn)行變異操作，產(chǎn)生3個子代個體。

步驟6 計算步驟5產(chǎn)生的子代個體和父代個體的適應(yīng)度，并選擇其中適應(yīng)度最大的個體組成新的種群。

步驟7 判斷是否滿足遺傳進(jìn)化終止條件。本文將最大進(jìn)化代數(shù)設(shè)為終止條件，若進(jìn)化代數(shù)小于進(jìn)化代數(shù)最大值，則返回步驟2繼續(xù)執(zhí)行;否則，算法結(jié)束，輸出適應(yīng)度最好的個體（即可行解）。

3 實驗設(shè)計與結(jié)果分析

3.1 數(shù)據(jù)介紹與案例說明

3.1.1 數(shù)據(jù)介紹

長征是1934—1936年中國共產(chǎn)黨領(lǐng)導(dǎo)的中國工農(nóng)紅軍第一、二、四方面軍和紅二十五軍分別從各根據(jù)地向陜甘地區(qū)進(jìn)行的戰(zhàn)略大轉(zhuǎn)移，其鑄就的長征精神和文化是我國優(yōu)秀文化和愛國精神的重要組成部分。長征跨越地域范圍廣，沿途旅游資源較為分散。

長征旅游景點(diǎn)數(shù)據(jù)以田競等[21-25]的《重走長征路》系列圖書為數(shù)據(jù)源收集景點(diǎn)數(shù)據(jù)，輔以望路者旅游網(wǎng)站、百度百科、文獻(xiàn)等的景點(diǎn)文化信息，共得到376個景點(diǎn)數(shù)據(jù)。對長征旅游景點(diǎn)等級狀況進(jìn)行統(tǒng)計，其中，國家4A級和5A級景點(diǎn)的數(shù)量分別為26個和4個，國家級文物保護(hù)單位70個。長征景點(diǎn)簡介信息是由景點(diǎn)的位置、基本情況及涉及的長征人物、時間等組成的文化文本，以福緣橋景點(diǎn)為例，如圖2所示。線路規(guī)劃時需要考慮景點(diǎn)的相關(guān)屬性信息，則景點(diǎn)所含信息見表2。

3.1.2 案例說明

以游客偏好為遵義會議的事件文化特征為例，與之相關(guān)的景點(diǎn)不只是遵義會址、紅軍總政治部。遵義會議是個歷史過程，其前后會議如通道會議、黎平會議、會理會議等可看作遵義會議的系列會議[26]，因此，這些會議也是遵義會議事件標(biāo)簽的組成部分。此標(biāo)簽集中分布在云貴川的交界區(qū)域，地理跨度較小，共包含17個景點(diǎn)，景點(diǎn)名稱及對應(yīng)評分、人物、事件、類型見表3。

3.2 實驗與結(jié)果分析

3.2.1 實驗環(huán)境與參數(shù)

實驗是在CPU為Intel（R）Core（TM） i7-4700 3.40 GHz、內(nèi)存為32 GB、操作系統(tǒng)為 Windows 7旗艦版的 PC 機(jī)上進(jìn)行。算法基于Eclipse軟件平臺，Java的版本為1.7的環(huán)境實現(xiàn)，使用到的工具包包括HanLP等。實驗參數(shù)見表4。

3.2.2 實驗結(jié)果與分析

為了驗證MMGA的優(yōu)越性，將MMGA與傳統(tǒng)GA以及SAA進(jìn)行比較，以線路的綜合評分為評價指標(biāo)。實驗分為兩部分：一是相同旅行天數(shù)不同時間約束對比，二是相同時間約束不同旅行天數(shù)對比。每次算法得到的線路綜合評分略有不同，因此每組實驗運(yùn)行100次，取平均值得到每組線路的綜合評分。其中，游客的起始位置設(shè)為遵義會議火車站。

1）相同旅行天數(shù)不同時間約束對比

以旅行天數(shù)為2天為例，每天的旅行時間約束分別為6、7、8、9、10、11、12 h，得到不同時間約束下算法的對比，如圖3所示。由圖3可知，時間約束為9 h之前，3種算法的線路綜合評分隨著每天旅行時間的增加逐漸增加;時間約束為9 h之后，MMGA線路綜合評分趨于平穩(wěn)，SAA先增后降，GA則略有增長;與GA、SAA相比，MMGA線路綜合評分最高，可以獲取更高綜合評分的線路。

2）相同時間約束不同旅行天數(shù)對比

通常每天的旅行時間ts為8 h，依據(jù)景點(diǎn)的關(guān)閉時間，將每天的時間約束設(shè)置為10 h。以天數(shù)分別為1、2、3、4、5、6 d的旅游天數(shù)為例，進(jìn)行6組實驗，生成遵義會議的一日至六日游的旅游路線，如圖4所示。由圖4可知，不同旅行天數(shù)限制下線路綜合評分的對比，MMGA可以獲得更高的線路綜合評分。

由于MMGA初始化種群產(chǎn)生方式的改進(jìn)和多子代策略，算法中種群個體更為多樣，后續(xù)參與遺傳進(jìn)化的種群個體有更高的適應(yīng)度，使得算法可以快速獲取優(yōu)質(zhì)可行解，有效避免了GA早收斂導(dǎo)致的局部最優(yōu)問題，提升了算法的全局尋優(yōu)能力。因此，MMGA在線路規(guī)劃方面的結(jié)果要優(yōu)于傳統(tǒng)GA和SAA，能夠推薦綜合評分更高的線路，在滿足景點(diǎn)熱度的同時滿足游客的文化需求，讓游客可以充分游覽景點(diǎn)，獲得更好的旅游體驗。但是，由于景點(diǎn)間的評分及文化特征差異較?。ū?），導(dǎo)致不同算法推薦線路的綜合評分差異不顯著。

4 結(jié)論與展望

本文基于OPTW構(gòu)建文化旅行線路規(guī)劃模型，該模型綜合考慮了游客的起始位置、文化偏好、旅行天數(shù)、景點(diǎn)開放時間等多種約束因素，并根據(jù)景點(diǎn)的文化特征綜合評價景點(diǎn)，設(shè)置線路利益目標(biāo)函數(shù)。為了有效求解上述模型，提出了MMGA，利用Jaccard提高初始種群質(zhì)量，通過多變異算子保持算法進(jìn)化過程種群多樣性，提升了算法全局尋優(yōu)能力。實驗結(jié)果表明，MMGA相較于傳統(tǒng)GA和SAA能夠規(guī)劃出更為合理的旅游線路。但改進(jìn)的算法相較于原算法更為復(fù)雜，算法運(yùn)行時間會增加，此外，線路規(guī)劃沒有考慮環(huán)境因素，例如游覽當(dāng)天的天氣狀況、交通狀況等;因此，今后工作中可以考慮算法運(yùn)行時間的優(yōu)化及多種現(xiàn)實條件下的線路規(guī)劃，使路線能更貼近實際。

參考文獻(xiàn)：

[1]GAVALAS D， KONSTANTOPOULOS C， MASTAKAS K， et al. A survey on algorithmic approaches for solving tourist trip design problems[J]. Journal of Heuristics， 2014， 20（3）： 291-328.

[2] GAVALAS D， KONSTANTOPOULOS C， MASTAKAS K， et al. Efficient metaheuristics for the mixed team orienteering problem with time windows[J]. Algorithms， 2016， 9（1）：1-21.

[3] SYLEJMANI K， DORN J， MUSLIU N. Planning the trip itinerary for tourist groups[J]. Information Technology & Tourism， 2017， 17（3）： 275-314.

[4] HUANG T， GONG Y J， ZHANG Y H， et al. Automatic planning of multiple itineraries： a niching genetic evolution approach[J]. IEEE Transactions on Intelligent Transportation Systems， 2020， 21（10）： 4225-4240.

[5] 崔琪， 吳秀麗， 余建軍. 變鄰域改進(jìn)遺傳算法求解混合流水車間調(diào)度問題[J]. 計算機(jī)集成制造系統(tǒng)， 2017， 23（9）： 1917-1927.

[6] ZHANG Y M， JIAO L J， YU Z J， et al. A tourism route-planning approach based on comprehensive attractiveness[J]. IEEE Access， 2020， 8： 39536-39547.

[7] MALIK S， KIM D. Optimal travel route recommendation mechanism based on neural networks and particle swarm optimization for efficient tourism using tourist vehicular data[J]. Sustainability， 2019， 11（12）： 1-26.

[8] QIAN X H， ZHONG X P. Optimal individualized multimedia tourism route planning based on ant colony algorithms and large data hidden mining[J]. Multimedia Tools and Applications， 2019， 78（15）： 22099-22108.

[9] LIN S W， YU V F. A simulated annealing heuristic for the team orienteering problem with time windows[J]. European Journal of Operational Research， 2012， 217（1）： 94-107.

[10]UMBARKAR A J， JOSHI M S， HONG W C. Comparative study of diversity based parallel dual population genetic algorithm for unconstrained function optimisations[J]. International Journal of Bio-Inspired Computation， 2016， 8（4）： 248-263.

[11]LI J C ， LI L. A hybrid genetic algorithm based on information entropy and game theory[J]. IEEE Access， 2020， 8： 36602-36611.

[12]譚文安， 趙堯. 基于混沌遺傳算法的Web服務(wù)組合[J]. 計算機(jī)集成制造系統(tǒng)， 2018， 24（7）： 1822-1829.

[13]SUN N， LU Y. A self-adaptive genetic algorithm with improved mutation mode based on measurement of population diversity[J]. Neural Computing and Applications， 2018， 31（5）： 1435-1443.

[14]WANG J， ERSOY O K， HE M Y， et al. Multi-offspring genetic algorithm and its application to the traveling salesman problem[J]. Applied Soft Computing， 2016， 43： 415-423.

[15]王福林， 付曉明， 朱會霞， 等. 基于兩點(diǎn)交叉多子代遺傳算法[J]. 東北農(nóng)業(yè)大學(xué)學(xué)報， 2016， 47（3）： 72-79.

[16]XIN J F， ZHONG J B， YANG F R， et al. An improved genetic algorithm for path-planning of unmanned surface vehicle[J]. Sensors， 2019， 19（11）： 2640.

[17]付哲， 李軍. 高性能正則表達(dá)式匹配算法綜述[J]. 計算機(jī)工程與應(yīng)用， 2018， 54（20）： 1-13.

[18]黃細(xì)嘉， 宋麗娟. 紅色旅游資源構(gòu)成要素與開發(fā)因素分析[J]. 南昌大學(xué)學(xué)報（人文社會科學(xué)版）， 2013， 44（5）： 53-59.

[19]ZHANG D H， YOU X M， LIU S， et al. Multi-colony ant colony optimization based on generalized jaccard similarity recommendation strategy[J]. IEEE Access， 2019， 7： 157303-157317.

[20]KATOCH S， CHAUHAN S S， KUMAR V. A review on genetic algorithm： past， present， and future[J]. Multimedia Tools and Applications， 2021， 80（5）： 8091-8126.

[21]田競， 王向東， 蘇北， 等. 重走長征路： 紅一方面軍： 上[M]. 北京：華文出版社， 2016.

[22]田競， 王向東， 蘇北， 等. 重走長征路： 紅一方面軍： 下[M]. 北京：華文出版社， 2016.

[23]杜麗英. 重走長征路： 紅二方面軍[M]. 北京： 華文出版社， 2016.

[24]田曉虹， 田毅， 田競， 等. 重走長征路： 紅四方面軍[M]. 北京： 華文出版社， 2016.

[25]田競， 蘇北. 重走長征路： 紅二十五軍[M]. 北京： 華文出版社， 2016.

[26]趙福超. 遵義會議前后六次政治局會議的內(nèi)在歷史聯(lián)系[J]. 吉首大學(xué)學(xué)報（社會科學(xué)版）， 2019， 40（增刊1）： 145-148.

（責(zé)任編輯：周曉南）

Improved Genetic Algorithm to Solve the Problem of

Cultural Tourism Route Planning

ZHANG Ruijiao1， CHEN Chongcheng*1， HUAGN Zhengrui1， FANG Hui1，2

（1.Academy of Digital China（Fujian） Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education， Fuzhou University， Fuzhou 350116， China; 2.Fujian Provincial Key Laborabory of Information Processing and Intelligent Control， Minjiang University， Fuzhou 350108， China）

Abstract：

Aiming at the nondeterministic polynomially problem（NP） characteristics of the tourist route planning problem and taking into account the diversity of cultural connotations of cultural tourist attractions， a genetic algorithm that can effectively maintain the diversity of the population is proposed to solve the tourist route planning problem. In order to solve the local optimization problem of the traditional genetic algorithms， the improved algorithm uses the Jaccard coefficient to generate the initial population and thus improves the population quality; After crossover operation， the multiple mutation operators are used to generate multiple offsprings， and the superior individuals of the offsprings and parents are retained， thus generating a new population and maintaining the diversity of the population in the evolutionary process. The experimental results show that the proposed algorithm can solve the tourism route planning problem more effectively.

Key words：

cultural tourism route planning; genetic algorithm; Jaccard coefficient; mutation operator; population diversity