游行鍵 張建軍

(同濟大學 經濟與管理學院，上海 200092)

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

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

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

2 階段1：目標學校評價

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

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

表1 變量解釋

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

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

表2 旋轉后的成分矩陣

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

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

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

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

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

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

圖1 聚類結果散點圖

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

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

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

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

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

圖2 大學分布矩陣

3 最短路徑規(guī)劃

3.1 問題描述與假設

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

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

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

(1)

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

為了明晰問題，補充如下假設：

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

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

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

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

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

3.2 游學路線規(guī)劃模型構建

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

(2)

則游學問題的目標函數(shù)為：

(3)

約束條件為：

(4)

(5)

(6)

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

3.3 蟻群算法設計

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

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

Step 2：對種群中每一個染色體計算適應度；

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

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

3.4 仿真結果分析

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

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

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

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

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

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

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

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

(7)

(8)

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

(9)

(10)

計算結果如下表所示：

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

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

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

圖5 改進的遺傳算法的最佳結果和搜索過程

4 總結和討論

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

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