基于改進遺傳算法的研學(xué)旅行線路優(yōu)化與實現(xiàn)※

樊 丹 史晉娜 許 霞

(四川旅游學(xué)院，四川 成都 610100)

2013年國家出臺的《國民旅游休閑綱要(2013—2020年)》中提出“研學(xué)旅行”[1]一詞以來，以“文化體驗”與“教育”為側(cè)重點的研學(xué)旅行逐漸成為學(xué)者研究的新熱點，研學(xué)旅行正處于大有可為的發(fā)展機遇期。2016年教育部、國家發(fā)展改革委等15個部門印發(fā)的《關(guān)于推進中小學(xué)生研學(xué)旅行的意見》中強調(diào)，要以基地為重要依托，積極推動資源共享和區(qū)域合作，打造一批示范性研學(xué)旅行精品線路，逐步形成布局合理、互聯(lián)互通的研學(xué)旅行網(wǎng)絡(luò)[2]。合理的研學(xué)旅行線路是高效開展研學(xué)旅行活動的重要保障，因此打造研學(xué)旅行精品線路成為研學(xué)旅行組織者和旅游服務(wù)部門的迫切需求。

1 問題描述

目前，針對研學(xué)旅行線路的設(shè)計，研究者普遍從旅游資源開發(fā)、保護等角度對景點進行篩選和串聯(lián)設(shè)計，較少涉及運用智能優(yōu)化算法對研學(xué)旅行線路進行設(shè)計及優(yōu)化，幾乎沒有將研學(xué)旅行線路進行實景虛擬旅游的創(chuàng)新應(yīng)用。

設(shè)計最優(yōu)研學(xué)旅行線路的問題，可簡化為連接各旅游目的地的最短路徑問題(TSP旅行商問題)。最短路徑問題解決的是如何尋找到一條路徑，遍歷所有的節(jié)點，使路徑總長度之和達到最小值。國內(nèi)外的學(xué)者對最短路徑問題進行了深入的研究，應(yīng)用較為廣泛的智能優(yōu)化算法有:粒子群算法[3]、布谷鳥算法[4]、遺傳算法[5]、螞蟻算法[6]等。

由于遺傳算法的擇優(yōu)機制是一種“軟”政策，使它具有良好的通用性、并行性和穩(wěn)健性，因此本文選擇對遺傳算法的擇優(yōu)機制進行改進，以此來提高算法的全局搜索能力。本文整體結(jié)構(gòu)如下：建立時間可達性模型對研學(xué)旅行景點進行篩選；使用改進的遺傳算法對篩選出的優(yōu)質(zhì)研學(xué)旅行景點進行串聯(lián)和優(yōu)化；重點將遺傳算法應(yīng)用到Android平臺，設(shè)計實現(xiàn)一款智能手機端的研學(xué)旅行線路優(yōu)化軟件，供用戶和線路設(shè)計者以借鑒與參考。

2 遺傳算法設(shè)計

遺傳算法(GA)起源于對生物系統(tǒng)所進行的計算機模擬研究，20世紀(jì)70年代初期由美國密歇根大學(xué)的Holland教授首先提出，在一系列研究工作的基礎(chǔ)上，同世紀(jì)80年代由Goldberg進行歸納總結(jié)，最終形成了遺傳算法的基本框架。遺傳算法模擬的是生物界優(yōu)勝劣汰進化過程，從一個種群開始，重復(fù)執(zhí)行選擇、交叉和變異等遺傳算子對種群進行不斷進化，最后得到全局最優(yōu)解[7]。

2.1 染色體的編碼與解碼

本文采用路徑表示的符號編碼方法，即將景點編號編碼為基因，以景點編號遍歷的完整路徑編碼為染色體，這種編碼的方式由路徑染色體出發(fā)，便于通過快速解碼的方式得到相應(yīng)可行解。

2.2 適應(yīng)度函數(shù)

本文將n個景點的最優(yōu)旅行線路問題簡化為對稱型TSP問題，選用的適應(yīng)度函數(shù)為：

(1)

式(1)中，D(i,j)表示第i個景點和第j個景點的實際距離。

2.3 選擇算子

為了使群體中的優(yōu)質(zhì)個體得以保留，本文選用精英策略與輪盤賭組合選擇算子。

2.3.1 采用精英策略來保留優(yōu)質(zhì)個體

在每一代的進化過程中，對相對適應(yīng)度進行排序，以設(shè)置保護因子的方式，保留多個優(yōu)質(zhì)個體直接復(fù)制進入下一代，不參與交叉、變異等遺傳運算。個體的相對適應(yīng)度，計算式如下：

(2)

式(2)中，λ(xi)是第i個個體xi的相對適應(yīng)度；F(xi)是個體xi自身的適應(yīng)度。

2.3.2 按輪盤賭的方式對其余的個體進行累計概率選擇，最終生成下一代的個體

選用精英策略與輪盤賭組合改進的選擇算子，既可以保證優(yōu)質(zhì)個體被保留在下一代群體中，又可以避免某個局部優(yōu)質(zhì)個體不易被淘汰而快速擴散，提高了算法的全局搜索能力。

