English  |  正體中文  |  简体中文  |  Items with full text/Total items : 90452/105769 (86%)
Visitors : 11941525      Online Users : 796
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    ASIA unversity > 資訊學院 > 會議論文 >  Item 310904400/5836


    Please use this identifier to cite or link to this item: http://asiair.asia.edu.tw/ir/handle/310904400/5836


    Title: Promising Edge Set Guided Genetic Local Search Algorithm for the Traveling Salesman Problem
    Other Titles: 由較佳邊集合引導之基因區域搜尋法及其應用於解旅行推銷員問題
    Authors: 曾怜玉;余家華
    Contributors: 國立中興大學資訊網路與多媒體研究所;國立中興大學資訊科學與工程系
    Keywords: 旅行推銷者問題;基因演算法;由較佳邊集合引導之基因區域搜尋法;LKH演算法;ANGEL演算法。Traveling salesman problem;genetic algorithm;promising edge set guided genetic local search algorithm;LKH algorithm;ANGEL algorithm
    Date: 2007-12-20
    Issue Date: 2009-12-15
    Publisher: 亞洲大學資訊學院;中華電腦學會
    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.
    Relation: 2007NCS全國計算機會議 12-20~21
    Appears in Collections:[資訊學院] 會議論文

    Files in This Item:

    File SizeFormat
    9015.pdf874KbAdobe PDF1436View/Open


    All items in ASIAIR are protected by copyright, with all rights reserved.


    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback