结合AHP及GA的多准则决策支援系统模型个人行程规划应用解析

1、2002 年管理創新與新願景研討會I-27結合 AHP 及 GA 的多準則決策支援系統模型：個人行程規劃應用An Integrated Model Based on AHP and GA for supporting MCDM:An Application to Itinerary Planning許芳誠、簡宏陸 * 、廖暐朕、洪銘祥真理大學資訊管理系*住址：淡水鎮新民街 21號 3 樓*TEL ：2626-5307*Email ： ulgamma.tw摘要交談式遺傳演算法 (Interactive Genetic Algorithms ， IGA) 模式，能夠讓使用者邊尋邊選 、處理目 標函

2、數未知及樣本數大的問題。固然有這些優勢的存在， IGA 卻因為須與使用者作多次的互動， 而造成使用者負擔。因此，本研究提出一個結合階層式分析法 (Analytic Hierarchy Process， AHP) 與 遺傳演算法 (Genetic Algorithms ，GA) 的 AHP_GA 模型，以階層式分析模組替代原本需要使用者 每一代和 GA 互動並提供適應值的過程，藉以減少與使用者互動的次數，希望能讓改善原傳統 IGA 的缺 點。為了證明本研究的 AHP_GA 模型能有效地改善傳統 IGA 造成使用者的負擔，我們將會把 AHP_GA 模型與傳統 IGA 模型套入一應用個案中，進行驗證

3、並比較結果。關鍵詞：階層式分析法、交談式遺傳演算法、多準則決策ABSTRACTfitnessThe IGA (Interactive Genetic Algorithms) model could support choice during search, and solve the problems with “ target functiounnknown ”and “ huge samples. A”lthough the IGA model has these superiorities, it must do lots of interactions with users, and

4、the users may suffer a heavy burden in the interactions. Therefore, we provide an AHP_GA model that integrates AHP (Analytic Hierarchy Process) and GA (Genetic Algorithms) to conquer the problem. In order to decrease the users burdemn,owdelutsoeleaanrnAHthPe usersfunction to replace the process that

5、 users need to interact with GA in every generation and assign fitness values. We expect it could provide superiority over traditional IGA. In order to verify the AHP_GA model superior to the traditional IGA, we will apply the AHP_GA model and traditional IGA model on a real case and compare them.Ke

6、ywords ： Analytic Hierarchy Process, Interactive Genetic Algorithms, Multiple Criteria Decision Making壹、 緒論遺傳演算法 (Genetic Algorithms ， GA)6 雖然可以在許多樣本數龐大的問題中取得較佳解，但在面臨 最適函數( Fitness function )無法清楚被定義時，如：人在判斷藝術品美醜的主觀因素， GA 的應用就受 到了限制。交談式遺傳演算法 (Interactive Genetic Algorithms ， IGA)11 的主要觀念就是延續原 GA 的基礎

7、觀念下，藉人與系統互動取代原 GA 中的最適函數，使 IGA 不再受到 GA 應用上的限制。但由於 IGA 需 要人與系統間多次的互動，使得使用者承擔了很大的負擔。在過去的文獻中，許芳誠 3 曾提出利用 IGA 運用在行程規劃上。該系統運用 GA 隨機產生六張行程 圖，並個別計算出六張行程圖的相關資訊(如時間、價錢、欲參加活動中可以參加的活動和不能參加的 活動、到達與離開每一景點的時間等) ，供使用者給定各行程適應值(Fitness value )。因為 IGA 每一代都要使用者介入並綜合各種主、客觀準則給定行程適應值，無形間會造成使用者的負擔，而這樣的做法也 是較沒效率的。又在 IGA 的理

8、論上，是需經歷大量的演化代數才能達到該方法論所提的較佳解。為了解決使用者與系統間大量的互動次數，我們提出結合階層式分析法 (Analytic Hierarchy Process, AHP)10 和 GA 的模型 ，希望能延續傳統 IGA 的理論基礎優勢 ，並試圖改善傳統 IGA 低效率的互動方式 。AHP 有處理多準則 (Multiple Criteria) 的能力 10 ，而 IGA 有解決樣本數大 、使用者目標函數 未知、邊尋邊選的特性3。AHP處理問題時，有樣本數不可過大的限制 10，在這一點上 GA 可以彌補 AHP 的限制。而在 IGA 觀念中會造成使用者負擔的互動次數問題，期望在A

