張瑞姣 陳崇成 黃正睿 方薈

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

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

中圖分類號(hào)：TP18;K909

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

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

目前，TTDP的求解方法主要包括精確算法、啟發(fā)式算法和智能化元啟發(fā)式算法。其中，精確算法雖然能得到精確的解，但其搜索能力較差，只能適用于小規(guī)模的POI規(guī)劃[4]。啟發(fā)式算法能夠在短時(shí)間內(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)用于各個(gè)領(lǐng)域，例如組合優(yōu)化、生產(chǎn)調(diào)度等。但GA也存在固有的弊端，種群會(huì)在進(jìn)化過程中因多樣性的減少而造成過早收斂問題，也稱局部最優(yōu)問題[10]。因此，保證種群多樣性以避免算法陷入局部最優(yōu)。國內(nèi)外學(xué)者對(duì)于上述GA問題的解決研究可大致分為兩類：一是提高初始種群質(zhì)量;二是保持進(jìn)化中種群多樣性等。LI等[11]提出了基于信息熵與博弈論的混合GA（hybrid genetic algorithm，HGA），利用信息熵生成初始種群以提升其多樣性，避免算法陷入局部最優(yōu)解。譚文安等[12]利用混沌理論在GA初始種群獲得更優(yōu)秀的初始群體， 從而提高算法效率。SUN等[13]提出了利用余弦相似性理論對(duì)相鄰種群間的多樣性和相似性進(jìn)行限定，通過對(duì)交叉和變異概率的自適應(yīng)調(diào)整，保持進(jìn)化過程中的種群多樣性，提高算法的收斂和全局最優(yōu)解。WANG等[14]提出了基于多子代的GA（multi-offspring genetic algorithm，MO-GA），利用多個(gè)交叉算子產(chǎn)生多個(gè)子代種群以提高種群子代的多樣性，解決旅行商問題，使得可行解更加接近最優(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)中遵義會(huì)議為例，對(duì)比提出算法與GA求解模型，證明了所提算法的優(yōu)越性。

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

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

Topentime≤Tarrivetime≤Tclosetime （1）

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

1.1 問題描述

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

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

定義1 景點(diǎn)信息。對(duì)于每一個(gè)景點(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 交通時(shí)間ttr。ttr為兩部分，分別是ttru和ttrs。對(duì)于線路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á)時(shí)間ta。ta對(duì)于不同時(shí)段的景點(diǎn)有不同的數(shù)學(xué)表達(dá)式。對(duì)于多日旅程，旅行第一天選定的第一景點(diǎn)的到達(dá)時(shí)間如式（5）所示，其余旅行新一天中第一個(gè)景點(diǎn)的到達(dá)時(shí)間如式（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 游客總旅行時(shí)間T。T由游客的交通時(shí)間和景點(diǎn)游覽時(shí)間組成，對(duì)于線路c={s1，s2，…，sk}，k=1，2，…，n，k≤n，則

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

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

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

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

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

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

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

1.2 OPTW模型

OPTW模型以綜合線路評(píng)分為目標(biāo)，充分考慮游客偏好、旅游時(shí)間等因素，從而求解更為合理的旅游線路。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要滿足游客的旅行總時(shí)間要求;式（13）表示對(duì)景點(diǎn)是否游覽標(biāo)注;式（14）表示更為嚴(yán)格的時(shí)間窗控制;式（15）表示游客從起始位置到首個(gè)景點(diǎn)的交通時(shí)間應(yīng)在某個(gè)時(shí)間段;式（16）表示一個(gè)假設(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相似度得到個(gè)體間的相似性，然后通過Jaccard距離計(jì)算個(gè)體間的差異。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分別為初始種群中的個(gè)體;M為種群規(guī)模。個(gè)體間的Jaccard距離與Jaccard相似度相反：J（pi，pi+1）越大表明個(gè)體間基因的重疊率越高，個(gè)體越相似，反之則差異越大;而D（pi，pi+1）越大，表明個(gè)體間差異越大。

2.1.2 多子代策略

根據(jù)WANG等[14]提出的多子代策略，在交叉算子后增加多個(gè)變異算子產(chǎn)生多個(gè)子代個(gè)體，從父代與子代個(gè)體中選擇適應(yīng)度最好的個(gè)體組成新種群。突變算子是一種維持從一個(gè)種群到下一個(gè)種群的遺傳多樣性的操作[20]，則多個(gè)突變算子可以增加種群多樣性。本文選擇常用的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個(gè)變異位置的基因插入第1個(gè)變異位置基因之后。

2.2 算法流程

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

MMGA的具體步驟如下：

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)與結(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個(gè)景點(diǎn)數(shù)據(jù)。對(duì)長征旅游景點(diǎn)等級(jí)狀況進(jìn)行統(tǒng)計(jì)，其中，國家4A級(jí)和5A級(jí)景點(diǎn)的數(shù)量分別為26個(gè)和4個(gè)，國家級(jí)文物保護(hù)單位70個(gè)。長征景點(diǎn)簡介信息是由景點(diǎn)的位置、基本情況及涉及的長征人物、時(shí)間等組成的文化文本，以福緣橋景點(diǎn)為例，如圖2所示。線路規(guī)劃時(shí)需要考慮景點(diǎn)的相關(guān)屬性信息，則景點(diǎn)所含信息見表2。

3.1.2 案例說明

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

3.2 實(shí)驗(yàn)與結(jié)果分析

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

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

3.2.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

4 結(jié)論與展望

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

參考文獻(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ì)算機(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ì)算機(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]王福林， 付曉明， 朱會(huì)霞， 等. 基于兩點(diǎn)交叉多子代遺傳算法[J]. 東北農(nóng)業(yè)大學(xué)學(xué)報(bào)， 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ì)算機(jī)工程與應(yīng)用， 2018， 54（20）： 1-13.

[18]黃細(xì)嘉， 宋麗娟. 紅色旅游資源構(gòu)成要素與開發(fā)因素分析[J]. 南昌大學(xué)學(xué)報(bào)（人文社會(huì)科學(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]趙福超. 遵義會(huì)議前后六次政治局會(huì)議的內(nèi)在歷史聯(lián)系[J]. 吉首大學(xué)學(xué)報(bào)（社會(huì)科學(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