論文の概要: Evaluating Genetic Algorithms through the Approximability Hierarchy
- arxiv url: http://arxiv.org/abs/2402.00444v1
- Date: Thu, 1 Feb 2024 09:18:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-02 15:47:39.979614
- Title: Evaluating Genetic Algorithms through the Approximability Hierarchy
- Title(参考訳): 近似可能性階層による遺伝的アルゴリズムの評価
- Authors: Alba Mu\~noz, Fernando Rubio
- Abstract要約: 本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。
特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
- 参考スコア(独自算出の注目度): 55.938644481736446
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Optimization problems frequently appear in any scientific domain. Most of the
times, the corresponding decision problem turns out to be NP-hard, and in these
cases genetic algorithms are often used to obtain approximated solutions.
However, the difficulty to approximate different NP-hard problems can vary a
lot. In this paper, we analyze the usefulness of using genetic algorithms
depending on the approximation class the problem belongs to. In particular, we
use the standard approximability hierarchy, showing that genetic algorithms are
especially useful for the most pessimistic classes of the hierarchy
- Abstract(参考訳): 最適化問題はしばしば科学領域に現れる。
多くの場合、対応する決定問題はnpハードであることが判明し、これらの場合、遺伝的アルゴリズムは近似解を得るためにしばしば用いられる。
しかし、異なるnp-ハード問題の近似の困難さは多岐にわたる。
本稿では,この問題が属する近似クラスに応じた遺伝的アルゴリズムの利用の有用性について検討する。
特に、標準的な近似可能性階層を用いて、遺伝的アルゴリズムが階層の最も悲観的なクラスに特に有用であることを示す。
関連論文リスト
- When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳(メタデータ) (2023-12-18T18:29:01Z) - Temporal Heterogeneity Improves Speed and Convergence in Genetic
Algorithms [0.0]
遺伝的アルゴリズムは自然選択をシミュレートし、様々な問題の解を探すためにパラメータ空間を探索する。
我々は、クロスオーバー確率を個人のフィットネスに逆比例するように設定した。
時間的不均一性はパラメータ空間の事前の知識を必要とせずに探索を改善する。
論文 参考訳(メタデータ) (2022-02-02T22:48:56Z) - Power of human-algorithm collaboration in solving combinatorial
optimization problems [0.0]
最適化問題のクラスは、$epsilon$ が任意の定数であるような乗法係数 $epsilon$ を期待して、効率的に解けることを示す。
提案手法は単に理論的なものであるに過ぎないが、通常は難解であると考えられるこれらの問題を解決する方法に新たな光を当てた。
論文 参考訳(メタデータ) (2021-07-25T11:21:59Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Towards Meta-Algorithm Selection [78.13985819417974]
インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。
メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
論文 参考訳(メタデータ) (2020-11-17T17:27:33Z) - Benchmarking Meta-heuristic Optimization [0.0]
多くのメタヒューリスティックアルゴリズムは非線形関数を解く際に非常に効率的である。
メタヒューリスティックアルゴリズムは、幅広い問題に適用できる問題に依存しない手法である。
論文 参考訳(メタデータ) (2020-07-27T12:25:31Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳(メタデータ) (2020-07-06T15:20:17Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳(メタデータ) (2020-06-08T09:25:47Z) - Genetic optimization algorithms applied toward mission computability
models [0.3655021726150368]
遺伝的アルゴリズムは計算ベースであり、計算に低コストである。
遺伝的最適化アルゴリズムをミッションクリティカルかつ制約対応の問題に記述する。
論文 参考訳(メタデータ) (2020-05-27T00:45:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。