9、HP 介入後，藉由AHP 取得最適函數 ，以減少使用者負擔的問題 。所以本研究在保留 IGA 互動的前提下 ，結合 AHP 與 GA， 使此一新模型同時具有上述四個特性，適合解決多準則、樣本數大 、使用者目標函數未知 、邊尋邊選的問題。為了證明本研究所提出的 AHP_GA 模型能有效地改善傳統 IGA 方法論的缺失 ，我們將會把 AHP_GA 模型與傳統 IGA 模型套入一個應用個案中，進行驗證並比較其結果。貳、 文獻探討2.1 階層式分析法 (AHP)2.1.1 階層式分析法簡介階層式分析法為 Thomas L Saaty所提岀的一套多屬性決策方法10，主要用在不確定情況下及具有多個評估準則

10、的決策問題上。透過一套選擇程序，評估各屬性的相對重要性，然後界定出各可行方案中 的最佳方案，而該有限個方案都為已知且離散的。譬如說，我們要從數個方案中選擇一個滿足所有評估 標準的方案，實在是不容易，因為每個人會依照主觀喜好決定評估標準，而且各標準不只一個，在這之 間可能會有利害衝突存在，而造成欲解決問題的一致性欠佳，使用AHP 則可解決這樣的難題。此外， AHP 還可以解決錯綜複雜的問題，並且不需設定任何限制條件。譬如說，數量化模型最大的 缺點就是條件的限制，因為很多無法數量化的因素將會被犧牲掉，但AHP 就沒有這種顧慮，因為它能將問題的內在層次與聯繫判斷量化，並做岀解決問題的優劣排序。因此，

11、AHP 具有決策過程時間短，所需參考資訊量卻很少之優點，所以特別適用於不確定性情況，以及有多個評估標準的決策問題。2.1.2 階層式分析法之優點AHP之優點在於解決問題時，系統所認定的要件(Entities)組成幾個互斥集合(Disjoint Sets)而形成上下隸屬 (Dominated) 的層級關係 1 ，並可藉由一致性檢定，篩選有效問卷以控制結果的可信度； 其模式操作較簡單，無繁複的運算；可處理的問題規模較大，考慮之層面及準則較完備，更能掌握實際 問題狀況。因此 AHP 較一般方法更具邏輯基礎，同時是以數量的方式處理，可提供決策者較明確之參考資訊，目前使用相當普遍。以下列舉 AHP 具有

12、之優點：層級結構具有穩定 (Stable) 及彈性 (Flexible) 的好處。就穩定性而言， 是指結構中的改變， 可控制掌握， 不致產生重大的變動；就彈性而言，則是可依需要在原有的結構中作一些影響因素的增添變化，這些性 質有助於我們在認定層級結構的過程中，得以做逐步地修正或擴充。由於層級結構中，各層級影響因素的優先程度，乃是逐層分別衡量比較產生的，所以我們可以很清 楚地觀察出上層影響因素間優勢結構的變化，對下一層影響因素發生的衝擊影響力，在研究問題系統結 構變化的衝擊影響上，此點是極為重要的。2.1.3 階層式分析法之限制雖然 AHP 可解決一致性的問題以及增加解決問題的效率 ，以減少使用

13、者等待的時間 ，但是因為 AHP 量化的基礎是建立在受訪者主觀判斷上，容易受極端值的影響，且當階層與元素較多時，受訪者容易失 去理性，影響方案的評選。故 AHP 較適宜在處理元素量不大的決策問題上。劉信宏於 2000 年5提出，雖然 AHP 方法已被廣泛的應用，但仍有面臨到對於專家的人數及其人選 為一個主要的限制，乃因人數過多或人選認定標準有所偏差時，將會影響分析結果的一致性。張春龍在 2000年4提出，在用以 AHP 解決問題時，若選擇要素超過一定的階層要素時(理論上以 九個為上限) ，則容易面臨到一致性準確度降低的問題。2.2 遺傳演算法 (Genetic Algorithms ， GA)

