予算最大カバレッジ問題のための有効可変深さ局所探索【JST・京大機械翻訳】

Zhou Jianrong; Zheng Jiongzhi; He Kun

プレプリント

J-GLOBAL ID：202202216803418974 整理番号：22P0285705

予算最大カバレッジ問題のための有効可変深さ局所探索【JST・京大機械翻訳】

Effective Variable Depth Local Search for the Budgeted Maximum Coverage Problem

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

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

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

標準的な0-1ナップサック問題と集合カバー問題の自然で実用的な拡張であるBudgeted Maxim Coverage問題(BMCP)に取り組んだ。非負重みのm要素,非負コストの要素のnサブセット,および総予算,BMCPは,選択されたサブセットの全コストが予算を超えないように,いくつかの部分集合を選択し,そして,関連要素の総重量を最大化した。本論文では,BMCPのための可変深さ局所探索アルゴリズム(VDLS)を提案した。VDLSは最初に greedy欲アルゴリズムにより初期解を生成し,次に,多重部分集合の状態(選択または非)を同時に変えることにより解を改良できる部分深さ優先探索法により解を反復的に改善した。そのような方法は,VDLSが,広く,そして,深く,そして,高品質解を生み出すために,解空間を探索することを可能にする。さらに,アルゴリズム性能を高めるための隣接構造を提案し,即ち,両部分集合は,少なくとも1つの共通関連要素を持つならば,隣接関係を持つ。隣接構造を適用することにより,VDLSは選択した部分集合を調整できるが,できるだけ少数のカバー要素として損失する。既存のBMCPベンチマークは単純な構造と小さいスケールを持つので,BMCPインスタンスの多様性を豊かにするために,比較的大規模で複雑な構造の60の新しいインスタンスを設計した。30の公開事例と60の新しい事例に関する実験結果は,VDLSがBMCPに対して既存の発見的方法と一般的CPLEX厳密ソルバよりも著しく優れていることを示した。【JST・京大機械翻訳】

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

数値計算 , グラフ理論基礎 , その他のオペレーションズリサーチの手法

, , ,

前のページに戻る