論文の概要: Genetic Algorithm for the Weight Maximization Problem on Weighted Automata

• arxiv url: http://arxiv.org/abs/2004.06581v1
• Date: Sat, 11 Apr 2020 09:30:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-14 09:57:52.054879
• Title: Genetic Algorithm for the Weight Maximization Problem on Weighted Automata
• Title（参考訳）: 重み付きオートマタの最大化問題に対する遺伝的アルゴリズム
• Authors: Elena Guti\'errez, Takamasa Okudono, Masaki Waga, Ichiro Hasuo
• Abstract要約: 重み問題 (WMP) は、重み付き有限状態オートマトン (WFA) 上での最高重みの単語を求める問題である。 WMPの解を近似するための遺伝的アルゴリズムに基づくメタヒューリスティックを提案し,評価する。
• 参考スコア（独自算出の注目度）: 3.0969191504482247
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The weight maximization problem (WMP) is the problem of finding the word of highest weight on a weighted finite state automaton (WFA). It is an essential question that emerges in many optimization problems in automata theory. Unfortunately, the general problem can be shown to be undecidable, whereas its bounded decisional version is NP-complete. Designing efficient algorithms that produce approximate solutions to the WMP in reasonable time is an appealing research direction that can lead to several new applications including formal verification of systems abstracted as WFAs. In particular, in combination with a recent procedure that translates a recurrent neural network into a weighted automaton, an algorithm for the WMP can be used to analyze and verify the network by exploiting the simpler and more compact automata model. In this work, we propose, implement and evaluate a metaheuristic based on genetic algorithms to approximate solutions to the WMP. We experimentally evaluate its performance on examples from the literature and show its potential on different applications.
• Abstract（参考訳）: 重み最大化問題 (WMP) は、重み付き有限状態オートマトン (WFA) 上での最高重みの単語を求める問題である。 オートマトン理論における多くの最適化問題に現れる重要な問題である。 残念なことに、一般的な問題は決定不能であることが示されるが、その有界決定版はNP完全である。 wmpに対する近似解を合理的な時間に生成する効率的なアルゴリズムを設計することは、wfaとして抽象化されたシステムの形式的検証を含む、いくつかの新しい応用につながる魅力的な研究方向である。 特に、リカレントニューラルネットワークを重み付きオートマトンに変換する最近の手順と組み合わせて、wmpのアルゴリズムを使用して、よりシンプルでよりコンパクトなオートマトンモデルを利用してネットワークを分析し検証することができる。 本稿では,WMPの解を近似する遺伝的アルゴリズムに基づくメタヒューリスティックを提案し,実装し,評価する。 文献の例での性能を実験的に評価し,その可能性を示した。

関連論文リスト

• A hybrid Quantum-Classical Algorithm for Mixed-Integer Optimization in Power Systems [0.0]
  量子コンピュータ(QC)を用いた電力系統最適化問題の解法フレームワークを提案する。 我々の指導的応用は、DC Optimal Power Flowを解くために訓練されたニューラルネットワークの最適送信切替と検証である。
  論文  参考訳（メタデータ） (2024-04-16T16:11:56Z)
• Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy Optimization [21.30645601474163]
  元々のQ-ラーニングは、非常に大きなネットワークにわたるパフォーマンスと複雑性の課題に悩まされている。 従来のQ-ラーニングに適応したモデルフリーアンサンブル強化学習アルゴリズムを提案する。 計算結果から,提案アルゴリズムは平均ポリシエラーを最大55%,実行時複雑性を最大50%削減できることがわかった。
  論文  参考訳（メタデータ） (2024-02-08T08:08:23Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• A Survey for Solving Mixed Integer Programming via Machine Learning [76.04988886859871]
  本稿では、混合整数(MIP)問題を解くための機械学習の動向について調査する。 本稿では、まず、MIPの定式化とプリミナリーと、MIPを解くための従来のアルゴリズムについて紹介する。 そして、機械学習とMIPアルゴリズムの異なる統合をさらに促進することを提唱する。
  論文  参考訳（メタデータ） (2022-03-06T05:03:37Z)
• Quantum optimisation via maximally amplified states [0.0]
  本稿では,短期量子コンピューティングの制限回路深度文脈における最適化のための新しい量子アルゴリズムを提案する。 最大増幅最適化アルゴリズム(MAOA)は、他の短期量子アルゴリズムよりもかなり優れている。
  論文  参考訳（メタデータ） (2021-11-01T09:43:53Z)
• Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming [0.0]
  本稿では,(混合)整数プログラミング(MIP)問題に対する実現可能な解を見つけるための深層強化学習(DRL)モデルを提案する。 多くの成功者は既知の初期の実現可能なソリューションに依存しているため、MIP問題に対する実現可能なソリューションを見つけることは重要です。 マルチレイヤ認識(MLP)に加えて,制約行列の隠れ情報を取得するために,ポリシーネットワークのための新しい畳み込みネットワーク(CNN)構造を提案する。
  論文  参考訳（メタデータ） (2021-02-18T23:18:17Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)

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

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