論文の概要: Cycle Mutation: Evolving Permutations via Cycle Induction

• arxiv url: http://arxiv.org/abs/2205.14125v2
• Date: Tue, 31 May 2022 16:06:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-05 06:49:26.727891
• Title: Cycle Mutation: Evolving Permutations via Cycle Induction
• Title（参考訳）: サイクル変異:サイクル誘導による進化的置換
• Authors: Vincent A. Cicirello
• Abstract要約: 本稿では、サイクルクロスオーバー演算子にインスピレーションを与える新しい突然変異演算子であるサイクル突然変異を提案する。 我々は、フィットネスランドスケープ分析を用いて、サイクル突然変異が最もうまく機能する問題の特徴を探索する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Evolutionary algorithms solve problems by simulating the evolution of a population of candidate solutions. We focus on evolving permutations for ordering problems like the traveling salesperson problem (TSP), as well as assignment problems like the quadratic assignment problem (QAP) and largest common subgraph (LCS). We propose cycle mutation, a new mutation operator whose inspiration is the well known cycle crossover operator, and the concept of a permutation cycle. We use fitness landscape analysis to explore the problem characteristics for which cycle mutation works best. As a prerequisite, we develop new permutation distance measures: cycle distance, $k$-cycle distance, and cycle edit distance. The fitness landscape analysis predicts that cycle mutation is better suited for assignment and mapping problems than it is for ordering problems. We experimentally validate these findings showing cycle mutation's strengths on problems like QAP and LCS, and its limitations on problems like the TSP, while also showing that it is less prone to local optima than commonly used alternatives. We integrate cycle mutation into the open-source Chips-n-Salsa library, and the new distance metrics into the open-source JavaPermutationTools library.
• Abstract（参考訳）: 進化的アルゴリズムは、候補解の集団の進化をシミュレートすることで問題を解決する。 我々は,巡回セールスパーソン問題 (tsp) や二次代入問題 (qap) や最大の共通部分グラフ (lcs) などの代入問題といった順序問題に対する順列の進化に焦点を当てた。 本稿では, サイクル交叉演算子にインスピレーションを与える新しい突然変異演算子であるサイクル突然変異と, 置換サイクルの概念を提案する。 我々は, 適応的ランドスケープ分析を用いて, サイクル変異が最適である問題特性を探索する。 前提条件として,サイクル距離,$k$サイクル距離,サイクル編集距離という,新しい置換距離尺度を開発した。 適応的ランドスケープ分析は、サイクル変異が順序問題よりも割当問題やマッピング問題に適していると予測する。 本研究は,QAP や LCS などの問題に対するサイクル変異の強度,TSP などの問題に対する制限,および一般的に用いられる代替品よりも局所的最適性が低いこと,などの知見を実験的に検証した。 我々は、サイクル変異をオープンソースのchips-n-salsaライブラリに、新しい距離メトリクスをオープンソースのjavapermutationtoolsライブラリに統合します。

関連論文リスト

• A Survey and Analysis of Evolutionary Operators for Permutations [0.0]
  置換を進化させるには、特別な進化作用素が必要である。 本稿では、置換のための進化的演算子の幅を調査する。 これらのすべては、進化計算のためのオープンソースのJavaライブラリであるChips-n-Salsaで実装しています。
  論文  参考訳（メタデータ） (2023-11-24T16:32:44Z)
• On Fitness Landscape Analysis of Permutation Problems: From Distance Metrics to Mutation Operator Selection [0.0]
  この理論を探求し、順列空間上の最適化問題に対するフィットネスランドスケープ解析の実践を拡大する。 まず、置換のための利用可能な距離メトリクスを調査し、次に主成分分析を使用してこれらのメトリクスを分類する。 置換メトリクス、置換突然変異演算子、および関連する進化的アルゴリズムの実装は、オープンソースのJavaライブラリの2つで利用可能です。
  論文  参考訳（メタデータ） (2022-08-23T20:46:49Z)
