面向旅游行程規劃的交互式多智能體遺傳算法
2008-12-31 00:00:00陸青梁昌勇黃永青張俊嶺
計算機應用研究 2008年11期
(1.合肥工業大學 計算機網絡系統研究所， 合肥 230009； 2.銅陵學院 計算機系， 安徽 銅陵 244000)
摘要：結合多智能體技術和交互式遺傳算法，提出了一種面向旅游行程規劃問題的交互式多智能體遺傳算法。算法通過讓固定在網格上的智能體展開進化和競爭行為來尋找滿意行程。在算法每代中，用戶只需評價選擇一個當代最優智能體，就可計算得到當代所有智能體的能量，減少了評價次數，有效緩解了用戶在評價過程中的疲勞問題。仿真實驗驗證了該算法在解決旅游行程規劃問題中的可行性和有效性，并對問題規模表現出很好的可伸縮性。
關鍵詞：交互式遺傳算法； 多智能體； 用戶疲勞； 旅游行程規劃
中圖分類號：TP18; TP301.6文獻標志碼：A
文章編號：1001-3695(2008)11-3311-03
Interactive multi-agent genetic algorithm for travel itinerary planning
LU Qing1， LIANG Chang-yong1， HUANG Yong-qing2， ZHANG Jun-ling1
(1.Institute of Computer Network， Hefei University of Technology， Hefei 230009， China; 2. Dept. of Computer， Tongling University， Tongling Anhui 244000， China)
Abstract:The paper proposed an interactive multi-agent genetic algorithm for the travel itinerary planning problem， which combined the multi-agent technology with the interactive genetic algorithm. The algorithm made agents fixed on a lattice evolve and compete in order to search the satisfactory itinerary. In every generation， a user only needed to evaluate and find out an agent which was the current best one， and then energies of all agents in this generation could be calculated automatically， which reduced the user’s evaluations and contributes to relieve the human fatigue in the evaluation process. The simulation experiment shows that the algorithm is a feasible and effective method for the travel itinerary planning problem， and has good scalability for the problem’s size.
Key words：interactive genetic algorithm; multi-agent; human fatigue; travel itinerary planning
0引言
旅游行程規劃問題(travel itinerary planning problem，TIPP)是對旅行商問題(TSP)的一個拓展，考慮的因素不僅包括路程、時間等客觀因素，還需考慮個人的偏好、情感和感性(KANSEI)等主觀因素。由于其目標函數不能完全建立，成為了一類目標函數未知且非常難以求解的復雜多準則決策問題[1]。
交互式遺傳算法(interactive genetic algorithm，IGA)利用人的主觀評價作為適應度[2]，實現了主觀心理空間和客觀特征空間的非線性映射，不僅具有傳統遺傳算法(GA)的優點，而且具備與決策者交互的機制，適合處理適應度函數難以建立的優化問題，得到了廣泛的應用[3~7]。文獻[8]使用IGA求解TIPP取得了一定的效果，驗證了IGA也是適合處理TIPP的技術方法。然而在IGA的求解過程中，用戶疲勞問題和進化效率問題是制約IGA的瓶頸問題，需要探索新的改進IGA來更好地求解TIPP。
近來，分布式人工智能中基于智能體(agent)的計算已經應用于計算機學科的各個領域，這些能夠感知環境并反作用于環境的物理的或虛擬的智能體涌現出相當大的智能，可以對復雜問題進行有效求解[9，10]。本文結合多智能體技術與交互式遺傳算法，提出一種面向旅游行程規劃問題的交互式多智能體遺傳算法(interactive multi-agent genetic algorithm，IMAGA)，能夠有效提高IGA的進化效率，緩解用戶在評價過程中的疲勞問題。仿真實驗驗證了其可行性和有效性。
1旅游行程規劃問題
11一些基本概念的定義
在一個旅游景區，設有n個景點，景點集合為sight={si｜i=1，2，…，n}。
a)行程段：任意兩景點所組成的序偶。
b)行程T：景點的排列，表示對景點的訪問順序。T=(si1，si2，…，sin)，其中(i1，i2，…，i3)是(1，2，…，n)的一個排列。
c)單元屬性：景點上的信息，如景點的門票費用、到達景點的時間等。
d)雙元屬性：行程段上的信息，如從一個景點到達另一景點的距離、時間花費等。
e)可加屬性：單元、雙元屬性中可以累加的屬性，如景點門票和車費等，累加后成為行程總費用。
f)非可加屬性：單元、雙元屬性中不可累加的屬性，如到達景點的時間等。
g)行程屬性：旅游行程所展示的信息，是旅游者主要關心的屬性，如總的費用花費、總的時間花費等，也包括旅游者關心的非可加屬性。
12問題描述
在某一旅游景區，旅游者需要選擇一條行程來參觀各個景點，使自己感到滿意。旅游行程規劃就是要找出使旅游者滿意度達到最大的行程。
max H=φ(T)(1)
其中：T∈N，N為所有可能行程的集合；H為滿意度。目標函數不僅包括可以量化的指標，如行程的距離、時間花費、費用花費等；也包括不能或者難以量化的指標，如旅游者對到達景點時間的偏好等，所以函數φ不能完全表示出來，無法用解析方法求解得到最優旅游行程T*。
通過IGA的交互式機制，用戶可以人工地給予行程一評價值，引導問題向著用戶滿意行程的方向收斂，這一評價值就是引導IGA運算的適應度：
fitness(T)=ψ(attribute)(2)
其中：attribute是行程T的屬性集；函數ψ是用戶的心理偏好評價函數，即根據個人的知識、經驗和偏愛等對行程的各種行程屬性給予的綜合評價。
2交互式多智能體遺傳算法
21智能體及其相關行為
在IMAGA中，將行程個體作為智能體，用戶評價的個體適應度作為智能體能量。智能體生存的目的是增大并最大化用戶的滿意程度，并由此帶給自身具有優勢的能量。所有智能體都生存在一種結構為m×n(m，n≥3)的環形智能體網格上，并與局部鄰域內的智能體發生作用，該鄰域稱為智能體的競爭鄰域。競爭鄰域的規模根據具體問題而有所不同，本文假設智能體能夠感知上、下、左、右、左上、右上、左下、右下八個相鄰的智能體，并只能與這八個智能體發生作用。
智能體有進化和競爭兩種行為，以實現生存和提高自身能量。在進化行為中，任意智能體agentij與其競爭鄰域中的最優智能體以概率Pc進行交叉，鄰域最優智能體保持不變；agentij由交叉子代替換，待交叉完成后，再以概率Pm進行變異。在競爭行為中，若智能體agentij的能量不小于其競爭鄰域中的任意一個智能體，則其可以生存；否則將死亡，agentij由鄰域最優智能體所產生的子代替換。
22IMAGA算法描述
考慮到用戶一次比較評價太多的個體會產生極大的疲勞，算法的進化種群一般不宜過大。針對行程個體表現型的特點，本文IMAGA的種群規模取12，排成3×4的智能體網格結構。圖1給出了IMAGA的流程。
a)設置有關參數，包括交叉概率、變異概率等。
b)隨機生成12個行程個體，按3×4的智能體網格排列，形成初始種群。
c)用戶評價標記當代最優個體，產生適應度。
d)滿意判斷，若用戶對當代最優個體滿意，則結束；否則進入下一步。
e)終止代判斷，若算法已到最大進化代數，則結束；否則進入下一步。
f)進化(競爭)行為，進行智能體進化或競爭行為，兩種行為在迭代過程中交替進行，轉c)。
3算法改進策略
31適應度策略
雖然IMAGA的種群規模比較小，但如果每代都要用戶對所有個體進行評價打分，則用戶仍十分疲勞，若進一步通過減少種群規模來解決疲勞問題，則又會影響算法進化效果。本文采用相對距離適應度給定法[8]來計算適應度，減輕用戶疲勞。首先用戶選出一個當代最滿意的行程個體作為最優智能體，并給予固定的適應度值FITNESS，則其他智能體的適應度按下式計算：
fitness=FITNESS×(1-RD)(3)
其中：RD為智能體與最優智能體間的相對距離。假設兩行程T1、T2，其相對距離計算如下：
RD(T1，T2)=w1[(L-Ls)/L]+w2[S/L](4)
其中：w1+w2=1，w1，w2∈R，通常w1=w2=0.5；L為個體的長度；LS為T1、T2最長相同子路徑的長度；S為T1、T2最長相同子路徑的相對位移。假設:
T1=(a1，a2，…，ai，…，ai+m，…，an)
T2=(b1，b2，…，bi+k，…，bi+k+m，…，bn)
其中：(ai，…，ai+m)和(bi+k，…，bi+k+m)是T1、T2最長相同子路徑，則其相對位移為S=｜k｜。
相對距離適應度給定法利用相對距離來度量其他智能體與當代最優智能體的相似程度，進而計算適應度。相對距離越小，則相似程度越大，適應度也相應越大。
32交叉策略
由于行程個體編碼的特點，按常規交叉會產生一些不符合行程定義的子代個體。為使子代能夠符合實際的行程路線，定義了一種新的交叉策略，假設待交叉個體：
T1=(a1，a2，…，ak，…，an)
T2=(b2，b2，…，bk，…，bn)
其中：T1第k(1≤k≤n-1)個基因座后為交叉點。交叉方法如下：
令C1=(ak+1，ak+2，…，an)，在T2中找出所有C1中的元素，仍按T2中的先后順序組成C2，交換C1、C2分別插入T1、T2中，得到交叉后的子代個體。
33變異策略
假設T=(b1，b2，…，bk，…，bn)對第k位基因座進行變異，則變異后的個體為
T′=b1，…，bk-1，bk+1，…，bk+j，bk，bk+j+1，…，bn); j≤n-k
(b1，…，bj-(n-k)，bk，bj-(n-k)+1，…，bk-1，bk+1，…，bn);
j＞n-k(5)
其中：j(1≤j≤n-2)為隨機生成的變異基因座移動位數。按這一變異策略產生的新個體符合行程定義，對應于一條實際的行程路線。
34死亡替換策略
競爭行為中，若智能體agentij死亡，則其由鄰域最優智能體所產生的子代替換，子代產生如下
agent′ij=agentrandom； r＜λ
clone(agentmax)； r≥λ(6)
其中：λ是控制種群多樣性的參數，λ∈[0，1]；r為算法產生的隨機數。當r＜λ，子代為隨機產生的智能體agentrandom；當r≥λ，子代是鄰域最優智能體agentmax產生的clone(agentmax)，它表示agentij與agentmax最長相同子路徑按agentmax中的情況保持不變，其他元素隨機排列填充所組成的新智能體。
通過這樣的死亡替換，既保持了種群多樣性，又能使替換的新智能體繼承了鄰域最優智能體的優良特性，有利于加快算法全局收斂速度。
4仿真實驗
以“合肥一日游”為應用研究背景，實現了基于IMAGA的旅游行程規劃實驗系統。根據旅游者所關心的內容，行程屬性選取了總距離、總花費、行程時間、總游玩時間、參加活動數以及達到各個景點的時間等進行統計，采用如圖2的行程個體表現型。IMAGA種群規模為12，按3×4的格式排列。為驗證IMAGA的有效性，將其與標準交互式遺傳算法(SIGA)進行比較。其中IMAGA參數設置為：交叉概率Pc=0.6，變異概率Pm=0.1，λ=0.3；SIGA參數設置為：交叉概率Pc=0.6，變異概率Pm=0.1，種群規模為8，采用比例選擇策略。算法結束方式都為用戶選擇滿意行程個體的手動結束方式，并都采用最優保留策略。
分別選取5~8個景點數進行實驗，兩種算法各進行五次實驗，實驗數據見表1、2，只統計用戶評價次數。IMAGA中評價次數是指用戶在算法過程中標記選擇每代最優個體的次數；SIGA中評價次數是指用戶在算法過程中評價個體并打分的次數。由于SIGA每代用戶都要進行八次評價打分并給出具體的適應度，評價次數多，用戶極易感到疲勞；而當SIGA進化幾代后，種群個體間的相似程度較高，用戶極難分清孰優孰劣，更加重了疲勞感；由于行程屬性較多，在SIGA前后代的評價中，用戶很難把握一個統一的評價標準，極易產生適應度評價噪聲。而用戶在IMAGA中，無須對所有個體給出具體的適應度，而只需選出當代最優個體行程即可，不用人為地強制維持一個統一的評價標準，能夠有效減少適應度評價噪聲的產生。
從表1和2可以看出，本文IMAGA的評價次數明顯較少，在5~8個景點數實驗中分別是SIGA評價次數的22.3%、27.6%、23.9%和20.3%，求解效率相比SIGA有著顯著的提高，且IMAGA無須給出具體的評價值，只需標記選擇每代最優個體，能夠有效緩解用戶的疲勞。另外，隨著景點數的增加，問題復雜程度大大提高，問題方案的搜索空間增大很多，SIGA的評價次數增加非常大，而IMAGA的評價次數增加較少
，對問題規模表現出了很好的可伸縮性。
5結束語
本文結合多智能體技術和交互式遺傳算法，提出了一種面向旅游行程規劃問題的交互式多智能體遺傳算法(IMAGA)。通過算法的多智能體行為機制，IMAGA提高了算法進化效率；在每代中，IMAGA無須用戶給出個體具體的評價值，只需標記選擇每代最優個體，有效緩解了用戶的疲勞。仿真實驗驗證了IMAGA對于解決旅游行程規劃問題的可行性和有效性，并對問題規模表現出了很好的可伸縮性，具有較高的實際應用價值。
參考文獻：
［1］陳稼興， 許芳誠. 以交互式遺傳算法為基礎的多準則決策支持模型：旅游行程規劃個案研究[J]. 管理學報， 2001，18(4):639-665.
[2]TAKAGI H. Interactive evolutionary computation: fusion of the capabilities of EC optimization and human evaluation[J].//Proceedings of the IEEE， 2001，89(9):1275-1296.
[3]OHSAKI M， TAKAGI H. Application of interactive evolutionary computation to optimal tuning of digital hearing aids[C]//Proc of the 5th International Conference on Soft Computing and Information. Fukuoka:[s.n.]， 1998:849-852.
[4]BILES J A. Life with Genjam:interacting with a musical IGA[C]//Proc ofIEEE International Conference on Systems， Man， and Cybernetics. Tokyo:[s.n.]， 1999:652-656.
[5]胡靜， 陳恩紅， 王上飛. 交互式遺傳算法中收斂性及用戶評估質量的提高[J]. 中國科學技術大學學報， 2002，32(2): 210-216.
[6]王上飛， 王勝惠， 王煦法. 結合SVM的交互式遺傳算法及其應用[J]. 數據采集與處理， 2003，18(4):429-433.
[7]黃永青， 陸青， 梁昌勇，等. 交互式多智能體進化算法及其應用[J]. 系統仿真學報， 2006，18(7):2030-2032.
[8]許芳誠. 智能型多準則決策支持研究：以交談式遺傳算法為基礎的模型[D]. 桃園，臺灣: 國立中央大學， 2000.
[9]鐘偉才， 薛明志， 劉靜，等. 基于AER模型的multi-agent遺傳算法[J]. 模式識別與人工智能， 2003，16(4):390-396.
[10]鐘偉才， 劉靜， 劉芳，等. 組合優化多智能體進化算法[J]. 計算機學報， 2004，27(10):1341-1353.
