Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/18345
標題: 解旅行推銷員問題及二次分配問題之混合超啓發式演算法
Hybrid Metaheuristics for the Traveling Salesman Problem and the Quadratic Assignment Problem
作者: 梁錫卿
Liang, Shyi Ching
關鍵字: Metaheuristic;超啓發式演算法;Traveling Saleman Problem;Quadratic Assignment Problem;Genetic Algorithm;Ant Colony Optimization;Local Search;旅行推銷員問題;二次分配問題;遺傳演算法;蟻群演算法;區域搜尋法
出版社: 應用數學系
摘要: 
這篇論文呈現了針對複雜問題尋求最佳解而發展的超啓發式 (Metaheuristic) 演算法所做的研究,這個新的超啓發式演算法是以結合三個演算法為基礎,分別為蟻群最佳化演算法 (Ant Colony Optimization)、遺傳演算法 (Genetic Algorithm)、以及區域搜尋方法,我們將之命名為ANGEL,其主要構想為藉由整合全域搜尋法與區域搜尋法來加強探索 (exploration) 及利用 (exploitation) 的能力。在遺傳演算法中,初始母體不是經由隨機產生而是擷取蟻群最佳化演算法產生的解來組成以提供效能的提昇。同時我們也利用費洛蒙更新 (pheromone updating) 來記憶遺傳演算法的搜尋努力,並將之利用在隨後的蟻群最佳化演算法中,以將蟻群最佳化演算法引導到較好的區域。遺傳演算法及蟻群最佳化演算法所產生的解會藉由區域搜尋方法來做改善,區域搜尋對於探索區域地貌是很有用的方法,對於特定解的鄰近解的檢視,所使用的是某種類型的操作。蟻群最佳化演算法與遺傳演算法交互合作的執行以協助對方,我們也提出一個概念稱為優生策略 (Eugenic Strategy),它能在不損失解品質的情況下加速GA的收斂。
我們使用了兩個測試問題,分別為旅行推銷員問題 (Traveling Salesman Problem) 及二次分配問題 (Quadratic Assignment Problem)。在解決旅行推銷員問題時,經由重複粹取最小擴展樹 (Minimum Spanning Tree),可以得到一組有希望包含最佳解的邊之集合,稱之為Promising Edges Set (PES),藉此特性,我們提出了一個新的遺傳演算法exploring PES GA (EPGA) 及一個新的交配子 exploring edge set crossover operator (EESX),同時,也提出另一個新的交配子 eugenic edge preserving crossover operator (EEPX),它是藉由利用PES來改善解的品質。
藉著執行一系列的實驗來評估這個新超啓發式演算法的能力,這兩個問題所使用的問題組包含各種大小的實驗組合,均取自相關著名的比較基準問題組,實驗結果顯明ANGEL的效能相當好。

This dissertation represents the research of the development of new metaheuristics for locating optimal solutions to difficult problems. The new metaheuristic is founded upon the combination of three algorithms, the ant colony optimization (ACO), the genetic algorithm (GA), and the local search method, which is called ANGEL. The key idea is to enhance the ability of exploration and exploitation by incorporating global search with local search. Instead of starting from randomly generated population, GA retrieves the solutions previously constructed by ACO to provide a performance boost. In GA, the pheromone updating is used to memorize the GA's search efforts. The updated pheromone will guide ACO to a hopefully better area. The solutions generated by ACO and GA are refined by means of the local search. Local search is useful for exploring a localized landscape. The examination of the neighborhood of a given solution is derived from some class of operations. The ACO and the GA runs alternatively and cooperatively to enhance each other. A concept called the eugenic strategy that guides the GA to converge quickly without degenerating solution quality also has been proposed.
Two test problems were used - the Traveling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP). In solving TSP, a set of promising edges, called promising edge set (PES), is derived by iteratively extracting the minimum spanning trees. A new genetic algorithm called the exploring PES GA (EPGA) with a new crossover operator called the exploring edge set crossover (EESX) is proposed. Also, a new crossover operator, called the eugenic edge preserving crossover (EEPX), is proposed to improve the solutions by exploiting PES.
A series of experiments were conducted to assess the capabilities of this new metaheuristic. Instances of these two problems were taken from well known benchmarks with different problem sizes.
URI: http://hdl.handle.net/11455/18345
Appears in Collections:應用數學系所

Show full item record
 

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.