（计算机应用技术专业论文）神经网络和遗传算法在基于输出域软件测试中的应用.pdf

摘要 神经网络和遗传算法在基于输出域软件测试中的应用 摘要 软件测试是保证软件质量的关键步骤。对于某些软件，输出域存在许 多值得关注的检测点，适合于从输出域出发设计测试用例。如果测试数据 能够自动生成，测试开销将显著降低。测试自动化的关键是测试输入和期 望输出的自动生成，但对于给定的输出，根据被测软件规格说明书自动生 成相应的输入较为困难。因此，探讨一种基于输出域的测试数据自动生成 的方法，具有十分重要的理论意义和实用价值。 对于大多数被测软件来说，输入和输出之间存在复杂的非线性关系； 因此，本文利用神经网络良好的非线性映射功能，构建被测软件的功能模 型，以模拟被测软件的功能，正确表达输入输出之间的关系；在此基础上， 对于给定的输出，利用遗传算法搜索相应的输入，并对遗传算法进行了改 进，提出了新的交叉算子和变异算子。实验结果表明：本文提出的基于输 出域的测试用例自动生成方法是行之有效的，构建的功能模型能够正确模 拟被测软件的功能，改进的遗传算法能够提高测试生成的效率和成功率。 关键词：神经网络，被测软件功能模型，测试用例生成，输出域，遗传算 法 摘要 a p p l i c a t i o no fn e u r a ln e t w o r k a n dg e n e t i ca l g o r i t h mi no u t p u t l 一 d o m a l nb a s e ds 0 t t 、v a r et e s t l n 2 a b s t r a c t s o r w a r et e s t i n gi se s s e n t i a lt oe n s u r es o r w a r eq u a l i t y s o m ek i n d so f s o r w a r ew h i c hh a v em a n yk e yo u t p u t sd e s e r v e da t t e n t i o na r em o r es u i t a b l et o d e v e l o pt e s t c a s e sf 两mo u 印u td o m a i n i ft e s ta u t o m a t i o nc o u l db ep u ti n p r a c t i c e ，t h ec o s to f s o r w a r et e s t i n gw o u l db es i g n i f i c a n t l yr e d u c e d t h ek e y e l e m e n ti nt e s ta u t o m a t i o ni st h ea u t o m a t i cg e n e r a t i o no ft e s ti n p u t sa i l d e x p e c t e do u t p u t s h o w e v e r f o rs o m eg i v e ni n p u t s ，a u t o m a t i c a l l yg e n e r a t i n g e x p e c t e do u t p u t sa c c o r d i n gt os p e c i f i c a t i o n s i sd i m c u l t t h e r e f o r e ，i ti s i m p o r t a n tt oe x p l o r eam e t h o df o ro u t p u td o m a i nb a s e da u t o m a t i ct e s tc a s e s g e n e r a t i o n m o s tk i n d so fs o 胁a r eh a v en o n l i n e a rr e l a t i o n s h i pb e t w e e ni n p u t sa n d o u t p u t s ，a n dt h en e u m ln e t w o r kc a nm a pn o n l i n e a rr e l a t i o n s h i pa d m i r a b l y t h u s ，m i sp a p e ru s e sn e u r a ln e t w o r kt oc r e a t ea 向n c t i o nm o d e lm a tc a nb e t a k e na sa 缸n c t i o ns u b s t i t u t ef o rt h es o r w a r eu n d e rt e s t t h e nb a s e do nm e c r e a t e d 如n c t i o nm o d e l ，f o rg i v e no u t p u t s ，g e n e t i ca l g o r i t h mi se m p l o y e dt o f i n dt h ec o r r e s p o n d i n g i n p u t s t h en e wc r o s s o v e ro p e r a t o ra n dm u t a t i o n o p e r a t o ra r ep r e s e n t e dt oi m p r o v et h eg e n e t i ca l g o r i t h m t h ee x p e r i m e n t a l r e s u l t si n d i c a t et h a tt h ea p p r o a c ho fo u t p u td o m a i nb a s e da u t o m a t i ct e s tc a s e s 北京化工大学硕士学位论文 g e n e r a t i o ni sp r o m i s i n ga n de f r e c t i v e ，t h ec r e a t e d 如n c t i o nm o d e lc a ns i m u l a t e t h e 如n c t i o no ft h es o r w a r eu n d e rt e s tp e r f e c t l y ，a n dt h ei m p r o v e dg e n e t i c a l g o r i t h m c a ne n h a n c et h e e f j e i c i e n c y a n ds u c c e s s 如lr a t i oo ft e s tc a s e g e n e r a t i o na tal a 玛e e x t e n t k e yw o r d s ：n e u r a ln e t w o r k ，如n c t i o nm o d e lo fs o r w a r eu n d e rt e s t ，t e s t c a s e sg e n e r a t i o n ，o u t p u td o m a i n ，g e n e t i ca l g o r i t h m i v 符号说明 符号说明 e p o c h ：神经网络训练最大迭代次数 p e r f o m l a n c e ：神经网络性能 f ：被测软件的功能模型 啊 n ，l o w e r n 】：被测软件输入变量的取值范围 p o p s i z e ：种群规模 p o p u l a t i o n ：种群 i 眦：遗传算法最大迭代次数 ：设定的最大适应度值 g ：目标输出值 p c ：交叉概率 p m ：变异概率 r e s u l t ：最优个体 f i t n e s s ：个体的适应度值 i x 北京化工大学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外一，本沦文不含 任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重 要贡献的个人和集体j 均己在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 作者签名：函峰巡 日期：j 逝二名： 一 关于论文使用授权的说明 学位论文作者完全了解北京化工大学有关保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京化工大 学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可 以允许采用影印、缩印或其它复制手段保存、汇编学位论文。 保密论文注释：本学位论文属于保密范围，在上年解密后适用本授 权书。非保密论文注释：本学位论文不属于保密范围，适用本授权书。 作者签名：幽 日期： 趟：丕： 导师签名：垫卑盔。日期：型生： 第一章绪论 第一章绪论 随着社会进步和计算机科学技术的飞速发展，计算机在国民经济和社会生活等方 面应用越来越广泛和深入。作为计算机的灵魂，软件在其中起着举足轻重的作用。软 件的失效有可能造成巨大的经济损失，甚至危及人的生命安全。例如，1 9 9 6 年觚a n e5 运载火箭的发射失败等都是由软件故障引起的【l 】：所以，人们对软件质量提出了新的 更高的要求，设计人员和使用人员都希望在将软件系统投入运行之前，能得到系统正 确性的保证，或能将系统正确性提高到比较高的程度。因此，作为保证软件质量、提 高软件可靠性的关键，软件测试在软件的整个开发过程中的地位同益凸现【2 3 】。有些软 件开发机构将研制力量的4 0 以上投入到软件测试之中；对于某些性命攸关的软件， 其测试费用甚至高达所有其他软件工程阶段费用总和的3 到5 倍【i 】。近年来，以软件测 试为中心的软件质量保障技术在软件生产实践中得到了迅速的发展，软件测试已成为 软件生产中必不可少的质量保障手段1 4 】。 1 1 课题研究的背景和意义 1 9 8 3 年，i e e e 提出了软件工程标准术语，软件测试定义为：“使用人工和自动手 段来运行或测试某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预 期结果与实际结果之间的差别。”该定义明确提出了软件测试以检验是否满足需求为 目标【5 1 。 软件测试方法主要分为白盒测试与黑盒测试两大类。其中，白盒测试又称为结构 性测试，按照程序内部的结构设计测试用例，对被测程序内部的变量状态、逻辑结构、 运行路径等进行检测，以检验程序中的每条通路是否都能按照预定要求正确工作，检 查程序内部动作或运行是否符合设计规格要求，所有内部成分是否按规定正常进行【6 】。 黑盒测试又称为功能性测试，独立于程序代码，是从用户的角度通过一定的测试步骤 与测试用例，验证软件功能、性能等指标能否满足实际应用需求的测试工作。在测试 时，把程序看作是一个不能打开的黑盒子，在完全不考虑程序内部结构和内部特性的 情况下，测试人员针对程序接口和用户界面进行测试，只检查程序功能是否按照需求 规格说明书的规定正常使用，程序是否能适当的接收输入数据而产生正确的输出信息 【7 ，8 】 o v o a s m c g r a w 认为白盒测试不适合于大规模的软件系统，无法检测出遗漏的代 码问题【9 l ，并且费用昂贵。因此，对于较大的代码单元或是软件系统来说，黑盒测试 比白盒测试效率更高。 北京化工大学硕上学位论文 功能测试从被测软件的规格说明书出发设计测试用例，常用的测试用例设计方法 有等价类划分、边界值分析、错误推测法、因果图法等，在用黑盒测试法测试时，必 须在所有可能的输入条件和输出条件中确定测试用例，即输入数据和期望输出数据等 【1 0 1 。因此，一个关键问题是如何从规格说明，以尽可能少的代价开发出有效的测试用 例。显然，如果测试自动化能够实现，测试开销会降低。测试自动化涉及测试输入的 自动生成，期望输出的自动产生，测试执行的自动实现以及测试结果的自动评估】， 其中测试输入和期望输出的自动生成是关键，但从规格说明自动产生期望输出比较困 难，特别是对于无法用形式化描述的规格说明，自动获得期望输出更加困难。 此外，某些软件存在许多值得关注的输出点，这类软件适合从输出域出发开发测 试用例。然而，对于给定的输出，自动获得相应的输入同样困难，尤其是大型复杂的 软件。因此，探讨一种基于输出域的测试数据自动生成的方法，具有十分重要的理论 和实际意义。 近年来，人工神经网络( a n i f i c i a ln c u r a ln 咖o r k ) 及遗传算法( g e i l e t i ca l g o r i t h m ) 等人工智能技术广泛的应用于软件测试领域中。人工神经网络( 以下简称神经网络) 是由多个非常简单的处理单元彼此按某种方式相互连接而形成的计算机系统，该系统 靠其状态对外部输入信息的动态相应来处理信息，换言之，神经网络是一种旨在模仿 人脑结构及其功能的信息处理系统。神经网络具有联想记忆、分类识别、优化计算以 及非线性映射功能【1 2 】。在许多实际问题中，系统的输入与输出之间存在复杂的非线性 关系，对于这类系统，往往难以用传统的数理方程建立其数学模型。神经网络在这方 面有独到的优势，设计合理的神经网络通过对系统输入输出样本进行训练学习，从理 论上讲，能够以任意精度逼近任意复杂的非线性函数。神经网络的这一优良性能使其 可以作为多维非线性函数的通用数学模型。而对于大多数被测软件来说，输入和输出 之间也存在复杂的非线性关系，可以考虑采用神经网络建立被测软件的通用数学模型 ( 本文中称为功能模型) ，表达被测软件输入与输出之间的映射关系，模拟被测软件 的功能。 遗传算法仿效生物学中遗传与进化的过程，遵从“生存竞争，优胜劣汰 的原则， 从一组随机生成的初始种群出发，借助选择、交叉、变异等遗传操作，逐步逼近所研 究问题的最优解，从实质而言，遗传算法是一种具有自适应调节功能的搜索寻优技术 【1 3 1 。然而，目前已有的这些利用遗传算法生成测试数据的方法，大多从程序输入域出 发，很少有文献提及如何从输出域出发自动生成测试用例，本文将遗传算法应用到基 于输出域的测试用例生成中。因此，本文的研究工作主要包括以下两个方面：一是研 究如何使用神经网络构建被测软件的功能模型，以最大精度逼近被测软件系统；二是 在已有功能模型的基础上，对于给定输出，探索如何利用遗传算法获得相应的输入。 第一章绪论 1 2 国内外研究现状 1 2 1 基于输出域的测试用例自动生成研究现状 软件测试的实质就是生成测试用例来驱动被测程序，观察程序的执行结果，验证 该结果与期望结果是否一致，然后做相应的纠错、调整和评价。因此软件测试的关键 和难点是如何生成测试用例。传统的测试用例生成方法大部分是靠手工完成，故测试 效率低下，质量也很难保证，因此国内外学者提出了很多测试用例自动生成方法。 基于规约的测试数据生成和基于程序的测试数据生成是两类常用的软件测试数 据生成方法。 通过对软件的形式化规格说明的分析，找到软件输入和输出之间的约束关系，再 利用数学方法得到软件输入域，根据相应测试理论( 如边界值分析法，等价类划分法 等) 得到测试用例，称为基于规约的测试用例生成方式。为了形式化描述软件功能， 广泛使用的是用形式化z 符号语言( zn o t a t i o n ) 和v d m 以及图形化的描述语言u m l 来描述软件的模型规格。例如，可以通过对软件z 规格说明的分析，找出描述软件输 入、输出约束的线性谓词，经过线性谓词转换，线性谓词到线性不等式组的转换，找出 区域边界顶点和边界附近的测试点等过程自动生成测试用例 1 4 j 。 基于程序的测试要求对被测程序的结构特性作到一定程度的覆盖，如语句覆盖、 分支覆盖、数据流覆盖、路径覆盖等。其测试数据生成是在输入域中，寻找满足测试 准则( 如语句覆盖) 的输入数据的过程。基于程序结构的测试，有三种测试数据生成方 法：随机测试数据生成方法，面向目标的测试数据生成方法以及面向路径的测试数据 生成方法【i 又m 。 随机测试数据生成方法：对于给定的语句( 分支、路径) ，随机测试数据生成方法 是在输入域内随机选取测试数据，使得给定语句被执行。 面向目标的测试数据生成方法：面向目标的测试数据生成方法，依据程序控制流 信息，将程序中所有的分支分成两类：一类是影响目标结点的分支，另一类是不影响 目标结点的分支。测试数据生成时，考虑影响目标结点的那些分支，利用分支函数极 小化，生成相应的测试数据，使得给定语句被执行。 面向路径的测试数据生成方法：面向路径的测试数据生成方法，首先确定一条经 过给定语句的程序路径，然后在输入域中寻找输入数据，使得在此输入之下，程序执 行沿该路径进行，从而使得给定语句被执行。 目前大多数方法都是从输入域出发自动生成测试用例，很少有文献涉及从输出域 出发进行测试用例的自动生成。然而，对于某些软件来说，更适合对输出域分析进行 测试用例生成。实际上，在常用的测试用例设计方法中，均可从输出域考虑设计测试 用例。例如，在边界值分析法中，任何一个程序都可以看作是一个函数，程序的输入 北京化工大学硕：t 学位论文 构成函数的定义域，程序的输出构成函数的值域。无数的测试实践表明，大量的软件 故障发生在定义域或值域的边界上，而不是在其内部。为检测边界附近的处理专门设 计测试用例，通常都会取得很好的测试效果。边界值分析法的基本思想是：选取正好 等于、刚刚大于或刚刚小于输入域和输出域边界的值作为测试数据，而不是选取等价 类中的典型值或任意值作为测试数据。而等价类划分法是把所有可能的输入数据或输 出数据，即程序的输入域或输出域划分为若干部分( 子集) ，然后从每一个子集中选 取少数具有代表性的数据作为测试用例。由此可见，从输出域考虑设计测试用例与输 入域具有同等重要的地位。 但是，在基于输出域的测试用例自动生成中，对于给定的输出，根据被测软件规 格说明书自动生成相应的输入较为困难。因此，本文将对此问题进行探讨，以便实现 基于输出域的测试数据自动生成。 1 2 2 神经网络和遗传算法在软件测试中的应用 对于神经网络和遗传算法在软件测试中的应用，国内外都进行了大量的研究。 1 神经网络在软件测试中的应用 文献【1 7 】指出神经网络在软件测试中的应用主要体现在两个方面：( 1 ) 将神经网络 作为分类器，预测测试数据的揭错能力，据此选用，精简测试数据；( 2 ) 神经网络用 作系统逼近器，代替真实的被测软件实施测试。 测试用例主要包括测试输入以及期望测试输出，给定测试输入通过测试数据生成 器( t e s t0 m c l e ) 自动生成期望的测试输出能够帮助测试实现自动化，比人工节省大 量的时间和花销，k k a g g a 刑a 1 【i i 】探讨了如何使用神经网络作为t e s to r a c l e 生成测试 数据。首先根据被测程序的规格说明书，获得被测程序的输入输出对并作为神经网络 的训练样本；然后使用获得的训练样本对多层前馈式神经网络进行训练；得到的神经 网络模型即可作为t e s to r a c l e ，给定输入数据，通过t e s to r a c l e 可以得到符合被测软 件规格说明书的期望输出数据；最后将期望输出数据和被测软件的实际输出数据进行 比较，可以判断被测程序是否出现错误。该文献使用三角形问题作为被测程序进行实 验，详细的描述了神经网络的构建，训练过程，以及各个参数的选择和调整，结果显 示神经网络经过合适的训练能够作为被测程序的t e s to r a c l e 进行测试数据的生成。 a n d e r s o n 等研究了如何使用神经网络进行错误预测，主要工作包括训练和预测 阶段。在神经网络训练阶段，训练样本包含测试用例相关信息和错误类型，其中测试 用例的相关信息作为神经网络的输入，错误类型作为神经网络的输出，使用样本对神 经网络进行训练【博j ，过程见图1 1 。 训练成功后，对神经网络输入某一测试用例的相关信息，神经网络便能够对该测 试用例能够揭示怎样类型的错误进行预测，另外，通过比较预测结果和真实结果可以 4 第一章绪论 对该神经网络的预测能力进行评估。预测过程见图1 2 。 图1 1 神经网络训练过程 f i gl - lt r a i n i n gp h a s eo f n e u r a ln 嘶o r k 图l - 2 神经网络预测过程 f i gl 2e v a l u a t i o np h eo f n 即m ln e t 、阳矗 2 遗传算法在软件测试中的应用 遗传算法是一个有效的全局优化算法，已广泛应用于软件测试用例自动生成中， 然而现有的文献主要讨论从输入域出发使用遗传算法生成测试数据。例如p 鹕a s 等利 用遗传算法生成满足语句覆盖的测试用删1 9 】。w e g e n e r 等采用遗传算法来进行分支覆 盖测试【2 0 1 。r o p e r 等介绍了一种使用遗传算法生成测试数据来自动达到分支覆盖的系 统，在被测程序种插入探针用以反馈测试数据的覆盖情况【2 1 1 。m h 猢a l l 等针对标志 变量，讨论了如何提高遗传算法生成测试数据的效率【2 2 】。 文献 2 3 提出了一种使用遗传算法自动生成非数值型的软件测试数抛的方法，并 针对两类路径构造了两种适应度函数：路径适应度和字符适应度，通过自动判别路径 的类型来选用合适的适应度函数，实现面向路径的非数值型软件测试数据的自动生 成。该文献的实验结果表明：在处理规模较大、结构较复杂的被测程序时，遗传算法 具有更大的优势，效率将明显提高。 近年来，随着神经网络和遗传算法技术在软件测试的广泛应用，它的优越性也越 来越显现出来，因此，本文将神经网络和遗传算法技术应用到基于输出域的测试数据 自动生成中，研究如何使用神经网络和遗传算法技术实现基于输出域的测试用例自动 北京化工大学硕士学位论文 生成。 1 3 本文的主要工作及组织结构 1 3 1 研究目标及内容 本文提出了一种基于输出域分析的测试用例自动生成方法。主要包括以下两部分 工作： 1 利用神经网络构建被测软件的功能模型。这部分主要研究如何使用神经网络 构建被测软件的功能模型，以最大精度模拟被测软件的功能，涉及神经网络模型的选 取，神经网络结构的确定，样本的采集，训练参数和训练算法等几方面。 2 在已有功能模型的基础上，探讨如何利用遗传算法实现基于输出域的测试用 例自动生成，即给定输出数据，如何利用遗传算法获得相应的输入数据。包括遗传算 法的编码方式，适应度函数，选择算子，交叉算子，变异算子等。， 1 3 2 本文的组织结构 第一章介绍了课题研究的背景，国内外研究现状，本文的主要工作及组织结构。 第二章介绍了神经网络技术和遗传算法技术，着重介绍了神经网络模型中的一 种，也是本文采用的模型，即b p 网络模型的基本内容；并对遗传算法的主要内容进行 了介绍。 第三章讨论了基于神经网络的被测软件功能模型的构建。对构建流程以及其中训 练样本和网络结构的设计，网络的训练，被测软件功能模型构建的m a t l a b 实现等进 行了介绍。 第四章探讨了在已有功能模型的基础上，如何利用遗传算法实现基于输出域的测 试用例自动生成。并且详细描述了本文定义和提出的适应度函数和交叉，变异算子。 第五章通过实验验证了本文提出的方法的可行性和执行效率，分为两部分：一是 验证功能模型是否能够较好的模拟被测软件的功能，表达被测软件输入输出之间的关 系；二是在已有功能模型的基础上利用遗传算法生成测试用例的成功率和生成效率。 第六章总结了本文主要贡献，并提出了进一步的工作计划。 6 第二章神经网络和遗传算法技术 第二章神经网络和遗传算法技术 2 1 神经网络技术 神经网络的研究可追溯到1 9 世纪末期，其发展历史可分为四个时期。第一个时 期为启蒙时期，开始于1 8 9 0 年美国著名心理学家w j 锄e s 关于人脑结构与功能的研 究，结束于1 9 6 9 年m i n s k y 和p 叩e n 发表感知器( p e r c 印仃d n ) 一书。第二个时期 为低潮时期，开始于1 9 6 9 年，结束于1 9 8 2 年h o 面e l d 发表著名的文章“神经网络和 物理系统 ( n c u f a ln e t w o r ka n dp h y s i c a ls y s t e m ) 。第三个时期为复兴时期，开始于 j j h o p f i e l d 的突破性研究论文，结束于1 9 8 6 年d e r u m e l h a n 和j l m c c l e l l a n d 领导 的研究小组发表的并行分布式处理( p a r a l l e ld i s t 曲u t e dp r o c e s s i n g ) 一书。第四个 时期为高潮时期，以1 9 8 7 年首届国际人工神经网络学术会议为开端，迅速在全世界 范围内掀起人工神经网络的研究应用热潮，至今势头不衰。 2 1 1 神经网络的基本特征和功能 神经网络是基于对人脑组织结构，活动机制的初步认识提出的一种新型信息处理 体系。通过模仿脑神经系统的组织结构以及某些活动机制，神经网络可呈现出人脑的 许多特征，并具有人脑的一些基本功能。 1 神经网络的基本特征 神经网络的特征归纳为结构特征和能力特征： 1 ) 结构特征： 并行处理，分布式存储与容错性神经网络是由大量简单处理单元相互连接构成 的高度并行的非线性系统，具有大规模并行性处理特征。虽然每个处理单元的功能十 分简单，但大量简单处理单元的并行活动使网络呈现出丰富的功能并具有较快的速 度。结构上的并行性使神经网络的信息存储必然采用分布式方式，即信息不是存储在 网络的某个局部，而是分布在网络所有的连接权中。一个神经网络可存储多种信息， 其中每个神经元的连接权中存储的是多种信息的一部分。当需要获得已存储的知识 时，神经网络在输入信息激励下采用“联想的办法进行会议，因而具有联想记忆功 能。神经网络内在的并行性与分布性表现在其信息的存储与处理都是空间上分布，时 间上并行的。这两个特点必然使神经网络在两个方面表现出良好的容错性：一方面， 由于信息的分布式存储，当网络中部分神经元损坏时不会对系统的整体性能造成影 响，这一点就像是人脑中每天都有神经细胞正常死亡而不会影响大脑的功能一样；另 一方面，当输入模糊，残缺或变形的信息时，神经网络能通过联想恢复完整的记忆， 从而实现对不完整输入信息的j 下确识别，这一特点就像是人可以对不规范的手写字进 北京化工大学硕士学位论文 行正确识别一样。 2 ) 能力特征： 自学习，自组织与自适应性自适应性是指一个系统能改变自身的性能以适应环 境变化的能力，它是神经网络的一个重要特征。自适应性包含自学习与自组织两层含 义。神经网络的自学习是指当外界环境发生变化时，经过一段时间的训练或感知，神 经网络能通过自动调整网络结构参数，使得对于给定输入能产生期望的输出，训练是 神经学习的途径，因此经常将学习与训练两个词混用。神经系统能在外部刺激下按一 定规则调整神经元之间的突触连接，逐渐构建起神经网络，这构建过程称为网络的 自组织。神经网络的自组织能力与自适应能力相关，自适应性是通过自组织实现的。 2 神经网络的基本功能 神经网络的基本功能简要介绍如下： 1 ) 联想记忆 由于神经网络具有分布存储信息和并行计算的性能，因此它具有对外界刺激信息 和输入模式进行联想记忆的能力。这种能力是通过神经元之间的协同结构以及信息处 理的集体行为而实现的。神经网络是通过其突触权值和连接结构来表达信息的记忆， 这种分布式存储使得神经网络能存储较多的复杂模式和恢复记忆的信息。神经网络通 过预先存储信息和学习机制进行自适应训练，可以从不完整的信息和噪声干扰中恢复 原始的完整信息，这一能力使其在图像复原，图像和语音处理，模式识别，分类等方 面具有巨大的潜在应用价值。其中，自联想记忆是指网络中预先存储多种模式信息， 当输入某个已存储模式的部分信息或带有噪声干扰的信息时，网络能通过动态联想过 程回忆起该模式的全部信息。异联想记忆是指网络中预先存储了多个模式对，每一对 模式均由两部分组成，当输入某个模式对的一部分时，即使输入信息是残缺的或迭加 了噪声，网络也能回忆起与其对应的另一部分。 2 ) 非线性映射 在客观世界中，许多系统的输入与输出之间存在复杂的非线性关系，对于这类系 统，往往很难用传统的数理方法建立其数学模型。设计合理的神经网络通过对系统输 入输出样本对进行自动学习，能够以任意精度逼近任意复杂的非线性映射。神经网络 的这一优良性能使其可以作为多维非线性函数的通用数学模型。该模型的表达是非解 析的，输入输出数据之间的映射规则由神经网络在学习阶段自动抽取并分布式存储在 网络的所有连接中。具有非线性映射功能的神经网络应用十分广阔，几乎涉及所有领 域。 3 ) 分类与识别 神经网络对外界输入样本具有很强的识别与分类能力。对输入样本的分类实际上 是在样本空间找出符合要求的分割区域，每个区域内的样本属于一类。传统分类方法 只适合解决同类相聚，异类分离的识别与分类问题。但客观世界中许多事物在样本空 第二章神经网络和遗传算法技术 间上的区域分割曲面是十分复杂的，相近的样本可能属于不同的类，而远离的样本可 能同属一类。神经网络可以很好的解决对非线性曲面的逼近，因此比传统的分类器具 有更好的分类与识别能力。 4 ) 优化计算 优化计算是指在己知的约束条件下，寻找一组参数组合，使由该组和确定的目标 函数达到最大值。某些类型的神经网络可以把待求解问题的可变参数设计为网络的状 态，将目标函数设计为网络的能量函数。神经网络经过动态演变过程达到稳定状态时 对应的能量函数最小，从而其稳定状态就是问题的最优解。这种优化计算不需要对目 标函数求导，其结果是网络自动给出的。 5 ) 知识处理 知识是人们从客观世界的大量信息以及自身的实践中总结归纳出来的经验，规则 和判据。神经网络获得知识的途径与人类似，也是从对象的输入输出信息中抽取规律 而获得关于对象的知识，并将知识分布在网络的连接中予以存储。神经网络的知识抽 取能力使其能够在没有任何先验知识的情况下自动从输入数据中提取特征，发现规 律，并通过自组织过程将自身构建成适合于表达所发现的规律。另一方面，人的先验 知识可以大大提高神经网络的知识处理能力，两者结合会使神经网络智能得到进一步 的提升【2 4 】。 2 1 2 生物神经元结构和人工神经元模型 神经元是脑组织的基本单位，是神经系统结构与功能的单位。据估计，人类大脑 大约包含有1 0 1 1 个神经元，每个神经元与大约1 0 3 1 0 5 个其他神经元相连接，构成 一个极为庞大而复杂的系统，即生物神经网络。生物神经元的结构如图2 1 所示： 图2 1 生物神经元结构 f i g2 一ls t r u c t u r eo f an e u r o n 9 北京化工大学硕士学位论文 生物神经元在结构上由细胞体，树突，轴突和突触四部分组成。其中，树突是从 细胞体向外延伸出的许多突起的神经纤维。神经元靠树突接受来自其他神经元的输入 信号，相当于细胞体的输入端。轴突是由细胞体伸出的最长的一条突起，用来传出细 胞体产生的输出电化学信号，相当于细胞体的输出端。神经元之间通过一个神经元的 轴突末梢和其他神经元的细胞体或树突进行通信连接，这种连接相当于神经元之间的 输入输出接口，称为突触。生物神经元具有以下基本特性： ( 1 ) 神经元是一个多输入单输出元件； ( 2 ) 具有非线性的输入输出特性； ( 3 ) 各神经元间传递信号的强度，即藕和紧密的程度是可变的，且输入信号有 兴奋作用与抑制作用之分； ( 4 ) 神经元的输出相应取决于所有输入信号迭加的结果，当综合输入值超过某 一阈值时，该神经元被激活；否则将处于抑制状态例。 人工神经元是对生物神经元的一种形式化描述，它对生物神经元的信息处理过程 进行抽象，并用数学语言予以描述；对生物神经元的结构和功能进行模拟，并用模型 图予以表达。m p 模型是经典的人工神经元模型，如图2 2 所示： 图2 2m p 模型 f i 9 2 - 2 m - p m o d e l 对于第j 个神经元，接受多个其他神经元的输入信号x i 。各突触强度以实系数w 西 表示，这是第i 个神经元对第j 个神经元作用的加权值。利用某种运算把输入信号的 作用结合起来，给出它们的总效果，称为“净输入一，以n e t i 或毛表示。净输入表达 式有多种类型，其中，最简单的一种形式是线性加权求和，即： = 坳t 2 1 此作用引起神经元j 的状态变化，而神经元j 的输出m 是其当前的函数。 m p 模型的数学表达式为： 、 少，= s g n i t g | 2 2 i o 第二章神经网络和遗传算法技术 式中，e 为阈值，s n g 是符号函数，当净输入超过阈值时，的取+ l 输出，反之 为一1 输出【1 2 1 。 2 1 3 神经网络技术的基本要素 在神经网络的设计及应用研究中，通常需要考虑3 个方面的内容，即神经元功能 函数，神经元之间的连接形式和网络的学习( 训练) 。 神经元在输入信号作用下产生输出信号的规律由神经元功能函数f ( a c t i v a t i o n f u n c t i o n ) 给出，也成激活函数，或称转移函数，这是神经元模型的外特性，它包含 了从输入信号到净输入，再到激活值，最终产生输出信号的过程f 2 习。 神经网络的强大功能与其大规模并行互连，非线性处理以及互连结构的可塑性密 切相关，因此必须按一定规则将神经元连接成神经网络，并使网络中各神经元的连接 权按一定规则变化。神经网络的连接形式也叫网络的拓扑结构，典型的有前馈型网络 和反馈型网络。其中，前馈型网络可用一个有向无环路的图表示。输入层常记为网络 的第一层，第一个隐层记为网络的第二层，其余类推。前馈式神经网络信息处理的方 向是从输入层到各隐层再到输出层逐层进行而得名。从信息处理能力看，网络中的节 点可分为两种：一种是输入节点，只负责从外界引入信息后向前传递给第一隐层；另 一种是具有处理能力的节点，包括各隐层和输出层节点。前馈型网络前一层的输山是 下一层的输入，信息的处理具有逐层传递进行的方向性，一般不存在反馈环路。因此 这类网络很容易串联起来建立多层前馈网络。图2 3 即为多层前馈式神经网络示意图。 ，。 l l l l l l f i 图2 3 多层前馈式网络 f i g2 - 3m u l t i l a y e rf e e d f o n a r dn e t 、】i r o r k 反馈式网络是指某层的输出通过连接权反馈到同一层或前一层的输入。在反馈网 络中所有节点都具有信息处理功能，而且每个节点既可以从外界接受输入，同时又可 ：i 匕京化工大学硕士学位论文 以向外界输出。 神经网络的功能特性由其连接的拓扑结构和突触连接强度，即连接权值决定。神 经网络的全体连接权值可用一个矩阵w 表示，其整体内容反映了神经网络对于所解 决问题的知识储备。神经网络能够通过对样本的学习训练，不断改变网络的连接权值 以及拓扑结构，以使网络的输出不断地接近期望的输出。这一过程称为神经网络的学 习或训练，其本质是对可变权值的动态调整。神经网络的学习算法众多，可以归纳为 三类：一类是有导师学习，二类是无导师学习，三类是死记式学习。 有导师学习又称为有监督学习，这种学习模式采用的是纠错规则。在学习训练过 程中需要不断给网络成对提供一个输入模式和一个期望网络正确输出的模式，称为 “教师信号”。将神经网络的实际输出同期望输出进行比较，当网络的输出与期望的 教师信号不符时，根据差错的方向和大小按一定的规则调整权值，以使下一次网络的 输出更接近期望结果。对于有导师学习，网络在能执行工作任务之前必须先经过学习， 当网络对于各种给定的输入均能产生所期望的输出时，即认为网络已经在导师的训练 下。学会力了训练数据集中包含的知识和规则，可以用来工作了。本文使用的神经网 络模型，b p 神经网络，即采用有导师的学习方式进行训练。 无导师学习也成为无监督学习。在学习过程中，需要不断地给网络提供动态输入 信息。网络能根据特有的内部结构和学习规则，在输入信息流中发现任何可能存在的 模式和规律，同时能根据网络的功能和输入信息调整权值，这个过程称为网络的自组 织，其结果是使网络能对属于同一类的模式进行自动分类。 死记式学习是指网络事先设计成能记忆特定的例子，以后当给定相关该例子的输 入信息时，例子便被回忆起来。死记式学习中网络的权值一旦设计好了就不再变动， 因此其学习是一次性的，而不是一个训练过程。 因此，网络的运行一般分为训练和工作两个阶段。训练的目的是为了从训练数据 中提取隐含的知识和规律，并存储于网络中供工作阶段使用【2 4 j 。 2 1 4b p 神经网络 1 b p 神经网络的基本思想 b p ( e n d rb a c kp r o p a g a t i o nn e 咐o d 【) 神经网络是目前应用最为广泛和成功的神经 网络之一。它是在1 9 8 6 年由r l l m e l h a n t 和m c c l e l l 雒d 提出的。是一种多层网络的“逆 推 学习算法。其基本思想是，学习过程由信号的正向传播与误差的反向传播两个过 程组成。正向传播时，输入样本从输入层传入，经隐层逐层处理后传向输出层。若输 出层的实际输出与期望输出( 教师信号) 不符，则转向误差的反向传播阶段。误差的 反向传播是将输出误差以某种形式通过隐层向输入层逐层反转，并将误差分摊给各层 的所有单元，从而获得各层单元的误差信号，此误差信号即作为修正个单元权值的依 第二章神经网络和遗传算法技术 据。这种信号正向传播与误差反向传播的各层权值调整过程是周而复始进行。权值不 断调整的过程，也就是网络的学习训练过程。此过程一直进行到网络输出韵误差减少 到可以接受的程度，或进行到预先设定的学习次数为止。 2 b p 神经网络的功能 非线性映射功能：多层前馈式神经网络能学习和存储大量输入输出模式映射关 系，而无需事先了解描述这种映射关系的数学方程。只要能提供足够多的样本模式对 供多层前馈式神经网络进行学习训练，它便能够完成由n 维输入空间到m 维输出空间 的非线性映射。在工程上及许多技术领域中经常遇到这样的问题：对某输入输出系统 已经积累了大量相关的输入输出数据，但对其内部蕴含的规律仍未掌握，因此无法用 数学方法来描述该规律。在软件测试中，许多被测软件输入输出之间存在着极其复杂 的无法用数学公式表达得映射关系，因此，使用多层前馈式神经网络进行模拟具有无 可比拟的优势。 泛化功能：多层前馈式神经网络训练后将所提取的样本对中的非线性映射关系存 储在权值矩阵中，在其后的工作阶段，当向网络输入训练时未曾见过得非样本数据时， 网络也能完成由输入空问向输出空间的正确映射，这种能力称为泛化能力。 容错功能：多层前馈式神经网络允许输入样本中带有较大的误差甚至个别错误。 因为对权矩阵的调整过程也是从大量的样本对中提取统计特性的过程，反映正确规律 的知识来自全体样本，个别样本中的误差不能左右对权矩阵的调整。 3 b p 神经网络模型 典型的三层b p 神经网络模型如图2 4 所示： 0 1 o l c o l x 1x 2 毪l巯 图2 _ 4 b p 神经网络结构 f i g2 _ 4s n c t u r eo fb pn e i l m ln e t w o r k 其中， 输入向量为x = ( 五，x ：，五，z 。) 7 ， 隐层输出向量为 y = ( y l ，少2 ，y ，y 。) r ，输出层输出向量为d = ( d l ，d ：，d ”，d ，) r ，期望输出向量为 北京化工大学硕士学位论文 矗= ( 盔，d ：，畋，d ，) f ，输入层到隐层之间的权值矩阵用v 表示， y = ( k ，巧，吃) r ，其中列向量巧为隐层第j 个神经元对应的权向量，隐层到输 出层的权值矩阵用w 表示，= ( 暇，暇，嘭) r ，其中列向量为输出层第k 个神经元对应的权向量。 对于输出层，有 d 七= ( 珂p 气) 七= l ，2 ， 2 - 3 ，扛 以e 气= w 陆j ， 七= l ，2 ， 以e 气2 乞j ，- ， 七2 l ，2 ， 卢o 对于隐层，有 y ，= 八，l 哆) = l ，2 ，m 删，= 而 ，= 1 ，2 ，朋 鹏02 乞b 而 _ ，2l ，2 ，朋 f i o 2 5 2 - 6 当网络输出与期望输出不等时，存在输出误差e ，定义如下： 层= 寺( d d ) 2 = 寺( 以一吼) 2 2 - 7 厶 七一l 将以上误差展开至输入层，有 e = 三喜c d 。一吼，2 = 圭套 d 。一厂 嘉厂c 喜毛， 2 2 s 网络输入误差是各层权值的函数，调整权值的原则是使误差不断地减小，因此应 使权值的调整量与误差的负梯度成正比，即 吨叫嚣例，1 ，2 ，棚 2 ， 毗叫筹 l 2 ，卅川，2 ，研 2 - 9 其中，刀表示学习速率。经过推导，可知权值的调整量为： w _ 肚= ，7 善f y ，= 刁( d t d ) d i ( 1 一d t ) y ， 2 - l o ， = 7 7 孝歹而= 刁( 善；肛) j ，( 1 一y ，) 七= l 其中， 1 4 2 1 1 第二章神经网络和遗传算法技术 嚣一嚣俨一盖 为误差信号。 2 1 2 b p 标准算法描述如下： ( 1 ) 初始化对权值矩阵w v 赋随机数，将样本模式计数器p 和训练次数计数器q 置为1 ，误差e 置0 ，学习率设为0 1 间小数，网络训练后达到的e l i i i 设为一正的小 数。 ( 2 ) 输入训练样本对，使用式2 3 ，2 _ 4 ，2 5 ，2 6 计算各层输出。 ( 3 ) 利用式2 7 计算网络输出误差。 ( 4 ) 计算各层误差信号。 ( 5 ) 应用式2 1 0