論文の概要: Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms

• arxiv url: http://arxiv.org/abs/2511.19089v1
• Date: Mon, 24 Nov 2025 13:30:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:25.213233
• Title: Theoretical and Empirical Analysis of Lehmer Codes to Search Permutation Spaces with Evolutionary Algorithms
• Title（参考訳）: 進化的アルゴリズムを用いた置換空間探索のためのリーマー符号の理論的および実証的解析
• Authors: Yuxuan Ma, Valentino Santucci, Carsten Witt,
• Abstract要約: 我々は、進化的アルゴリズムの多くの実践的応用の核となる置換空間における問題に焦点をあてる。 逆ベクトルは置換空間$S_n$の代替表現であり、古典的なエンコーディングは$n$ユニークなエントリのベクトルである。
• 参考スコア（独自算出の注目度）: 1.491109220586182
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A suitable choice of the representation of candidate solutions is crucial for the efficiency of evolutionary algorithms and related metaheuristics. We focus on problems in permutation spaces, which are at the core of numerous practical applications of such algorithms, e.g. in scheduling and transportation. Inversion vectors (also called Lehmer codes) are an alternative representation of the permutation space $S_n$ compared to the classical encoding as a vector of $n$ unique entries. In particular, they do not require any constraint handling. Using rigorous mathematical runtime analyses, we compare the efficiency of inversion vector encodings to the classical representation and give theory-guided advice on their choice. Moreover, we link the effect of local changes in the inversion code space to classical measures on permutations like the number of inversions. Finally, through experimental studies on linear ordering and quadratic assignment problems, we demonstrate the practical efficiency of inversion vector encodings.
• Abstract（参考訳）: 候補解の表現の適切な選択は、進化アルゴリズムと関連するメタヒューリスティックスの効率に不可欠である。 我々は、スケジューリングや輸送において、このようなアルゴリズムの多くの実践的応用の核となる置換空間の問題に焦点をあてる。 逆ベクトル (英: Inversion vector) あるいはリーマー符号 (Lehmer codes) は、古典的なエンコーディングが$n$ユニークなエントリのベクトルであるのに対し、置換空間 $S_n$ の代替表現である。 特に、制約処理は一切不要である。 厳密な数学的ランタイム解析を用いて、逆ベクトル符号化の効率を古典表現と比較し、それらの選択について理論誘導的なアドバイスを与える。 さらに、反転符号空間の局所的な変化が、逆数数などの置換に対する古典的測度に結びついている。 最後に、線形順序付けと二次代入問題の実験的研究を通じて、逆ベクトル符号化の実用的効率を実証する。

関連論文リスト

• Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables [0.7015624626359264]
  トラベリングパーソン販売問題(TSP)の例を用いて、最適化問題に対するより量子効率の高い回路構成を示す。 特定の冗長性を取り除いた場合、上記の従来の符号化に比べて、必要量子ビットの数は線形因子によって減少することができる。 実験の結果, 提案した符号化法と同等に精度が向上する一方, 必要な古典的反復回数はわずかに増加することがわかった。
  論文  参考訳（メタデータ） (2024-12-10T12:12:34Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• A Survey and Analysis of Evolutionary Operators for Permutations [0.0]
  置換を進化させるには、特別な進化作用素が必要である。 本稿では、置換のための進化的演算子の幅を調査する。 これらのすべては、進化計算のためのオープンソースのJavaライブラリであるChips-n-Salsaで実装しています。
  論文  参考訳（メタデータ） (2023-11-24T16:32:44Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  量子コンピューティングは、カーネルマシンが量子カーネルを利用してデータ間の類似度を表現できるようにすることで、機械学習モデルを強化することができる。 本稿では,ニューラルアーキテクチャ検索やAutoMLと同じような最適化手法を用いて,この問題に対するアプローチを提案する。 その結果、高エネルギー物理問題に対する我々のアプローチを検証した結果、最良のシナリオでは、手動設計のアプローチに関して、テストの精度を一致または改善できることが示された。
  論文  参考訳（メタデータ） (2022-09-22T16:42:14Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。 本研究では,理論特性の知見を得るための後悔分析法を提案する。 二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
  論文  参考訳（メタデータ） (2021-02-26T10:15:57Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications [34.269044536641665]
  低次元部分空間におけるスパースベクトル(方向)を求める問題はスパース回復問題の同種変種と見なすことができる。 低次元部分空間におけるスパースベクトル(方向)を求める問題はスパース回復問題の同種変種と見なすことができる。
  論文  参考訳（メタデータ） (2020-01-20T04:48:43Z)

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

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