16:20 〜 16:40
[1H3-GS-1b-04] 一般化相互割当問題に対するヒューリスティックアルゴリズムの非同期かつ動的なステップサイズ
キーワード：マルチエージェントシステム、分散最適化、一般化相互割当問題、ラグランジュ分解、ヒューリスティックアルゴリズム
一般化相互割当問題 (GMAP) は分散最適化問題の一種であり, ロボットタスク割当問題等, 実世界への応用が期待されている. GMAPはNP困難であり, 解の実行可能性判定ですらNP完全であるため, 実行可能解を得ることは容易ではない. 先行研究において, GMAPの実行可能解を求めるラグランジュ分解に基づいたヒューリスティックアルゴリズムが提案されている. このアルゴリズムでは, GMAPにおける従来の定式化をラグランジュ分解を用いて再定式化し, ラグランジュ乗数を各エージェントにおいて非同期に更新することで, 効率よく実行可能解を生成することができる. ラグランジュ乗数の更新にはステップサイズを調整するパラメータrが必要であり, これは得られる実行可能解の質に影響を与える. しかし, パラメータrは問題の規模に合わせて手動で設定する必要があり, 適切な値は自明ではない. 本研究では良質な実行可能解を得ることを目的とし,パラメータrを非同期かつ動的に調整する更新則を提案する. これにより, 問題例の種類や規模に適応するパラメータの更新を, 自動で行うことができるようになる. 提案手法はシミュレーションにより有効性を確認する.
講演PDFパスワード認証
論文PDFの閲覧にはログインが必要です。参加登録者の方は「参加者用ログイン」画面からログインしてください。あるいは論文PDF閲覧用のパスワードを以下にご入力ください。