論文の概要: Devolutionary genetic algorithms with application to the minimum
labeling Steiner tree problem
- arxiv url: http://arxiv.org/abs/2004.10048v1
- Date: Sat, 18 Apr 2020 13:27:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-12 05:00:23.038802
- Title: Devolutionary genetic algorithms with application to the minimum
labeling Steiner tree problem
- Title（参考訳）: 進化的遺伝的アルゴリズムと最小ラベル付けスタイナーツリー問題への応用
- Authors: Nassim Dehouche
- Abstract要約: 本稿では、進化的遺伝的アルゴリズムを特徴付けるとともに、最小ラベル付けスタイナーツリー(MLST)問題を解く際の性能を評価する。
我々は、進化的アルゴリズムを、時間とともに超最適で実現不可能な解の集団を進化させることによって実現可能な解に到達する過程として定義する。
我々は, 交叉, 突然変異, 適合性などの古典的進化的概念が, 最適解, 最適解に到達するためにどのように適応できるかを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper characterizes and discusses devolutionary genetic algorithms and
evaluates their performances in solving the minimum labeling Steiner tree
(MLST) problem. We define devolutionary algorithms as the process of reaching a
feasible solution by devolving a population of super-optimal unfeasible
solutions over time. We claim that distinguishing them from the widely used
evolutionary algorithms is relevant. The most important distinction lies in the
fact that in the former type of processes, the value function decreases over
successive generation of solutions, thus providing a natural stopping condition
for the computation process. We show how classical evolutionary concepts, such
as crossing, mutation and fitness can be adapted to aim at reaching an optimal
or close-to-optimal solution among the first generations of feasible solutions.
We additionally introduce a novel integer linear programming formulation of the
MLST problem and a valid constraint used for speeding up the devolutionary
process. Finally, we conduct an experiment comparing the performances of
devolutionary algorithms to those of state of the art approaches used for
solving randomly generated instances of the MLST problem. Results of this
experiment support the use of devolutionary algorithms for the MLST problem and
their development for other NP-hard combinatorial optimization problems.
- Abstract（参考訳）: 本稿では,進化的遺伝的アルゴリズムを特徴付け,議論し,最小ラベリングスタイナー木(mlst)問題を解く際の性能評価を行う。
我々は、超最適解の集団を時間をかけて回転させることによって実現可能な解に到達する過程として、進化的アルゴリズムを定義する。
広く使われている進化的アルゴリズムと区別することは適切であると主張する。
最も重要な違いは、以前のタイプのプロセスでは、値関数が連続した世代の解よりも減少し、計算プロセスに自然停止条件を与えるという事実にある。
われわれは, 交差, 突然変異, 適合性などの古典的進化的概念が, 第一世代の実現可能な解の最適解, 最適解に到達するためにどのように適応できるかを示す。
さらに,mlst問題に対する新しい整数線形計画定式化と,進化過程の高速化に有効な制約を導入する。
最後に,devolutionaryアルゴリズムの性能と,mlst問題のランダム生成問題の解法として用いられる最先端手法との比較実験を行う。
この実験の結果は、mlst問題に対するdevolutionaryアルゴリズムの使用と、他のnp-hard combinatorial optimization問題に対するそれらの開発をサポートする。
関連論文リスト
- Benchmarking Differential Evolution on a Quantum Simulator [0.0]
微分進化(DE)はラストリギン関数やローゼンブロック関数などの関数の最小値を計算するために用いられる。
この研究は、古典的チューリングモデル計算で生成される候補個体を用いて、これらの関数にDE法を適用した結果の研究である。
論文 参考訳（メタデータ） (2023-11-06T14:27:00Z) - Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic
Algorithm for Solving Combinatorial Optimization Problems [1.8434042562191815]
遺伝的アルゴリズム(GA)は最適化問題の解法における効率性で知られている。
本稿では遺伝子工学の概念からインスピレーションを得るため,遺伝子工学アルゴリズム(GEA)と呼ばれる新しいメタヒューリスティックアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-28T13:05:30Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Doubly Stochastic Matrix Models for Estimation of Distribution
Algorithms [2.28438857884398]
本稿では,自然置換問題のマッチングと割当てにDSM(Douubly Matrices)を用いる方法について検討する。
具体的には、分散アルゴリズムの推定の枠組みを採用し、DSMを置換問題に対する既存の提案と比較する。
二次代入問題の事例に関する予備実験は、この研究の行を検証し、DSMが非常に競争力のある結果が得られることを示した。
論文 参考訳（メタデータ） (2023-04-05T14:36:48Z) - Evolving Evolutionary Algorithms using Linear Genetic Programming [0.0]
このモデルは線形遺伝的プログラミング(LGP)技術に基づいている。
機能最適化のためのいくつかの進化的アルゴリズム、トラベリングセールスマン問題、および擬似アサインメント問題は、検討されたモデルを用いて進化する。
論文 参考訳（メタデータ） (2021-08-21T19:15:07Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳（メタデータ） (2021-06-09T08:05:36Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - AdaLead: A simple and robust adaptive greedy search algorithm for
sequence design [55.41644538483948]
我々は、容易で、拡張性があり、堅牢な進化的欲求アルゴリズム(AdaLead)を開発した。
AdaLeadは、様々な生物学的に動機づけられたシーケンスデザインの課題において、アートアプローチのより複雑な状態を克服する、驚くほど強力なベンチマークである。
論文 参考訳（メタデータ） (2020-10-05T16:40:38Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Genetic optimization algorithms applied toward mission computability
models [0.3655021726150368]
遺伝的アルゴリズムは計算ベースであり、計算に低コストである。
遺伝的最適化アルゴリズムをミッションクリティカルかつ制約対応の問題に記述する。
論文 参考訳（メタデータ） (2020-05-27T00:45:24Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。