遺伝アルゴリズムによる巡回セールスマン問題の一解法 A Method for the Traveling Salesman Problem Based on the Genetic Algorithm

この論文にアクセスする

この論文をさがす

著者

抄録

The genetic algorithm (GA) is an optimization technique simulating the process of natural evolution, and it has been successfully applied to several optimization problems which are difficult to solve exactly by conventional methods. This paper proposes a new method for solving the traveling salesman problem (TSP) based on the GA. In applications of GA to TSP proposed so far, a coding where the chromosome represents a list of cities arrayed in the visiting order has been mainly used. However, in such a coding, we have to devise a crossover operator that keeps each chromosome to be a permutation, and it inevitably causes a difficulty in inheritance of tour characteristics.<br>The present paper proposes a new method in which a genetic coding represents edges of the tour, and a crossover operator exchanges the edges of the parent tours. The effectiveness of the proposed method is confirmed through several computational experiments, including a comparison with another typical method. Furthermore, the paper proposes an algorithm which combines GA with the 2-opt method, a local search technique. The effectiveness of this algorithm is also confirmed through a comparison with other methods for solving the TSP.

収録刊行物

  • 計測自動制御学会論文集  

    計測自動制御学会論文集 31(5), 598-605, 1995-05-31 

    The Society of Instrument and Control Engineers

参考文献:  12件

参考文献を見るにはログインが必要です。ユーザIDをお持ちでない方は新規登録してください。

被引用文献:  36件

被引用文献を見るにはログインが必要です。ユーザIDをお持ちでない方は新規登録してください。

各種コード

  • NII論文ID(NAID)
    10002484234
  • NII書誌ID(NCID)
    AN00072392
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    04534654
  • NDL 記事登録ID
    3607104
  • NDL 雑誌分類
    ZM11(科学技術--科学技術一般--制御工学)
  • NDL 請求記号
    Z14-482
  • データ提供元
    CJP書誌  CJP引用  NDL  J-STAGE 
ページトップへ