論文の概要: A GRASP-based memetic algorithm with path relinking for the far from most string problem

• arxiv url: http://arxiv.org/abs/2406.07567v1
• Date: Mon, 27 May 2024 21:33:15 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-23 13:45:35.959220
• Title: A GRASP-based memetic algorithm with path relinking for the far from most string problem
• Title（参考訳）: 多くの弦問題から遠ざかる経路リリンクを用いたGRASPに基づくメメティックアルゴリズム
• Authors: José E. Gallardo, Carlos Cotta,
• Abstract要約: FAR MOST STRING PROBLEM (FFMSP) は文字列選択問題である。 FFMSPに対処するメメティックアルゴリズム(MA)を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The FAR FROM MOST STRING PROBLEM (FFMSP) is a string selection problem. The objective is to find a string whose distance to other strings in a certain input set is above a given threshold for as many of those strings as possible. This problem has links with some tasks in computational biology and its resolution has been shown to be very hard. We propose a memetic algorithm (MA) to tackle the FFMSP. This MA exploits a heuristic objective function for the problem and features initialization of the population via a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, intensive recombination via path relinking and local improvement via hill climbing. An extensive empirical evaluation using problem instances of both random and biological origin is done to assess parameter sensitivity and draw performance comparisons with other state-of-the-art techniques. The MA is shown to perform better than these latter techniques with statistical significance.
• Abstract（参考訳）: FAR FROM MOST STRING PROBLEM (FFMSP) は文字列選択問題である。 目的は、ある入力集合内の他の文字列との距離が、できるだけ多くの文字列に対して与えられた閾値を超える文字列を見つけることである。 この問題は計算生物学のいくつかの課題と関連しており、その解決は非常に難しいことが示されている。 FFMSPに対処するメメティックアルゴリズム(MA)を提案する。 このMAは、この問題に対するヒューリスティックな目的関数を利用し、グレディランダム化適応探索法(GRASP)による人口の初期化を特徴とし、経路リリンクによるメタヒューリスティックで集中的な再結合と、登山による局所的な改善を特徴としている。 ランダムおよび生物学的起源の両方の問題事例を用いた広範囲な実験評価を行い、パラメータ感度を評価し、他の最先端技術との比較を行う。 MAは、統計的に有意なこれらの後者の手法よりも優れた性能を示すことが示されている。

関連論文リスト

• Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
  最大傾き問題(英: maximum clique problem、MCP)は、グラフ理論と計算複雑性の基本的な問題である。 様々なメタヒューリスティックがMPPを近似するために使われており、遺伝的アルゴリズムやメメティックアルゴリズム、アリコロニーアルゴリズム、欲求アルゴリズム、タブアルゴリズム、シミュレートされたアニーリングなどがある。 以上の結果から,モンテカルロのアルゴリズムはランダム検索を用いてグラフを生成するが,速度と能力の両面で遺伝的アルゴリズムを上回っていることが示唆された。
  論文  参考訳（メタデータ） (2024-09-26T12:50:00Z)
• A Three-Stage Algorithm for the Closest String Problem on Artificial and Real Gene Sequences [39.58317527488534]
  ストロースト文字列問題(Closest String Problem)は、与えられた文字列の集合に属するすべての列から最小距離の文字列を見つけることを目的としたNPハード問題である。 本稿では,次の3段階のアルゴリズムを提案する。まず,検索領域を効果的に見つけるために,検索空間を削減するために,新しいアルファベットプルーニング手法を適用する。 第二に、解を見つけるためのビーム探索の変種を用いる。この方法は、部分解の期待距離スコアに基づいて、新たに開発された誘導関数を利用する。
  論文  参考訳（メタデータ） (2024-07-17T21:26:27Z)
• Reweighted Solutions for Weighted Low Rank Approximation [47.790126028106734]
  重み付き低階近似(WLRA)は、統計解析から信号処理に至るまで、重要かつ困難なプリミティブである。 そこで本研究では,WLRAに対して,必ずしも低ランクではないが極めて少ないパラメータで保存可能な行列を出力する緩和解を提案する。 我々の中心となる考え方は、重み行列自体を低階解の重み付けに利用することであり、これは非常に単純なアルゴリズムであり、顕著な経験的性能を与える。
  論文  参考訳（メタデータ） (2024-06-04T15:50:35Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Stochastic Natural Thresholding Algorithms [18.131412357510158]
  計算効率を向上したNatural Thresholding (NT) が提案されている。 本稿では,線形測度を用いて決定性版を拡張することにより,自然しきい値決定アルゴリズムの収束保証を提案する。
  論文  参考訳（メタデータ） (2023-06-07T18:49:19Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• HARRIS: Hybrid Ranking and Regression Forests for Algorithm Selection [75.84584400866254]
  両アプローチの強みを両アプローチの弱さを緩和しつつ組み合わせ, 特殊林を利用した新しいアルゴリズムセレクタを提案する。 HARRISの決定は、ハイブリッドランキングと回帰損失関数に基づいて最適化された木を作成する森林モデルに基づいている。
  論文  参考訳（メタデータ） (2022-10-31T14:06:11Z)
• Determinantal Beam Search [75.84501052642361]
  ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。 複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。 ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
  論文  参考訳（メタデータ） (2021-06-14T13:01:46Z)
• Mean Field Approximation for solving QUBO problems [0.0]
  平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。 提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
  論文  参考訳（メタデータ） (2021-06-06T20:35:28Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• MLE-guided parameter search for task loss minimization in neural sequence modeling [83.83249536279239]
  ニューラル自己回帰シーケンスモデルは、さまざまな自然言語処理(NLP)タスクのシーケンスを生成するために使用される。 本稿では,現在のパラメータとその周辺における乱探索の混合である更新方向の分布から,最大至適勾配の分布をサンプリングする,最大至適誘導パラメータ探索(MGS)を提案する。 以上の結果から,MGS は,機械翻訳における最小リスクトレーニングに比べて,繰り返しや非終端の大幅な削減を図り,シーケンスレベルの損失を最適化できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-04T22:21:22Z)

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

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