基因演算法在多目標組合最佳化問題之研究-以旅行推銷員問題為例

Abstract

多目標決策(Multiple Criteria Decision Making)理論在組合最佳化 問題(Combinatorial Optimization Problem)的應用上，會增加大量的計 算負擔。本研究的目的即在利用基因演算法(Genetic Algorithm)的平行 搜尋特性，發展一套多目標基因演算法，同時解決傳統多目標方法無法處 理動態資訊影響的問題。 本研究主要包括三個部份：發展動態權重模式 、以旅行推銷員問題的國際題庫驗證基因演算法的績效、提出可解決上述 問題的多目標基因演算法。由於內容涵蓋甚廣，茲將主要成果條列如下 ：(1) 以習慣領域(Habitual Domain)學說為基礎，發展一套動態權重計 算模式；(2) 深入分析基因演算法在路線問題中的關鍵：基因交配運算( CrossOver)，並以路線編碼方式將23種方法一一分類、測試，同時提出三 種改善方法；(3) 針對路線問題的基因交配運算，提出雙向最近可用鄰點 的運算方式，並以國內外研究的著名路網驗證其績效；(4) 提出樣板資料 庫的觀念，以提升基因交配運算的品質；(5) 針對路線問題，改良混沌理 論(Chaos Theory)中的空間填充曲線(Space-Filling Curve)法，提出一 套快速的路線初始化方法；(6) 結合雙向最近可用鄰點與樣板資料庫，設 計出一套適合傳統旅行推銷員問題的基因演算法。並由國際題庫(TSPLIB) 中取出35個著名路網，規模由48至657個節點。測試結果十分理想，有27 個例題找到最佳解，平均誤差僅有0.03%；(7) 結合動態權重模式與基因 演算法的平行搜尋特色，提出一套多目標基因演算法，其特色為：(a)可 由搜尋過程的結果，動態修正決策權重；(b)將多目標規劃的計算需求降 低至單目標水準；(c)以目標間連結度代替直接輸入決策權重，並可在最 後得到規劃結果的同時，自動計算出決策權重；(8) 將上述多目標基因演 算法應用在台北市快捷郵件收攬作業上，以簡例說明此方法的操作細節 ；(9) 於附錄中分析並實際撰寫程式測試組合最佳化與旅行推銷員問題的 數百種方法，與數百篇相關參考文獻之心得。同時於網際網路(Internet) 上構建首頁(HomePage)，以提供原始程式碼與相關資料查詢服務。 The most methods of Multiple Criteria Decision Making (MCDM) will cause acomputational burden tremendously in applying to the combinatorial optimization problem. Besides, the most methods of MCDM ignore the new-coming information and cannot deal the weight of decision maker dynamically. Using the parallel- searching, this research develops a Genetic Algorithm (GA) to overcome theseshortages. There are three primary parts in this research: developing a dynamic weight assessing method, proving the effectiveness of GA in the traveling salesman problem (TSP), developing a method to overcome the shortages above. Theimportant results are listed in the below.(1) To develop a weight assessingmethod by Habitual Domain.(2) To analyze the genetic Crossover operator in TSP,and to classify and implement 23 relative operators, and to propose 3 improving operators.(3) To develop the "Doubly-Nearest-Available neighborhood" crossover operator, and to compare its performance with others by 24 well- knownnetworks.(4) To propose the concept of template database for improving thequality of crossover.(5) To improve a Space- Filling Curve of Chaos Theoryas a quick procedure of tour initialization.(6) To propose a Genetic Algorithm to solve the TSP by combining Doubly-Nearest-Available neighborhoodand template database. And, to measure its performance by 35 networks that are from 48 to 657 nodes and are obtained from TSPLIB. The result is excellent: this method finds 27 exact solutions in 35 networks with only 0.03%error rate in average.(7) To combine the weight assessing method and theparallel-searching of GA, and propose a multiple-objectives GA. The mainproperties are (a) modifying weight dynamically with the results in searching process; (b) and reducing to computational requirement to the levelof single-objective; (c) and computing the weight directly.(8) To apply theabove method to the post-office in Taipei, and to demonstrate the detail by a numeric example.(9) To analyze and write the computer language ofmethods of combinatorial optimization problem and TSP, and to review thehundred's reference of them. And to build a homepage in the Internet forsupplying the source code and relative inquiry service.