14、2.2.1 遺傳演算法簡介遺傳演算法源自於達爾文在 1859 年出書物種原始的演化思想，他提出物競天擇之理論，說 明自然界的生物是以適者生存、不適者淘汰的演化定律，指出適合目前生存環境的物種擁有較大的 適應力生存下來，相對的，較不適合此一環境的物種將面臨被淘汰的自然規律，這就是天擇 。在經過 天擇後的生物繼續繁衍，使得子代遺傳上一代適合環境的特徵，得以在環境中生存，如此代代演化下去， 整個物種就會朝著更能適應環境的演化方向走下去。雖然達爾文最早提出適者生存、不適者淘汰的觀念，但將這種觀念推用到人工智慧系統的重要開創者是John Holla nd。他為了做好學習機器的研究及獲得一個良好的學習算法

15、，因此建立岀一個包含許多候選條件的群體，進而進行繁殖演化，此研究想法起源於遺傳演化，於是Holland 將此研究領域命名為遺傳演算法 9。一直到 1975 年 Holland 岀版了 Adaptation in Natural and Artificial Systems ，遺傳演算法 的名稱才逐漸被人所知。2.2.2 遺傳演算法之優點經由資料的匯總之後 ，我們可得岀在與傳統的優化算法相比下 ，遺傳演算法可歸納岀其優點的表現：【1】在與傳統的優化算法相比下，遺傳演算法主要有三個不同之處10 ：(1) 遺傳演算法是以參數集合之編碼進行運算而不是參數本身。(2) 遺傳演算法的蒐集不是以單個點，而是

16、以一個點的群體開始蒐集。(3) 遺傳演算法利用適應值的資訊，而不需要其它輔助資訊(如：梯度 )。【2】遺傳演算法本身的優越性：(1)它在搜索過程中不容易陷入局部最優化，即使在所定義的適應函數是不連續的，非規則的或有噪 音的情況下，它也能以很大的概率找到整體的最佳解。錢明淦於19986 提岀以基因演算法為基礎的啟發式解法，以求解一多資源組態與資源限制下專案排程的問題，說明了基因演算法具有不易陷入局部最佳 化之困境，且可趨向於問題整體的收斂。（2）由於它固有的並行性，遺傳算法非常適用於大規模的並行計算機。2.2.3 遺傳演算法之限制 遺傳演算法的優點於能夠解決大範圍的樣本數搜尋，對於定量問題解決亦

17、是如此。但是對於定性問 題數量化的不易及常因為太早收斂而較不易得到最佳解，這兩點為遺傳演算法在面臨問題時的限制。面 臨這樣的問題，可採取交談式遺傳演算法（ IGA ），以解決其限制性。2.3 交談式遺傳演算法2.3.1 交談式遺傳演算法簡介1991 年， Coldwell and Johnston 提出了交談式遺傳演算法（ IGA ）。事實上， IGA 是從 GA 的觀念發 展出來的，目的就是為了解決 GA 所面臨的關鍵問題，也就是最適函數的訂定。主要概念就是由決策者 來扮演傳統 GA 中最適函數的取得，其餘部分和傳統 GA 並沒有什麼不同，而這概念，卻可以使 GA 不 僅解決定量的問題，同時

18、也能解決定性的問題。如此一來，使得 GA 的應用領域變得更為寬廣。2.3.2 交談式遺傳演算法之優點IGA 最大的優勢就在由決策者扮演最適函數的角色，使定義最適函數不再有偏頗，無須擔心最適函 數是否不準確，只須留意使用者決策前後是否有想法上的出入，這也就是一致性判斷的用意。所以在這 觀念下，理論上是可以達到最佳解的求得，無論屬性是定性或定量， 在使用 IGA 處理時， 都是不成問題。 這是許多演算法所望塵莫及的。2.3.3 交談式遺傳演算法之限制由於 IGA 每一代的演化都需要決策者的參與，面對數十代，甚至數百代的演化，使用者需對每一代 族群中的所有染色體進行評估，並給定適應值，對使用者而言毋

