論文の概要: Evolutionary Algorithm for Chance Constrained Quadratic Multiple Knapsack Problem

• arxiv url: http://arxiv.org/abs/2511.02500v1
• Date: Tue, 04 Nov 2025 11:39:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-05 18:47:05.976229
• Title: Evolutionary Algorithm for Chance Constrained Quadratic Multiple Knapsack Problem
• Title（参考訳）: クナップサック問題に対する時間制約付き多重クナップサック問題の進化的アルゴリズム
• Authors: Kokila Kasuni Perera, Aneta Neumann,
• Abstract要約: 二次多重クナップサック問題(英: Quadratic multiple knapsack problem、QMKP)は、多重重み容量制約によって特徴づけられる最適化問題である。 我々は、利益がランダム変数と見なされるこの問題の変種について研究する。 進化的アルゴリズム(EA)と多要素最適化(MFO)にインスパイアされた局所最適化戦略を組み合わせたハイブリッドアプローチを提案する。
• 参考スコア（独自算出の注目度）: 3.6439154309310013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quadratic multiple knapsack problem (QMKP) is a combinatorial optimisation problem characterised by multiple weight capacity constraints and a profit function that combines linear and quadratic profits. We study a stochastic variant of this problem where profits are considered as random variables. This problem reflects complex resource allocation problems in real-world scenarios where randomness is inherent. We model this problem using chance constraints to capture the stochastic profits. We propose a hybrid approach for this problem, which combines an evolutionary algorithm (EA) with a local optimisation strategy inspired by multi-factorial optimisation (MFO). EAs are used for global search due to their effectiveness in handling large, complex solution spaces. In the hybrid approach, EA periodically passes interim solutions to the local optimiser for refinement. The local optimiser applies MFO principles, which are typically used in multi-tasking problems. The local optimiser models the local problem as a multi-tasking problem by constructing disjoint search spaces for each knapsack based on an input solution. For each item, its assignment across all knapsacks is considered to determine the preferred knapsack. Items are then divided into disjoint groups corresponding to each knapsack, allowing each knapsack to be treated as a separate optimisation task. This structure enables effective application of MFO-based local refinements. We consider two EAs for the problem, (1+1) EA and ($\mu+\lambda$) EA. We conduct experiments to explore the effectiveness of these EAs on their own and also with the proposed local optimiser. Experimental results suggest that hybrid approaches, particularly those incorporating MFO, perform well on instances where chance constraints and capacity constraints are tight.
• Abstract（参考訳）: 二次多重クナップサック問題(英: Quadratic multiple knapsack problem、QMKP)は、重み付け容量の制約と、線形および二次的利益を組み合わせた利益関数を特徴とする組合せ最適化問題である。 本研究では、利益をランダム変数と見なすこの問題の確率的変種について検討する。 この問題は、ランダム性が固有の実世界のシナリオにおける複雑なリソース割り当て問題を反映している。 確率的利益を捉えるために、確率制約を用いてこの問題をモデル化する。 本稿では、進化的アルゴリズム(EA)と多要素最適化(MFO)にインスパイアされた局所最適化戦略を組み合わせたハイブリッドアプローチを提案する。 EAは、大規模で複雑なソリューション空間を扱うために、グローバル検索に使用される。 ハイブリッドアプローチでは、EAは定期的に中間解を局所オプティマイザに渡して精製を行う。 ローカルオプティマイザはMFOの原則を適用しており、通常はマルチタスク問題に使用される。 局所オプティマイザは、入力解に基づいて各クナップサックに対する不整合探索空間を構築することにより、局所問題をマルチタスク問題としてモデル化する。 各項目について、すべてのクナプサックにまたがる割り当ては、好まれるクナプサックを決定すると考えられる。 その後、項目は各クナプサックに対応する非結合群に分割され、各クナプサックを別の最適化タスクとして扱うことができる。 この構造は、MFOベースの局所改質を効果的に適用することができる。 1+1) EAと(\mu+\lambda$) EAの2つのEAを考えます。 我々は、これらのEAの有効性を独自に調査する実験を行い、また、提案したローカルオプティマイザを用いて検討する。 実験結果から,ハイブリッドアプローチ,特にMFOを取り入れたアプローチは,可能性制約やキャパシティ制約が厳密なインスタンスにおいて良好に機能することが示唆された。

関連論文リスト

• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  本稿では,最適化問題に適した汎用的で効率的な局所探索手法を提案する。 ランダムキーの概念を用いて、RKOは解をランダムキーのベクトルとしてエンコードし、後に実行可能な解に復号する。 RKOフレームワークは古典的メタヒューリスティクスの多元体を組み合わせ、それぞれが独立して、あるいは並列に動作可能であり、エリートソリューションプールを通じてソリューション共有が促進される。
  論文  参考訳（メタデータ） (2024-11-06T22:23:29Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  組合せ最適化(CO)問題はしばしばNPハードであり、正確なアルゴリズムには及ばない。 GFlowNetsは、複合非正規化密度を逐次サンプリングする強力な機械として登場した。 本稿では,異なる問題に対してマルコフ決定プロセス(MDP)を設計し,条件付きGFlowNetを学習して解空間からサンプルを作成することを提案する。
  論文  参考訳（メタデータ） (2023-05-26T15:13:09Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights [15.402666674186936]
  本研究では,ランダム化探索アルゴリズム (RSA) と基本進化アルゴリズム (EA) のランタイム解析を行った。 本稿では,重み相関と異なる種類の利益プロファイルが,確率制約条件下での両アルゴリズムの実行動作にどのように影響するかを示す。
  論文  参考訳（メタデータ） (2021-02-10T23:40:01Z)
• Combinatorial Bayesian Optimization with Random Mapping Functions to Convex Polytopes [43.19936635161588]
  大規模空間でうまく動作するような空間におけるベイズ最適化法を提案する。 提案アルゴリズムは,既存手法と比較して良好な性能を示す。
  論文  参考訳（メタデータ） (2020-11-26T02:22:41Z)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  目的関数を滑らかな局所関数と凸(おそらく非滑らか)結合関数の和とするマルチエージェント共有最適化問題について検討する。
  論文  参考訳（メタデータ） (2020-06-15T19:40:24Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。