文献

J-GLOBAL ID：201702258839421718   整理番号：17A1773733

二次ナップサック問題のための反応性探索【Powered by NICT】

A reactive search for the quadratic knapsack problem

著者 (3件)： Al-Iedani Najat (Universite de Picardie Jules Verne, EPROAD EA-4669, Amiens, France) ,  Hifi Mhand (Universite de Picardie Jules Verne, EPROAD EA-4669, Amiens, France) ,  Saadi Toufik (Universite de Picardie Jules Verne, EPROAD EA-4669, Amiens, France)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： CoDIT  ページ： 0495-0499  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 本論文では,二次ナップサック問題(注目QKP)を解くために反応法を提案した。二次ナップサック問題はよく研究された組合せ最適化問題である。二次ナップサック問題の全ての変異体では,与えられた項目の組の場合,利益だけでなく,個々の項目だけでなく,それらの対に帰属した。二対応する項目は共に同じナップサックに含まれている場合にのみ対利益は二次目的値に加えた。容量Cを持つナップサックと候補物体(または項目)のセットを,各項目は正の重みw_iを持ち,選択すれば,利益Piを対象利益p_iと他の選択された物体を用いてペアごと利益P_ijを生成する。QKPの目的は全体利益を最大化するようにナップサックを埋めるために物体のサブセットを選択することであるが,全重量はナップサック容量はC.超えないこの問題は二次ナップサック問題として知られており,強くNP困難が示されており,それは,様々な重要な応用の,衛星の位置における,空港,駅または貨物ターミナルなどを適用した。提案した方法は主に二つの相補的相に基づいている。第1段階では,出発溶液を提供するための欲張りアルゴリズムを用いた。破壊と修復過程を適用した反応性探索に基づく出発溶液の品質を改善した第二段階では,反応相は,多様化と強化戦略双方に基づいている。得られた結果は,Cplex solverlと文献によって達成されたものと比較した。,実験結果により,提案アプローチの有効性を示し,計算結果はこのアルゴリズムが他の方法では解決できないことをQKPのインスタンスを解くことができることを示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 貨物ターミナル ,  NP困難 ,  *反応性 ,  品質 ,  空港 ,  組合せ最適化問題 ,  多様化 ,  部分集合 ,  *ナップサック問題 ,  アルゴリズム ,  鉄道駅
準シソーラス用語： 欲張りアルゴリズム , 【Automatic Indexing@JST】

分類 (2件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  数理計画法  (KA03030M)

タイトルに関連する用語 (3件)： ナップサック問題 ,  反応性 ,  探索