[[alternative]]由較佳邊集合引導之基因區域搜尋法及其應用於解旅行推銷員問題

[[abstract]]旅行推銷員問題(Traveling Salesman Problem ; TSP)為典型的組合最佳化(Combinatorial Optimization )問題之一。自西元1930年以來，它便吸引許多不同領域的學者投入研究，然而TSP問題已被證明是NP-hard問題，因此如何發展出在有限時間內能找出全域最佳解(global optimum)的方法，便是研究學者的最大挑戰。近年來的研究中，發現可利用TSP問題修正過之邊成本結合最小生成樹的規則來取得一些較佳邊，稱為較佳邊集合 ，在過去研究中利用了較佳邊集合來加速求解過程中收斂速度，但較為可惜的是，過去研究並無針對較佳邊集合的特性作進一步的利用。因此本論文結合較佳邊集合與基因區域搜尋法以期能有效應用於求解TSP問題的研究上，且透過較佳邊集合能夠有效連結全域搜尋與區域搜尋的合作機制，使其兩者達到更完善的搜尋效果與求解品質。本論文採用TSPLIB題庫之35題來測試本研究提出的基因區域搜尋法。在測試結果發現 ，本研究的基因區域搜尋法相較於目前表現較佳的LKH演算法與ANGEL演算法，有相當不錯的求解品質與效能表現。The traveling salesman problem is an important combinatorial optimization problem. Since 1930, many researchers had been devoting their efforts in solving this problem. Being an NP-hard problem, the traveling salesman problem is unlikely to be solved in polynomial time. Hence a main research issue is to design efficient algorithms to find near optimal solutions for the TSP. In recent studies, the collection of promising edges by deriving the edges of the minimum spanning trees had been proposed. But the promising edges were not fully utilized in previous studies. In the paper, we used the promising edge set to guide the search of a genetic local search algorithm. First, the promising edge set was generated by iteratively generating the minimum spanning trees. Then, the promising edge set was used to guide the genetic local search algorithm in searching the promising areas. Furthermore, the promising edge set will evolve along the search. The proposed algorithm was tested on 35 instances taken from TSPLIB. The experimental results revealed that the solution quality of the proposed algorithm is similar to that of the ANGEL and is better than that of the LKH