论文标题
加权自动机的重量最大化问题的遗传算法
Genetic Algorithm for the Weight Maximization Problem on Weighted Automata
论文作者
论文摘要
重量最大化问题（WMP）是在加权有限态自动机（WFA）上找到最高权重的问题。这是一个基本问题，在自动机理论中的许多优化问题中出现。不幸的是，一般问题可以证明是不可决定的，而其有限的决策版本则是NP完整的。设计有效的算法在合理时间内为WMP产生近似解决方案是一个吸引人的研究方向，可以导致几种新应用，包括对WFA的系统的正式验证。特别是，结合将复发性神经网络转换为加权自动机的最新过程，WMP的算法可通过利用更简单，更紧凑的自动机模型来分析和验证网络。在这项工作中，我们提出，实施和评估基于遗传算法的元疗法，以将解决方案近似于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.
