論文の概要: Evolving Reliable Differentiating Constraints for the Chance-constrained Maximum Coverage Problem
- arxiv url: http://arxiv.org/abs/2405.18772v1
- Date: Wed, 29 May 2024 05:22:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-30 18:48:25.157619
- Title: Evolving Reliable Differentiating Constraints for the Chance-constrained Maximum Coverage Problem
- Title（参考訳）: 環境制約付き最大被覆問題に対する信頼性のある微分制約の展開
- Authors: Saba Sadeghi Ahouei, Jacob de Nobel, Aneta Neumann, Thomas Bäck, Frank Neumann,
- Abstract要約: 確率制約付きグラフにおける古典的最大カバレッジ問題について検討する。
我々のゴールは、アルゴリズムの性能が著しく異なるグラフに対する信頼性の高い確率制約設定を進化させることである。
本研究では、2つの探索アルゴリズムの性能を高い信頼性で区別する確率制約セットを提供する進化的アルゴリズムを開発する。
- 参考スコア（独自算出の注目度）: 8.98161858972433
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Chance-constrained problems involve stochastic components in the constraints which can be violated with a small probability. We investigate the impact of different types of chance constraints on the performance of iterative search algorithms and study the classical maximum coverage problem in graphs with chance constraints. Our goal is to evolve reliable chance constraint settings for a given graph where the performance of algorithms differs significantly not just in expectation but with high confidence. This allows to better learn and understand how different types of algorithms can deal with different types of constraint settings and supports automatic algorithm selection. We develop an evolutionary algorithm that provides sets of chance constraints that differentiate the performance of two stochastic search algorithms with high confidence. We initially use traditional approximation ratio as the fitness function of (1+1)~EA to evolve instances, which shows inadequacy to generate reliable instances. To address this issue, we introduce a new measure to calculate the performance difference for two algorithms, which considers variances of performance ratios. Our experiments show that our approach is highly successful in solving the instability issue of the performance ratios and leads to evolving reliable sets of chance constraints with significantly different performance for various types of algorithms.
- Abstract（参考訳）: チャンス制約問題(英語版)は、小さな確率で破ることができる制約の確率的成分を含む。
確率制約が反復探索アルゴリズムの性能に与える影響について検討し,確率制約のあるグラフにおける古典的最大被覆問題について検討する。
我々のゴールは、アルゴリズムの性能が期待されるだけでなく、高い信頼性で著しく異なるグラフに対する信頼性の高い確率制約設定を進化させることである。
これにより、異なるタイプのアルゴリズムが、異なるタイプの制約設定にどのように対処できるかを学習し、理解し、自動アルゴリズム選択をサポートすることができる。
本研究では、2つの確率探索アルゴリズムの性能を高い信頼性で区別する確率制約セットを提供する進化的アルゴリズムを開発する。
まず、(1+1)〜EAの適合度関数として従来の近似比を用いてインスタンスを進化させ、信頼性のあるインスタンスを生成するのに不適切であることを示す。
そこで本研究では,性能比の分散を考慮した2つのアルゴリズムの性能差を計算するための新しい尺度を提案する。
実験の結果,本手法は性能比の不安定性の問題の解決に成功しており,様々なアルゴリズムの性能に大きく違いがあるような,信頼性の高い確率制約セットの進化に繋がることがわかった。
関連論文リスト
- Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
本稿では,POMDPにおける最大到達可能性確率問題(indefinite-horizon)と呼ばれる問題について検討する。
割引問題に対するポイントベース手法の成功に触発され,MRPPへの拡張について検討した。
本稿では,これらの手法の強みを有効活用し,信念空間を効率的に探索するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-05T02:33:50Z) - Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection [25.29451529910051]
本稿では,アルゴリズムの特徴に基づくアルゴリズム選択の証明可能な最初の保証を提案する。
アルゴリズムの特徴に関連する利点とコストを分析し、一般化誤差が様々な要因にどのように影響するかを考察する。
論文 参考訳（メタデータ） (2024-05-18T17:38:25Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Provably Efficient Learning in Partially Observable Contextual Bandit [4.910658441596583]
古典的帯域幅アルゴリズムの改善に因果境界をどのように適用できるかを示す。
本研究は,実世界の応用における文脈的包括的エージェントの性能を高める可能性を秘めている。
論文 参考訳（メタデータ） (2023-08-07T13:24:50Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - An Application of a Multivariate Estimation of Distribution Algorithm to
Cancer Chemotherapy [59.40521061783166]
癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。
より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。
我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
論文 参考訳（メタデータ） (2022-05-17T15:28:46Z) - Instance-Dependent Confidence and Early Stopping for Reinforcement
Learning [99.57168572237421]
強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。
この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。
次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
論文 参考訳（メタデータ） (2022-01-21T04:25:35Z) - Generating Instances with Performance Differences for More Than Just Two
Algorithms [2.061388741385401]
本稿では,2つ以上のアルゴリズムに対して,同時に大きな性能差を示すインスタンスを進化させるフィットネス関数を提案する。
原理の証明として、3つの不完全TTP解法に対する多成分トラベリングティーフ問題(TTP)のインスタンスを進化させる。
論文 参考訳（メタデータ） (2021-04-29T11:48:41Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Heuristic Strategies for Solving Complex Interacting Stockpile Blending
Problem with Chance Constraints [14.352521012951865]
本稿では,材料グレードの不確実性について考察し,信頼性の高い制約を確実にするために使用される確率制約を導入する。
ストックパイルブレンディング問題と確率制約に対処するため, 2つの補修演算子を組み合わせた微分進化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-10T07:56:18Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。