最短道順の実時間探索ための複数方策メタ戦略融合GA方式

• Item type: SIG Technical Reports(1)
• 公開日: 2009-12-10
• タイトル: 最短道順の実時間探索ための複数方策メタ戦略融合GA方式
• タイトル / 言語: en
• タイトル: Inner Random Restart Genetic Algorithm to Optimize Delivery Schedule
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京電機大学情報環境学部情報環境学科
• 著者所属: 東京電機大学情報環境学部情報環境学科
• 著者所属: 東京電機大学情報環境学部情報環境学科
• 著者所属: 東京電機大学情報環境学部情報環境学科
• 著者所属(英): en
• 著者所属(英): Department of Information Environment, School of Information Environment, Tokyo Denki University
• 著者所属(英): en
• 著者所属(英): Department of Information Environment, School of Information Environment, Tokyo Denki University
• 著者所属(英): en
• 著者所属(英): Department of Information Environment, School of Information Environment, Tokyo Denki University
• 著者所属(英): en
• 著者所属(英): Department of Information Environment, School of Information Environment, Tokyo Denki University
• 著者名: 櫻井, 義尚; 塚本, 奈津貴; 高田, 考平; 鶴田, 節夫
• 著者名(英): Yoshitaka, Sakurai; Natsuki, Tsukamoto; Kouhei, Takada; Setsuo, Tsuruta
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 物流ネットワークや配送ルートの最適化システムでは，30～数百拠点 （都市） の最短道順探索問題 （巡回セールスマン問題：TSP) を対話的応答時間 （3 秒以下） かつ誤差 3％ 以下で解かなければならない．これらの要求を満たすために，複数の方策を遺伝的アルゴリズム GA に組込む方法を研究してきた．まず，各々異なる方策 （発見的知識）を １ つ組込んだ複数の GA を，ランダムに初期化し直すメタ戦略 （ランダムリスタート法） により順次実行することを指定時間だけ反復し，各 GA の解のうち最適な解を実行可能解あるいは近似最適解として選んだ．次に，各世代内に複数方策をまとめて組込んだ GA を指定時間まで実行し，実行可能解 (近似最適解) を得る方式を提案した．これらは同種目的の他方式よりもシンプルで高性能だが，規模が 250 都市以上では最悪誤差が 4％ を越えた．この解決のため，複数方策やメタ戦略を GA へ融合する改良方式を提案する．これは，1 つの GA の指定世代において，メタ戦略としてのランダムリスタートを評価の悪いまたは同種の （ここでは評価が同じ） 子個体群に適用し上記の発見的知識を用い局所最適化した後に世代の最終評価をして集団の多様性を保つ方式である．世界一高速な厳密解法の 1 つである Concorde でも 10 秒から 100 秒かかる 200-600 都市前後の TSPLIB の問題を本方式で 1000 回試行した結果，最悪ケースでも 3％ 以下の誤差の解が 3 秒以内で探索可能なことを実験で確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A delivery route optimization that improves the efficiency of real time delivery or a distribution network requires to solve several tens to hundreds cities Traveling Salesman Problems (TSP) within interactive response time, with expert-level accuracy (less than about 3% of error rate). To meet these requirements, an Inner Random Restart Genetic Algorithm (Irr-GA) method is developed. This method combines random restart and GA that have several types of heuristics. This method uses a different type of heuristics such as a 2-opt type mutation and a block (Nearest Insertion) type mutation. Comparison based on the results of experiments proved that the method is superior to others and our previously proposed method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12055912
• 書誌情報: 研究報告バイオ情報学（BIO）; 巻 2009-BIO-19, 号 17, p. 1-8, 発行日 2009-12-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会