19、寧是一個相當大的負擔，如何降低使用 者的負擔一直是 IGA 應用上的一個待解決問題。許方誠在 2000 年發表的論文 3中提到， IGA 若要達到實用的階段，目前有兩個必須克服的問題： （1）如何改善染色體的評估手續，使得以降低每一代使用者花費在評估染色體的時間。（2）如何讓演化結果維持在可接受水準的前提下，降低收斂的代數。參、 AHP_GA 模型3.1 AHP 結合 GA 的演算法流程圖AHP_GA 的演算法如下所示，而它的流程圖如圖3.1。其中的元素編碼 （表 3.1） 是為了構成染色體，好方便在 GA 中做運算上的使用。在表3.2 AHP問卷調查表中所提的元素排列組合後的屬性a、B、丫，

20、舉例來說，在行程規劃上它可以是，時間、價錢、可參加的活動數等等。而在演算法中所提的演化結果未達收斂，是指在演化結果呈現穩定、不再輕易變化的狀態。在這演算法流程中，系統會要求使用者填寫 AHP 的屬性問卷，之後，系統會評估問卷一致性後並自 重執行，將該 AHP 計算的結果導入 GA（ 導入方法如圖 3.2），經過 GA 不斷地演化之後會得出一個系統認 定最佳的建議元素組合方案。如使用者不滿意該方案，可重填AHP 問卷，再重複上述動作，交由系統處理，達到邊尋邊選的觀念，直到出來的元素組合方案是接近使用者所想要的為止。AHP_GA （）使用者輸入組成方案的元素，及元素相關資訊將使用者輸入的元素編碼

21、（如表 3.1）Do2002年管理創新與新願景研討會1-33使用者填寫元素間排列組合的AHP屬性比對問卷（如表3.2）if （C.R.vO.1 &C.l.vO.1）計算各階層的權重else要求使用者重新填寫AHP屬性比對問卷GA從元素間排列組合的方案隨機挑選n筆資料While （演化結果未達收斂）系統個別計算出這n筆資料的總權重值（此值作為GA的適應值）把這n筆資料總權重值高的留下進行元素排列組合之方案間的交配及突變運算產生新一代內含有n筆資料系統將新的元素排列組合之方案展示給使用者參考 While （使用者滿意為止）()圖3.1AHP GA演算法流程兀素名稱ABCDEFGHIJ染色體基因 型

22、00011001000000100101101011010001100011011011001001元素編號341521201213229表3.1兀素編碼表屬性偏好重要尚可一樣尚可重要元素排列組合後的屬性aV元素排列組合後的屬性元素排列組合後的屬性V元素排列組合後的屬性Y元素排列組合後的屬性YV元素排列組合後的屬性a表3.2 AHP問卷調查表/0,4*0,7 + 0.2*0.5 + -+0.2*0.1 邁憊值（、總權重分數）、0.4*0.1/0.2*0.5 + *- + 0.2:fc0.6 =0.4+ 0.2*0.4 + -+02*03=適應值（總罐重分囊片GA毎一代所要求出來的N佃適廳值遽握

23、判用AHP州呆蒔的题權茫裁段也就是G蠱輕西曲駅的適應值圖3.2AHP導入GA的模型肆、個案說明近幾年，因為國民所得逐步的提昇，加上週休二日的影響，使得越來越多人更重視假日休閒活動。 對於逛街這個活動，如果我們能夠事先取得相關店家、行程等資訊，那我們就能先規劃自己時間排程， 減少不必要的時間浪費，以增加時間安排的效率，而且更能針對個人的偏好來選擇店家，使得這趟行程 對自己得到最大的收益。本研究個案將以台北西門町為例，因西門町歷史淵源深厚為台灣最知名，且最多變化的流行商圈之 一，可提供給各族群消費者不同的需求。在這個議題中，產生了幾個需要被解決的問題。其中有，因為 行程多樣化產生的多準則；再加上近

