論文の概要: Insights from Multi-tasking the EAX Algorithm for the Travelling Salesperson Problem

• arxiv url: http://arxiv.org/abs/2608.12772v1
• Date: Thu, 13 Aug 2026 03:31:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-14 18:29:38.381557
• Title: Insights from Multi-tasking the EAX Algorithm for the Travelling Salesperson Problem
• Title（参考訳）: 旅行セールスマン問題に対するEAXアルゴリズムのマルチタスクによる考察
• Abstract要約: 我々は,古典的トラベリングセールスパーソン問題(TSP)を解決するために,エッジアセンブリクロスオーバー(MT-EAX)と進化的マルチタスクの統合を検討する。 この結果から, MT-EAX は検索の初期段階において, 有効性が高く, 解品質が等しい場合, 60%$から90%$の計算コストを節約できることが示唆された。
• 参考スコア（独自算出の注目度）: 38.89429976668438
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary multitasking allows several related problems to be solved in a single run of an algorithm. In this paper, we investigate integrating evolutionary multitasking with Edge Assembly Crossover (MT-EAX) to solve the classical Travelling Salesperson Problem (TSP). To fairly compare MT-EAX against standard EAX under strict compute budgets, we evaluate three scaling methods: generation scaling, population scaling, and balanced scaling. Our results show that generationally scaled MT-EAX is highly effective compute-wise in the early stages of the search, saving $60\%$ to $90\%$ of compute for equal or better solution quality. We observe that instance geometry has a significant impact, with clustered, normally distributed instances securing larger improvements than uniformly distributed ones. However, when scaling by population or utilising explicit solution transfer, the results are negative due to population starvation and incompatible cross-instance parent selection. We demonstrate that the advantage of MT-EAX derives from increased diversity through parallel search in early generations, which can be successfully preserved using a decoupled configuration to often strictly outperform or match standard EAX performance at final convergence.
• Abstract（参考訳）: 進化的マルチタスクは、アルゴリズムの単一実行でいくつかの関連する問題を解くことができる。 本稿では,従来のトラベリングセールスパーソン問題(TSP)を解決するために,エッジアセンブリクロスオーバー(MT-EAX)と進化的マルチタスキングの統合を検討する。 MT-EAXを厳格な計算予算下で標準EAXと比較するために,生成スケーリング,集団スケーリング,バランスの取れたスケーリングという3つのスケーリング手法を評価した。 この結果から, MT-EAX は検索の初期段階において, 有効性が高く, 解の質が等しければ 60 %$ から 90 %$ に抑えられることがわかった。 クラスタ化された通常分散インスタンスは、一様分散インスタンスよりも大きな改善を確実にする。 しかし、人口別スケーリングや明示的なソリューション移行の活用においては、人口減少と非互換な親選択のため、結果は否定的である。 MT-EAXの利点は、初期における並列探索による多様性の向上に起因し、分離された構成で保存し、最終的な収束時に標準的なEAX性能を厳密に上回ったり、一致させたりすることができることを実証する。

関連論文リスト

• Exploring Test-time Scaling via Prediction Merging on Large-Scale Recommendation [13.057539100440634]
  テスト期間中に計算資源を効率的に活用し、スケールアップする方法は、まだ未定である。 DLRSにテスト時間スケーリングを適用する上で重要なポイントは、多様だが有意義なアウトプットを効果的に生成することにある。 オンラインデプロイ時の並列サーバの増加により、テスト時間のスケーリングはシームレスに加速できる。
  論文  参考訳（メタデータ） (2025-12-08T15:41:10Z)
• ATTS: Asynchronous Test-Time Scaling via Conformal Prediction [112.54016379556073]
  大規模な言語モデル(LLM)は、テスト時のスケーリングの恩恵を受けるが、しばしば高い推論遅延によって妨げられる。 統計的に保証された適応スケーリングフレームワークであるATTS(Asynchronous Test-Time Scaling)を紹介する。 ATTSは、テストタイムのスケーリングにおいて最大56.7倍のスピードアップと4.14倍のスループット向上を実現している。
  論文  参考訳（メタデータ） (2025-09-18T16:55:09Z)
