基于遗传算法的神经网络设计本科生毕业设计

江西理工大学2010届本科生毕业设计（论文）摘要随着科学技术的发展，各学科交叉渗透，利用遗传算法用于解决传统计算所遇到的寻找最优解或准优解显得尤为重要。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。遗传算法经实践证明特别有效的算法。本课题将在对神经网络、遗传算法等进行基础理论研究的前提下，注重对遗传算法的C语言实现进行研究，同时对GA在优化和神经网络训练等方面的应用和实现进行较深入的探讨。本文阐述了将遗传算法用于神经网络权值学习和训练的原理和方法，并详述了神经网络权值学习和训练中遗传算法的具体实现过程。关键词：遗传算法；神经网络；繁殖；交叉；变异；适应度ABSTRACTWiththedevelopmentofscienceandtechnology,infiltratedthevariousdisciplines,thetraditionaluseofgeneticalgorithmsforsolvingencounteredcalculationtofindtheoptimalsolutionorquasi-optimalsolutionisveryimportant.Therefore,thestudycanbeautomaticallyinthesearchprocessandtheaccumulationofknowledgeofthesearchspace,andcanadaptivelycontrolthesearchprocess,therebyyieldingtheoptimalsolutionorthequasi-solvabilityofthegeneralsearchalgorithmhasbeenaremarkablesubject.GAprovenparticularlyeffectivemethod.Thisissuewillbeonneuralnetworks,geneticalgorithmsandbasicpremiseoftheory,focusingontheClanguageimplementationofgeneticalgorithmresearch,whileGAoptimizationandneuralnetworktrainingintheareasofapplicationandimplementationofmorein-depth.Inthispaper,geneticalgorithmneuralnetworkweightlearningandtrainingprinciplesandmethods,anddetailedstudyofneuralnetworkweightsandtraininginthespecificrealizationofgeneticalgorithmKeywords:geneticalgorithm;neuralnetwork;fitness;crossover;mutationbreeding;毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作者签名：日期：指导教师签名：日期：使用授权说明本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名：日期：

学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名： 日期：年月日导师签名：日期：年月日

