論文の概要: High-level hybridization of heuristics and metaheuristics to solve symmetric TSP: a comparative study
- arxiv url: http://arxiv.org/abs/2410.21274v1
- Date: Mon, 28 Oct 2024 17:59:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-29 12:23:03.945213
- Title: High-level hybridization of heuristics and metaheuristics to solve symmetric TSP: a comparative study
- Title（参考訳）: 対称TSPを解くためのヒューリスティックスとメタヒューリスティックスの高レベルハイブリッド化 : 比較研究
- Authors: Carlos Alberto da Silva Junior, Roberto Yuji Tanaka, Luiz Carlos Farias da Silva, Angelo Passaro,
- Abstract要約: トラベリングセールスマン問題 - TSPは、経済、輸送、物流に関する真の問題を解決するために、科学文献の中で最も検討された問題の1つである。
本稿では,高次ハイブリッド化を用いた古典的TSPの解に焦点をあてる。
50から280都市での問題は解決されている。
- 参考スコア（独自算出の注目度）: 0.1874930567916036
- License:
- Abstract: The Travelling Salesman Problem - TSP is one of the most explored problems in the scientific literature to solve real problems regarding the economy, transportation, and logistics, to cite a few cases. Adapting TSP to solve different problems has originated several variants of the optimization problem with more complex objectives and different restrictions. Metaheuristics have been used to solve the problem in polynomial time. Several studies have tried hybridising metaheuristics with specialised heuristics to improve the quality of the solutions. However, we have found no study to evaluate whether the searching mechanism of a particular metaheuristic is more adequate for exploring hybridization. This paper focuses on the solution of the classical TSP using high-level hybridisations, experimenting with eight metaheuristics and heuristics derived from k-OPT, SISR, and segment intersection search, resulting in twenty-four combinations. Some combinations allow more than one set of searching parameters. Problems with 50 to 280 cities are solved. Parameter tuning of the metaheuristics is not carried out, exploiting the different searching patterns of the eight metaheuristics instead. The solutions' quality is compared to those presented in the literature.
- Abstract（参考訳）: トラベリングセールスマン問題 - TSPは、経済、輸送、物流に関する真の問題を解決するために科学文献の中で最も検討された問題の1つであり、いくつかの事例を引用している。
異なる問題を解決するためにTSPを適用することは、より複雑な目的と異なる制約を持つ最適化問題のいくつかの変種に端を発している。
メタヒューリスティックスは多項式時間でこの問題を解決するために使われてきた。
いくつかの研究は、解の質を改善するために、メタヒューリスティックスと専門のヒューリスティックスとのハイブリッド化を試みた。
しかし, 特定のメタヒューリスティックの探索機構が, ハイブリダイゼーションの探索に適しているかどうかを評価する研究は行われていない。
本稿では, k-OPT, SISR, セグメント交叉探索から得られた8つのメタヒューリスティックおよびヒューリスティックスを用いて, 高レベルなハイブリッド化を用いた古典的TSPの解について検討する。
いくつかの組み合わせは複数の探索パラメータを許容する。
50から280都市での問題は解決されている。
メタヒューリスティックスのパラメータチューニングは行わず、代わりに8つのメタヒューリスティックの異なる探索パターンを利用する。
解の質は文献で示されたものと比較される。
関連論文リスト
- Metaheuristics for the Template Design Problem: Encoding, Symmetry and Hybridisation [0.0]
テンプレート設計問題(TDP)は、多くの対称性を持つ難しい問題であり、それをより複雑にしている。
本稿では,テンプレート設計の適合性を評価することを目的として,多種多様なメタヒューリスティクスを探索し,解析する。
論文 参考訳（メタデータ） (2024-11-05T06:29:12Z) - Towards Multi-Objective High-Dimensional Feature Selection via
Evolutionary Multitasking [63.91518180604101]
本稿では,高次元特徴選択問題,すなわちMO-FSEMTのための新しいEMTフレームワークを開発する。
タスク固有の知識伝達機構は、各タスクの利点情報を活用するように設計され、高品質なソリューションの発見と効果的な伝達を可能にする。
論文 参考訳（メタデータ） (2024-01-03T06:34:39Z) - 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) - Applying Autonomous Hybrid Agent-based Computing to Difficult
Optimization Problems [56.821213236215634]
本稿では,EMASのハイブリッドバージョンを提案する。
これには、複数のハイブリッド演算子の選択と導入、およびメインアルゴリズムのハイブリッドステップを開始するためのルールの定義が含まれる。
これらのハイブリッドステップは、既存の、よく知られた、そして証明された、効率的なメタヒューリスティックスを活用し、その結果をメインのアルゴリズムに統合する。
論文 参考訳（メタデータ） (2022-10-24T13:28:35Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Solving the Travelling Thief Problem based on Item Selection Weight and
Reverse Order Allocation [8.620967398331265]
旅行泥棒問題(TTP)は多くの学者を引き付ける挑戦的な最適化問題です。
本論文では,TTPを理論的および実証的に検討する。
提案した選択項目と逆順序のソート項目の定式化によって算出されたスコア値に基づくアルゴリズムを提案し,この問題を解く。
論文 参考訳（メタデータ） (2020-12-16T12:06:05Z) - AT-MFCGA: An Adaptive Transfer-guided Multifactorial Cellular Genetic
Algorithm for Evolutionary Multitasking [17.120962133525225]
本稿では,進化的マルチタスク環境を扱うための適応メタヒューリスティックアルゴリズムを提案する。
AT-MFCGAはセルラーオートマトンを利用して、検討中の最適化問題の知識を交換する機構を実装している。
論文 参考訳（メタデータ） (2020-10-08T12:00:10Z) - Dise\~no e implementaci\'on de una meta-heur\'istica multi-poblacional
de optimizaci\'on combinatoria enfocada a la resoluci\'on de problemas de
asignaci\'on de rutas a veh\'iculos [1.223416994447554]
この論文は、さまざまな種類の車両ルーティング問題を解決するための新しいメタヒューリスティックの開発に注力する。
メタヒューリスティックによって得られた結果は、類似した哲学の他の4つのアルゴリズムによって得られたものと比較された。
論文 参考訳（メタデータ） (2020-03-24T14:43:41Z) - Multi-Task Multicriteria Hyperparameter Optimization [77.34726150561087]
この記事は最適なハイパーパラメータを選択する問題に関する数学的定式化から始まる。
この問題を解決するMTMC法の手順を述べる。
提案手法は畳み込みニューラルネットワークを用いて画像分類問題に対して評価する。
論文 参考訳（メタデータ） (2020-02-15T12:47:53Z) - Dynamic Multi-objective Optimization of the Travelling Thief Problem [4.859986264602551]
現実的なシナリオを反映した詳細かつ複雑な最適化問題の定式化の研究は、急成長する研究分野である。
トラベリング・ティーフ問題(Traveling Thief Problem)には、多目的の定式化や、それを解決するための正確で近似的な方法の比較を含む、増大する作業体が存在する。
TTP問題の3つの領域におけるダイナミックスの定義には、都市部、アベイラビリティマップ、アイテム値がある。
動的変化に応答して, 溶液生成法を混合して複合集団を提供する組み合わせアプローチは, 動的TTP定式化の異なるインスタンスにおいて, 性能を向上する。
論文 参考訳（メタデータ） (2020-02-07T06:33:05Z) - Pareto Multi-Task Learning [53.90732663046125]
マルチタスク学習は複数の相関タスクを同時に解くための強力な方法である。
異なるタスクが互いに衝突する可能性があるため、すべてのタスクを最適化するひとつのソリューションを見つけることは、しばしば不可能である。
近年,マルチタスク学習を多目的最適化として活用することにより,タスク間のトレードオフが良好である1つのパレート最適解を求める方法が提案されている。
論文 参考訳（メタデータ） (2019-12-30T08:58:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。