文献

J-GLOBAL ID：201902244235055527   整理番号：19A0897804

他個体を参照した進化的計算による巡回セールスマン問題の解法

A Novel Evolutionary Algorithm for Solving the Traveling Salesman Problem

著者 (2件)： 佐藤豊浩 (東京都市大 大学院工学研究科) ,  穴田一 (東京都市大 大学院工学研究科)
資料名： 情報処理学会論文誌ジャーナル(Web)
巻： 60  号： 3  ページ： 926-933 (WEB ONLY)  発行年： 2019年03月15日 
JST資料番号： U0452A  ISSN： 1882-7764  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 進化的計算は,生物学的進化から着想を得た操作により,生物個体を模した複数の解候補を解空間上で移動させることで高精度な解を探索するという近似解法の枠組みの1つである.しかし,進化的計算の考えを基に設計された既存手法には,自然界の生物の仕組みに囚われ過ぎている部分がある.加えて,探索集団が持ち合わせない新規要素の発見が乱数に強く依存している.そこで,本研究では進化的計算の考えを基に,自然界の仕組みよりも巡回セールスマン問題を解くことに重点を置いた,乱数に強く依存しない突然変異を導入した新たなアルゴリズム,参照進化(Referential Evolution,RE)を構築した.そして,巡回セールスマン問題のベンチマーク問題を用いて,近似解を高精度かつ高速に求めることでその有効性を確認した.(著者抄録)

シソーラス用語： *巡回セールスマン問題 ,  *進化的計算 ,  *遺伝的アルゴリズム ,  ベンチマーク ,  解 ,  近似法 ,  *組合せ最適化問題
準シソーラス用語： *進化的アルゴリズム ,  ベンチマーク問題 ,  近似解

分類 (3件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  ネットワーク法  (KA03040X) ,  システム最適化手法  (IA02050Z)

引用文献 (12件)：

• Holland, J.H.: Adaptation in Natural and Artificial Systems, The MIT Press, Commonwealth of Massachusetts (1975).
• Kennedy, J. and Eberhart R.: Particle Swarm Optimization, Proc. IEEE/ICNN, pp.1942-1948 (1995).
• Dorigo, M., Maniezzo, V. and Colorni, A.: Ant system: Optimization by a colony of cooperating agents, IEEE Trans. Syst. Man. Cybern., Part B, Vol.26, No.1, pp.29-41 (1996).
• Maekawa, K., Tamaki, H., Kita, H. and Nishikawa, Y.: A method for the traveling salesman problem based on the genetic algorithm, Trans. SICE, Vol.31, No.5 (1995).
• 永田裕一,小林重信:巡回セールスマン問題に対する交叉:枝組み立て交叉の提案と評価,人工知能学会誌, Vol.14, No.5, pp.848-859 (1998).

タイトルに関連する用語 (5件)： 個体 ,  参照 ,  進化的計算 ,  巡回セールスマン問題 ,  解法