24、來自我行銷概念的盛行，消費者的消費意識抬頭，建立一個可以 讓使用者隨時做一對一交談的系統，構成了使用者目標函數未知的問題；而於行程規劃上，點與點 間大量的排列組合，造成了樣本數大的問題；況且，使用者的偏好通常不會在第一次就馬上被確認，所以需要有邊尋邊選的概念，才能適當地解決偏好異動的問題。由於以上四個特性，在本研究所提 岀的AHP_GA新模型理論，是可以套用的。所以我們將此議題導入AHP_GA模型與傳統IGA模型，並比較兩者的實驗結果，進行驗證AHP_GA模型是否有改善傳統 IGA模型的缺失。本研究個案中將會提供的地理資訊皆為實地訪察後所得的真實資料。由於西門町的主要道路目前都 規劃成行人專用

25、道，因此本研究個案以步行為主要的交通工具。4.1行程規劃模型因應本個案需求，我們提岀行程規劃模型，其系統架構如圖4.1。模型中除了使用者之外，尚有三個主要模組：（1）地理資訊模組，（2）互動式介面模組，及（3）AHP_GA為基礎之行程規劃模組。圖4.1行程規劃模型4.1.1地理資訊模組在我們提出的模型中，內含一地理資訊資料庫，提供以下多種類型的基本資訊。1. 時間資訊（Temporal information）:例如，隨便兩參訪點的距離花費時間（traffic time），參加活動所需時間。2. 一般資訊（General information）:例如，各店家的簡介，參訪點及活動的圖片。3.

26、空間資訊（Spatial information）：例如，任意參訪點的座標，參訪點的活動資訊。4.1.2互動式介面模組此模型主要是以地圖介面為主，主要功能有四：一是讓使用者作AHP問卷填表（如表4.1、4.2），二是提供使用者瀏覽景點資訊及相關活動資訊，三是讓使用者經由此介面選岀自己想要參訪的景點，四是 配合行程規劃輸出結果，提供使用者參考。透過本模組，使用者除了可根據自己的偏好，點選自己所感興趣的店家，並經由地理資訊模組 取得店家簡介及店家當期活動資訊。使用者透過地理資訊模組瀏覽相關資訊時，我們也可以要求使用者輸入相關需求，以定義他的 行程需求。使用者所輸入的資料包括：1. 起點及終點。2.

27、 行程開始的時間。3. 想參加的活動。4. 每個活動準備花費的時間。當使用者完成上述要求資料後，所有欲參訪的景點在地圖介面上將呈現明顯的標記。4.1.3 AHP_GA為基礎之行程規劃模組AHP_GA的演算法如下所示，而它的流程圖如圖4.2。其中所提到的使用者輸入的點編碼 （如表4.3），是為了構成染色體，好方便在 GA中做運算上的使用。而在演算法中所提的演化結果未達收斂，是指在演化結果呈現穩定、不再輕易變化的狀態。在這演算法流程中，系統會要求使用者填寫AHP的屬性問卷，之後，系統會評估問卷一致性後並自重執行，將該 AHP計算的結果導入 GA（導入方法如圖3.2），經過GA不斷地演化之後會得岀一

28、個系統認 定最佳的建議行程。如使用者不滿意該方案，可重填AHP問卷，再重複上述動作，交由系統處理，達到邊尋邊選的觀念，直到出來的建議行程是接近使用者所想要的為止。AHP_GA ()將使用者輸入的點編碼（如表4.3）Do使用者填寫行程規劃的 AHP屬性比對問卷if （C.R.vO.1 &C丄0.1）計算各階層的權重（如表4.4）else要求使用者重新填寫AHP屬性比對問卷GA從行程規劃的方案隨機挑選n筆行程資料While （演化結果未達收斂）系統個別計算岀這n筆行程資料的總權重值（此值作為GA的適應值）（如圖4.3）把這n筆資料總權重值高的行程留下進行行程間的交配及突變運算產生新一代內含有n筆行