2.4 交叉和變異算子

由于普通交叉算子不適合解決TSP問題，本文采用二點交叉和逆轉(zhuǎn)變異的算子來進行產(chǎn)生新子代的操作，在一定程度上使最優(yōu)模式得以最大可能保留。

2.5 終止原則

對種群進行迭代，當(dāng)達到最大迭代次數(shù)后，即可輸出當(dāng)代最優(yōu)解和目標(biāo)函數(shù)值，結(jié)束遺傳算法。

3 遺傳算法求解及結(jié)果

3.1 案例背景

本文以成都市為例。成都市作為首批國家歷史文化名城，承載著四千余年的歷史，獨特的地理環(huán)境和悠久的歷史文化造就了成都市豐富的旅游資源，文化旅游特別是研學(xué)旅行發(fā)展?jié)摿薮?，現(xiàn)有人文景區(qū)景點172處[8]。

3.2 旅游景點篩選

本文使用定性和定量結(jié)合的方法來完成優(yōu)質(zhì)研學(xué)旅行景點的篩選與整理。

3.2.1 定性方法

針對研學(xué)旅行中旅行者對于出游需求、景點選擇的明確程度各有差異的情況，本文選擇的研學(xué)景點側(cè)重于節(jié)省出游路途時間與文化遺傳類景點。出于節(jié)省研學(xué)旅行時間的考慮，所選景點盡量避開交通擁堵的區(qū)域。研學(xué)旅行更多需要體現(xiàn)它的“教育”功能[9]，在旅行中感受文化的滋養(yǎng)與熏陶，而文化遺產(chǎn)類景點正好切合這一點。結(jié)合上述的兩個條件，對成都市172個人文景點進行首次篩選和整理，定性地選出35個文化遺產(chǎn)類景點。

3.2.2 景點綜合評價模型

運用景點綜合評價模型[10]對旅游景點進行定量計算與評價。通過量化各影響因素的權(quán)重，求解出景點的綜合評價值，客觀反映景點的“性價比”，選擇出優(yōu)質(zhì)研學(xué)景點。計算公式如下：

(3)

式(3)中，EV代表該景點的綜合評價值，其值越大表明該景點的“性價比”越高，wi代表第i個影響因素ci的權(quán)重，vi代表第i個影響因素ci的評價值。

假設(shè)研學(xué)旅行是以旅行大巴或私家車為交通工具，路況通暢，天氣等一切突發(fā)情況不納入考慮范圍。運用ArcGIS10.0軟件，對景點間的線路進行數(shù)字化處理，計算出各景點間的運行時間，得到各景點之間的最短通行時間矩陣。對各景點間的最短通行時間矩陣采用加權(quán)平均通行時間的計算，計算公式如下：

(4)

式(4)中，Tij為區(qū)域中景點i到景點j的最短通行時間，n為區(qū)域中參與分析景點的個數(shù)，Mij為景點i到景點j的權(quán)重系數(shù)，Ai為旅游景點i的時間可達性系數(shù)。

3.2.3 景點篩選結(jié)果

通過計算可得35個景點的時間可達性系數(shù)，綜合考慮景點等級、門票費用、時間限制等影響因素，最終選擇綜合評價值排名前8的景點，景點綜合評價值見表1。

表1 景點綜合評價指標(biāo)

3.3 遺傳算法的仿真實驗結(jié)果

3.3.1 遺傳算法參數(shù)選取

遺傳算法參數(shù)的選取會影響到最終輸出結(jié)果的優(yōu)劣，考慮仿真結(jié)果的客觀性，程序中初步選取的遺傳算法參數(shù)如表2所示。

表2 遺傳算法參數(shù)表

3.3.2 實驗結(jié)果

通過對優(yōu)選的8個研學(xué)景點進行時間、經(jīng)緯度等數(shù)據(jù)的采集，使用MATLAB R2017a對數(shù)據(jù)進行編碼、初始化以及遺傳等操作，得出優(yōu)化前后的研學(xué)旅行路徑圖如1、圖2所示。

圖1 遺傳算法優(yōu)化前路徑圖

圖2 遺傳算法優(yōu)化后路徑圖

本文因使用路徑染色體編碼的優(yōu)勢，可直接在可行解中得到從不同景點出發(fā)的最優(yōu)路線，如表3所示。

表3 最優(yōu)研學(xué)旅行線路

3.3.3 實驗結(jié)果分析

隨著進化代數(shù)的增加，最短路徑長度逐步下降，在進化至120代之后趨于穩(wěn)定，如圖3所示。

圖3 遺傳進化路線

由圖1、圖2、圖3的分析可以看出，本文中改進的遺傳算法可以有效解決研學(xué)旅行線路優(yōu)化問題，由此驗證了經(jīng)過改進的遺傳操作策略是可行與有效的。

4 Android終端程序設(shè)計與實現(xiàn)

