遗传算法用于解决赋权自动机的权重最大化问题(cs.NE)---用户7199428

权重最大化问题（WMP）是在赋权有限状态自动机（WFA）上寻找最大权重的单词。这是一个出现在很多自动机理论优化问题中一个至关重要的部分。不幸的是，这个普遍的问题被认为是不可判定的，因此它与NP-complete的决策版本是绑定的。设计一个有效算法用于给WMP在合理时间提供近似解是一个富有吸引力的研究方向，它能够产生一些新的应用，其中就包括可以被提取为WFA系统的形式证明。特别的是，当应用于WMP的算法与近期一个将周期性神经网络翻译成赋权自动机的过程相结合时，就可以通过探索一个更加简单和紧凑的自动机模型，从而分析和认证网络。在这篇论文中，我们提出，实现和评估一个基于元启发式的遗传算法来获取WMP问题的近似解。我们在实验中通过文学方面的样例评估了算法的性能，并且展示了它在不同应用上的潜力。

原文题目：Genetic Algorithm for the Weight Maximization Problem on Weighted Automata

原文：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.

原文作者：Elena Gutiérrez, Takamasa Okudono, Masaki Waga, Ichiro Hasuo

原文地址：https://arxiv.org/abs/2004.06581