29、程系統將新的行程展示給使用者參考 While （使用者滿意為止）圖4.2AHP GA系統模型流程4.2個案演練小陸要到西門町去旅遊，而他是從南部上來的遊客，對西門町一點也不了解。可是他又想把西門町 玩得夠徹底，不希望敗興而歸。此時他就可以利用此一系統（如圖4.1 ）來解決他的問題。首先他會先在地理模組上選擇他所要的點（國賓戲院、鴨肉扁、烏龍院、賽門甜不辣、九五樂府、阿宗麵線、木吉他、萬年、淘兒、玫瑰唱片行）。選完點之後，系統將他所選的點編碼，如表4.3。系統將點編碼完後，他會被要求填寫AHP的屬性問卷調查，如表4.1、表4.2、圖4.4 （其中圖4.4是此一個案屬性的階層示意圖，表4.1、表4

30、.2的屬性分別為該圖的第一階、第二階元素），此時系統會先判斷他所填的內容是否有達到一致性，如果沒有的話系統會要求他重作AHP填表的動作。如果有，則將計算所填問卷，計算結果如表4.4。之後，所有的動作都是由系統自動執行了。此時系統會把AHP計算的結果導入GA（導入方法如圖4.5）經過GA不斷地演化之後會得出一個系統認定最佳的建議行程。如果小陸不喜歡這一條行程的話，那 他就重填AHP問卷，再交由系統去處理，達到邊尋邊選的觀念，直到出來的行程是接近他所想要的為止。偏好屬性水準、重要尚可一樣尚可重要/時間丁V價錢價錢V附加功能附加功能V時間表4.1 AHP問卷格式屬性水準偏好-. .重要尚可一樣尚可重

31、要時間4小時以下V時間4小時至7小時時間4小時至7小 時V時間7小時以上時間7小時以上V時間4小時以下價錢1000元以下V價錢1000元至3000元價錢1000元至3000 元V價錢3000元以上價錢3000元以上V價錢1000元以下浪漫街道V攤販街道攤販街道V拍貼街道拍貼街道V浪漫街道表4.2 AHP問卷格式景點名稱國賓 戲院鴨肉 扁烏龍 院賽門 甜不 辣九五 樂府阿宗 麵線木吉他萬年淘兒玫瑰 唱片 行染色體基因00011001000000100101101011010001100011011011001001甫錢崎間附加甜辅咼中低BC-AG舘蔽方素的屬注木率，價錢時間附加功能0.2600.

32、1050.633表4.3行程規劃的編碼組成方案的屬性水準代表的意義，是例如在方案一中，為價錢高、時間 C、 附加功能C的屬性水準；在方案二中，為價錢低、時間 C、附加功能A的 屬性水準，依此類推型景點編號341521201213229圖4.4此個案構成的屬性階層樹使用者調查後的屬性權重價錢1000元以下10003000元3000元以上屬性水準低中高權重分數0.6340.2600.106時間四小時以下四小時七小時以上屬性水準ABC權重分數0.1060.2600.634附加功能ABC屬性浪漫街道攤販街道拍貼街道權重分數0.4290.4290.142表4.4各階層權重值2002 年管理創新與新願景研

33、討會I-350.260*0:14+0.10*0 十 0.63+ 0 42Q = 002Si9160 x0.260 0.10； r 0.634 +0.633*0.429 -0.40500,260 *a Z6O + . 10 *Q. 1 oei + 0,63xD. J42 - n,lS79抚個盘中3丸舟*优所貝罷出起陀6個適密卫莫一咂申亲，用AHP4#一碍算鮒樓f追證利用AHP所耒捋的漣罐重甘箍矩軌是C1A裡.面所詢眄通應蛙圖4.5AHP導入GA的模型伍、討論與結論本研究所提岀的 AHP_GA模型最大的特色就是修正了，傳統IGA在互動時所造成的困擾點。也就是使用者每一代都要介入，綜合主、客觀因素，並給其適應值。而本研究利用AHP_GA的新模型來解決此困擾，其綜合此兩個方法論的優點，除了延續原IGA擅長解決樣本數大、使用者目標函數未知邊尋邊選的問題外，也加入了AHP處理多準則問題的優勢。而此類的模型理論應可應用在許多的排程類問題，並產生效益，例如此個案中所提的旅遊行程規劃、或是工廠