Hybrid Metaheuristics for the Traveling Salesman Problem and the Quadratic Assignment Problem

這篇論文呈現了針對複雜問題尋求最佳解而發展的超啓發式 (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.Contents 1 Introduction ……………………………………………………………………… 1 1.1 Motivation …………………………………………………………………… 1 1.2 An Overview ………………………………………………………………… 3 2 Two Combinatorial Optimization Problems …………………………………… 5 2.1 The Traveling Salesman Problem …………………………………………… 5 2.1.1 Definition ………………………………………………………………… 5 2.1.2 Previously Proposed Algorithms ………………………………………… 6 2.2 The Quadratic Assignment Problem ………………………………………… 7 2.2.1 Definition ………………………………………………………………… 7 2.2.2 Previously Proposed Algorithms ………………………………………… 8 3 Techniques Used in ANGEL………………………………………………………… 10 3.1 Ant Colony Optimization …………………………………………………… 10 3.1.1 Overview of the Ant Colony Optimization ……………………………… 10 3.1.2 Ants, Pheromones, and Solutions Evaluation …………………………… 11 3.2 Genetic Algorithm …………………………………………………………… 13 3.2.1 Overview of the Genetic Algorithm …………………………………… 13 3.2.2 Genetic Operators ……………………………………………………… 14 3.3 Local Search ………………………………………………………………… 14 3.3.1 Overview of the Local Search …………………………………………… 14 3.3.2 2-OPT, 3-OPT, and Their Variants ……………………………………… 15 3.3.3 The Lin-Kernighan Algorithm …………………………………………… 16 4 Two Hybrid Metaheuristics for the Traveling Salesman Problem ……………… 18 4.1 The Exploring PES Genetic Algorithm ……………………………………… 18 4.1.1 Generation of the Promising Edge Set …………………………………… 19 4.1.2 Applying EPGA for the TSP ……………………………………………… 24 4.1.3 Solution representation …………………………………………………… 24 4.1.4 Decoding and evaluation ………………………………………………… 24 4.1.5 Genetic operators ………………………………………………………… 25 4.1.6 Initialization ……………………………………………………………… 27 4.1.7 Experimental results and discussions …………………………………… 29 4.2 ANGEL Metaheuristic for the TSP ………………………………………… 31 4.2.1 The Ant Colony Optimization …………………………………………… 32 4.2.2 The Genetic Algorithm …………………………………………………… 34 4.2.3 The Lin-Kernighan Heuristic……………………………………………… 39 4.2.4 Design of Experiments …………………………………………………… 39 4.2.5 Evaluation of Experimental Results ……………………………………… 41 5 ANGEL Metaheuristic for the Quadratic Assignment Problem ……………… 50 5.1 ANGEL Metaheuristic for the QAP ………………………………………… 51 5.1.1 The ACO Phase …………………………………………………………… 53 5.1.2 The GA Phase …………………………………………………………… 55 5.1.3 The Local Search ………………………………………………………… 61 5.2 Design of Experiments ………………………………………………………… 62 5.3 Evaluation of Experimental Results …………………………………………… 64 6 Conclusions and Future Research Works ……………………………………… 82 Bibliography …………………………………………………………………………… 84 VITA …………………………………………………………………………………… 93 Publications ……………………………………………………………………………… 94 List of Figures 3.1 An iteration of the ACO metaheuristic ……………………………………………… 11 3.2 A 2-opt move ……………………………………………………………………… 15 3.3 A 3-opt move ……………………………………………………………………… 15 4.1 Construction process of the PES for the instance att48 …………………………… 20 4.2 Representation of a chromosome …………………………………………………… 24 4.3 The decoding procedure …………………………………………………………… 25 4.4 The EESX crossover operator ……………………………………………………… 26 4.5 EPGA for TSP ……………………………………………………………………… 28 4.6 ANGELTSP metaheuristic for the TSP ……………………………………………… 31 4.7 The illustration of the OX1 crossover for TSP ……………………………………… 35 4.8 The illustration of the EEPX crossover for TSP …………………………………… 36 4.9 The illustration of the mutation operator …………………………………………… 38 5.1 The representation of a solution …………………………………………………… 51 5.2 ANGELQAP metaheuristic …………………………………………………………… 52 5.3 The ACOQAP phase of ANGEL for QAP …………………………………………… 53 5.4 The GA phase of ANGEL for QAP ………………………………………………… 56 5.5 The illustration of OX1 crossover for QAP ……………………………………… 58 5.6 The illustration of DPX crossover for QAP ………………………………………… 60 List of Tables 4.1 Analysis of the optimal tour edges' coverage rate in PES ………………………… 22 4.2 EPGA's test results of some TSPLIB instances …………………………………… 30 4.3 The comparison of ANGELTSP and LKH on TSPLIB instances with sizes greater than 500. ………………………………………………………… 44 4.4 ANGELTSP's test results of the Random Uniform Euclidean instances, Clustered Euclidean instances, and Random Matrix instances. …………………… 45 4.5 ANGELTSP's test results of Large TSPLIB instances. ……………………………… 46 4.6 The comparison of ANGELTSP's results and other methods' results on the Random Uniform Euclidean instances (E*), the Clustered Euclidean instances (C*), and the Random Matrix instances (M*). ………………………… 47 4.7 The comparison of ANGELTSP's results and other methods' results on large instances. ……………………………………………………………………… 48 4.8 The comparison of ANGELTSP, ANGELcandidatelist, Without ACO, and ANGELw/o eepx. ………………………………………………………………… 49 5.1 The computational results of ANGELQAP on all QAPLIB instances with sizes not less than 30. ……………………………………………………………… 68 5.2 Comparison of results obtained by ANGELQAP, GA+LS, and ACO+LS. ………… 69 5.3 Comparison of results obtained by ANGELQAP, GA+LS, and ACO+LS. ………… 70 5.4 Comparison of results obtained by ANGELQAP and ANGELQAP +EliteGroup. …… 71 5.5 Comparison of results obtained by ANGELQAP using different crossover operators. …………………………………………………………… 72 5.6 Quality of various heuristic methods for QAPLIB instances. ……………………… 73 5.7 The computation results of ANGELQAP on QAPLIB nug type instances. ………… 76 5.8 The computation results of ANGELQAP on QAPLIB bur type instances. ………… 76 5.9 The computation results of ANGELQAP on QAPLIB chr type instances. ………… 77 5.10 The computation results of ANGELQAP on QAPLIB esc and els type instances. … 77 5.11 The computation results of ANGELQAP on QAPLIB had and kra type instances. … 78 5.12 The computation results of ANGELQAP on QAPLIB scr and rou type instances. … 78 5.13 The computation results of ANGELQAP on QAPLIB tho, wil and ste type instances. …………………………………………………………………………… 79 5.14 The computation results of ANGELQAP on QAPLIB sko type instances. ………… 79 5.15 The computation results of ANGELQAP on QAPLIB tai type instances. ………… 80 5.16 The computation results of ANGELQAP on QAPLIB tai-b type instances. ……… 80 5.17 The computation results of ANGELQAP on QAPLIB lipa-a type instances. ……… 81 5.18 The computation results of ANGELQAP on QAPLIB lipa-b type instances. ……… 8