樊 丹 史晉娜 許 霞

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

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

1 問題描述

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

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

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

2 遺傳算法設(shè)計(jì)

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

2.1 染色體的編碼與解碼

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

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

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

(1)

式(1)中，D(i,j)表示第i個(gè)景點(diǎn)和第j個(gè)景點(diǎn)的實(shí)際距離。

2.3 選擇算子

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

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

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

(2)

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

2.3.2 按輪盤賭的方式對(duì)其余的個(gè)體進(jìn)行累計(jì)概率選擇，最終生成下一代的個(gè)體

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

2.4 交叉和變異算子

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

2.5 終止原則

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

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

3.1 案例背景

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

3.2 旅游景點(diǎn)篩選

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

3.2.1 定性方法

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

3.2.2 景點(diǎn)綜合評(píng)價(jià)模型

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

(3)

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

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

(4)

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

3.2.3 景點(diǎn)篩選結(jié)果

通過計(jì)算可得35個(gè)景點(diǎn)的時(shí)間可達(dá)性系數(shù)，綜合考慮景點(diǎn)等級(jí)、門票費(fèi)用、時(shí)間限制等影響因素，最終選擇綜合評(píng)價(jià)值排名前8的景點(diǎn)，景點(diǎn)綜合評(píng)價(jià)值見表1。

表1 景點(diǎn)綜合評(píng)價(jià)指標(biāo)

3.3 遺傳算法的仿真實(shí)驗(yàn)結(jié)果

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

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

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

3.3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

圖3 遺傳進(jìn)化路線

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

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

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

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

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

表4 配置環(huán)境

4.2 界面設(shè)計(jì)實(shí)施

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

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

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

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

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

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

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

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

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

圖6 其他功能界面運(yùn)行

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

4.3.1 系統(tǒng)測(cè)試

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

4.3.2 測(cè)試結(jié)果分析

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

4.3.3 用戶使用

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

5 結(jié)論與展望

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