為了使研學(xué)旅行者能更好地獲取旅游景點，更快捷地獲得最優(yōu)旅行線路等相關(guān)信息，達到集體和自主旅行的多重目標(biāo)。本小節(jié)將改進的遺傳算法應(yīng)用到Android平臺上，設(shè)計開發(fā)了一款智能手機端的研學(xué)旅行軟件，從遺傳算法的角度合理地減少旅行者在時間和經(jīng)濟等方面一些不必要的開支。

4.1 開發(fā)環(huán)境搭建

本文中選用Android Studio 2.3.3進行Android項目的開發(fā)，軟件配置環(huán)境如表4所示。

表4 配置環(huán)境

4.2 界面設(shè)計實施

4.2.1 系統(tǒng)功能設(shè)計

研學(xué)旅行APP主要以成都市周邊研學(xué)旅行線路優(yōu)化為例，其主要服務(wù)對象是研學(xué)旅行者，主要功能是為研學(xué)旅行者提供最優(yōu)旅行線路規(guī)劃、定位及景點查詢服務(wù)。系統(tǒng)功能設(shè)計如圖4所示。

圖4 研學(xué)旅行系統(tǒng)功能結(jié)構(gòu)圖

研學(xué)景點模塊是整個系統(tǒng)功能的核心模塊，包括研學(xué)景點概覽、智能規(guī)劃兩個子頁面。研學(xué)景點概覽頁面采用列表的形式展示各個研學(xué)景點介紹及圖片信息的選擇按鈕。智能規(guī)劃頁面通過研學(xué)線路智能規(guī)劃的選擇按鈕，主要展示利用改進的遺傳算法對研學(xué)景點的數(shù)據(jù)信息進行整合與計算，推送給用戶最優(yōu)的研學(xué)旅行行程總覽，實現(xiàn)實景虛擬旅游的創(chuàng)新運用。

4.2.2 用戶界面的設(shè)計實現(xiàn)

4.2.2.1 研學(xué)景點功能設(shè)計實現(xiàn)

研學(xué)景點模塊是系統(tǒng)的核心功能模塊。界面的編程在SpinnerActivity類中實現(xiàn)，在SpinnerActivity類中，分別對各個圖標(biāo)按鈕的點擊事件setOnItemClickListener()進行監(jiān)聽，并重寫onItemClick()方法。當(dāng)用戶進行選擇操作時，控制當(dāng)前Activity跳轉(zhuǎn)到具體的功能界面。該界面的運行效果截圖如圖5所示。

4.2.2.2 搜索景點與定位功能設(shè)計實現(xiàn)

搜索景點、定位模塊其主要作用是為用戶提供其他輔助功能，通過對百度地圖的二次開發(fā)實現(xiàn)該模塊的功能,可搜索成都及其他城市旅游景點信息及定位。界面的編程分別在Main3Activity及l(fā)ocationActivity類中實現(xiàn)，運行效果截圖如圖6所示。

圖6 其他功能界面運行

4.3 系統(tǒng)測試與測試結(jié)果分析

4.3.1 系統(tǒng)測試

對客戶端的測試主要分為功能測試、開發(fā)平臺測試兩個方面。在整個系統(tǒng)的開發(fā)階段，測試設(shè)備的類型包括Android虛擬機和Redmi Note3，測試平臺為:蒲公英內(nèi)測平臺。

4.3.2 測試結(jié)果分析

從測試結(jié)果來看，系統(tǒng)的界面功能模塊實現(xiàn)正常、運行穩(wěn)定，各項的測試結(jié)果均達到預(yù)期效果。特別是研學(xué)景點這一核心功能模塊，將本文所改進的遺傳算法應(yīng)用到系統(tǒng)中進行研學(xué)旅行線路優(yōu)化，及時推送給用戶有效地優(yōu)化旅游線路，輸出的詳細(xì)規(guī)劃結(jié)果更具智能化和人性化。

4.3.3 用戶使用

用戶只需通過掃描二維碼的形式免費下載使用，二維碼如圖7所示。

5 結(jié)論與展望

面對研學(xué)旅行組織者在線路規(guī)劃方面所遇到的困難與旅行者的個性化旅游需求現(xiàn)狀，本文利用改進的遺傳算法求解成都周邊研學(xué)旅行線路優(yōu)化問題，設(shè)計并實現(xiàn)了遺傳算法科學(xué)應(yīng)用到Android開發(fā)平臺的研學(xué)旅行APP。經(jīng)過嚴(yán)格的算法實驗與系統(tǒng)測試后，結(jié)果表明遺傳操作是有效的，研學(xué)旅行系統(tǒng)的功能模塊實現(xiàn)正確、運行穩(wěn)定。改進的遺傳算法對研學(xué)旅行線路優(yōu)化及研學(xué)旅行APP的設(shè)計與實現(xiàn)，使研學(xué)旅行線路規(guī)劃更加智能和實用，為研學(xué)旅行線路的設(shè)計優(yōu)化提供有力的支撐，具有較好的借鑒、參考意義。