基于聚類分析和遺傳算法的國際游學(xué)路線規(guī)劃研究：以英國為例

游行鍵 張建軍

(同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海 200092)

國際游學(xué)，指的是通過參觀國外高校獲得知識和體驗的游學(xué)活動。隨著社會和經(jīng)濟(jì)的發(fā)展，國內(nèi)游學(xué)教育快速增長，在2019年達(dá)到3121萬人次的用戶規(guī)模，其中國際游學(xué)以每年10%的增速成為主要增長點。在快速增長的同時，學(xué)生及家長對行程安排、游學(xué)時間等要求也越來越高，研學(xué)產(chǎn)品質(zhì)量不高成為一大問題，提升游學(xué)服務(wù)質(zhì)量勢在必行。與傳統(tǒng)旅游路線規(guī)劃相比，游學(xué)路線規(guī)劃雖然面臨著學(xué)生與家長個性化需求和時間約束等多種挑戰(zhàn)，但由于高校有排名等公開數(shù)據(jù)，以及結(jié)構(gòu)化的數(shù)據(jù)資料，使得基于數(shù)據(jù)分析的精準(zhǔn)路線規(guī)劃成為可能。相應(yīng)地，當(dāng)前基于大數(shù)據(jù)的游學(xué)路線規(guī)劃也成為改善游學(xué)服務(wù)質(zhì)量的重要方向。

另一方面，游學(xué)作為一類高速發(fā)展的新興產(chǎn)業(yè)，目前相關(guān)研究還較為滯后。尚夢杰通過對英國歐陸游學(xué)進(jìn)行研究，認(rèn)為游學(xué)是突破應(yīng)試教育的一種學(xué)習(xí)方式，但我國游學(xué)產(chǎn)業(yè)還不夠成熟，需要不斷改善產(chǎn)品質(zhì)量。陳東軍等通過梳理以“研學(xué)旅行”、“游學(xué)”等話題為關(guān)鍵詞的文章，認(rèn)為研究的缺失和游學(xué)產(chǎn)業(yè)的蓬勃發(fā)展形成了矛盾，并認(rèn)為游學(xué)產(chǎn)品開發(fā)等方向是今后相關(guān)研究的方向。McGladdery等人認(rèn)為研學(xué)旅行行業(yè)的研究跟不上目前產(chǎn)業(yè)發(fā)展的步伐，教育旅行除了對個人發(fā)展有利外，還對培養(yǎng)開放、寬容的全球公民有益。諶春玲預(yù)測我國留學(xué)市場規(guī)模可能達(dá)到3000億元并快速增長，但是認(rèn)為產(chǎn)品設(shè)計需要改善，游學(xué)選校靈活性差、路線設(shè)計不合理等問題給國際游學(xué)市場帶來挑戰(zhàn)。Abubakar等人調(diào)查了各國學(xué)生參與游學(xué)的動機(jī)，發(fā)現(xiàn)參與游學(xué)的理由從未來工作和教育質(zhì)量到獲得簽證、了解當(dāng)?shù)匚幕鹊雀鞑幌嗤?。該研究從?cè)面應(yīng)證了基于大數(shù)據(jù)和算法選擇個性化游學(xué)目的地的重要性。吳水田等通過情境認(rèn)知理論研究研學(xué)旅行如何實現(xiàn)教育功能，認(rèn)為學(xué)生是在和環(huán)境的互動中學(xué)習(xí)的，所以課程設(shè)計十分重要，應(yīng)該合理的選擇游學(xué)的目的地。

在路線規(guī)劃方面，目前人們主要關(guān)注旅游景點的最優(yōu)最短路線，如：李景文等使用改進(jìn)的模擬退火算法解決游客在陌生城市旅游時路線定制問題，并通過混沌尋優(yōu)進(jìn)行初始溫度設(shè)定，降低了陷入局部最優(yōu)的可能性。勞國煒通過把游客分為一日游和多日游，制定不同的路線來解決高峰期的景區(qū)擁堵問題，以鼓浪嶼為例使用了其他算法和其改良后的蟻群算法進(jìn)行比較，得出了其方法可以明顯降低擁堵的結(jié)論。周福來通過粒子群算法，解決了暑期旅行如何達(dá)到最短路線的問題。在算法的比較方面，Halim等人比較了6種用于解決TSP問題的啟發(fā)式算法，其中遺傳算法在計算時間、平均結(jié)果和解的方差方面表現(xiàn)優(yōu)異，因為有交叉和變異算子存在，搜索能力較強(qiáng)，在大規(guī)模問題上可以得到比較滿意的解。

