Fugu-MT 論文翻訳(概要): Evaluating Genetic Algorithms through the Approximability Hierarchy

論文の概要: 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-ハード問題の近似の困難さは多岐にわたる。本稿では,この問題が属する近似クラスに応じた遺伝的アルゴリズムの利用の有用性について検討する。特に、標準的な近似可能性階層を用いて、遺伝的アルゴリズムが階層の最も悲観的なクラスに特に有用であることを示す。

関連論文リスト

Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論と計算複雑性の基本的な問題である。様々なメタヒューリスティックがMPPを近似するために使われており、遺伝的アルゴリズムやメメティックアルゴリズム、アリコロニーアルゴリズム、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングなどがある。以上の結果から,モンテカルロのアルゴリズムはランダム検索を用いてグラフを生成するが,速度と能力の両面で遺伝的アルゴリズムを上回っていることが示唆された。
論文参考訳（メタデータ） (2024-09-26T12:50:00Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
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)

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