論文の概要: Perfect Edge-Transmitting Recombination of Permutations
- arxiv url: http://arxiv.org/abs/2005.01113v1
- Date: Sun, 3 May 2020 15:15:49 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-07 06:24:50.928392
- Title: Perfect Edge-Transmitting Recombination of Permutations
- Title（参考訳）: 置換の完全エッジ伝達再結合
- Authors: Adriaan Merlevede and Carl Troein
- Abstract要約: 我々は、エッジの完全伝送を実現する置換のクロスオーバーのアルゴリズムを導出する。
また,非対称走行セールスマン問題に対する数学的に最適な子孫を生成するアルゴリズムの修正についても述べる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Crossover is the process of recombining the genetic features of two parents.
For many applications where crossover is applied to permutations, relevant
genetic features are pairs of adjacent elements, also called edges in the
permutation order. Recombination of edges without errors is thought to be an
NP-hard problem, typically approximated by heuristics that either introduce new
edges or are only able to produce a small variety of offspring. Here, we derive
an algorithm for crossover of permutations that achieves perfect transmission
of edges and produces a uniform sampling of all possible offspring, in
quadratic average computation time. The algorithm and its derivation reveal a
link between cycle crossover (CX) and edge assembly crossover (EAX), offering a
new perspective on these well-established algorithms. We also describe a
modification of the algorithm that generates the mathematically optimal
offspring for the asymmetric travelling salesman problem.
- Abstract（参考訳）: クロスオーバーは、2人の親の遺伝的特徴を再結合する過程である。
置換にクロスオーバーが適用される多くの応用において、関連する遺伝的特徴は、置換順序の辺とも呼ばれる隣接する要素のペアである。
誤りのないエッジの再結合はNPハード問題であり、一般に新しいエッジを導入するか、少数の子孫しか生成できないヒューリスティックスによって近似される。
ここでは、エッジの完全透過を実現する置換の交叉アルゴリズムを導出し、二次平均計算時間において、可能なすべての子孫の均一サンプリングを生成する。
このアルゴリズムとその導出により、サイクルクロスオーバー (cx) とエッジアセンブリクロスオーバー (eax) のリンクが明らかとなり、これらの確立されたアルゴリズムに対する新しい視点が示された。
また,非対称走行セールスマン問題に対する数学的に最適な子孫を生成するアルゴリズムの修正についても述べる。
関連論文リスト
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - A Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman
Problem [0.9790236766474201]
本稿では,Multiple Traveling Salesman Problem (mTSP) を解くためのハイブリッド遺伝的アルゴリズムを提案する。
新たなクロスオーバーオペレーターは、2人の親からの同様のツアーを組み合わせるように設計されており、人口に対して大きな多様性を提供する。
我々のアルゴリズムは、ベンチマークセットに対してテストした場合に、同様のカットオフ時間しきい値で、すべての既存のアルゴリズムを平均で上回ります。
論文 参考訳（メタデータ） (2023-07-14T01:57:10Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Kernelized multi-graph matching [0.0]
本稿では,グラフの属性とエッジの両方を扱う,新しいカーネル化されたマルチグラフマッチング手法を提案する。
結果の安定性の向上につながるプロジェクタをいくつか提案する。
論文 参考訳（メタデータ） (2022-10-11T07:22:47Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Regularization for Shuffled Data Problems via Exponential Family Priors
on the Permutation Group [8.40077201352607]
シャッフルデータ(Shuffled data)とは、(X, Y)ペアの正しいペアリングが未知のインデックス置換によって表現されるデータである。
この目的のために、置換群に先立ってフレキシブル指数族を提案する。
推論は、抽出可能なEステップをFisher-Yatesアルゴリズムで近似するEMアルゴリズムに基づいている。
論文 参考訳（メタデータ） (2021-11-02T17:43:28Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable
Crossover Probability [4.33419118449588]
我々は、突然変異またはランダムに選択された2人の親の再結合によって子孫を生成する、$(mu+lambda)$ Genetic Algorithms (GAs)の家系を調査する。
クロスオーバー確率を拡大することにより、完全突然変異のみのアルゴリズムから完全クロスオーバーベースGAへの補間が可能となる。
論文 参考訳（メタデータ） (2020-06-10T15:22:44Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。