蚁群演算法之应用

2007/12/08專題報告1蟻群演算法於自行車遊憩路線最佳化之研究立德管理學院資源環境研究所學生：王秀霞學號：E09514016指導教授：李宗霖教授胡子陵教授林妤蓁教授2007/12/08專題報告2大綱一、緒論二、文獻探討三、研究方法四、預期結果五、參考文獻2007/12/08專題報告3一、緒論1.1研究動機1.2研究目的1.3研究方法1.4研究流程2007/12/08專題報告41.1研究動機(1)隨著週休二日的實施，國人休閒遊憩的風氣日盛，自行車活動已逐漸演變成大眾重要的休閒活動之ㄧ。自行車具有經濟、無空氣污染、節約能源、方便性等優點，是一種有益健康與環保的交通工具。自行車活動是一種既可達到休閒活動的目的，而且與其他活動的相容性高是一種適合全家大小共同參與的活動。(林建堯，1999)2007/12/08專題報告51.1研究動機(2)騎自行車也是能源再生的一種貢獻，既可以鍛鍊身體又可以節省能源是一種「不虧欠地球」的好運動；可以增加心肺功能、降低血壓、保持體態苗條而且運動傷害少。(周盟桂，2001）一個好的自行車遊憩休閒活動除了地點的選擇外，路線的規劃也是一個相當重要的考量。本研究針對已規劃之自行車路線用蟻群最佳化演算法（ACO）來規畫出最佳之路徑，供自行車使用者參考。2007/12/08專題報告61.2研究目的目前國內外的旅遊路線規劃大多利用經驗法則為基礎規劃，而非使用演算法系統來進行一較科學方式來規劃，而目前自行車活動蔚為風潮，本文擬利用蟻群最佳化演算方法(ACO)，具有可搜尋最佳之路徑功能，來建立自行車遊憩路徑最佳規劃系統，期能提供自行車遊憩者最佳路線規劃之參考，使能節省時間及成本，並享受到最佳的休閒遊憩活動，相較於之前以經驗法則為基礎規劃好的自行車路線。2007/12/08專題報告71.3研究方法本研究以ACO的理論模擬，設計出自行車遊憩時所需最佳路線規劃之模式，因此研究中所做之各項假設及限制條件如下：1.各遊憩路徑上，因個人需求不同，故停留時間暫時忽略不計。2.每次遊憩過程所搭乘之交通工具於本此研究中暫時不納入考量。3.原路線為曲線問題，本研究中任其兩景點間皆取直線最短距離計算。4.凡已拜訪過之景點，則假設不會再次遊訪。2007/12/08專題報告81.4研究流程自行車路線剖析文獻蒐整與閱讀確認研究動機與目的確認研究範圍與問題描述文獻探討確認研究架構與方法自行車路線蒐集與整理導入路線規劃之系統結論與建議2007/12/08專題報告9二、文獻回顧(1)2.1遊憩（recreation）之定義Recreation，英文原意是為使精神恢復或再創造，指利用休閒時間從事之行為（張薇文，2003），牽涉型為個體與支持產生愉悅經驗的資源與空間。黃昆祥（2003）提出遊憩活動是指人類於閒暇時，依其興趣極需要尋求滿足感的自然表現，其於個人或團體參與活動的動機，乃是基於能獲得享受和滿足的體驗為由。2007/12/08專題報告10二、文獻回顧(2)林晏州（1984）對遊憩的定義如下：1.遊憩乃是一種目標導向之行為，其目的在於滿足個人實質、社會及心理之需求。2.遊憩之參與乃發生於無義務時間或所謂休閒時間。3.遊憩活動必須由個人自由選擇。4.遊憩乃為一種活動或ㄧ種體驗。曹正（1979）認為遊憩意指於自由時間內所從事讓身心復元、精神愉快之行為，且獲得個人滿足與愉快之體驗。綜合上述諸多學者之意見，遊憩乃指一種在個人的自由時間或閒暇時間下，經由個人意志選擇而從事的活動，並能達到個人身心舒暢、精神愉悅滿足的一種體驗活動言之。2007/12/08專題報告11二、文獻回顧(3)2.2遊憩路線在旅客選擇旅遊路線模式之影響因素，從相關理論與諸多學者之研究中指出，可分為三部份探討，即旅遊特性、路徑特性、目的地特性。旅遊特性指客源地、旅遊類型及目的地數量、旅遊天數與旅伴組合情況等。路徑特性則包括：旅遊距離、旅運工具及路徑特色。目的地特性則包括:住宿類型空間結構旅遊時間資訊及費用等。（黃盈錚，2005）2007/12/08專題報告12二、文獻回顧(4)旅遊模式可區分為三大部分，即節點、路徑及旅遊方式三種:（黃盈錚，2005）1.節點（Nodes）此指客源地-目的地的相對概念，代表著旅行者所在地區的資源或人口的區位，亦表現供給和需求之間的實質或潛在關係，當從節點間產生移動，就有了旅遊研究的基本空間要素。2.路徑（Routes）此指連接點間之旅遊路線在節點間移動，則產生了旅遊路徑此種路徑可發生在一種或ㄧ種以上的旅遊方式。3.旅遊方式（Modalchoice）此指路徑移動時所採用的旅遊工具類型之選擇。2007/12/08專題報告13二、文獻回顧(5)2.3路線規劃2.3.1旅行推銷員問題（Travelingsalesmanproblem,TSP）TSP為一位推銷員計畫如何安排拜訪n個城市，即推銷員需從某一個城市出發，訪問所有的城市一次，最後再回到原出發的城市，以求取其總旅行距離最短。而以n個城市（節點）的TSP問題為例若從已選定的起始點出發至返回原出發的城市（節點）則存在著(n-1)!/2種可能的路徑(Route)選擇欲從之中找到最短路徑距離組合則將花費相當多的運算時間。2007/12/08專題報告14二、文獻回顧(6)2.3.2基因演算法則(geneticalgorithms,GA)基因演算法(GA)其實是模擬大自然生物的一種演算法，透過競爭和生存，擁有好基因的品種會有較高的機會生存到下一代，而與生存較無關的基因則會隨著時間逐漸被淘汰。在理想的狀態下，競爭和生存會迫使不具優勢的品種逐漸消失。然而只擁有一種好基因是不夠的；透過基因的交配，不同的個體把它們的好基因組合起來，變成更具優勢的下一代；而若不然，則會加速被淘汰。除此之外，還要再配合突變，產生革命性的改變，進而對族群進步有突破性的發展。1975年Holland根據生物演化現象的觀察，把問題轉為基因型(genotype)，利用自然、淘汰、交叉、突然變異進化過程的適應現象，即複製、交配與突變三個基本運算元，提出GA模型方案，重複運作把較差的解淘汰尋求出問題的最佳解答。蔡正發(2004)等以將「動態性」、「載運量」及「即時性」等加入GA中，以期輔助企業於路線規劃的問題。2007/12/08專題報告15二、文獻回顧(7)2.3.3模擬退火法(simulatedannealing,SA)退火是一種物理過程，一種金屬物體再加熱至一定的溫度後，由固體結構瓦解變為液體，所有分子在狀態空間中自由運動。隨著溫度的下降，這些分子逐漸停留在不同的狀態。在溫度最低且分子再變回固體結構時，分子重新以一定的結構排列，其中分子的分布則以波茲曼(boltzamnn)概率分布回到穩定狀態。因而1983年Kirkpatrick等人合作，根據物體退火過程，發展出一套演算法，可用來解決組合問題等的尋求最佳解。而羅中育(2001)藉由調整SA參數組合，以使其求解各種TSP問題時能穩健求得平均數低且變異性低的參數，研究中同時進行等比下降型及等差下降型兩種不同降溫時機及次數下降的方式做求解效能的比較。2007/12/08專題報告16二、文獻回顧(8)2.3.4蟻群最佳化演算法(antcolonyoptimization,ACO)1992年Dorigo利用螞蟻尋找食物時在路徑上所殘留的「費洛蒙」(pheromone)濃度配合群體合作的原理，進而尋找出最短路徑之行為提出螞蟻系統(antsystem,AS)，並於1996年與GA、SA等啟發式演算法以TSPLIB國際列題進行比較，其結果皆優於其他的演算法，誤差皆小於3.5%(在城市小於200的情況下)，1997年因求解方式對於複雜、雜訊多、及資訊不完整之尋優問題有良好的表現，繼而又改良螞蟻系統(AS)後提出蟻群演算法(antcolonysystem,ACS)，應用於旅行推銷員(TSP)。後來Dorigo、Caro和Gambardella等三人則將其它由AS或ACS所延伸最佳化問題的演算法稱之為蟻群最佳化演算法(ACO)，且其應用範圍除不僅是在旅行推銷員問題(TSP)外，亦包括車輛途程問題(VRP)、工作排程問題(JSP)、網路途程問題(NRP)、二次分配問題(QAP)、著色問題(GCP)、背包問題(multipleknapsackproblem,MKP)、最短超字串的問題(SSP)、序列排序問題(SOP)、武器目標分配問題(WTAP)等等相關尋優問題上。2007/12/08專題報告17三、研究方法-蟻群演算法之應用（一）螞蟻行為-螞蟻外出覓食之示意圖AB巢穴食AB食巢穴（a）AB食巢穴AB食巢穴（b）（c）（d）2007/12/08專題報告18螞蟻系統(AS)是1992年由M.Dorigo在博士論文中提出，基本上是一種機率型尋優方法，在螞蟻進行路徑尋優時，係利用一轉換機率進行下一節點的選擇，而考慮的因素為費洛蒙強度及節線長度，其方程式如下：1997年Dorigo以AS為基礎，加入轉換規則、變更整體更新法則與加入局部更新法則進一步提出螞蟻族群系統(ACS)。（二）螞蟻演算法之理論三、蟻群演算法之應用－蟻群最佳化演算法2007/12/08專題報告19：代表在路徑ij上所遺留的費洛蒙素的數量。：為節點i及節點j間距離之倒數。：位於節點i隻第k隻螞蟻尚未拜訪過之節點集合。、：決定費洛蒙與距離兩者間相對重要性之參數。otherwiseiTjifuiuijijijiPkiTukk0)(),(),(),(),(),()()(tijij)(iJk三、蟻群演算法之應用－蟻群最佳化演算法2007/12/08專題報告201997年Dorigo以AS為基礎，加入轉換規則、變更整體更新法則與加入局部更新法則進一步提出螞蟻族群系統(ACS)。（二）螞蟻演算法之理論-ACS三、蟻群演算法之應用－蟻群最佳化演算法132007/12/08專題報告211.轉換規則在模式中，螞蟻在節點i是否移動至鄰近節點j，是由一個介於[0.1]間程均勻分配之隨機亂數q決定。若qq0：其行為較偏向「探索法則」(exploration)，即類似AS。若q≦q０則直接選取具有最大吸引力的節點（費洛蒙濃度高、距離長度短），此行為較偏向「追隨法則」(exploitation)（二）螞蟻演算法之理論-ACS三、蟻群演算法之應用－蟻群最佳化演算法2007/12/08專題報告221.轉換規則-程式如下（二）螞蟻演算法之理論-ACSotherwiseqiTjifuiuijijijiPkiTukk0q;)(),(),(),(),(),(0)(otherwiseq,),(),(maxarg0)(JqifjijijiJuk三、蟻群演算法之應用－蟻群最佳化演算法2007/12/08專題報告232.變更整體更新法則則是將所有人工螞蟻各完成節點拜訪後，針對其每次的可行解中，選取最佳解答的路徑改變其費洛蒙，與AS將所有螞蟻行走過程中所殘留的費洛蒙量加總更新於最佳解是有所差異的，其目的在對最佳解答路徑給予「獎賞」，以利引導螞蟻依據此路徑進行開發及探勘。（二）螞蟻演算法之理論-ACS1)()()1()1(bestLttijij三、蟻群演算法之應用－蟻群最佳化演算法2007/12/08專題報告243.局部更新法則其主要觀念是凡螞蟻走過的路徑，即減少其路徑上的費洛蒙量，便會對螞蟻的吸引力越來越小，最後螞蟻則可以發掘新路徑，可避免螞蟻侷限在一狹隘的範圍內。（二）螞蟻演算法之理論-ACS0)()1()(ttijkij三、蟻群演算法之應用－蟻群最佳化演算法2007/12/08專題報告253.局部更新法則其主要觀念是凡螞蟻走過的路徑，即減少其路徑上的費洛蒙量，便會對螞蟻的吸引力越來越小，最後螞蟻則可以發掘新路徑，可避免螞蟻侷限在