• Revisiting End-to-End Learning with Slide-level Supervision in Computational Pathology [53.63533391049205]
  教師付きエンドツーエンド学習(E2E)は,高い計算要求や準最適結果などの課題に直面していることを示す。 この問題を軽減するために, ABMILX と呼ばれる新しい MIL を提案する。 E2EトレーニングされたResNetとAMMILXは、2段階のパラダイムの下でSOTA基盤モデルを上回る。
  論文  参考訳（メタデータ） (2025-06-03T03:46:50Z)
• To Repair or Not to Repair? Investigating the Importance of AB-Cycles for the State-of-the-Art TSP Heuristic EAX [1.8434042562191815]
  Edge Assembly Crossover (EAX)アルゴリズムは、旅行セールスパーソン問題(TSP)を解決するための最先端技術である。 そこで本研究では,内部最適化手順中に生成したABサイクルが,有効なツアーを生成するかどうかを迅速に検証する手法を提案する。 そこで本研究では,EAXの改良版をいくつか提案し,評価する。
  論文  参考訳（メタデータ） (2025-05-01T19:04:23Z)
• When To Solve, When To Verify: Compute-Optimal Problem Solving and Generative Verification for LLM Reasoning [87.88936168664344]
  大規模な言語モデルの推論能力を向上するための重要な戦略として、テスト時間計算のスケーリングが登場した。 次世代予測課題としてのジェネレーティブ・リワード・モデル(GenRM)再フレーム検証の最近の進歩 我々は、さまざまなモデルやデータセットにまたがる最も実用的な推論予算について、GenRMと自己整合性(SC)を評価した。
  論文  参考訳（メタデータ） (2025-04-01T17:41:57Z)
• Efficient Distributed Learning over Decentralized Networks with Convoluted Support Vector Machine [2.722434989508884]
  本稿では,分散ネットワーク上での高次元データを効率的に分類する問題に対処する。 我々は、ペナル化SVMを解くために、乗算器の効率的な一般化交互方向法(ADMM)を開発した。
  論文  参考訳（メタデータ） (2025-03-10T17:31:26Z)
• A Parallel Ensemble of Metaheuristic Solvers for the Traveling Salesman Problem [2.44755919161855]
  トラベリングセールスマン問題(TSP)は、文献でよく研究されているNPハード問題の一つである。 最近の研究は、再起動機構を持つEAXが広範囲のTSPインスタンスで良好に動作することを示唆している。 2,000から85,900の問題について検討する。 ハイブリッド版のアンサンブルは、1万以上の都市で、最先端の問題解決者より優れています。
  論文  参考訳（メタデータ） (2023-08-13T21:12:56Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable Crossover Probability [4.33419118449588]
  我々は、突然変異またはランダムに選択された2人の親の再結合によって子孫を生成する、$(mu+lambda)$ Genetic Algorithms (GAs)の家系を調査する。 クロスオーバー確率を拡大することにより、完全突然変異のみのアルゴリズムから完全クロスオーバーベースGAへの補間が可能となる。
  論文  参考訳（メタデータ） (2020-06-10T15:22:44Z)
• XEM: An Explainable-by-Design Ensemble Method for Multivariate Time Series Classification [61.33695273474151]
  マルチ変数時系列分類のためのeXplainable-by-design Ensemble法であるXEMを提案する。 XEMは、明示的なブースティング・バッグ・アプローチと暗黙的なディペンション・アンド・コンカ・アプローチを組み合わせた新しいハイブリッド・アンサンブル法に依存している。 評価の結果、XEM は、パブリック UEA データセット上で最先端の MTS 分類器よりも優れていることがわかった。
  論文  参考訳（メタデータ） (2020-05-07T17:50:18Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。