2 階段1：目標(biāo)學(xué)校評價

2.1 評價數(shù)據(jù)基礎(chǔ)：QS世界大學(xué)排名

本文采用QS世界大學(xué)排名作為學(xué)校評價的數(shù)據(jù)基礎(chǔ)。這是英國公司Quacquarelli Symonds發(fā)表的權(quán)威大學(xué)排行榜，從2004年開始對全球大學(xué)開始排名。QS排名與世界大學(xué)學(xué)術(shù)排名和《泰晤士報》高等教育一樣，被認(rèn)為是全球三大閱讀量最高的大學(xué)排名之一。QS排名提供的變量如下表所示，其中排名是定序數(shù)據(jù)，其他得分以100分為滿分。

表1 變量解釋

2.2 對數(shù)據(jù)集的因子分析

本次數(shù)據(jù)中除了所在國家之外都是數(shù)值型變量，使用從教育質(zhì)量排名到專利排名的八個變量進(jìn)行因子分析。年因子載荷矩陣使用方差最大法進(jìn)行旋轉(zhuǎn)，使得每個新變量重疊的信息能夠最少，旋轉(zhuǎn)后的矩陣如下表所示：

表2 旋轉(zhuǎn)后的成分矩陣

提取方法：主成分分析法。旋轉(zhuǎn)方法：凱撒正態(tài)化最大方差法。旋轉(zhuǎn)在3次迭代后已收斂

從上表可以看出第一個指標(biāo)F1主要是由學(xué)術(shù)聲譽(yù)得分(Academic Reputation)，雇主聲譽(yù)得分(Employer Reputation)，師生比得分(Faculty Student)等方面組成的，這個指標(biāo)越高，該學(xué)校在學(xué)術(shù)和就業(yè)方面的聲譽(yù)越好。綜上所述，F(xiàn)1這一指標(biāo)可以命名為綜合實力。

第二個指標(biāo)主要由國際學(xué)生得分(International Students)，國際教師得分(International Faculty)，每個教師的平均引用(International Faculty)和系數(shù)為0.269的學(xué)術(shù)聲譽(yù)得分(Academic Reputation)組成，這一指標(biāo)主要反映了國際化程度和單個教師的學(xué)術(shù)實力，對于之后想在本地就業(yè)的同學(xué)，該指標(biāo)影響較小。綜上所述，F(xiàn)2這一指標(biāo)可以命名為國際化程度。

綜合以上信息，兩個指標(biāo)分別命名為綜合實力和國際化程度。

2.3 對數(shù)據(jù)集的聚類分析

本次數(shù)據(jù)集較小，僅僅選取了英國地區(qū)的前49所大學(xué)，覆蓋至QS排名前485的英國所有學(xué)校，使用K-Means算法把學(xué)校聚類成三類，可以得到下圖。

圖1 聚類結(jié)果散點圖

從上圖可以得出英國的學(xué)校大致可以分為三類，第一類是F1和F2指數(shù)都較高的學(xué)校，這類學(xué)校綜合實力強(qiáng)勁，學(xué)術(shù)聲譽(yù)和就業(yè)方面的雇主聲譽(yù)都很好。同時這類學(xué)校國際化程度高，對于未來想要繼續(xù)在其他國家深造的同學(xué)而言具有優(yōu)勢。于此同時，從上圖還可以看出第二個趨勢是有一類學(xué)校F1適中但是F2低，還有一類學(xué)校F2適中F1較低。上圖可以看出英國高?；旧鲜欠譃槿齻€不同角度，所以本文使用K-Means聚類將其分為三類，分別稱之為C1、C2、C3，分類后C1到C3分別有17、16、16所學(xué)校。分類的結(jié)果如表3所示.

