困難適応カリキュラムによる巡回セールスマン問題を解決するための学習【JST・京大機械翻訳】

Zhang Zeyang; Zhang Ziwei; Wang Xin; Zhu Wenwu

プレプリント

J-GLOBAL ID：202202200093063639 整理番号：22P0327658

困難適応カリキュラムによる巡回セールスマン問題を解決するための学習【JST・京大機械翻訳】

Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum

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

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

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

巡回セールスマン問題(TSP)のような組合せ最適化問題に取り組むために,様々なニューラルネットワークモデルを提案した。既存の学習ベースTSP法は,訓練と試験データが独立で同一に分布している簡単な設定を採用する。しかし,既存の文献は,訓練と試験データが異なる分布を持つとき,TSPインスタンスを解決できない。具体的には,異なる訓練と試験分布が,より困難なTSPインスタンス,すなわち,モデルによって得られた解が最適解から大きなギャップを持つことを見出した。この問題に取り組むために,本研究では,訓練と試験データが適応-硬度,即ち,TSPインスタンスがソルバーに対してどのように難しいかを用いて,訓練とテストデータが異なる分布を持つときの学習ベースTSP法を研究した。この問題は,硬度測定を定量的に定義するのが簡単であるため,挑戦的である。(2)モデル訓練において,十分にハードなTSPインスタンスを効率的かつ連続的に生成する。(3)より強力なTSPソルバを学習するために,異なるレベルの硬度を有する事例を完全に利用する。これらの課題を解決するため,まず,TSP事例の硬度を定量化するための原理的硬度測定を提案した。次に,異なる硬度を持つインスタンスを生成するために,硬度適応発電機を提案した。さらに,TSPソルバを訓練するために,これらのインスタンスを完全に利用するカリキュラム学習者を提案する。実験は,著者らの硬度適応発電機が既存の方法より10倍硬い事例を発生でき,著者らの提案方法が最適性ギャップに関して最先端のモデルに対して顕著な改良を達成することを示した。【JST・京大機械翻訳】

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

その他のオペレーションズリサーチの手法 , 人工知能

, , ,

前のページに戻る