論文の概要: Computing Diverse Sets of High Quality TSP Tours by EAX-Based
Evolutionary Diversity Optimisation
- arxiv url: http://arxiv.org/abs/2108.05005v2
- Date: Thu, 12 Aug 2021 01:07:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-18 19:25:53.651352
- Title: Computing Diverse Sets of High Quality TSP Tours by EAX-Based
Evolutionary Diversity Optimisation
- Title（参考訳）: EAXに基づく進化的多様性最適化による高品質TSPツアーの計算
- Authors: Adel Nikfarjam, Jakob Bossek, Aneta Neumann, and Frank Neumann
- Abstract要約: 旅行セールスパーソン問題(TSP)に対する進化的多様性最適化(EDO)アプローチを導入する。
高品質なソリューションを見つけるだけでなく、人口の多様性を最大化するためにEAXを採用する方法を示す。
既存のアプローチと比較すると、EAX-EDOの方が明らかに優れています。
- 参考スコア（独自算出の注目度）: 10.609857097723266
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary algorithms based on edge assembly crossover (EAX) constitute
some of the best performing incomplete solvers for the well-known traveling
salesperson problem (TSP). Often, it is desirable to compute not just a single
solution for a given problem, but a diverse set of high quality solutions from
which a decision maker can choose one for implementation. Currently, there are
only a few approaches for computing a diverse solution set for the TSP.
Furthermore, almost all of them assume that the optimal solution is known. In
this paper, we introduce evolutionary diversity optimisation (EDO) approaches
for the TSP that find a diverse set of tours when the optimal tour is known or
unknown. We show how to adopt EAX to not only find a high-quality solution but
also to maximise the diversity of the population. The resulting EAX-based EDO
approach, termed EAX-EDO is capable of obtaining diverse high-quality tours
when the optimal solution for the TSP is known or unknown. A comparison to
existing approaches shows that they are clearly outperformed by EAX-EDO.
- Abstract（参考訳）: エッジアセンブリクロスオーバー(EAX)に基づく進化的アルゴリズムは、よく知られた旅行セールスパーソン問題(TSP)の最も優れた不完全な解法の一つである。
多くの場合、特定の問題に対する単一のソリューションだけでなく、意思決定者が実装のために1つを選択できる様々な高品質なソリューションのセットを計算することが望ましい。
現在、TSPの多様なソリューションセットを計算するためのアプローチはわずかである。
さらに、それらのほとんど全てが最適解が知られていると仮定している。
本稿では,TSPにおける進化的多様性最適化(EDO)アプローチについて紹介する。
高品質なソリューションを見つけるだけでなく、人口の多様性を最大化するためにEAXを採用する方法を示す。
EAX-EDO(EAX-EDO)と呼ばれるEAXベースのEDOアプローチは、TSPの最適解が分かっていない場合、様々な高品質なツアーを得ることができる。
既存のアプローチと比較すると、EAX-EDOの方が明らかに優れています。
関連論文リスト
- 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) - Obtaining Smoothly Navigable Approximation Sets in Bi-Objective
Multi-Modal Optimization [0.0]
MM-BezEAは、個々のニッチをカバーし、固有の決定空間の滑らかさを示す近似セットを生成する。
MM-BezEAは最高の超体積の点で最高の性能を示した。
論文 参考訳（メタデータ） (2022-03-17T10:05:54Z) - An Analysis of Phenotypic Diversity in Multi-Solution Optimization [118.97353274202749]
マルチモーダル最適化は高い適合性ソリューションを生み出し、品質の多様性は遺伝的中立性に敏感ではない。
オートエンコーダは表現型特徴を自動的に発見するために使用され、品質の多様性を備えたさらに多様なソリューションセットを生成する。
論文 参考訳（メタデータ） (2021-05-10T10:39:03Z) - Ensemble Feature Extraction for Multi-Container Quality-Diversity
Algorithms [0.2741266294612775]
品質多様性アルゴリズムは多種多様な高性能なソリューションのコレクションを探索する。
MC-AURORA(Quality-Diversity approach)について述べる。
このアプローチは、単一表現アプローチによって生成されるソリューションよりも、より多様なソリューションを生成することを示す。
論文 参考訳（メタデータ） (2021-05-03T08:35:00Z) - Ensuring smoothly navigable approximation sets by Bezier curve
parameterizations in evolutionary bi-objective optimization -- applied to
brachytherapy treatment planning for prostate cancer [0.0]
決定空間における滑らかなベジエ曲線として近似集合をパラメータ化する場合について検討する。
高品質な近似集合をBezEAで得ることができ、時には支配とUHVに基づくアルゴリズムよりも優れていることを示す。
論文 参考訳（メタデータ） (2020-06-11T13:57:33Z) - BOP-Elites, a Bayesian Optimisation algorithm for Quality-Diversity
search [0.0]
本稿では,エリートアルゴリズム(BOP-Elites)のベイズ最適化を提案する。
機能領域のユーザ定義領域を‘ニッチ’として考えることで、ニッチ毎に最適なソリューションを見つけることが私たちのタスクになります。
得られたアルゴリズムは、特徴空間におけるニッチに属する探索空間の部分を特定し、ニッチごとに最適な解を見つけるのに非常に効果的である。
論文 参考訳（メタデータ） (2020-05-08T23:49:13Z) - An Eigenspace Divide-and-Conquer Approach for Large-Scale Optimization [9.501723707464432]
ディバイド・アンド・コンカー(DC)の進化的アルゴリズムは、大規模な最適化問題に対処する上で顕著な成功を収めた。
本研究では,固有空間分割・コンカレント(EDC)手法を提案する。
論文 参考訳（メタデータ） (2020-04-05T07:29:44Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。
このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。
本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文 参考訳（メタデータ） (2020-03-11T13:52:41Z) - Discovering Representations for Black-box Optimization [73.59962178534361]
ブラックボックス最適化符号化は手作業で行うのではなく,自動的に学習可能であることを示す。
学習された表現は、標準的なMAP-Elitesよりも桁違いに少ない評価で高次元の問題を解くことができることを示す。
論文 参考訳（メタデータ） (2020-03-09T20:06:20Z) - GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal
Black Box Constraint Satisfaction [69.94831587339539]
本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。
我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
論文 参考訳（メタデータ） (2020-02-17T20:21:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。