論文の概要: Analysis of Evolutionary Diversity Optimisation for Permutation Problems
- arxiv url: http://arxiv.org/abs/2102.11469v4
- Date: Mon, 31 Oct 2022 02:38:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-10 03:48:34.316120
- Title: Analysis of Evolutionary Diversity Optimisation for Permutation Problems
- Title（参考訳）: 変分問題に対する進化的多様性最適化の解析
- Authors: Anh Viet Do and Mingyu Guo and Aneta Neumann and Frank Neumann
- Abstract要約: 最もよく研究された置換問題の3つに対する進化的多様性最適化に関する研究
その結果、これらの問題に対する多くの突然変異演算子により、最大多様な個体群への収束が保証された。
QAPLIBおよび合成インスタンス上で、制約のない、制約のない環境で実験を行う。
- 参考スコア（独自算出の注目度）: 17.268191781480745
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Generating diverse populations of high quality solutions has gained interest
as a promising extension to the traditional optimization tasks. This work
contributes to this line of research with an investigation on evolutionary
diversity optimization for three of the most well-studied permutation problems,
namely the Traveling Salesperson Problem (TSP), both symmetric and asymmetric
variants, and Quadratic Assignment Problem (QAP). It includes an analysis of
the worst-case performance of a simple mutation-only evolutionary algorithm
with different mutation operators, using an established diversity measure.
Theoretical results show many mutation operators for these problems guarantee
convergence to maximally diverse populations of sufficiently small size within
cubic to quartic expected run-time. On the other hand, the result on QAP
suggests that strong mutations give poor worst-case performance, as mutation
strength contributes exponentially to the expected run-time. Additionally,
experiments are carried out on QAPLIB and synthetic instances in unconstrained
and constrained settings, and reveal much more optimistic practical
performances, while corroborating the theoretical finding regarding mutation
strength. These results should serve as a baseline for future studies.
- Abstract（参考訳）: 高品質なソリューションの多様な集団を生み出すことは、従来の最適化タスクの有望な拡張として関心を集めている。
この研究は、トラベルセールスパーソン問題(TSP)、対称変種、非対称変種、および擬似代入問題(QAP)の3つの最もよく研究されている置換問題に対する進化的多様性最適化の研究に寄与する。
それは、確立された多様性尺度を用いて、異なる突然変異演算子を持つ単純な突然変異のみの進化アルゴリズムの最悪の性能の分析を含む。
理論的な結果は、これらの問題に対する多くの突然変異演算子は、四進法内で十分小さいサイズの最大に多様な集団に収束することを保証していることを示している。
一方、QAPの結果は、突然変異強度が期待される実行時間に指数関数的に寄与するため、強い突然変異が最悪の場合のパフォーマンスを低下させることを示唆している。
さらに、QAPLIBと合成インスタンス上で、制約のない、制約のない環境で実験を行い、より楽観的な実用的な性能を示しながら、突然変異強度に関する理論的発見を裏付ける。
これらの結果は将来の研究のベースラインとなるはずである。
関連論文リスト
- Towards Self-adaptive Mutation in Evolutionary Multi-Objective
Algorithms [10.609857097723266]
自己適応が多目的進化アルゴリズムに与える影響について検討する。
単一目的最適化とハイパーボリュームに基づく突然変異率の適応は,GSEMOの収束を早めることができることを示す。
本稿では,単一目的の最適化を考慮し,各ソリューションの突然変異率を個別に調整する自己適応突然変異GSEMOを提案する。
論文 参考訳（メタデータ） (2023-03-08T14:26:46Z) - High-Probability Bounds for Stochastic Optimization and Variational
Inequalities: the Case of Unbounded Variance [59.211456992422136]
制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。
これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
論文 参考訳（メタデータ） (2023-02-02T10:37:23Z) - Effective Mutation Rate Adaptation through Group Elite Selection [50.88204196504888]
本稿では,GESMR(Group Elite Selection of Mutation Rates)アルゴリズムを提案する。
GESMRは解の集団とMRの集団を共進化させ、各MRは解群に割り当てられる。
同じ数の関数評価とオーバーヘッドのほとんどないGESMRは、以前のアプローチよりも早く、より良いソリューションに収束する。
論文 参考訳（メタデータ） (2022-04-11T01:08:26Z) - 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) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Variance Minimization in the Wasserstein Space for Invariant Causal
Prediction [72.13445677280792]
そこで本研究では,ICPで行ったアプローチを,予測器数で線形にスケールする一連の非パラメトリックテストとして再検討する。
これらのテストはそれぞれ、最適輸送理論の道具から導かれる新しい損失関数の最小化に依存している。
我々は,本手法が同定可能な直接原因の集合を回復できるという軽微な仮定の下で証明し,他のベンチマーク因果探索アルゴリズムと競合することを示す。
論文 参考訳（メタデータ） (2021-10-13T22:30:47Z) - Breeding Diverse Packings for the Knapsack Problem by Means of
Diversity-Tailored Evolutionary Algorithms [13.026567958569965]
我々はknapsack問題(KP)に対する進化的多様性の最適化について研究する。
我々のゴールは、KP のよく知られた FPTAS によって計算された初期近似解で、すべての利益が少なくとも$(mu+1)$-EA である解の集団を進化させることである。
論文 参考訳（メタデータ） (2021-04-27T12:26:18Z) - A Rank based Adaptive Mutation in Genetic Algorithm [0.0]
本稿では,染色体ランクを用いた突然変異確率生成の代替手法を提案する。
単純な遺伝的アルゴリズム(SGA)と一定の突然変異確率と限られた資源制約内での適応的アプローチとの比較実験を行った。
論文 参考訳（メタデータ） (2021-04-18T12:41:33Z) - Evolutionary Diversity Optimization and the Minimum Spanning Tree
Problem [13.264683014487376]
多様性最適化の文脈において、よく知られた最小スパンニングツリー問題(MST)について検討する。
単純な$(mu+1)$-EAは、高品質の木々の多様化した個体群を効果的に計算できることを示す。
論文 参考訳（メタデータ） (2020-10-21T11:50:49Z) - AT-MFCGA: An Adaptive Transfer-guided Multifactorial Cellular Genetic
Algorithm for Evolutionary Multitasking [17.120962133525225]
本稿では,進化的マルチタスク環境を扱うための適応メタヒューリスティックアルゴリズムを提案する。
AT-MFCGAはセルラーオートマトンを利用して、検討中の最適化問題の知識を交換する機構を実装している。
論文 参考訳（メタデータ） (2020-10-08T12:00:10Z) - EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm
for Constrained Global Optimization [68.8204255655161]
EOSは実数値変数の制約付きおよび制約なし問題に対する大域的最適化アルゴリズムである。
これはよく知られた微分進化(DE)アルゴリズムに多くの改良を加えている。
その結果、EOSisは、最先端の単一人口自己適応Dアルゴリズムと比較して高い性能を達成可能であることが証明された。
論文 参考訳（メタデータ） (2020-07-09T10:19:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。