從表3可知，C1類總分(Overall Score)最高，達(dá)到74.65分，而第二類與第三類總分接近，都為38分左右。C1類排名平均值為52名，涵蓋了英國的主要名校，C2類QS排名平均為183名，C3類綜合排名為375名。其中C1類代表了英國的知名高校，綜合實力和國際化程度都比較強(qiáng)，C2類代表英國第二類高校，該類高校國際化程度很高，單個教師的文章引用也很強(qiáng)，導(dǎo)致綜合排名較高。C3類高校雖然排名不高，但是其綜合實力較強(qiáng)，只是國際化水平偏低拉低了排名。

表3 各聚類的參數(shù)平均值

綜上所述，C1類高校是國際化程度高、綜合實力強(qiáng)的名校，適合各項水平都很高的學(xué)生游學(xué)。C2類高校排名適中，綜合實力不如前兩類高校，但是國際化程度高，適合想要體驗國際化生活的學(xué)生。C3類高校屬于“性價比”較高的高校，該類學(xué)校雖然排名較低，但是學(xué)術(shù)聲譽(yù)、雇主聲譽(yù)都很好，綜合實力強(qiáng)。主要拉低排名的因素是國際化水平，該類高校特別適合希望留學(xué)之后留在英國工作、生活的同學(xué)選擇。

通過之前的聚類可以得知，高?？梢员环殖扇?，其中第一類是綜合實力和國際化程度都強(qiáng)的名校，第二類是國際化程度高，綜合實力較弱的高排名學(xué)校，第三類是QS排名底，但是實力較好的“性價比”高校。使用一個矩陣描述這三類英國高校，如下圖所示：

圖2 大學(xué)分布矩陣

3 最短路徑規(guī)劃

3.1 問題描述與假設(shè)

由于當(dāng)前國際游學(xué)通常有明確的目標(biāo)學(xué)校需求，大多數(shù)游學(xué)人群是需要參觀名校，因此接下來本文選取圖2中C1類17高校作為參觀的目標(biāo)，并基于公開數(shù)據(jù)探索個性化的最短環(huán)游路徑。

將選中的所有學(xué)校環(huán)繞一圈屬于旅行商問題，簡稱為TSP，這樣的問題是給定一系列城市和城市間的距離，求訪問每一個城市的最短回路，是組合優(yōu)化中的NP-Hard問題。其數(shù)學(xué)模型可以表示為在一個城市集C=(c0,c1,…,cn)中每一對城市距離為d(ci,cj)∈R^+，求經(jīng)過C中每一城市的最短路徑R=(cm0,cm1,…,cmn)，使得：

min∑n-1i=1d(cmi,cmi+1)+d(cmi-1,cm0)

(1)

旅行商問題有對稱和非對稱兩種，在國際游學(xué)問題中通常設(shè)定國際往返的距離相同，為對稱的TSP問題。

為了明晰問題，補(bǔ)充如下假設(shè)：

(1)忽略道路、河流等造成的誤差，用兩點之間的直線距離計算兩點的運(yùn)輸距離；

(2)使用經(jīng)緯度計算兩點的近似距離；

(3)游學(xué)活動從C1類某個大學(xué)出發(fā)，最后回到該城市，并且必須經(jīng)過且只經(jīng)過所有篩選出的大學(xué)；

(4)游學(xué)的路線只形成一個閉圈；

(5)游學(xué)路線中往來距離相等。

3.2 游學(xué)路線規(guī)劃模型構(gòu)建

待游歷的n個學(xué)校記為一個頂點集合V=(V1,V2,…,Vn+1)；學(xué)校之間兩兩相連記為邊集合E=(Vij),i,j∈(1,2,…,n+1)；學(xué)校i與學(xué)校j之間距離為dij。記：

(2)

則游學(xué)問題的目標(biāo)函數(shù)為：

(3)

約束條件為：

(4)

(5)

(6)

其中式(4)和(5)表示每個節(jié)點只有一條邊進(jìn)、一條邊出，式(6)表示沒有子回路產(chǎn)生。

3.3 蟻群算法設(shè)計

TSP問題是NP-Hard問題，求解最優(yōu)解難度較大，本文采用遺傳算法求解，基本步驟如下：

Step 1:對問題進(jìn)行編碼，給出有N個個體的初始種群POP(1)；

