Genetic algorithm for the weight maximization problem on weighted automata
Genetic algorithm for the weight maximization problem on weighted automata
复制标题
加权自动机权重最大化问题的遗传算法
DOI：
10.1145/3377930.3390227
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hasuo Ichiro
中科院分区：
文献类型：
--
作者：
Gutierrez Elena;Okudono Takamasa;Waga Masaki;Hasuo Ichiro
权重最大化问题（WMP）是在一个加权的有限状态自动机（WFA）上寻找最高权重的词的问题。这是自动机理论中许多最优化问题的基本问题。不幸的是，一般问题可以被证明是不可判定的，而其有界决策版本是NP完全的。设计有效的算法，在合理的时间内产生近似解的WMP是一个有吸引力的研究方向，可以导致几个新的应用程序，包括形式化验证的系统抽象为WFAs。特别是，结合最近的程序，将一个循环神经网络转化为加权自动机，WMP的算法可以用来分析和验证网络，通过利用更简单，更紧凑的自动机model.In这项工作中，我们提出，实施和评估一个基于遗传算法的元启发式近似的解决方案WMP。我们实验评估其性能的例子，从文献中，并显示其在不同的应用程序的潜力。
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.