論文の概要: Imperialist Competitive Algorithm with Independence and Constrained
Assimilation for Solving 0-1 Multidimensional Knapsack Problem
- arxiv url: http://arxiv.org/abs/2003.06617v1
- Date: Sat, 14 Mar 2020 12:19:31 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-23 19:52:48.475727
- Title: Imperialist Competitive Algorithm with Independence and Constrained
Assimilation for Solving 0-1 Multidimensional Knapsack Problem
- Title(参考訳): 0-1多次元ナップサック問題を解くための独立性と制約付き同化を伴う帝国主義的競争アルゴリズム
- Authors: Ivars Dzalbs, Tatiana Kalganova, Ian Dear
- Abstract要約: The Imperialist Competitive Algorithm with Constrained Assimilation (ICAwICA)。
提案アルゴリズムは、植民地独立の概念を導入し、帝国主義者や他の帝国主義者に対する古典的なICA同化を自由に選択する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The multidimensional knapsack problem is a well-known constrained
optimization problem with many real-world engineering applications. In order to
solve this NP-hard problem, a new modified Imperialist Competitive Algorithm
with Constrained Assimilation (ICAwICA) is presented. The proposed algorithm
introduces the concept of colony independence, a free will to choose between
classical ICA assimilation to empires imperialist or any other imperialist in
the population. Furthermore, a constrained assimilation process has been
implemented that combines classical ICA assimilation and revolution operators,
while maintaining population diversity. This work investigates the performance
of the proposed algorithm across 101 Multidimensional Knapsack Problem (MKP)
benchmark instances. Experimental results show that the algorithm is able to
obtain an optimal solution in all small instances and presents very competitive
results for large MKP instances.
- Abstract(参考訳): 多次元ナップサック問題(英: multidimensional knapsack problem)は、多くの実世界の工学応用においてよく知られた制約付き最適化問題である。
このNPハード問題を解決するために,ICAwICA (Constrained Assimilation) を改良した帝国主義者競合アルゴリズムを提案する。
提案アルゴリズムは、植民地独立の概念を導入し、帝国主義者や他の帝国主義者に対する古典的なICA同化を自由に選択する。
さらに、人口多様性を維持しつつ、古典的なICA同化と革命演算子を組み合わせた制約付き同化プロセスが実施されている。
本研究は,101 次元 Knapsack Problem (MKP) ベンチマークインスタンスにおける提案アルゴリズムの性能について検討する。
実験の結果、このアルゴリズムは全ての小さなインスタンスで最適解を得ることができ、大きなMKPインスタンスに対して非常に競争力のある結果が得られることが示された。
関連論文リスト
- Addressing The Knapsack Challenge Through Cultural Algorithm
Optimization [0.0]
我々は,0-1knapsack問題の解法に特化して設計された,新しい文化アルゴリズムの変種を紹介する。
提案アルゴリズムは,集団を改良するための信念空間と,交叉率と突然変異率を動的に調節する2つの重要な機能を導入している。
我々は,このアルゴリズムがグローバルな最適点を一貫して見つけ出す上で,顕著な効率性を示す証拠を提供する。
論文 参考訳(メタデータ) (2023-10-30T17:05:19Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Unbalanced penalization: A new approach to encode inequality constraints
of combinatorial problems for quantum optimization algorithms [58.720142291102135]
余分なスラック変数を必要としない代替手法を提案する。
我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。
この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文 参考訳(メタデータ) (2022-11-25T06:05:18Z) - Finding and Exploring Promising Search Space for the 0-1
Multidimensional Knapsack Problem [18.19836641663039]
0-1 多次元クナップサック問題(MKP)は、多くの工学的応用において古典的なNPハード最適化問題である。
我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-08T05:11:47Z) - Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
Bin Packing Problem (BPP) は、ロジスティクスにおけるパラダイム最適化問題として際立っている。
我々は最近,一次元BPPに対するハイブリッドアプローチを提案している。
他の古典的手法と比較する。
論文 参考訳(メタデータ) (2022-07-15T13:09:12Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳(メタデータ) (2022-06-30T03:15:23Z) - First-Order Algorithms for Nonlinear Generalized Nash Equilibrium
Problems [88.58409977434269]
非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。
我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。
これらのアルゴリズムに対する漸近的理論的保証を提供する。
論文 参考訳(メタデータ) (2022-04-07T00:11:05Z) - Constraint-Handling Techniques for Particle Swarm Optimization
Algorithms [0.0]
人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。
本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
論文 参考訳(メタデータ) (2021-01-25T01:49:10Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - A State Aggregation Approach for Solving Knapsack Problem with Deep
Reinforcement Learning [3.614984020677526]
本稿では,knapsack問題の解法として,Deep Reinforcement Learning (DRL)アプローチを提案する。
状態集約ポリシーは、knapsack問題の各問題インスタンスに適用される。
ステートアグリゲーション戦略を用いた提案モデルは、より良いソリューションを提供するだけでなく、ステートアグリゲーションのないモデルよりも少ないタイムステップで学習する。
論文 参考訳(メタデータ) (2020-04-25T11:52:24Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳(メタデータ) (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。