論文の概要: A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem

• arxiv url: http://arxiv.org/abs/2508.14020v1
• Date: Tue, 19 Aug 2025 17:27:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-20 15:36:32.030458
• Title: A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem
• Title（参考訳）: 分岐型ランダム鍵遺伝的アルゴリズムによる最長周期問題の解法
• Authors: Christian Blum, Pedro Pinacho-Davidson,
• Abstract要約: Biased Random Key Genetic Algorithm (BRKGA) を用いた最長ランサブシーケンス(LRS)問題の解を提案する。 その結果, BRKGAは現在, LRS問題の最先端技術であることがわかった。
• 参考スコア（独自算出の注目度）: 0.9668407688201361
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The longest run subsequence (LRS) problem is an NP-hard combinatorial optimization problem belonging to the class of subsequence problems from bioinformatics. In particular, the problem plays a role in genome reassembly. In this paper, we present a solution to the LRS problem using a Biased Random Key Genetic Algorithm (BRKGA). Our approach places particular focus on the computational efficiency of evaluating individuals, which involves converting vectors of gray values into valid solutions to the problem. For comparison purposes, a Max-Min Ant System is developed and implemented. This is in addition to the application of the integer linear programming solver CPLEX for solving all considered problem instances. The computation results show that the proposed BRKGA is currently a state-of-the-art technique for the LRS problem. Nevertheless, the results also show that there is room for improvement, especially in the context of input strings based on large alphabet sizes.
• Abstract（参考訳）: 最長実行サブシーケンス問題 (LRS) は、生物情報学のサブシーケンス問題のクラスに属するNPハード組合せ最適化問題である。 特に、この問題はゲノム組換えにおいて重要な役割を果たしている。 本稿では,Biased Random Key Genetic Algorithm (BRKGA) を用いたLSS問題の解を提案する。 提案手法は、グレー値のベクトルを問題に対する有効な解に変換することを含む、個人評価の計算効率に特に焦点をあてる。 比較のために、Max-Min Ant Systemが開発・実装されている。 これは、整数線形プログラミング解法 CPLEX の全ての問題インスタンスを解くための応用である。 計算結果から,提案したBRKGAは現在,RS問題の最先端技術であることがわかった。 それにもかかわらず、結果は、特に大きなアルファベットサイズに基づく入力文字列の文脈において、改善の余地があることも示している。

関連論文リスト

• Guiding Genetic Programming with Graph Neural Networks [0.20718016474717196]
  本稿では,記号回帰問題から付加的な知識を引き出すためにグラフニューラルネットワークを用いたEvoNUDGEを提案する。 多数の問題インスタンスに対する広範な実験では、EvoNUDGEは複数のベースラインを大幅に上回っている。
  論文  参考訳（メタデータ） (2024-11-03T20:43:31Z)
• Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
  最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論と計算複雑性の基本的な問題である。 様々なメタヒューリスティックがMPPを近似するために使われており、遺伝的アルゴリズムやメメティックアルゴリズム、アリコロニーアルゴリズム、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングなどがある。 以上の結果から,モンテカルロのアルゴリズムはランダム検索を用いてグラフを生成するが,速度と能力の両面で遺伝的アルゴリズムを上回っていることが示唆された。
  論文  参考訳（メタデータ） (2024-09-26T12:50:00Z)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  本稿では,問題の近似クラスに依存する遺伝的アルゴリズムの有用性を解析する。 特に, 遺伝的アルゴリズムは階層の最も悲観的なクラスに特に有用であることを示す。
  論文  参考訳（メタデータ） (2024-02-01T09:18:34Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  離散データからベイズネットワーク(BNSL)の構造を学習することはNPハードタスクであることが知られている。 本研究では,可能なクラスタカットのサブセットを発見するための新しい時間アルゴリズムを提案する。 最適ではないにもかかわらず、性能は桁違いに向上することを示す。 結果として得られる解法は、BNSL問題に対する最先端の解法である GOBNILP と好意的に比較できる。
  論文  参考訳（メタデータ） (2021-06-23T09:46:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
  本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。 ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
  論文  参考訳（メタデータ） (2020-07-07T17:03:02Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  本稿では,マイニングパターンを用いて問題サイズの削減を行うMineReduceという手法を提案する。 異種車両ルーティング問題に対するMineReduceの適用について述べる。
  論文  参考訳（メタデータ） (2020-05-15T08:49:50Z)
• Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem [0.0]
  本稿では、進化的遺伝的アルゴリズムを特徴付けるとともに、最小ラベル付けスタイナーツリー(MLST)問題を解く際の性能を評価する。 我々は、進化的アルゴリズムを、時間とともに超最適で実現不可能な解の集団を進化させることによって実現可能な解に到達する過程として定義する。 我々は, 交叉, 突然変異, 適合性などの古典的進化的概念が, 最適解, 最適解に到達するためにどのように適応できるかを示す。
  論文  参考訳（メタデータ） (2020-04-18T13:27:28Z)

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

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