自动机的推导与优化算法的结合

【作者】 万敏；

【导师】 莫智文；

【作者基本信息】 四川师范大学 ， 运筹学与控制论， 2004， 硕士

【摘要】 文法推理由于其广泛的应用前景而受到越来越多的关注，它已被成功地应用于：句法模式识别[13]，演讲和自然语言的处理，基因分析，图像处理，序列预测，信息检索，密码术等等。由于文法推理与推导相应的自动机是等价的[14]，所以作者将研究的重心集中在获得能识别给定样本的自动机上。本文主要研究了几种优化算法在此领域中的应用。 目前，国内外对神经网络与自动机的结合的研究己取得了一系列成果；在第一章，我们首先将对这些结果以及这个领域的研究思想与方法做一个概要的介绍；然后提出一种推导模糊有限状态自动机的构造性算法，解决了仿真实验中所给出的具体网络的隐藏层神经元个数的确定问题；在实验中，我们首先将样本输入带1个隐藏层神经元的反馈网络训练，150个纪元以后增加神经元，此时的新网络在124纪元时收敛；而Blanco[3]的固定性网络学习好相同的样本需要432个纪元。 第二章我们设计了一种用于模糊有限自动机推导的进化策略：（μ，λ）^FA-策略，该策略将自动机的转移函数和输出函数用矩阵的形式表示出来，并产生了一个与此编码特征相对应的变异操作以及自动机个体关于模糊训练样本集的适应度函数。通过实验证明该策略是有效的，从而为自动机的推导提出了一种新方法。此方法与使用神经网络的方法相比，更直观，简单，并且在其他研究中也有着广泛的应用。最后我们提出了将擅长于全局搜索的进化算法与擅长于局部搜索的梯度下降法结合起来推导自动机（有限状态自动机，下推自动机，模糊自动机）的具有指导性的实现步骤：首先使用进化算法训练给定的样本集，当群体的最优个体的“适应度”变化不明显或者进化代数达到预定值时，则将此时得到的自动机编码入网络中，训练网络直到误差达到期望值。一旦网络训练好后，使用抽取算法从中将自动机抽取出来。 第三章提出了待研究的几个开问题。更多还原

【Abstract】 Grammar inference has received more and more attention due to its wide application. This paper is concerned with the combination of several optimal algorithms with this research field.In chapter 1, we begin with some results of the grammar inference using neural networks and then a construction method is proposed to induce the fuzzy finite state automaton. This algorithm recovers the absence of the empiric in the case of the fixed-topology network and generates an optimal topology automatically. We end this chapter with some problems in the future.In chapter 2, We present an evolution strategy to infer fuzzy finite-state automaton, The fitness function of a generated automaton with respect to the set of examples of a fuzzy language, the representation of the transition and the output of the automaton and the simple mutation operators that work on these representations are given. Results are reported on the inference of a fuzzy language.Evolution algorithm and gradient decent algorithm are combined to the grammar inference. First use an evolution algorithm to infer the automaton from examples of a language and then encode the generated automaton to a network. The expected automaton is finally extracted from the trained network.更多还原