論文の概要: To Repair or Not to Repair? Investigating the Importance of AB-Cycles for the State-of-the-Art TSP Heuristic EAX
- arxiv url: http://arxiv.org/abs/2505.00803v1
- Date: Thu, 01 May 2025 19:04:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-05 17:21:19.800428
- Title: To Repair or Not to Repair? Investigating the Importance of AB-Cycles for the State-of-the-Art TSP Heuristic EAX
- Title（参考訳）: 修復・修復にかかわらないか : 現状TSPヒューリスティックEAXにおけるABサイクルの重要性を探る
- Authors: Jonathan Heins, Darrell Whitley, Pascal Kerschke,
- Abstract要約: Edge Assembly Crossover (EAX)アルゴリズムは、旅行セールスパーソン問題(TSP)を解決するための最先端技術である。
そこで本研究では,内部最適化手順中に生成したABサイクルが,有効なツアーを生成するかどうかを迅速に検証する手法を提案する。
そこで本研究では,EAXの改良版をいくつか提案し,評価する。
- 参考スコア（独自算出の注目度）: 1.8434042562191815
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Edge Assembly Crossover (EAX) algorithm is the state-of-the-art heuristic for solving the Traveling Salesperson Problem (TSP). It regularly outperforms other methods, such as the Lin-Kernighan-Helsgaun heuristic (LKH), across diverse sets of TSP instances. Essentially, EAX employs a two-stage mechanism that focuses on improving the current solutions, first, at the local and, subsequently, at the global level. Although the second phase of the algorithm has been thoroughly studied, configured, and refined in the past, in particular, its first stage has hardly been examined. In this paper, we thus focus on the first stage of EAX and introduce a novel method that quickly verifies whether the AB-cycles, generated during its internal optimization procedure, yield valid tours -- or whether they need to be repaired. Knowledge of the latter is also particularly relevant before applying other powerful crossover operators such as the Generalized Partition Crossover (GPX). Based on our insights, we propose and evaluate several improved versions of EAX. According to our benchmark study across 10 000 different TSP instances, the most promising of our proposed EAX variants demonstrates improved computational efficiency and solution quality on previously rather difficult instances compared to the current state-of-the-art EAX algorithm.
- Abstract（参考訳）: エッジアセンブリ・クロスオーバー(エッジアセンブリ・クロスオーバー、英語: Edge Assembly Crossover、EAX)は、トラベリングセールスパーソン問題(TSP)を解決するための最先端のヒューリスティックアルゴリズムである。
また、Lin-Kernighan-Helsgaun ヒューリスティック (LKH) など、様々な TSP インスタンスにまたがる他の手法を定期的に上回る。
EAXは基本的に、現在のソリューションの改善に焦点を当てた2段階のメカニズムを採用しています。
アルゴリズムの第2段階は過去に徹底的に研究され、構成され、洗練されてきたが、特に第1段階についてはほとんど研究されていない。
そこで本稿では,EAXの第1段階に着目し,内部最適化手順で生成したABサイクルが,有効なツアーを生成するか,修復が必要なか,を迅速に検証する手法を提案する。
後者の知識は、GPX (Generalized Partition Crossover) のような他の強力なクロスオーバー演算子を適用する前にも特に関係がある。
そこで本研究では,EAXの改良版をいくつか提案し,評価する。
10000の異なるTSPインスタンスを対象としたベンチマーク調査によると、提案されているEAXの変種で最も有望なのは、現在の最先端のEAXアルゴリズムと比較して、これまでかなり難しいインスタンスにおける計算効率とソリューション品質の改善である。
関連論文リスト
- Avoiding $\mathbf{exp(R_{max})}$ scaling in RLHF through Preference-based Exploration [20.76451379043945]
RLHF(Reinforcement Learning from Human Feedback)は,大規模言語モデル(LLM)アライメントのための重要な手法として登場した。
本稿では、オンラインRLHFの設定と、サンプル効率の向上に焦点をあてる。
論文 参考訳（メタデータ） (2025-02-02T04:40:04Z) - Deep Active Ensemble Sampling For Image Classification [8.31483061185317]
アクティブラーニングフレームワークは、最も有益なデータポイントのラベル付けを積極的に要求することで、データアノテーションのコストを削減することを目的としている。
提案手法には、不確実性に基づく手法、幾何学的手法、不確実性に基づく手法と幾何学的手法の暗黙の組み合わせなどがある。
本稿では, サンプル選択戦略における効率的な探索・探索トレードオフを実現するために, 不確実性に基づくフレームワークと幾何学的フレームワークの両方の最近の進歩を革新的に統合する。
本フレームワークは,(1)正確な後続推定,(2)計算オーバーヘッドと高い精度のトレードオフの2つの利点を提供する。
論文 参考訳（メタデータ） (2022-10-11T20:20:20Z) - Multipoint-BAX: A New Approach for Efficiently Tuning Particle
Accelerator Emittance via Virtual Objectives [47.52324722637079]
マルチポイントクエリにおけるブラックボックス最適化のための情報理論アルゴリズムであるMultipoint-BAXを提案する。
我々はマルチポイントBAXを用いてLinac Coherent Light Source(LCLS)とAdvanced Accelerator Experimental Tests II(FACET-II)の発光を最小化する。
論文 参考訳（メタデータ） (2022-09-10T04:01:23Z) - Optimizing Two-way Partial AUC with an End-to-end Framework [154.47590401735323]
ROC曲線のエリア(AUC)は、機械学習にとって重要な指標である。
最近の研究は、TPAUCが既存のPartial AUCメトリクスと本質的に矛盾していることを示している。
本論文では,この新指標を最適化するための最初の試行について述べる。
論文 参考訳（メタデータ） (2022-06-23T12:21:30Z) - Efficient Few-Shot Object Detection via Knowledge Inheritance [62.36414544915032]
Few-shot Object Detection (FSOD) は、未確認のタスクに少ないトレーニングサンプルで適応できるジェネリック検出器を学習することを目的としている。
計算量の増加を伴わない効率的なプレトレイン・トランスファー・フレームワーク(PTF)のベースラインを提案する。
また,予測された新しいウェイトと事前訓練されたベースウェイトとのベクトル長の不整合を軽減するために,適応長再スケーリング(ALR)戦略を提案する。
論文 参考訳（メタデータ） (2022-03-23T06:24:31Z) - A Simple Information-Based Approach to Unsupervised Domain-Adaptive
Aspect-Based Sentiment Analysis [58.124424775536326]
本稿では,相互情報に基づくシンプルだが効果的な手法を提案し,それらの用語を抽出する。
実験の結果,提案手法はクロスドメインABSAの最先端手法よりも4.32%高い性能を示した。
論文 参考訳（メタデータ） (2022-01-29T10:18:07Z) - ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
バイレベル最適化(BO)は多くの現代の機械学習問題を解決する強力なツールとして生まれてきた。
既存の勾配法では、ヤコビアンあるいはヘッセンベクトル計算による二階微分近似が必要となる。
本稿では,進化戦略(ES)に基づく新しいBOアルゴリズムを提案し,BOの過勾配における応答ヤコビ行列を近似する。
論文 参考訳（メタデータ） (2021-10-13T19:36:50Z) - Computing Diverse Sets of High Quality TSP Tours by EAX-Based
Evolutionary Diversity Optimisation [10.609857097723266]
旅行セールスパーソン問題(TSP)に対する進化的多様性最適化(EDO)アプローチを導入する。
高品質なソリューションを見つけるだけでなく、人口の多様性を最大化するためにEAXを採用する方法を示す。
既存のアプローチと比較すると、EAX-EDOの方が明らかに優れています。
論文 参考訳（メタデータ） (2021-08-11T03:16:11Z) - Solving Inverse Problems by Joint Posterior Maximization with
Autoencoding Prior [0.0]
JPal Autoencoder (VAE) が先行する画像における不適切な逆問題解決の問題に対処する。
本手法は,提案した目的関数を満たすのに十分であることを示す。
結果は、より堅牢な見積もりを提供するアプローチの堅牢性も示しています。
論文 参考訳（メタデータ） (2021-03-02T11:18:34Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。