論文の概要: Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions

• arxiv url: http://arxiv.org/abs/2603.08209v1
• Date: Mon, 09 Mar 2026 10:39:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-10 15:13:15.801815
• Title: Multi-Objective Evolutionary Optimization of Chance-Constrained Multiple-Choice Knapsack Problems with Implicit Probability Distributions
• Title（参考訳）: 帰属確率分布を考慮したチャンス制約付きマルチコースクナップサック問題の多目的進化最適化
• Authors: Xuanfeng Li, Shengcai Liu, Wenjie Chen, Yew-Soon Ong, Ke Tang,
• Abstract要約: 本稿では,Multiple-choice knapsack problem (MCKP) の重要かつ未解明な拡張について検討する。 問題の目標は、総コストを同時に最小化し、キャパシティ制約を満たす信頼性レベルを最大化することである。 合成ベンチマークと実世界の5Gネットワーク構成ベンチマークの実験は、NHILSがいくつかの最先端のマルチオブジェクトを一貫して上回っていることを示している。
• 参考スコア（独自算出の注目度）: 40.96538452098451
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multiple-choice knapsack problem (MCKP) is a classic combinatorial optimization with wide practical applications. This paper investigates a significant yet underexplored extension of MCKP: the multi-objective chance-constrained MCKP (MO-CCMCKP) under implicit probability distributions. The goal of the problem is to simultaneously minimize the total cost and maximize the confidence level of satisfying the capacity constraint, capturing essential trade-offs in domains like 5G network configuration. To address the computational challenge of evaluating chance constraints under implicit distributions, we first propose an order-preserving efficient resource allocation Monte Carlo (OPERA-MC) method. This approach adaptively allocates sampling resources to preserve dominance relationships while reducing evaluation time significantly. Further, we develop NHILS, a hybrid evolutionary algorithm that integrates specialized initialization and local search into NSGA-II to navigate sparse feasible regions. Experiments on synthetic benchmarks and real-world 5G network configuration benchmarks demonstrate that NHILS consistently outperforms several state-of-the-art multi-objective optimizers in convergence, diversity, and feasibility. The benchmark instances and source code will be made publicly available to facilitate research in this area.
• Abstract（参考訳）: MCKP(Multi-choice knapsack problem)は、古典的な組合せ最適化であり、幅広い応用がある。 本稿では,MCKPの暗黙の確率分布下での多目的確率制約型MCKP (MO-CCMCKP) の拡張について検討する。 問題の目標は、総コストを同時に最小化し、キャパシティ制約を満たす信頼性レベルを最大化し、5Gネットワーク構成のようなドメインにおける重要なトレードオフを捉えることである。 暗黙の分布下での確率制約を評価することの計算課題を解決するために,まず,命令保存効率のよいモンテカルロ(OPERA-MC)法を提案する。 提案手法は,評価時間を大幅に削減しつつ,支配関係を維持するためにサンプリング資源を適応的に割り当てる。 さらに,NSGA-IIに特殊初期化と局所探索を統合し,スパース可能な領域をナビゲートするハイブリッド進化アルゴリズムであるNHILSを開発した。 合成ベンチマークと実世界の5Gネットワーク構成ベンチマークの実験により、NHILSは収束性、多様性、実現可能性において、最先端の多目的最適化よりも一貫して優れていることが示された。 ベンチマークインスタンスとソースコードは、この分野の研究を促進するために公開されます。

関連論文リスト

• MMR1: Enhancing Multimodal Reasoning with Variance-Aware Sampling and Open Resources [113.33902847941941]
  VAS (Variance-Aware Sampling) は、Variance Promotion Score (VPS) によって導かれるデータ選択戦略である。 我々は、1.6MのCoT冷間開始データと15kのRLQAペアを含む大規模かつ慎重にキュレートされたリソースをリリースする。 数学的推論ベンチマークによる実験では、キュレートされたデータと提案されたVASの有効性が示されている。
  論文  参考訳（メタデータ） (2025-09-25T14:58:29Z)
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz [0.0]
  本稿では,ポートフォリオ最適化のための新しい量子フレームワークを提案する。 このアンザッツの重要な強みは、量子系を実現可能な状態のみの重ね合わせで初期化することである。 その結果、CMA-ESと組み合わせると、Dicke状態のアンザッツは収束率、近似比、測定確率の点で優れた性能が得られることがわかった。
  論文  参考訳（メタデータ） (2025-08-19T15:45:07Z)
• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  本稿では,両者の時間的分離を必要とせずに,意思決定とIS分布を共同で更新する反復型アルゴリズムを提案する。 本手法は,IS分布系に対する目的的,軽度な仮定の凸性の下で,最小の変数分散を達成し,大域収束を保証する。
  論文  参考訳（メタデータ） (2025-04-04T16:10:18Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications [38.98556852157875]
  ランダムな重みの確率分布が未知であるがサンプルデータのみが利用可能であるCCMCKPの実践シナリオに注目した。 CCMCKPを解決するために,データ駆動型適応局所探索(DDALS)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-26T13:35:05Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  独立して通常は分散しているコンポーネントのシナリオについて研究する。 期待されるコストとその分散をトレードオフする問題を多目的に定式化する。 また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
  論文  参考訳（メタデータ） (2021-09-13T09:24:23Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  本稿では,平均場近似ポリシ最適化(MF-PPO)アルゴリズムを提案する。 我々は,MF-PPOが収束のサブ線形速度で世界的最適政策を達成することを証明した。 特に、置換不変ニューラルアーキテクチャによって引き起こされる誘導バイアスは、MF-PPOが既存の競合より優れていることを示す。
  論文  参考訳（メタデータ） (2021-05-18T04:35:41Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  確率分布が未知な分布の不確実性の下でBQOについて検討する。 標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。 この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
  論文  参考訳（メタデータ） (2020-01-19T12:00:33Z)

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

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