• Runtime Analysis for Permutation-based Evolutionary Algorithms [9.044970217182117]
  ビットストリングの場合のように、スクランブル演算子の重み付きバージョンは、ジャンプサイズが$m$のジャンプ関数において、$mTheta(m)$の順序の高速化につながることを示す。 短い経験的分析によりこれらの知見が裏付けられるが、また、ヴォイド突然変異率のような小さな実装の詳細が重要な違いをもたらすことも明らかである。
  論文  参考訳（メタデータ） (2022-07-05T15:49:29Z)
• On the Difficulty of Evolving Permutation Codes [7.673465837624365]
  本稿では,進化的アルゴリズム (EA) による置換符号の設計について,反復的アプローチを用いて検討する。 単一のランダムな置換から始めて、最小距離制約を満たす新しい置換をコードに追加する。 我々は、EAアプローチによる結果と単純なランダム検索の結果を比較し、どちらの手法も問題の大きさによく対応していないことを指摘した。
  論文  参考訳（メタデータ） (2021-11-25T21:08:16Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  我々は、訓練データから高品質な生成順序を純粋に検出する、教師なし並列化可能な学習装置を開発した。 エンコーダを非因果的注意を持つトランスフォーマーとして実装し、1つのフォワードパスで置換を出力する。 言語モデリングタスクにおける経験的結果から,我々の手法は文脈認識であり,一定の順序と競合する,あるいはより優れた順序を見つけることができる。
  論文  参考訳（メタデータ） (2021-10-27T16:08:09Z)
• Markov Decision Process modeled with Bandits for Sequential Decision Making in Linear-flow [73.1896399783641]
  会員/加入者の獲得と保持では、複数のページを連続してマーケティングコンテンツを推奨する必要がある。 遷移確率行列をモデル化するためにBandits を用いた MDP としてこの問題を定式化することを提案する。 提案したMDPのBanditsアルゴリズムは,$epsilon$-greedyと$epsilon$-greedy,$epsilon$,IndependentBandits,InteractionBanditsでQ-learningを上回っている。
  論文  参考訳（メタデータ） (2021-07-01T03:54:36Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。 本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
  論文  参考訳（メタデータ） (2021-06-11T09:43:09Z)
• SPANet: Generalized Permutationless Set Assignment for Particle Physics using Symmetry Preserving Attention [62.43586180025247]
  大型ハドロン衝突型加速器の衝突は、観測された粒子の可変サイズの集合を生成する。 崩壊生成物の物理対称性は、観測された粒子の崩壊生成物の割り当てを複雑にする。 本稿では,対称性を保った注目ネットワークを構築するための新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-07T18:18:20Z)
• Multiview Sensing With Unknown Permutations: An Optimal Transport Approach [42.62524143925126]
  我々は、最適な輸送のレンズを介して未知の置換の対象となる信号を回復する問題を再検討します。 これを利用して、ソリューションのより可能性の高い置換を促進する正規化関数を導入しています。 一般的な問題は凸ではありませんが、結果として生じる正規化問題の適切な緩和は、OTのよく発達した機械を利用し、トラクタブルアルゴリズムを開発することを可能にします。
  論文  参考訳（メタデータ） (2021-03-12T18:48:18Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。 本研究では,理論特性の知見を得るための後悔分析法を提案する。 二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
  論文  参考訳（メタデータ） (2021-02-26T10:15:57Z)
• Tell Me How to Ask Again: Question Data Augmentation with Controllable Rewriting in Continuous Space [94.8320535537798]
  機械読解(MRC)、質問生成、質問答え自然言語推論タスクのための制御可能な書き換えベースの質問データ拡張(CRQDA)。 質問データ拡張タスクを制約付き質問書き換え問題として扱い、コンテキスト関連、高品質、多様な質問データサンプルを生成する。
  論文  参考訳（メタデータ） (2020-10-04T03:13:46Z)

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

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