《进化计算的进展和应用》由会员分享，可在线阅读，更多相关《进化计算的进展和应用（15页珍藏版）》请在金锄头文库上搜索。
1、 1.进化计算相关概念21.1 进化计算21.2 进化计算应用32 进化计算内涵42.1 进化计算的研究现状42.2 进化算法52.2.1 遗传算法52.2.2遗传编程52.2.3 进化策略和进化规划62.2.4 进化策略62.2.5 进化规划62.2.6 进化策略与进化规划的关系62.2.7进化策略与进化规划的差别72.2.8学习分类系统72.3 群智能72.3.1蚁群优化82.3.2 粒子群优化82.3.3蜂群算法92.4 自组织理论102.4.1 竞争神经网络102.4.2自组织映射102.4.3神经气体102.4.4增长型神经气体112.5人工免疫系统112.6其他算法112.6.1差
2、分进化112.6.2文化算法122.6.3和谐搜索算法122.7 人工生命123 进化计算在智能控制中的应用12参考文献15综述题进化计算的进展和应用1.进化计算相关概念1.1 进化计算人的智能归根结蒂是从生物进化中得到的,反映在遗传基因中,脑的结构变化也是通过基因的变化一代一代遗传下来,每一种基因产生的生物个体(看成一种结构)对环境有一定的适应性,或叫适合度(Fitness),杂交和基因突变可能产生对环境适应性强的后代,通过优胜劣汰的自然选择,适合度高的结构被保存下来。因此，从进化的观点来看,结构是适合度的结果。在这种观点启发下,60年代Fogol等提出了进化程序(EvolutionalPr
3、ogramming)思想,70年代Hoxzand提出了遗传算法(oenetselgorithm,简称eA)。如同神经网络研究一样,经过20年的沉寂,到80年代后期,由于在经济预测等应用领域获得成功,进化计算成为十分热门的研究课题。进化计算实质上是自适应的机器学习方法,它的核心思想是利用进化历史中获得的信息指导搜索或计算。常用的进化计算包括遗传算法、遗传程序(Geneticprogram-ming)、进化程序、爬山法(即局部搜索)、人工神经网络、决策树的归纳以及模拟退火等等。这些不同的方法具有以下几项共同的要素:自适应结构、随机产生的或指定的初始结构、适合度的评测函数或判据、修改结构的操作、每一
4、步中系统的状态即存储器、终止计算的条件、指示结果的方法、控制过程的参数。上述几种进化计算方法中,只有遗传算法与遗传程序是一组结构同时进化,其它方法是一个结构的进化。所谓遗传程序与通常的遗传算法的主要区别在于采用的“结构”(即问题的表示)不同。最初的遗传算法的自适应结构为定长的二进制字符串;而遗传程序的结构是分层的树,表示LlsP语言中的s表达式,即一个解决指定定理的程序。遗传程序的目标是自动生成程序。不同进化计算方法采用不同的结构,实质是不同的问题表示。一个问题的复杂性决定于它的问题表示,因为一种表示限制了系统观察世界的窗口。因此进化计算应从问题表示入手,即选择表示能力强又操作方便的结构。与通
5、常的遗传算法的主要区别在于采用的“结构”(即问题的表示)不同。最初的遗传算法的自适应结构为定长的二进制字符串;而遗传程序的结构是分层的树,表示LlsP语言中的s表达式,即一个解决指定定理的程序。遗传程序的目标是自动生成程序。不同进化计算方法采用不同的结构,实质是不同的问题表示。一个问题的复杂性决定于它的问题表示,因为一种表示限制了系统观察世界的窗口。因此进化计算应从问题表示入手,即选择表示能力强又操作方便的结构。众所周知,任何一种传统的科学或工程方法都具有正确性、一致性、可验证性、确定性、次序性及简洁性等特点。进化计算是模拟自然界的进化过程,自然界是靠适应性而不是靠简洁性解决问题,常常采用间接
6、的复杂的方法。与自然进化类似,进化计算一般不提供简洁的求解方法。在进化计算中,随机选择是关键的因素,因此往往具有不确定性,甚至同时支持用不一致的相互予盾的途径去求解。进化计算一般不采用严格同步控制。与传统算法最大的不同是计算不是自动终止,往往是人为限制进化多少代结束,或通过控制进化结果的一致性程度设定终止条件。在进化过程中即使达到了最优解或要求的目标,程序本身并不知道(除非设置一个全局监视器)。许多从事神经网络求解优化问题和进化计算的学者都深有体会,常常无法判断自己得到的结果好坏如何。进化计算的这些新特点给我们带来许多新的研究课题。1.2 进化计算应用在计算机科学中,进化计算是人工智能的一个分
7、支。它采用迭代的方法,使得解朝着最优解的方向前进。一般这种处理步骤均与进化的机制密切相关,因此统称为“进化计算”。 进化计算的主要优点是简单、通用、鲁棒性强和适于并行处理。目前进化计算已广泛用于最优控制、符号回归、自动生成程序、发现博奕策略、符号和积分微分及许多实际问题求解。它比盲目的搜索效率高得多,又比专门的针对特定问题的算法通用性强,它是一种与问题无关的求解模式。当然,若配合与领域有关的知识,求解效率会明显提高。总之,进化计算不论从理论上还是实际应用上都为我们提供了一个新的研究领域。2 进化计算内涵2.1 进化计算的研究现状进化计算的研究与应用，无论是研究队伍的规模，发表的论文数量还是网上
8、的信息资源，发展速度都很快，已经得到了国际学术界的广泛认可。1994 年，IEEE 神经网络委员会主持召开了第一届进化计算国际会议，并成立了 IEEE 进化计算委员会，此会每 3 年与 IEEE 神经网络国际会议、IEEE 模糊系统国际会议在同一地点先后连续举行，共同称为IEEE计算智能CI国际会议， 并分别出版并列的IEEE Transactions on Evolutionary Computation, IEEE Transactions on Neural Networks 和 IEEE Transactions on Fuzzy Sets学术期刊。另外，进化计算的国际期刊Evolut
9、ionary Computation也于1993年诞生。以遗传算法为主的进化计算的研究内容也在其他学术期刊中出版了专辑， 同时在Machine Learning; IEEE Transactions on Systems, Man and Cybernetics; Complex Systems; Artificial Intelligence 等重要国际期刊上经常见到。由此可见进化计算的发展之快。进化计算如图1.1所示粗略分为五个子类:进化算法、群智能、自组织网络、人工免疫系统。目前国内介绍进化计算的专著颇多,但多停留在对遗传算法系列的阐述上。另外,由于进化计算内各学科处于蓬勃发展中,不断有
10、新的算法、新的技术涌现，下面将综合最新的学科发展并按照图一所示,给出“进化计算”的研究现状。进化计算进化算法群智能自组织理论人工免疫系统其他遗传算法进化规划进化策略进化编程学习分类系统蚁群算法蜂群算法粒子群优化细菌群优化竞争神经网络自组织映射神经气体增长型神经气体负向选择算法克隆选择算法免疫网络算法树状细胞算法差分进化人工生命文化算法和谐搜索图1.1 进化计算内涵框架2.2 进化算法2.2.1 遗传算法标准遗传算法可视作一个达尔文进化系统。尽管简单,但对非线性、随机、暂态、混沌的问题均表现优异。而传统的优化技术如梯度法、爬山法和纯随机搜索法,则对此表现不佳。首先初始化群体。除了一般的随机产生之
11、外,还有两种方法:获得近似解；用户指定解。然后,计算每个个体的适应度。2.2.2遗传编程遗传编程(GP)定义为基于进化算法来寻找能够执行用户定义任务的一段计算机程序。它可视作遗传算法的特殊形式,即每个个体为一小段计算机程序,不断优化直到寻找到最优的计算机程序。自1992年Koza创立以来,短短数年间,已取得巨大成果。遗传编程的个体表示法可根据基本结构分为3种:树形、线性的、图形的,这与传统的基因表示有巨大区别，其中最常见的是树形结构。2.2.3 进化策略和进化规划德国学者Schwefel和Rechenburg美国学者Fogel分别提出进化策略ES和进化规划EP。这三种方法具有共同的本质，分别强
12、调了自然进化中的不同方面：遗传算法强调染色体的操作，进化策略强调了个体级的行为变化。而进化规划则强调种群级上的行为变化。现在学术界把遗传算法GA、进化策略ES和进化规划EP通称为进化算法EC。2.2.4 进化策略进化策略对极值优化问题的求解有一定的优势。他的主要执行步骤为：编码：对要求解的问题以数字串的方式进行编码（由目标参数和策略参数组成），计算适合度值；判断是否满足终止条件。如满足则输出结果；否则执行下述步骤：选择n个父代参与繁殖；按给定的方式执行交叉操作（可选）；按基于高斯分布的扰动执行变异操作；产生m个子代，并计算适合度值（mn）；返回。2.2.5 进化规划进化规划，同进化策略类似，适
13、用于解决目标函数或约束条件不可微的复杂的非线性实值连续优化问题。进化规划与进化策略在原理上相似，但在具体实现方面有差别。其中最为显著的区别是进化规划中不采用交叉算子，仅通过变异操作来维持两代之间的联系。其基本步骤为：编码：对要求解的问题以数字串的方式进行编码（由目标参数和策略参数组成），计算适合度值；判断是否满足终止条件。如满足则输出结果；否则执行下述步骤；选择n个父代参与繁殖；按基于高斯分布的扰动执行变异操作；产生n个子代，并计算适合度值；返回。2.2.6 进化策略与进化规划的关系单从进化策略与进化规划的解题步骤就能看出，它们有很多的相似之处。进化策略与进化规划在编码方面，不像传统遗传算法那
14、样需要对要求解的问题进行0-1编码和解码，而是直接对所要求解的问题进行编码，即直接将优化问题的解表示为数字串的形式，不需要特定的编码和译码。 2.2.7进化策略与进化规划的差别 实际应用时，进化策略与进化规划的差别主要体现在以下几个方面：进化策略中的交叉算子是可选的；如需要进行交叉运算时，采用类似遗传算法的处理方法，如离散交叉或中值交叉方式。进化规划本身就没有交叉算子，这也是该两种方法最本质的区别；在父代选择方面：进化策略采用概率选择的方式形成父代，通常根据均与随机分布的方式抽取父代个体，这样每一个父代个体都能以同样的概率被选中。进化规划则采用确定性的方式，即当前种群中的每一个父代都要经过变异
15、来产生子代；在具体变异表达式方面，进化策略与进化规划也存在差别。2.2.8学习分类系统学习分类系统(LCS)是一种机器学习系统,与增强学习(RL)和GA密切相关。LCS通过与环境的相互作用,从环境获得奖励,学习的目的在于如何将奖励最大化。一个基本的LCS模型包括4个重要组件,分别是：规则群、运行组件、增强组件、发现组件。LCS运行时,环境首先给系统发送一个当前状态s的信号。其次,工作组件接收到这个信号后,从分类器集中选择前提是s的分类器,据此建立一个匹配分类器集。接着,系统根据每个分类器的行动建议,根据某个准则进行评价。然后,系统选定某个最优的分类器,设其给出行动建议a,将行动a发送回环境。外界环境根据当前状态s,与系统返回的行动a,根据某个现实准则计算出奖励r,发送给增强组件。增强组件将r分配给做出贡献的分类器。发现组件的作用在于随机选择两个分类器,采用交叉、变异算法产生两个新分类器。新分类器插入群体后,必须将两个旧的分类器丢弃,以维护群体大小固定。2.3 群智能1989年Gerardo Beni在研究分子机器人系统时提出群智能(Swarm Intelligence, SI)的概念,即一种基于分散自组织系统的集体行为。2.3.1蚁群优化蚁群优化算法是一种模仿蚁群觅食行为的概率搜索
