第二讲-计算智能-进化计算

计算智能是信息科学、生命科学、认知科学等不同学科相互交叉的产物。它主要借鉴仿生学的思想，基于人们对生物体智能机理的认识，采用数值计算的方法去模拟和实现人类的智能。计算智能主要研究领域包括：神经计算、进化计算、模糊计算、免疫计算、DNA计算、粗糙集等。2.1概述2.1.1什么是计算智能2.1.2计算智能的产生与发展2.1.3计算智能与人工智能的关系2.2进化计算第2讲计算智能之进化计算12.1.1什么是计算智能概念解释计算智能（ComputationalIntelligence，CI）目前还没有一个统一的的定义，使用较多的是美国科学家贝慈德克（J.C.Bezdek）从计算智能系统角度所给出的定义。从计算智能系统角度如果一个系统仅处理低层的数值数据，含有模式识别部件，没有使用人工智能意义上的知识，且具有计算适应性、计算容错力、接近人的计算速度和近似于人的误差率这4个特性，则它是计算智能的。从学科范畴看计算智能是在神经网络（NeuralNetworks,NN）、进化计算（EvolutionaryComputation,EC）及模糊系统（FuzzySystem,FS）这3个领域发展相对成熟的基础上形成的一个统一的学科概念。22.1.1什么是计算智能研究领域神经网络是一种对人类智能的结构模拟方法，它是通过对大量人工神经元的广泛并行互联，构造人工神经网络系统去模拟生物神经系统的智能机理的。进化计算是一种对人类智能的演化模拟方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。模糊计算是一种对人类智能的逻辑模拟方法，它是通过对人类处理模糊现象的认知能力的认识，用模糊逻辑去模拟人类的智能行为的。综合解释从贝慈德克的定义和上述学科范畴可以看出以下两点：第一，计算智能是借鉴仿生学的思想，基于生物神经系统的结构、进化和认知对自然智能进行模拟的。第二，计算智能是一种以模型（计算模型、数学模型）为基础，以分布、并行计算为特征的自然智能模拟方法。32.1.2计算智能的产生与发展1992年，贝慈德克在《ApproximateReasoning》学报上首次提出了“计算智能”的概念。1994年6月底到7月初，IEEE在美国佛罗里达州的奥兰多市召开了首届国际计算智能大会(简称WCCI’94)。会议第一次将神经网络、进化计算和模糊系统这三个领域合并在一起，形成了“计算智能”这个统一的学科范畴。在此之后，WCCI大会就成了IEEE的一个系列性学术会议，开始是4年举办一次，现在是每2年举办一次。1998年5月，在美国阿拉斯加州的安克雷奇市又召开了第2届计算智能国际会议WCCI’98。2002年5月，在美国夏威夷州首府火奴鲁鲁市又召开了第3届计算智能国际会议WCCI’02。WCCI’2014在北京召开。此外，IEEE还出版了一些与计算智能有关的刊物:IEEETrans.NeuralNetworks,IEEETrans.FuzzySystems,IEEETrans.EvolutionaryComputation。目前，计算智能已成为智能科学技术一个重要的研究领域。42.1.3计算智能与人工智能的关系目前，对计算智能与人工智能的关系有2种观点，一种认为计算智能是人工智能的一个子集，另一种认为计算智能和人工智能是不同的范畴。第一种观点的代表人物是贝慈德克。他把智能（Intelligence，I）和神经网络（NeuralNetwork，NN）都分为计算的（Computational，C）、人工的（Artificial，A）和生物的（Biological,B）3个层次，并以模式识别（PR）为例，给出了下图所示的智能的层次结构。在该图中，底层是计算智能（CI），它通过数值计算来实现，其基础是CNN；中间层是人工智能（AI），它通过人造的符号系统实现，其基础是ANN；顶层是生物智能（BI），它通过生物神经系统来实现，其基础是BNN。按照贝慈德克的观点，CNN是指按生物激励模型构造的NN，ANN是指CNN+知识，BNN是指人脑，即ANN包含了CNN，BNN又包含了ANN。对智能也一样，贝慈德克认为AI包含了CI，BI又包含了AI，即计算智能是人工智能的一个子集。5CNNCPRCIANNAPRAIBNNBPRBI人类知识(+)传感输入知识(+)传感数据计算(+)传感器B~生物的A~符号的C~数值的复杂性复杂性输入层次贝慈德克的智能的3个层次2.1.3计算智能与人工智能的关系6第二种观点是大多数学者所持有的观点，其代表人物是艾伯哈特（R.C.Eberhart）。他们认为：虽然人工智能与计算智能之间有重合，但计算智能是一个全新的学科领域，无论是生物智能还是机器智能，计算智能都是其最核心的部分，而人工智能则是外层。事实上，CI和传统的AI只是智能的两个不同层次，各自都有自身的优势和局限性，相互之间只应该互补，而不能取代。大量实践证明，只有把AI和CI很好地结合起来，才能更好地模拟人类智能，才是智能科学技术发展的正确方向。2.1.3计算智能与人工智能的关系72.1概述2.2进化计算2.2.1进化计算概述2.3.2遗传算法第2讲计算智能之进化计算8进化计算（EvolutionaryComputation,EC）是在达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。它主要包括遗传算法（GeneticAlgorithm，GA）进化策略（EvolutionaryStrategy,ES）进化规划（EvolutionaryProgramming,EP）遗传规划（GeneticProgramming,GP）四大分支。其中，第一个分支是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。因此我们主要讨论遗传算法。2.2进化计算9进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的繁殖（Reproduction）变异（Mutation）竞争（Competition）选择（Selection）引入到了算法中。2.2.1进化计算概述1.进化计算及其生物学基础(1/3)(1)什么是进化计算10(2)进化计算的生物学基础自然界生物进化过程是进化计算的生物学基础，它主要包括遗传(Heredity)、变异(Mutation)和进化(Evolution)理论。①遗传理论遗传是指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代），使子代能够继承其父代的特征或性状的这种生命现象。在自然界，构成生物基本结构与功能的单位是细胞（Cell）。细胞中含有一种包含着所有遗传信息的复杂而又微小的丝状化合物，人们称其为染色体（Chromosome）。在染色体中，遗传信息由基因（Gene）所组成，基因决定着生物的性状，是遗传的基本单位。染色体的形状是一种双螺旋结构，构成染色体的主要物质叫做脱氧核糖核酸(DNA)，每个基因都在DNA长链中占有一定的位置。一个细胞中的所有染色体所携带的遗传信息的全体称为一个基因组。2.2.1进化计算概述1.进化计算及其生物学基础(2/3)11②变异理论变异是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象。变异是一种随机、不可逆现象，是生物多样性的基础。引起变异的主要原因：杂交，是指有性生殖生物在繁殖下一代时两个同源染色体之间的交配重组。复制差错，是指在细胞复制过程中因DNA上某些基因结构的随机改变而产生出新的染色体。③进化论进化是指在生物延续生存过程中，逐渐适应其生存环境，使得其品质不断得到改良的这种生命现象。遗传和变异是生物进化的两种基本现象，优胜劣汰、适者生存是生物进化的基本规律。达尔文的自然选择学说：在生物进化中，一种基因有可能发生变异而产生出另一种新的基因。这种新基因将依据其与生存环境的适应性而决定其增殖能力。通常，适应性强的基因会不断增多，而适应性差的基因则会逐渐减少。通过这种自然选择，物种将逐渐向适应于生存环境的方向进化，甚至会演变成为另一个新的物种，而那些不适应于环境的物种将会逐渐被淘汰。2.2.1进化计算概述1.进化计算及其生物学基础(3/3)12进化计算自20世纪50年代以来，其发展过程大致可分为三个阶段。(1)萌芽阶段这一阶段是从20世纪50年代后期到70年代中期。20世纪50年代后期，一些生物学家在研究如何用计算机模拟生物遗传系统中，产生了遗传算法的基本思想，并于1962年由美国密执安（Michigan）大学霍兰德（Holland）提出。1965年德国数学家雷切伯格（Rechenberg）等人提出了一种只有单个个体参与进化，并且仅有变异这一种进化操作的进化策略。同年，美国学者弗格尔（Fogel）提出了一种具有多个个体和仅有变异一种进化操作的进化规划。1969年美国密执安（Michigan）大学的霍兰德（Holland）提出了系统本身和外部环境相互协调的遗传算法。至此，进化计算的三大分支基本形成。(2)成长阶段这一阶段是从20世纪70年代中期到80年代后期。1975年，霍兰德出版专著《自然和人工系统的适应性（AdaptationinNaturalandArtificialSystem）》，全面介绍了遗传算法。同年，德国学者施韦费尔（Schwefel）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组这两种进化操作的进化策略。1989年，霍兰德的学生戈尔德伯格（Goldberg）博士出版专著《遗传算法----搜索、优化及机器学习（GeneticAlgorithm----inSearchOptimizationandMachineLearning）》，使遗传算法得到了普及与推广。2.2.1进化计算概述2.进化计算的产生与发展(1/2)13(3)发展阶段这一阶段是从20世纪90年代至今。1989年，美国斯坦福（Stanford）大学的科扎（Koza）提出了遗传规划的新概念，并于1992年出版了专著《遗传规划----应用自然选择法则的计算机程序设计（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》该书全面介绍了遗传规划的基本原理及应用实例，标志着遗传规划作为计算智能的一个分支已基本形成。进入20世纪90年代以来，进化计算得到了众多研究机构和学者的高度重视，新的研究成果不断出现、应用领域不断扩大。2.2.1进化计算概述2.进化计算的产生与发展(2/2)14进化计算尽管有多个重要分支，但它们却有着共同的进化框架。若假设P为种群(Population，或称为群体)，t为进化代数，P(t)为第t代种群,则进化计算的基本结构可粗略描述如下：{确定编码形式并生成搜索空间；初始化各个进化参数，并设置进化代数t=0；初始化种群P(0);对初始种群进行评价（即适应度计算）；while（不满足终止条件）do{t=t+1;利用选择操作从P(t-1)代中选出P(t)代群体；对P(t)代种群执行进化操作；对执行完进化操作后的种群进行评价（即适应度计算）；}}可以看出，上述基本结构包含了生物进化中所必需的选择操作、进化操作和适应度评价等过程。2.2.1进化计算概述3.进化计算的基本结构15遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法所涉及到的基本概念主要有以下几个：种群（Population）：种群是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。个体（Individual）：个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。染色体（Chromos）：染色体是指对个体进行编码后所得到的编码串。其中的每1位称为基因，若干个基因构成的一个有