目录第一章绪论 41.1遗传算法的产生及特点 41.2遗传算法的发展及其应用 51.3本课题的选题背景 51.5本课题研究目的与意义 6第二章神经元网络及BP算法 72.1神经网络概述 72.2神经元的数学模型 72.3BP学习算法 92.4BP算法的原理 9第三章遗传算法 153．1遗传算法概述 153.2遗传算法的步骤 163.2.1编码问题 163.2.3选择 173.2.4交叉 183.2.5变异 193.2.6全局最优收敛 19第四章遗传算法在神经网络中的应用 214.1遗传算法与神经网络的结合 214.2遗传算法训练神经网络C语言实现 224.2.1用遗传算法训练神经网络的要求 224.2.3遗传算法训练神经网络C语言实现 244.3结果分析 35第五章结束语 38参考文献： 39第一章绪论BP网(BackPropagationNetwork)是目前应用最为广泛的神经网络，具有相当强的输入输出映射能力．但是，由于BP算法的基本思想是最小二乘法，采用的是梯度搜索技术，难免存在收敛速度慢、局部极小等问题。神经网络和遗传算法都是比较先进的计算方法，它们已成功地应用于工业、经济管理、交通运输、工业设计等领域，解决了许多问题。但是神经网络权值训练和学习过程的复杂和长期性，特别是神经网络易有训练过度的缺点，这些都大大影响了神经网络的更广泛普及和应用。遗传算法是一种高效和计算简单的优化算法，它完全可以应用于神经网络权值的训练和学习中，提高神经网络的学习效率和学习速度，减轻网络学习过度的问题，为神经网络的更广泛应用奠定基础。1.1遗传算法的产生及特点遗传算法是根据生物进化思想而启发得出的一种全局优化算法，并且遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。遗传算法作为一种快捷、简便、容错性强的算法，在各类结构对象的优化过程中显示出明显的优势。与传统的搜索方法相比，遗传算法具有如下特点：搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作。搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的方法，降低了陷入局部最优解的可能性，并易于并行化。采用概率的变迁规则来指导搜索方向，而不采用确定性搜索规则。对搜索空间没有任何特殊要求（如连通性、凸性等），只利用适应性信息，不需要导数等其它辅助信息，适应范围更广。遗传算法具有许多独特的优点:1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，几乎可处理任何问题。3．遗传算法有极强的容错能力遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。5．遗传算法具有隐含的并行性。遗传算法在操作上具有高度的并行性,许多研究人员都在探索在并行机和分布式系统上高效执行遗传算法的策略。对分布并行遗传算法的研究表明,只要通过保持多个群体和恰当控制群体间的相互作用来模拟并行执行过程,即使不使用并行计算机,也能提高算法的执行效率。1.2遗传算法的发展及其应用遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。1.3本课题的选题背景当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。但是，近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种背景下产生并经实践证明特别有效的算法。1.4本课题主要研究内容学习是神经网络研究的一个重要内容，它的适应性是通过学习实现的。根据环境的变化，对权值进行调整，改善系统的行为。由Hebb提出的Hebb学习规则为神经网络的学习算法奠定了基础。Hebb规则认为学习过程最终发生在神经元之间的突触部位，突触的联系强度随着突触前后神经元的活动而变化。在此基础上，人们提出了各种学习规则和算法，以适应不同网络模型的需要。有效的学习算法，使得神经网络能够通过连接权值的调整，构造客观世界的内在表示，形成具有特色的信息处理方法，信息存储和处理体现在网络的连接中。1.5本课题研究目的与意义本课题任务主要是在监督学习中，利用C语言编程，研究通过GA算法直接训练神经网络和训练初始权值的方法。将训练样本的数据加到网络输入端，同时将相应的期望输出与网络输出相比较，得到误差信号，以此控制权值连接强度的调整，经多次训练后收敛到一个确定的权值。当样本情况发生变化时，经学习可以修改权值以适应新的环境。第二章神经元网络及BP算法2.1神经网络概述神经网络是大量的简单神经元按一定规则连接构成的网络系统。网络能够模拟人类大脑的结构和功能,自1943年第一个神经网络模型MP模型提出至今，神经网络发展非常迅速。特别是1982年提出的Hopfield网络模型和1985年提出的BP算法,神经网络逐步得到更加广泛的应用。神经网络是由大量神经元广泛互连形成大规模并行处理和分布式的信息存储的复杂网络系统。单一神经元可以有许多输入、输出。神经元之间的相互作用通过连接的权重体现，神经元的输出是其输入的函数。单一简单的神经元，经过大规模的互联形成了复杂庞大的系统，可实现多种多样的日任务。神经网络计算的基本特征是大规模并行处理、容错性、自适应性和自组织性。大规模并行处理指能同时处理与决策有关的因素．采用某种学习算法从训练样本中学习，并将获取的知识存储在网络各单元之间的连接权中，神经网络和基于符号的传统K9技术相比，具有直观性、并行性和抗噪性。目前已出现了多种网络模型和学习算法，主要用于分类、优化、模式识别、预测和控制等领域。2.2神经元的数学模型从神经元的特性和功能可以知道，神经元是一个多输入单输出的信息处理单元，而且它对信息的处理是非线性的。根据神经元的特性和功能，可以把神经元抽象为一个简单的数学模型。工程上用的人工神经元模型如图2-2所示。图2-2神经元的数学模型在图2—2中，，，……，是神经元的输入，即是来自前级n个神经元的轴突的信息W是i神经元的阀值；，……，分别是i神经元对，，……，的权系数，也即突触的传递效率；是i神经元的输出；f[·]是激发函数，它决定i神经元受到输人，，……，的共同刺激达到阀值时以何种方式输出。从图2-2的神经元模型，可以得到神经元的数学模型表达式：(2-1)图2-3.典型激发函数对于激发函数f[·]有多种形式，其中最常见的有阶跃型、线性型和S型三种形式，这三种形式如图2—3所示。为了表达方便；令：=（2-2）则公式(2-1)可写成下式：=F[]；

(2-3)显然，对于阶跃型激发函数有：（2-4）对于线性型激发函数，有：f()=；