Step 2：對種群中每一個染色體計算適應(yīng)度；

Step4：通過交配，得到有N個染色體的交配后種群CrossPOP(t+1)；

Step5：以某個概率p，使染色體的基因發(fā)生變異，記為MutPOP(t+1)，變異后的種群為新種群POP(t+1)，返回Step2

3.4 仿真結(jié)果分析

基于C1中的17個學(xué)校，位置由其經(jīng)緯度決定，初始種群大小選擇10，不同迭代次數(shù)、交叉和變異概率的結(jié)果如下：

表4 不同參數(shù)下的計算結(jié)果

圖3 遺傳算法所得最優(yōu)路徑圖和搜索過程

使用MATLAB編程求解得到表3的結(jié)果，可以看到交叉概率在0.5，變異概率在0.3時得到了最優(yōu)的結(jié)果，觀察圖4的搜索過程可以看到，最優(yōu)解在迭代超過250次之后幾乎沒有改變。本算法在多次迭代之后陷入了局部最優(yōu)，算法沒有進(jìn)行有效的探索。考慮到不同游學(xué)人群會在不同學(xué)校組中尋找最優(yōu)路線，應(yīng)增加算法的搜索能力，避免陷入局部最優(yōu)成了亟待解決的問題。

圖4 循環(huán)200次時最優(yōu)路徑搜索過程

3.5 優(yōu)化后仿真結(jié)果分析

為了解決固定參數(shù)遺傳算法后期搜索能力弱、容易陷入局部最優(yōu)的問題，本文通過可變參數(shù)的遺傳算法來求解最小的路徑，參考于瑩瑩等人2014年提出的基于自適應(yīng)交叉和變異算子的改進(jìn)方法對算法進(jìn)行優(yōu)化。

在交叉算子方面，早期應(yīng)該交換概率較大，讓種群能夠快速搜索各種解，但是在后期，交換概率應(yīng)該逐漸減小，保留性能較好的基因。為了既讓早期保持較大交換概率以保證搜索范圍，又讓后期交換概率減小以保留優(yōu)質(zhì)解，本文將交換概率pc的表達(dá)式設(shè)置為：

(7)

(8)

在變異概率方面，早期種群變異概率應(yīng)該較小，讓方法專注基因的提升，后期的變異概率應(yīng)當(dāng)逐漸增大，讓解不會過早收斂，跳出局部最優(yōu)，變異概率具體取值如下：

(9)

(10)

計算結(jié)果如下表所示：

表5 改進(jìn)的遺傳算法在不同參數(shù)下的計算結(jié)果

可以看到在表格中第二次嘗試達(dá)到了最優(yōu)，其搜索過程如圖5所示。

和圖5相比，改進(jìn)的自適應(yīng)參數(shù)遺傳算法在迭代后期仍舊能夠大范圍搜索，最終找到了比原算法更優(yōu)的解。在解決游學(xué)最短路徑問題上，使用基于自適應(yīng)算子的遺傳算法求解有著更好的穩(wěn)定性。

圖5 改進(jìn)的遺傳算法的最佳結(jié)果和搜索過程

4 總結(jié)和討論

針對國際游學(xué)路線規(guī)劃問題，本文綜合運(yùn)用機(jī)器學(xué)習(xí)和數(shù)學(xué)規(guī)劃方法進(jìn)行分析，首先基于世界大學(xué)排名的數(shù)據(jù)集，采用因子分析方法構(gòu)建了相對簡潔的指標(biāo)體系，之后使用聚類分析方法對學(xué)校進(jìn)行類型劃分，實現(xiàn)了向游學(xué)者進(jìn)行推薦的游學(xué)學(xué)校集合。在此基礎(chǔ)上，如何環(huán)游目標(biāo)學(xué)校成為了一類TSP問題，本文首先使用傳統(tǒng)遺傳算法求解，再通過優(yōu)化后的遺傳算法解決了在迭代后期收斂的問題。

在后續(xù)進(jìn)一步的研究中，可以考慮在更為個性化的需求標(biāo)簽(如GPA、TOEFL和GRE成績，錄取概率等)之下對目標(biāo)學(xué)校進(jìn)行評價、劃分，并