一般化相互割当問題に対するヒューリスティックアルゴリズムの非同期かつ動的なステップサイズ

DOI

書誌事項

タイトル別名
  • Asynchronous and Dynamic Step Size for Heuristic Algorithm in Generalized Mutual Assignment Problem

抄録

<p>一般化相互割当問題 (GMAP) は分散最適化問題の一種であり, ロボットタスク割当問題等, 実世界への応用が期待されている. GMAPはNP困難であり, 解の実行可能性判定ですらNP完全であるため, 実行可能解を得ることは容易ではない. 先行研究において, GMAPの実行可能解を求めるラグランジュ分解に基づいたヒューリスティックアルゴリズムが提案されている. このアルゴリズムでは, GMAPにおける従来の定式化をラグランジュ分解を用いて再定式化し, ラグランジュ乗数を各エージェントにおいて非同期に更新することで, 効率よく実行可能解を生成することができる. ラグランジュ乗数の更新にはステップサイズを調整するパラメータrが必要であり, これは得られる実行可能解の質に影響を与える. しかし, パラメータrは問題の規模に合わせて手動で設定する必要があり, 適切な値は自明ではない. 本研究では良質な実行可能解を得ることを目的とし,パラメータrを非同期かつ動的に調整する更新則を提案する. これにより, 問題例の種類や規模に適応するパラメータの更新を, 自動で行うことができるようになる. 提案手法はシミュレーションにより有効性を確認する.</p>

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390569845479646464
  • NII論文ID
    130008051561
  • DOI
    10.11517/pjsai.jsai2021.0_1h3gs1b04
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • CiNii Articles
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