（2-5）对于S型激发函数，有：（2-6）对于阶跃型激发函数，它的输出是单位脉冲，故而这种激发函数的神经元称离散输出模型。对于线性激发函数，它的输出是随输入的激发总量成正比的；故这种神经元称线性连续型模型。对于用s型激发函数，它的输出是非线性的；故这种神经元称非线性连续型模型。阀值函数(Thresh0ldFunction)阀值函数又叫阶跃函数，当激活函数仅用来实现判定神经元所获得的网络输入是否超过闭值θ时，使用此函数。（2-7）其小，β、γ、θ均为非负实数。通常，人们都用公式（2—7）的二值形式：有时候，还将公式（2—8）中的0改为—1，此时就变成了双极形式：（2-8`）上面所叙述的是最广泛应用而且人们最熟悉的神经元数学模型；也是历史最长的神经元模型。近若干年来，随着神经网络理论的发展，出现了不少新颖的神经元数学模型，这些模型包括逻辑神经元模型，模糊神经元模型等，并且渐渐也受到人们的关注和重视。2.3BP学习算法反向传播算法也称BP算法。由于这种算法在本质上是一种神经网络学习的数学模型，所以，有时也称为BP模型。BP（Backpropagation）神经网络又称为多层前馈神经网络，这种神经网络模型的特点是：各层神经元仅与相邻层神经元之间有连接；各层内神经元之间无任何连接；各层神经元之间无反馈连接。BP算法是为了解决多层前向神经网络的权系数优化而提出来的；所以，BP算法也通常暗示着神经网络的拓扑结构是一种无反馈的多层前向网络。故而．有时也称无反馈多层前向网络为BP模型。在这里，并不要求过于严格去争论和区分算法和模型两者的有关异同。感知机学习算法是一种单层网络的学习算法。在多层网络中．它只能改变最后权系数。因此，感知机学习算法不能用于多层神经网络的学习。1986年，Rumelhart提出了反向传播学习算法，即BP(back-propagation)算法。这种算法可以对网络中各层的权系数进行修正，故适用于多层网络的学习。BP算法是目前最广泛用的神经网络学习算法之一，在自动控制中是最有用的学习算法。2.4BP算法的原理BP算法是用于前馈多层网络的学习算法，前馈多层网络的结构一般如图2-4所示图2-4网络学习结构它含有输人层、输出层以及处于输入输出层之间的中间层。中间层有单层或多层，由于它们和外界没有直接的联系，故也称为隐层。在隐层中的神经元也称隐单元。隐层虽然和外界不连接．但是，它们的状态则影响输入输出之间的关系。这也是说，改变隐层的权系数，可以改变整个多层神经网络的性能。设有一个m层的神经网络，并在输入层加有样本X；设第k层的i神经元的输入总和表示为，输出；从第k—1层的第j个神经元到第k层的第i个神经元的权系数为各个神经元的激发函数为f，则各个变量的关系可用下面有关数学式表示：(2-9)(2-10)反向传播算法分二步进行，即正向传播和反向传播。这两个过程的工作简述如下：1．正向传播输入的样本从输入层经过隐单元一层一层进行处理，通过所有的隐层之后，则传向输出层；在逐层处理的过程中，每一层神经元的状态只对下一层神经元的状态产生影响。在输出层把现行输出和期望输出进行比较，如果现行输出不等于期望输出，则进入反向传播过程。2．反向传播反向传播时，把误差信号按原来正向传播的通路反向传回，并对每个隐层的各个神经元的权系数进行修改，以望误差信号趋向最小。2.5BP算法的数学表达BP算法实质是求取误差函数的最小值问题。这种算法采用非线性规划中的最速下降方法，按误差函数的负梯度方向修改权系数。为了说明BP算法，首先定义误差函数e。取期望输出和实际输出之差的平方和为误差函数，则有：（2-11）其中：Yi是输出单元的期望值；它也在这里用作教师信号；是实际输出；因为第m层是输出层。由于BP算法按误差函数e的负梯度方向修改权系数，故权系数的修改量A，和e△-（2-12）也可写成△-（2-13）其中：η为学习速率，即步长。很明显，根据BP算法原则，求是最关键的。下面求；有（2-14）由于(2-15)故而(2-16)从而有(2-17)令（2-18）则有学习公式：（2-19）从公式(2-9)可知在公式(2-17)中，有其中：η为学习速率，即步长，一般取0-1间的数。从上面可知，实际仍末给出明显的算法公式，下面求的计算公式。（2-20）从公式(2-9)可知在公式(2-20)中，有（2-21）为了方便进行求导，取f为连续函数。一般取非线性连续函数，例如Sigmoid函数。当取f为非对称Sigmoid函数时，有：（2-22）则有（2-23）再考虑式(2-20)中的偏微分项e／，有两种情况需考虑的：如果k＝m，则是输出层，这时有是输出期望值，它是常数。由于公式(2-11)中有(2-24)从而有=(1-)(-Yi)(2-25)2．如果k<m，则该层是隐层。这时应考虑上一层对它的作用，故有：（2-26）从公式(2-18)中，可知有：（2-27）从公式(2-10)中，可知有：（2-28）故而有：（2-29）最后有：（2-30）从上述过程可知：多层网络的训练方法是把一个样本加到输入层，并根据向前传播的规则：（2-31）不断一层一层向输出层传递，最终在输出层可以得到输出。把和期望输出进行比较．如果两者不等，则产生误差信号e，接着则按下面公式反向传播修改权系数：（2-32）其中（2-33）（2-34）上面公式中，求取本层时，要用到高一层的；可见，误差函数的求取是从输出层开始，到输入层的反向传播过程。在这个过程中不断进行递归求误差。通过多个样本的反复训练，同时向误差渐渐减小的方向对权系数进行修正，以达最终消除误差。从上面公式也可以知道，如果网络的层数较多时，所用的计算量就相当可观，故而收敛速度不快。为了加快收敛速度，一般考虑上一次的权系数，并以它作为本次修正的依据之一，故而有修正公式：（2-35）其中：η为学习速率，即步长，η＝0.1—0.4左右为权系数修正常数，取0.7—0.9左右。在上面，公式(2-32)也称为一般化的Delta法则。对于没有隐层的神经网络，可取（2-36）其中：为期望输出；为输出层的实际输出；为输入层的输入。这显然是一种十分简单的情况，公式(2-36)也称为简单Delta法则。在实际应用中，只有一般化的Delta法则公式（2-36）或公式(2-35)才有意义。简单Delta法则式(2-36)只在理论推导上有用。第三章遗传算法3．1遗传算法概述遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：注意以下格式问题！一、串(String)

它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。二、群体(Population)个体的集合称为群体，串是群体的元素三、群体大小(PopulationSize)在群体中个体的数量称为群体的大小。四、基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。

五、基因位置(GenePosition)一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。六、基因特征值(GeneFeature)

在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。七、串结构空间SS

在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。八、参数空间SP这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。九、非线性它对应遗传学中的异位显性(Epistasis)十、适应度(Fitness)表示某一个体对于环境的适应程度。3.2遗传算法的步骤3.2.1编码问题标准遗传算法主要通过遗传操作(交叉与变异)对种群中的个体施加结构重组处理，通过选择操作不断优化群体中的个体结构，从而搜索到最优结构的个体，达到逼近问题的最优解的目的。由此可见，标准遗传算法不能直接对问题空间进行操作，必须将问题空间的解变量转换成遗传空间，由基因按一定结构组成染色体，这一转换操作就叫做编码。（一）编码原则评价编码策略通常考虑一下三个方面:(1)完备性。问题空间中的所有点都能作为遗传空间中的点(染色体)来表现。(2)健全性。遗传空间中的染色体能对应所有问题空间中的候选解。(3)非冗余性。染色体和候选解一一对应。对于很多问题很难设计出同时满足上面三条要求的编码方案，但是完备性是必须满足的一项。这三个评价规范是独立于问题领域的普遍准则，具有普遍意义，但是缺乏具体的指导思想，特别是满足这些条件的编码设计不一定能有效地提高遗传算法的搜索效率。相比之下，DeJong提出较为客观明确的编码评估准则，称之为编码原理，由于可操作性较强，又称之为编码规则。具体为:(1)有意义基因块的编码规则。所定编码应当易于生成与所求问题相关的短距和低阶的基因块。(2)最小字符集编码规则。所定编码应采用最小字符集，以使问题得到自然的表示或描述。(二)编码方法下面介绍几种常用的遗传算法编码技术。(1)一维染色体编码。一维染色体编码是指问题空间的候选解转换到遗传空间后，其相应的染色体呈一维排列的基因链码。通常采用的一维染色体编码技术有:1)二进制编码。二进制编码是将问题空间的候选解转换为遗传空间的各位数值为“0”或“1”的字符串。二进制编码方法是最为经典和常用的编码方法，它的优点有:①符合最小字符集的编码原则;②编码简单，便于进行交叉、变异等遗传操作，且物理概念清晰;③便于用模式定理川进行分析与预测。但是对于多维、高精度问题，二进制编码就会显示出一些不足，主要有:①二进制编码不能直接反映出所求问题的本身结构特征;②二进制编码的染色体长度与问题空间的区域大小和精度要求直接相关，对于大区间、高精度的问题，染色体的长度会很长，搜索空间也会很大，这样的搜索相当困难;③相邻的二进制编码可能会有较大的Hamming距离，从而降低了遗传算子的搜索效率。2)灰码编码。利用灰码编码方法可以在一定程度上克服上述缺点。灰码编码是将二进制编码通过一个变换而得到的编码，其表现也为二进制的形式，所不同的是灰码编码技术保证了在遗传空间相互靠近的两个点也必须在问题空间里靠近，反之亦然。3)浮点编码。浮点编码是灰码转换，只是保证了问题空间相邻的点在遗传空间有数值为1的Hamming距离，但遗传空间还不是问题空间。如果采用浮点表达的编码方法，即每个染色体向量被编码成一个与解向量相同长度的浮点数向量，那么，在执行上，遗传空间就是问题空间，染色体直接反映了问题的规律与特性。浮点编码与二进制编码相比有以下优点:①精度依赖于所使用的机器，与编码本身无关，比二进制要灵活、方便；②浮点编码能够表达很大的区域，而二进制编码必须以牺牲精度来增加表达区域；③容易设计出封闭的、动态的遗传算子，容易处理非常规约束。一维编码的方法还有很多，如交叉编码、多参数编码、可变长编码等等。二维染色体编码。在很多实际问题中，解本身就是以二维或多维的形式存在的，为了使问题的表达更直观，可直接采用多维染色体编码。选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。

通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。3.2.2适应度函数在遗传算法的进化过程中，对染色体的评价是由适应度函数来完成的，函数的函数值作为选择运算的依据。即遗传算法向着适应值增加的方向进化适应度，所以目标函数的寻优方向与适应度函数值增加的方向一致，这是适应度函数设计的先决条件。另外，为了理论分析的方便，最好保证适应度函数非负。有时适应值为负的清况，要进行适当的转换。将目标函数转换成适应度一般要遵循下面两个基本原则。(1)优化过程中目标函数的优化方向(如寻求目标函数的最大值或最小值)与种群进化过程中适应度函数值增加的方向相一致。(2)适应度函数值大于等于零。如果目标函数是求最小值问题，可通过适当转换，如:fit(x)=c-f(x),c≥fmax3.2.3选择选择运算是推动进化的直接动力。如果选择压力过大，遗传算法会过早收敛，使搜索落入局部极小点;选择压力过小搜索过程会非常缓慢。一般来讲，在进化的初始阶段，宜采用较小的选择压力，尽量保持种群个体的多样性;在进化的后期，宜采用较大的选择压力，以提高优良个体的竞争力，使搜索向着最优解的方向发展。选择可以通过以下三个方面进行描述:（1）采样空间。（2）采样机理。（3）选择概率。三者对于选择压力以至于遗传算法的性能都有很大的影响。1.采样空间采样空间可划分为规则的采样空间和扩大的采样空间两种。2.采样机理采样机理使如何从采样空间中选择染色体的理论，对种群个体的选择从原理上可分为三种:(1)随机采样;(2)确定采样;{3)混合采样。随机采样方法首先根据各染色体个体的适应值评价出其生存概率，再由生存概率确定每个染色体的实际繁殖数量。每个染色体的生存概率是确定性的，而染色体个体实际的繁殖数量是其生存概率随机产生的，是随机性的。整个选择过程可由两步完成:(1)确定种群中个体的生存概率。{2)根据个体的生存概率进行随机选择。随机采样的基本思想是:适应值大的个体对应较高的生存概率，则被选择进入F1代的几率相对较高。但是，并不能保证最优的个体被选择。确定采样的基本思想是:保证最好的染色体被选择进入下一代。常用的方法有截断选择法、精英选择法和期望选择法等。混合采样同时具备随机采样和确定采样的特征。3.选择概率种群中的染色体的选择概率与选择压力直接相关。Holland的原始遗传算法所采用的轮盘算法是一种正比选择方法，选择概率正比于染色体的适应值。正比选择的缺点是在进化的早期，一些超级染色体会充斥选择过程，容易失去种群染色体的多样性;而进化的后期，优良染色体的竞争能力减弱，使选择变得像随机搜索。标定法和排序法就是为解决上述问题而提出的。(1)标定法。标定法就是通过调整适应度函数来控制种群中染色体的生存概率。对适应度函数进行调整的意义在于:①使种群中染色体的适应值之间保持合理的差距:②限制某些超级染色体的繁殖速度，以满足早期限制竞争，后期鼓励竞争的要求。常用的标定方法有线性标定法、α截断法、幂律标定法和指数标定法等等。(2)排序法。排序法以种群中染色体适应值的大小顺序来确定各个染色体的生存概率，而不是以适应值的数值大小来确定，该方法克服了基于适应值进行选择。常用的方法有;线性排序法和指数排序法。3.2.4交叉对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。单点交叉(one-pointcrossover)又称一点交叉。只有一个交叉点位置，任意挑选经过选择操作后种群的两个个体作为交叉对象，随机产生一个交叉点位置，两个个体在交叉点位置互换部分基因码，形成两个子个体。例如有个体S1=100101S2=010111选择它们的左边3位进行交叉操作，则有S1=010101S2=100111多点交叉（multi-pointcrossover）是单点交叉的推广，有时也称为广义交叉(generalizedcrossover)。多点交叉是指设置多个交叉点，交叉点依然是随机选择，两个个体在交叉点位置互换部分基因码，形成两个子个体。一般较少采用多点交叉，因为它影响遗传算法的在线性能和离线性能。当交叉过多时，上一代中性能优良的结构被破坏的可能性增大，这有些类似于随机搜索行为。多点交叉不能有效地保存重要的模式。例如有个体S1=100101S2=010111选择它们的左边2位和右边2位进行交叉操作则有S1=010111S2=100101一般而言，交叉概率的取值为0.25—0.75。交叉运算是重要的遗传操作，种群通过交叉产生新的染色体，从而不断扩展搜索空间,最终达到全局搜索的目的。常用的交叉算子有：1、算术交叉算子。算术交叉算子对于凸搜索空间有这样的性质:对解空间D里的任何两个点x1,x:的线性组合为:ax1+(1-a)x2a∈[0,1]算术交叉的操作过程为:假定种群中的x1,x2被选为交叉运算的双亲，则有双亲产生后代为:x'1=ax1+(1-a)x2x'2=ax2+(1-a)x1随机数a属于[0,1]，从而保证了x'1,x'2，属于D。2、启发式交又算子。启发式交叉是一种独特的交叉算子，其特点为:以目标函数值确定搜索方向:只产生一个后代;可能根本不产生后代。假定从种群中选择的双亲为x1,x2，则由双亲产生的后代为:x3=r(x2-x1)+x23.2.5变异根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

例如有个体S＝101011。

对其的第1，4位置的基因进行变异，则有

S'=001111

单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。变异操作首先是在群体中随机选择一个个体，对于选中的个体以一定的概率随机改变串结构的数据中某个串的值，即对群体中的每个个体，以某一概率（称为变异概率，MutationRate）改变某一个或某一些基因座上的基因值为其他的等位基因。同生物界一样，遗传算法中变异发生的概率很低。变异为新个体的产生提供了机会。变异算子的作用效果在于:一方面，遗传算法具有局部搜索的能力，使遗传算法能够搜索到精确解;另一方面，可以保持种群的多样性，防止出现过早收敛的现象。常用的变异有:基本变异，均匀变异，边界变异，非均匀变异。使用变异算子的目的只有两个：一是保持遗传算法的多样性，以防止出现早熟现象；二是加强遗传算法的局部随机搜索能力。当遗传搜索已经接近最优解区间，利用变异算子可以加速向最优解收敛。3.2.6全局最优收敛当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。图3.1表示了遗传算法的执行过程。图3.1遗传算法的执行过程算法的停止条件最简单的有如下二种：（1）完成了预先给定的进化代数则停止；（2）群体中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。根据遗传算法思想可以画出简单遗传算法框图3.2。图3.2简单遗传算法框图第四章遗传算法在神经网络中的应用4.1遗传算法与神经网络的结合遗传算法用于ANN的一个方面是用遗传算法学习神经网络的权重，也就是用遗传算法来取代一些传统的学习算法。评价一个学习算法的标准是：简单性、可塑性和有效性。一般的，简单的算法并不有效，可塑的算法又不简单，而有效的算法则要求算法的专一性、完美性，从而又与算法的可塑性、简单性相冲突。目前广泛研究的前馈网络中采用的是Rumelhart等人推广的误差反向传播(BP)算法，BP算法具有简单和可塑的优点，但是BP算法是基于梯度的方法，这种方法的收敛速度慢，且常受局部极小点的困扰，采用GA则可摆脱这种困境。当然，使用GA可以把神经网络的结构优化和权值学习合并起来一起求解，但这对计算机的处理能力要求很高。由于BP网络模型有收敛于局部最小点这一个不可克服的弱点。遗传算法是基于生物进化机理的数学算法系统，许多实践已经证明遗传算法是进行全局搜索的有效工具。目前,遗传算法与神经网络的结合方式有几种，大致归纳如下：(1)进化神经网络的权重；(2)进化神经网络的拓扑结构；(3)同时进化神经网络的权重与拓扑结构；(4)分析神经网络的训练数据与训练结果。其中,进行神经网络的分析是指用遗传算法来揭示输入样本之间的相关性，从而确定如何对输入分组进行网络训练。这类研究现在还无法确定其广泛应用的有效性。实践证明，不管是否同时进化网络的权重与否，单就进化网络的权重与否，这是一件非常困难的事情，这种方法只解决一些简单问题；况且，对如何选择网络的拓扑结构问题，目前无论在理论还是在方法上，都还没找到有效的指导原则。所以，遗传算法与神经网络相结合的研究，大都结合在网络权重的训练上。本文中也是采用遗传算法优化网络权重的方法。遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。1．遗传算法在网络学习中的应用在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用(1)学习规则的优化用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。(2)网络权系数的优化用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。2．遗传算法在网络设计中的应用

用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：(1)直接编码法这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。(2)参数化编码法参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。(3)繁衍生长法这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。3．遗传算法在网络分析中的应用遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。4.2遗传算法训练神经网络C语言实现4.2.1用遗传算法训练神经网络用遗传算法训练神经网络并用C语言编程实现以下函数已知训练样本如下表所示，要求设计图中所示的神经网络。输入输出样本X1X2yX1X2y1.401.803.702.002.062.524.284.961.312.714.131.581.184.293.351.781.114.711.961.902.703.632.271.871.851.433.522.243.741.793.661.602.461.842.141.954.854.661.304.511.522.513.413.881.483.771.452.701.382.553.141.052.554.632.664.421.564.511.372.804.444.711.321.844.431.973.111.064.081.672.812.474.473.661.422.031.882.661.351.763.913.621.952.081.241.415.051.672.232.752.811.351.973.383.701.511.924.251.922.833.701.514.612.681.631.484.442.443.044.971.443.372.131.994.823.801.392.841.243.422.581.972.222.581.972.294.101.712.274.353.901.401.651.383.942.221.353.39遗传算法（GA）用于神经网络训练研究及其在C语言中的实现用GA算法来训练网络，要求：用C语言编制训练网络的算法程序；画出训练完成后的网络图，并标出各权值；C)随机产生10个检验样本来检验网络，给出平均值、最大误差、均方差4.2.2面向神经网络权值学习的遗传算法通过以上各节所讨论的内容，本文选择以下遗传算子来训练网络。编码方式：神经网络的权值学习是一个复杂的连续参数优化问题，本文选择二进制进行编码，神经网络的各个权值按一定的顺序级联为一个长串，串上的每一个位置对应着网络的一个权值。本文的每个权值的串长度取值为10神经网络定义为2个输入节点，5个隐节点，1个输出节点，2个阈值节点，所以总共有21个权值，所以染色体串的长度为10×21。2、评价函数f：将染色体上表示的各权值分配到给定的网络结构中，网络以训练集样本为输入输出，运行后返回染色体的评价函数。3、初始化过程：初始染色体集中，网络的各权值是以概率分布e-|γ|来随机确定的，这点有别于BP算法。在BP算法中，初始权值一般取-1.0～1.0之间均匀分布的随机数。遗传算法的这种随机分布的取法是通过以往的大量实验得出的，可以发现，当网络收敛后，权值的绝对值一般都较小，但也有一些权值是较大的。采用以上初始化方法的原因是使遗传算法能够搜索所有可行解的范围。4、遗传算子：对于不同的应用问题，遗传算子的形式多种多样，这里采用了权值交叉和权值变异算子.权值交叉算子：对于子代染色体中的每个权值输入位置，交叉算子从两个亲代染色体中随机选取若干个交叉位置，并将这一代染色体在交叉位置进行交叉运算，这样子代染色体便含有两个亲代的遗传基因。权值变异算子：对于子代染色体中的每个权值输入位置，变异算子以概率Pm在初始概率分布中随机选择一个值，然后与该输入位置上的权值相加。5、选择方式：这里不采用比例选择方式，而使用亲代度量S决定群体中每个个体被选中的概率[14]，群体中的个体以下式所示的概率成为亲代染色体。4.2.3参照以上的选择算子，对于网络训练的编程如下：#include"stdio.h"#include"stdlib.h"#include"time.h"#include"math.h"#include"process.h"#include"conio.h"/**********常量的定义************/#definepopsize40/*最大群体个数*/#definecmax1/*一个较大的数（用于适应度的确定）*//**********神经网络结构的定义************/#defineSIZE50/*训练样本数*/#defineIN2/*输入层节点数*/#defineHN5/*隐层节点数*/#defineOUT1/*输出层节点数*/#defineJD(IN+1)*HN+(HN+1)*OUT#defineW10/*用于检验的样本数*/doublew_h_i[HN][IN+1];/*输入层到隐层权值*/doublew_o_h[HN+1][OUT];/*隐层到输出层权值*/doubleo_o[SIZE][OUT];/*样本网络输出值*//**********用户数据定义************/#definelength10/*编码长度*/#definechromlength10*21/*染色体长度*/longDecodeNum[JD];doublepc=0.65;/*交叉概率（0.4-0.99）*/doublepm=0.008; /*变异概率（0.0001-0.1）*/doubleB=2.5;intpop=40;/*群体大小（20-100）*/intmaxgeneration=1000;/*最大遗传代数（100-500）*//**********全局变量定义************/intgeneration;/*当前遗传代数*/intbest_index;/*当代最佳染色体序号*/intworst_index;/*当代最差染色体序号*/structindividual/*个体结构定义*/{charchrom[chromlength+1];/*个体染色体编码*/doublevalue;/*个体目标值*/doublefitness;/*个体适应度*/};structindividualbestindividual;/*当代最佳个体*/structindividualworstindividual;/*当代最差个体*/structindividualcurrentbest;/*目前最佳个体*/structindividualpopulation[popsize];/*群体数组*//**********训练样本结构及处理系数************/doubleXS=10.0;/*样本处理系数*/structsamples{floatin_sign[IN];/*样本输入数组*/floattch_sign;/*样本输出值*/}samp[SIZE]={{1.40,1.80,3.70},{4.28,4.96,1.31},{1.18,4.29,3.35},{1.96,1.90,2.70},{1.38,2.55,3.14},{2.46,2.12,2.22},{2.66,4.42,1.56},{4.44,4.71,1.32},{3.11,1.06,4.08},{4.47,3.66,1.42},{1.35,1.76,3.91},{1.24,1.41,5.05},{1.85,1.43,3.52},{3.77,1.45,2.70},{4.84,4.32,1.33},{1.05,2.55,4.63},{4.51,1.37,2.80},{1.84,4.43,1.97},{1.67,2.81,2.47},{2.03,1.88,2.66},{3.62,1.95,2.08},{3.38,3.70,1.51},{2.83,3.70,1.51},{1.48,4.44,2.44},{3.37,2.13,1.99},{2.84,1.24,3.42},{1.19,1.53,4.99},{4.10,1.71,2.27},{1.65,1.38,3.94},{2.00,2.06,2.52},{2.71,4.13,1.58},{1.78,1.11,4.71},{3.63,2.27,1.87},{2.24,3.74,1.79},{1.81,3.18,2.20},{4.85,4.66,1.30},{3.41,3.88,1.48},{3.66,1.60,2.46},{3.64,2.14,1.95},{4.51,1.52,2.51},{2.81,1.35,1.97},{1.92,4.25,1.92},{4.61,2.68,1.63},{3.04,4.97,1.44},{4.82,3.80,1.39},{2.58,1.97,2.29},{4.14,4.76,1.33},{4.35,3.90,1.40},{2.22,1.35,3.39},{1.67,2.23,2.75}};/**********全局函数定义************/voidinitialpopulation(void);/*群体初始化*/voidnextpopulation(void);/*产生下代群体*/voidevaluatepopulation(void);/*群体评估*/longdecodechromosome(char*,int,int);/*解码*/voidobjectvalue(void);/*目标值计算*/voidfitnessvalue(void);/*适应度计算*/voidfindbestandworstindividual(void);/*寻找最佳和最差个体*/voidperformevolution(void);/*利用"最优保存策略"（ElitistModel)优化进化*/voidselectionoperator(void);/*选择算子*/voidcrossoveroperator(void);/*交叉算子*/voidmutationoperator(void);/*变异算子*/voidoutputtextreport(void);/*当代进化情况报告*/voidSampleChang(void);/*样本转化*/voidGetW(void);/*权值的获得*/voidNetOut(void);/*样本网络输出*/voidcheck(void);/*结果检验*/doublesigmoid(double);/*Sigmoid函数定义*//**********主函数************/main(){doublesum;inti;SampleChang();do{sum=0.0;generation=0;initialpopulation();evaluatepopulation();for(i=0;i<pop;i++)sum+=population[i].fitness;}while(sum==0.0);while(generation<maxgeneration){generation++;if(currentbest.fitness==0.98)B=3;nextpopulation();evaluatepopulation();if(currentbest.fitness>=0.92)break;performevolution();outputtextreport();}getch();check();getch();}/**********样本处理函数************/voidSampleChang(void){inti;for(i=0;i<SIZE;i++){samp[i].tch_sign/=XS;}}/**********权值的获得************/voidGetW(void){inti,j;ints=0;for(j=0;j<HN;j++){ for(i=0;i<=IN;i++) { w_h_i[j][i]=1.0*DecodeNum[s]/1023.0-0.5; s++; }for(i=0;i<OUT;i++) { w_o_h[j][i]=1.0*DecodeNum[s]/1023.0-0.5; s++;}}for(i=0;i<OUT;i++){ w_o_h[HN][i]=1.0*DecodeNum[s]/1023.0-0.5; s++;}}/**********网络输出计算************/voidNetOut(void){inti,j,l;doublenet;doubleo_h[SIZE][HN];for(i=0;i<SIZE;i++){for(j=0;j<HN;j++){net=0.0;for(l=0;l<IN;l++)net=net+samp[i].in_sign[l]*w_h_i[j][l];net=net+w_h_i[j][IN];o_h[i][j]=sigmoid(net);}for(j=0;j<OUT;j++){net=0.0;for(l=0;l<HN;l++)net=net+o_h[i][l]*w_o_h[l][j];net=net+w_o_h[HN][j];o_o[i][j]=sigmoid(net);}}}/**********变形的Sigmoid函数************/doublesigmoid(doublez){doublezout;zout=(exp(z)-exp(-z))/(exp(z)+exp(-z));/*zout=1.0/(1+exp(-z));*/return(zout);}/**********群体初始化函数************/voidinitialpopulation(void){inti,j;randomize();for(i=0;i<pop;i++){for(j=0;j<chromlength;j++)population[i].chrom[j]=(random(10)<5)?'0':'1';population[i].chrom[chromlength]='\0';}}/**********产生下一代群体************/voidnextpopulation(void){selectionoperator();crossoveroperator();mutationoperator();}/**********群体的评价************/voidevaluatepopulation(void){objectvalue();fitnessvalue();findbestandworstindividual();}/**********编码解码************/longdecodechromosome(char*string,intpoint,intleng){longdecimal=0L;char*pointer;inti;for(i=0,pointer=string+point;i<leng;i++,pointer++){decimal+=(*pointer-'0')<<(leng-1-i);}return(decimal);}/**********目标值计算************/voidobjectvalue(void){inti,h,j,s;doubleo=0.0;doubleout[SIZE];for(i=0;i<SIZE;i++)for(j=0;j<OUT;j++) o_o[i][j]=0;for(h=0;h<pop;h++){for(s=0;s<JD;s++) DecodeNum[s]=decodechromosome(population[h].chrom,length*s,length);GetW();NetOut();for(i=0;i<SIZE;i++){ for(j=0;j<OUT;j++) {out[i]=o_o[i][j]-samp[i].tch_sign;} /*o=o+out[i]*out[i]/2.0;*/ o+=fabs(out[i]);}population[h].value=o/SIZE;}}/**********适应度计算************/voidfitnessvalue(void){inti;doubletemp;for(i=0;i<pop;i++){if(population[i].value<cmax)temp=cmax-population[i].value;elsetemp=0.0;population[i].fitness=pow(temp,B);/*population[i].fitness=1-population[i].value