論文の概要: Exploring the Feature Space of TSP Instances Using Quality Diversity

• arxiv url: http://arxiv.org/abs/2202.02077v2
• Date: Tue, 12 Apr 2022 08:06:49 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-26 21:01:14.911034
• Title: Exploring the Feature Space of TSP Instances Using Quality Diversity
• Title（参考訳）: 品質多様性を用いたTSPインスタンスの特徴空間の探索
• Authors: Jakob Bossek, Frank Neumann
• Abstract要約: 機能領域全体を探索できる品質多様性(QD)に基づく新しいアプローチを提案する。 QDアルゴリズムは、ボックスに分割し、各ボックス内のソリューション品質を改善することで、所定の機能空間内で高品質なソリューションを作成することができる。
• 参考スコア（独自算出の注目度）: 13.264683014487376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Generating instances of different properties is key to algorithm selection methods that differentiate between the performance of different solvers for a given combinatorial optimization problem. A wide range of methods using evolutionary computation techniques has been introduced in recent years. With this paper, we contribute to this area of research by providing a new approach based on quality diversity (QD) that is able to explore the whole feature space. QD algorithms allow to create solutions of high quality within a given feature space by splitting it up into boxes and improving solution quality within each box. We use our QD approach for the generation of TSP instances to visualize and analyze the variety of instances differentiating various TSP solvers and compare it to instances generated by a $(\mu+1)$-EA for TSP instance generation.
• Abstract（参考訳）: 異なる性質のインスタンスを生成することは、与えられた組合せ最適化問題に対する異なる解法の性能を区別するアルゴリズム選択手法の鍵となる。 近年,進化計算技術を用いた多種多様な手法が提案されている。 本稿では,品質多様性(qd)に基づく新たなアプローチを提供し,機能領域全体を探索することで,この領域の研究に寄与する。 QDアルゴリズムは、ボックスに分割し、各ボックス内のソリューション品質を改善することで、所定の機能空間内で高品質なソリューションを作成することができる。 我々は、TSPインスタンスの生成にQDアプローチを使用して、様々なTSPソルバを識別する様々なインスタンスを視覚化し分析し、TSPインスタンスの生成に$(\mu+1)$-EAで生成されたインスタンスと比較する。

関連論文リスト

• Large Language Models as In-context AI Generators for Quality-Diversity [8.585387103144825]
  In-context QDは、QDアーカイブから品質の異なる例をコンテキストとして、少数ショットと多ショットのプロンプトを使って興味深いソリューションを生成することを目的としている。 In-context QD display promising results than both QD baselines and similar strategy developed for single-jective optimization。
  論文  参考訳（メタデータ） (2024-04-24T10:35:36Z)
• 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)
• A Pareto-optimal compositional energy-based model for sampling and optimization of protein sequences [55.25331349436895]
  深層生成モデルは、生命科学における逆問題に対する一般的な機械学習ベースのアプローチとして登場した。 これらの問題は、データ分布の学習に加えて、興味のある複数の特性を満たす新しい設計をサンプリングする必要があることが多い。
  論文  参考訳（メタデータ） (2022-10-19T19:04:45Z)
• Analysis of Quality Diversity Algorithms for the Knapsack Problem [14.12876643502492]
  我々は,knapsack問題における動的プログラミング動作のシミュレーションにQDパラダイムを適用した。 予測された擬似ポリノミカル時間内に最適解を計算することができることを示す。
  論文  参考訳（メタデータ） (2022-07-28T12:15:33Z)
• Evolutionary Diversity Optimisation for The Traveling Thief Problem [11.590506672325668]
  解の集合の構造的多様性を最大化する二段階の進化的アルゴリズムを導入する。 多様性を得る最良の方法を実証的に決定する。 実験の結果,ほとんどのTTPベンチマークインスタンスにおける構造的多様性の観点から,QDアプローチの大幅な改善が示された。
  論文  参考訳（メタデータ） (2022-04-06T10:13:55Z)
• Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods [73.35353358543507]
  SGDA(Gradient Descent-Ascent)は、min-max最適化と変分不等式問題(VIP)を解くための最も顕著なアルゴリズムの1つである。 本稿では,多種多様な降下指数法を網羅した統合収束解析を提案する。 本研究では,新しい分散化手法 (L-SVRGDA) や,新しい分散圧縮方式 (QSGDA, DIANA-SGDA, VR-DIANA-SGDA) ,座標ランダム化方式 (SEGA-SGDA) など,SGDAの新しい変種を開発した。
  論文  参考訳（メタデータ） (2022-02-15T09:17:39Z)
• Expressivity of Parameterized and Data-driven Representations in Quality Diversity Search [111.06379262544911]
  2つの異なる検索空間で実施した品質多様性進化探索の出力多様性を比較する。 学習モデルは、未知の例への外挿や拡大よりも、既知のデータポイント間の補間が優れている。
  論文  参考訳（メタデータ） (2021-05-10T10:27:43Z)
• Ensemble Feature Extraction for Multi-Container Quality-Diversity Algorithms [0.2741266294612775]
  品質多様性アルゴリズムは多種多様な高性能なソリューションのコレクションを探索する。 MC-AURORA(Quality-Diversity approach)について述べる。 このアプローチは、単一表現アプローチによって生成されるソリューションよりも、より多様なソリューションを生成することを示す。
  論文  参考訳（メタデータ） (2021-05-03T08:35:00Z)
• Isometric Multi-Shape Matching [50.86135294068138]
  形状間の対応を見つけることは、コンピュータビジョンとグラフィックスの基本的な問題である。 アイソメトリーは形状対応問題においてしばしば研究されるが、マルチマッチング環境では明確には考慮されていない。 定式化を解くのに適した最適化アルゴリズムを提案し,コンバージェンスと複雑性解析を提供する。
  論文  参考訳（メタデータ） (2020-12-04T15:58:34Z)
• BOP-Elites, a Bayesian Optimisation algorithm for Quality-Diversity search [0.0]
  本稿では,エリートアルゴリズム(BOP-Elites)のベイズ最適化を提案する。 機能領域のユーザ定義領域を‘ニッチ’として考えることで、ニッチ毎に最適なソリューションを見つけることが私たちのタスクになります。 得られたアルゴリズムは、特徴空間におけるニッチに属する探索空間の部分を特定し、ニッチごとに最適な解を見つけるのに非常に効果的である。
  論文  参考訳（メタデータ） (2020-05-08T23:49:13Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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