論文の概要: Niching-based Evolutionary Diversity Optimization for the Traveling Salesperson Problem

• arxiv url: http://arxiv.org/abs/2201.10316v2
• Date: Tue, 19 Apr 2022 03:41:53 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-27 22:41:57.660635
• Title: Niching-based Evolutionary Diversity Optimization for the Traveling Salesperson Problem
• Title（参考訳）: ニッチに基づく旅行セールスパーソン問題の進化的多様性最適化
• Authors: Anh Viet Do, Mingyu Guo, Aneta Neumann, Frank Neumann
• Abstract要約: 本稿では,旅行セールスパーソン問題(TSP)に対するツアーの集合を,所定のコスト制約を満たしつつ,多様性を最大化する問題を考える。 本研究は, ニッチ適用による多様性の最大化効果を, 単に維持することよりも検討することを目的とする。
• 参考スコア（独自算出の注目度）: 17.268191781480745
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we consider the problem of finding a set of tours to a traveling salesperson problem (TSP) instance maximizing diversity, while satisfying a given cost constraint. This study aims to investigate the effectiveness of applying niching to maximize diversity rather than simply maintaining it. To this end, we introduce a 2-stage approach where a simple niching memetic algorithm (NMA), derived from a state-of-the-art for multi-solution TSP, is combined with a baseline diversifying algorithm. The most notable feature of the proposed NMA is the use of randomized improvement-first local search instead of 2-opt. Our experiment on TSPLIB instances shows that while the populations evolved by our NMA tend to contain clusters at tight quality constraints, they frequently occupy distant basins of attraction rather than close-by regions, improving on the baseline diversification in terms of sum-sum diversity. Compared to the original NMA, ours, despite its simplicity, finds more distant solutions of higher quality within less running time, by a large margin.
• Abstract（参考訳）: 本研究では,旅行セールスパーソン問題 (TSP) に対するツアーの集合を,所定のコスト制約を満たしつつ,多様性を最大化する問題を考える。 本研究は, ニチングを適用して多様性を最大化する効果を, 単に維持することよりも検討することを目的とする。 そこで本研究では,マルチソリューション TSP の最先端技術から派生した単純なニッチ・メメティックアルゴリズム (NMA) をベースライン多様化アルゴリズムと組み合わせた2段階手法を提案する。 提案したNMAの最も重要な特徴は、2オプトの代わりにランダム化された改善優先の局所探索を使用することである。 TSPLIB を用いた実験では,NMA によって発達した個体群は,厳密な品質制約で群集を包含する傾向にあるが,近縁な地域よりも遠縁なアトラクションの流域をしばしば占有し,総和多様性の点からベースラインの多様性の向上が示されている。 オリジナルのNMAと比較すると、単純さにもかかわらず、より少ない実行時間でより高い品質のソリューションを、大きなマージンで見つけることができます。

関連論文リスト

• Balancing Pareto Front exploration of Non-dominated Tournament Genetic Algorithm (B-NTGA) in solving multi-objective NP-hard problems with constraints [0.0]
  提案手法をB-NTGA(B-NTGA)に適用した新しい平衡選択演算子を提案する。 提案したB-NTGAは,Thief Traveling ProblemやMulti-Skill Resource-Constrained Project Scheduling Problemのような,多目的および多目的の現実世界の2つのベンチマークで検討した。 実験の結果,B-NTGAは最先端手法よりも効率が高く,性能も優れていた。
  論文  参考訳（メタデータ） (2024-10-08T05:34:13Z)
• Illuminating the Diversity-Fitness Trade-Off in Black-Box Optimization [9.838618121102053]
  現実世界のアプリケーションでは、ユーザーは1つの高品質なソリューションよりも構造的に多様な設計選択を好むことが多い。 本稿では, この課題に対する新たな視点として, 与えられたしきい値を超えるペア距離の一定数の解を同定する問題を考察する。
  論文  参考訳（メタデータ） (2024-08-29T09:55:55Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。 赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
  論文  参考訳（メタデータ） (2024-06-21T05:57:08Z)
• A Unified Algorithm Framework for Unsupervised Discovery of Skills based on Determinantal Point Process [53.86223883060367]
  教師なしオプション発見における多様性とカバレッジは、実際には同じ数学的枠組みの下で統一可能であることを示す。 提案アルゴリズムであるODPPは,MujocoとAtariで作成した課題に対して,広範囲に評価されている。
  論文  参考訳（メタデータ） (2022-12-01T01:40:03Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  本稿では,平均場近似ポリシ最適化(MF-PPO)アルゴリズムを提案する。 我々は,MF-PPOが収束のサブ線形速度で世界的最適政策を達成することを証明した。 特に、置換不変ニューラルアーキテクチャによって引き起こされる誘導バイアスは、MF-PPOが既存の競合より優れていることを示す。
  論文  参考訳（メタデータ） (2021-05-18T04:35:41Z)
• Niching Diversity Estimation for Multi-modal Multi-objective Optimization [9.584279193016522]
  ニッチは進化的多目的最適化において重要かつ広く用いられている手法である。 MMOPでは、対象空間の解は決定空間に複数の逆像を持つことができ、これは等価解と呼ばれる。 MMOPの処理において、標準多様性推定器をより効率的にするために、一般的なニチング機構を提案する。
  論文  参考訳（メタデータ） (2021-01-31T05:23:31Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• Hybrid Adaptive Evolutionary Algorithm for Multi-objective Optimization [0.0]
  本稿では、MoHAEAと呼ばれるハイブリッド適応進化アルゴリズム(HAEA)の拡張として、新しい多目的アルゴリズムを提案する。 MoHAEAは、MOEA/D、pa$lambda$-MOEA/D、MOEA/D-AWA、NSGA-IIの4つの状態と比較される。
  論文  参考訳（メタデータ） (2020-04-29T02:16:49Z)
• dMFEA-II: An Adaptive Multifactorial Evolutionary Algorithm for Permutation-based Discrete Optimization Problems [6.943742860591444]
  本稿では、最近導入されたMFEA-II(Multifactorial Evolutionary Algorithm II)を、置換に基づく離散環境に適用する。 提案手法の性能を5種類のマルチタスク設定で評価した。
  論文  参考訳（メタデータ） (2020-04-14T14:42:47Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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