論文の概要: RIGA: A Regret-Based Interactive Genetic Algorithm
- arxiv url: http://arxiv.org/abs/2311.06063v1
- Date: Fri, 10 Nov 2023 13:56:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-13 15:07:28.261353
- Title: RIGA: A Regret-Based Interactive Genetic Algorithm
- Title（参考訳）: riga: 後悔に基づく対話型遺伝的アルゴリズム
- Authors: Nawal Benabbou and Cassandre Leroy and Thibaut Lust
- Abstract要約: そこで本研究では,多目的最適化問題を優先的精度で解くための対話型遺伝的アルゴリズムを提案する。
我々のアルゴリズムはRIGAと呼ばれ、集約関数がパラメータ内で線形であることから、任意の多目的最適化問題に適用できる。
いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
- 参考スコア（独自算出の注目度）: 14.388696798649658
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we propose an interactive genetic algorithm for solving
multi-objective combinatorial optimization problems under preference
imprecision. More precisely, we consider problems where the decision maker's
preferences over solutions can be represented by a parameterized aggregation
function (e.g., a weighted sum, an OWA operator, a Choquet integral), and we
assume that the parameters are initially not known by the recommendation
system. In order to quickly make a good recommendation, we combine elicitation
and search in the following way: 1) we use regret-based elicitation techniques
to reduce the parameter space in a efficient way, 2) genetic operators are
applied on parameter instances (instead of solutions) to better explore the
parameter space, and 3) we generate promising solutions (population) using
existing solving methods designed for the problem with known preferences. Our
algorithm, called RIGA, can be applied to any multi-objective combinatorial
optimization problem provided that the aggregation function is linear in its
parameters and that a (near-)optimal solution can be efficiently determined for
the problem with known preferences. We also study its theoretical performances:
RIGA can be implemented in such way that it runs in polynomial time while
asking no more than a polynomial number of queries. The method is tested on the
multi-objective knapsack and traveling salesman problems. For several
performance indicators (computation times, gap to optimality and number of
queries), RIGA obtains better results than state-of-the-art algorithms.
- Abstract（参考訳）: 本稿では,多目的組合せ最適化問題を解くための対話型遺伝的アルゴリズムを提案する。
より正確には、解に対する意思決定者の選好をパラメータ化された集計関数(例えば、重み付き和、owa演算子、コケ積分)で表現できる問題を考える。
良質な推薦を迅速に行うために、私たちは次の方法で説明と検索を組み合わせる。
1) パラメータ空間を効率的に削減するために, 後悔に基づく推論手法を用いる。
2) パラメータ空間をよりよく探索するために, パラメータインスタンス(解ではなく)に遺伝的演算子を適用する。
3) 既知の選好問題に対する既存の解法を用いて, 期待できる解(人口)を生成する。
このアルゴリズムは riga と呼ばれ, 任意の多目的組合せ最適化問題に適用可能であり, 集約関数はそのパラメータにおいて線形であり, 既知の選好問題に対して(近傍)最適解を効率的に決定できる。
RIGAは、多項式数以上のクエリを要求しながら、多項式時間で実行されるように実装できる。
この方法は多目的クナップサック問題とトラベルセールスマン問題でテストされている。
いくつかのパフォーマンス指標(計算時間、最適性とクエリ数のギャップ)に対して、RIGAは最先端のアルゴリズムよりも優れた結果を得る。
関連論文リスト
- Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。
本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。
提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文 参考訳（メタデータ） (2024-11-04T15:17:19Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Learning Adaptive Evolutionary Computation for Solving Multi-Objective
Optimization Problems [3.3266268089678257]
本稿では, 深層強化学習(DRL)を用いた適応パラメータ制御とMOEAを統合したフレームワークを提案する。
DRLポリシは、最適化中のソリューションに対する突然変異の強度と確率を決定する値を適応的に設定するように訓練されている。
学習されたポリシーは転送可能であることを示す。つまり、単純なベンチマーク問題で訓練されたポリシーは、複雑な倉庫最適化問題を解決するために直接適用可能である。
論文 参考訳（メタデータ） (2022-11-01T22:08:34Z) - Enhanced Opposition Differential Evolution Algorithm for Multimodal
Optimization [0.2538209532048866]
現実の問題は、本質的には複数の最適値からなるマルチモーダルである。
古典的な勾配に基づく手法は、目的関数が不連続あるいは微分不可能な最適化問題に対して失敗する。
我々は,MMOPを解くために,拡張オポポジション微分進化(EODE)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-23T16:18:27Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - A Simple Evolutionary Algorithm for Multi-modal Multi-objective
Optimization [0.0]
マルチモーダル・多目的最適化問題(MMOP)を解くための定常進化アルゴリズムを提案する。
本報告では,1000関数評価の低計算予算を用いて,様々なテストスイートから得られた21個のMMOPの性能について報告する。
論文 参考訳（メタデータ） (2022-01-18T03:31:11Z) - QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver
Surrogates [14.905085636501438]
問題のインスタンスの集合に関するソルバデータから学習することで,quboソルバのサロゲートモデルを構築する。
このようにして、インスタンスの共通構造とそれらの解決者との相互作用を捉えることができ、ペナルティパラメータを適切に選択することができる。
qrossは分散型データセットや様々な種類のquboソルバによく一般化されている。
論文 参考訳（メタデータ） (2021-03-19T09:06:12Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - Bayesian preference elicitation for multiobjective combinatorial
optimization [12.96855751244076]
DM(Decision Maker)のノイズ応答に対処できる新しいインクリメンタルな選好推論手法を提案する。
DMの選好はパラメータが未知の集約関数で表され、その不確実性はパラメータ空間上の密度関数で表されると仮定する。
論文 参考訳（メタデータ） (2020-07-29T12:28:37Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。