論文の概要: 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インスタンスに対して非常に競争力のある結果が得られることが示された。
関連論文リスト
- Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
独立支配問題(IDP)は、様々な現実のシナリオにおいて実践的な意味を持つ。
IDPの既存の古典的アルゴリズムは計算の複雑さに悩まされている。
本稿では、IDPに対処するための量子近似最適化(QAOA)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-10-22T17:49:00Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - 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) - Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem [18.19836641663039]
我々は,0-1 MKPを解くために,進化計算と正確なアルゴリズムを組み合わせた新しいアルゴリズムを提案する。
一連のソリューションを維持し、人口の情報を利用して、優れた部分的な割り当てを抽出する。
既存のアルゴリズムよりも優れた解を見つけ、大規模で難しい10のインスタンスに新しい下位境界を提供する。
論文 参考訳（メタデータ） (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) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。