大規模TSPインスタンスを解くためのアリコロニー最適化効率の改善【JST・京大機械翻訳】

Skinderowicz Rafal

プレプリント

J-GLOBAL ID：202202216620271966 整理番号：22P0298878

大規模TSPインスタンスを解くためのアリコロニー最適化効率の改善【JST・京大機械翻訳】

Improving Ant Colony Optimization Efficiency for Solving Large TSP Instances

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (1件)：
資料名：
発行年： 2022年03月04日プレプリントサーバーでの情報更新日： 2022年03月04日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

※このプレプリント論文は学術誌に掲載済みです。なお、学術誌掲載の際には一部内容が変更されている可能性があります。

アリコロニー最適化(ACO)は,困難な最適化問題に対する近似解を見つけるのにしばしば適用される,自然で触発されたメタヒューリスティックのファミリーである。正確な方法よりも著しく速いにもかかわらず,ACOは,特に基本的問題固有の発見的方法と比較して,まだ,まだ遅い。最近の研究が示すように,マルチコアCPUと専用アクセラレータからのアルゴリズム精密化と注意深い並列実装により性能を著しく改善できる。本論文では,新しいACO変異体,すなわち集中ACO(FACO)を提示した。FACOのコア要素の1つは,新しく構築したおよび選択した以前の解の間の差異の数を制御する機構である。機構は,より集中的な探索プロセスをもたらし,既存の解の品質を維持しながら改善を見つけることができる。付加的利点は,問題固有の局所探索とより効率的な統合である。巡回セールスマン問題インスタンスの範囲に基づく計算機研究は,FACOが大規模TSPインスタンスを解決するとき最先端のACOより優れていることを示した。特に,FACOは8コア商品CPU時間の1時間未満を必要とし,TSP Art Instancesが100000~200000ノードの範囲の高品質解(最高既知結果から1%以内)を見出した。【JST・京大機械翻訳】

, , , , , , , ,
, , , , , , , 【Automatic Indexing@JST】

工程管理 , ネットワーク法 , システム最適化手法 , 数値計算

, ,

前のページに戻る