第5章 计算智能的知识

第5章计算智能(2)进化进化计算进化计算（EvolutionaryComputation,EC）是在达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。进化计算包括：遗传算法(geneticalgorithms，GA)进化策略(evolutionstrategies)进化编程(evolutionaryrogramming)遗传编程(geneticprogramming)人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。人工生命是人工智能和计算智能的一个新的研究热点。2进化计算及其生物学基础什么是进化计算进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的繁殖（Reproduction）,变异（Mutation）,竞争（Competition）,选择（Selection）等引入到了算法中。自然界的生物进化过程是进化计算的生物学基础，它主要包括遗传（Heredity）、变异（Mutation）和进化（Evolution）理论。3进化计算及其生物学基础遗传理论指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代），使子代能够继承其父代的特征或性状的这种生命现象自然界，构成生物基本结构与功能的单位是细胞（Cell）。细胞中含有一种包含着所有遗传信息的复杂而又微小的丝状化合物，人们称其为染色体（Chromosome）。在染色体中，遗传信息由基因（Gene）所组成，基因决定着生物的性状，是遗传的基本单位。染色体的形状是一种双螺旋结构，构成染色体的主要物质叫做脱氧核糖核酸（DeoxyribonucleicAcid，DNA），每个基因都在DNA长链中占有一定的位置。一个细胞中的所有染色体所携带的遗传信息的全体称为一个基因组（Genome）。细胞在分裂过程中，其遗传物质DNA通过复制转移到新生细胞中，从而实现了生物的遗传功能。4进化计算及其生物学基础变异理论是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象是生物进化过程中发生的一种随机现象是一种不可逆过程变异在生物多样性方面具有不可替代的作用，其选择和积累是生物多样性的根源。引起变异的主要原因有两种杂交--指有性生殖生物在繁殖下一代时两个同源染色体之间的交配重组，即两个染色体在某一相同处的DNA被切断后再进行交配重组，形成两个新的染色体复制差错--指在细胞复制过程中因DNA上某些基因结构的随机改变而产生出新的染色体5进化计算及其生物学基础进化论进化是指在生物延续生存过程中，逐渐适应其生存环境，使得其品质不断得到改良的这种生命现象。两种基本现象遗传变异生物进化的基本规律优胜劣汰、适者生存达尔文的自然选择（NeturalSelection）学说在生物进化中，一种基因有可能发生变异而产生出另一种新的生物基因。这种新基因将依据其与生存环境的适应性而决定其增殖能力。一般情况下，适应性强的基因会不断增多，而适应性差的基因则会逐渐减少。通过这种自然选择，物种将逐渐向适应于生存环境的方向进化，甚至会演变成为另一个新的物种，而那些不适应于环境的物种将会逐渐被淘汰。6进化计算的产生与发展进化计算自20世纪50年代以来，其发展过程大致可三个阶段萌芽阶段（20世纪50年代后期到70年代中期）20世纪50年代后期，一些生物学家在研究如何用计算机模拟生物遗传系统中，产生了遗传算法的基本思想，并于1962年由美国密执安（Michigan）大学霍兰德（Holland）教授提出。1965年德国数学家雷切伯格（Rechenberg）等人提出了一种只有单个个体参与进化。并且仅有变异这一种进化操作的进化策略。同年，美国学者弗格尔（Fogel）提出了一种具有多个个体和仅有变异一种进化操作的进化规划。1969年美国密执安（Michigan）大学的霍兰德（Holland）教授提出了系统本身和外部环境相互协调的遗传算法。至此，进化计算的三大分支基本形成。7进化计算的产生与发展成长阶段（20世纪70年代中期到80年代后期）1975年，霍兰德教授出版专著《自然和人工系统的适应性（AdaptationinNaturalandArtificialSystem）》，全面介绍了遗传算法。同年，德国学者施韦费尔（Schwefel）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组（Recombination）这两种进化操作的更加完善的进化策略。1989年，霍兰德教授的学生戈尔德伯格（Goldberg）博士出版专著《遗传算法----搜索、优化及机器学习（GeneticAlgorithm----inSearchOptimizationandMachineLearning）》，使遗传算法得到了普及与推广。8进化计算的产生与发展发展阶段（20世纪90年代至今）1989年，美国斯坦福（Stanford）大学的科扎（Koza）提出了遗传规划的新概念，并于1992年出版了专著《遗传规划----应用自然选择法则的计算机程序设计（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》该书全面介绍了遗传规划的基本原理及应用实例，标志着遗传规划作为计算智能的一个分支已基本形成。进入20世纪90年代以来，进化计算得到了众多研究机构和学者的高度重视，新的研究成果不断出现、应用领域不断扩大。目前，进化计算已成为人工智能领域的又一个新的研究热点。9进化计算的基本结构进化计算有多个重要分支不同分支的编码方案、选择策略和进化操作也有可能不同但有着共同的进化框架若假设P为种群(Population，或称为群体)，t为进化代数，P(t)为第t代种群,则进化计算的基本结构可粗略描述如下：{确定编码形式并生成搜索空间；初始化各个进化参数，并设置进化代数t=0；初始化种群P(0);对初始种群进行评价（即适应度计算）；while（不满足终止条件）do{t=t+1;

利用选择操作从P(t-1)代中选出P(t)代群体；对P(t)代种群执行进化操作；对执行完进化操作后的种群进行评价（即适应度计算）；}} 可以看出，上述基本结构包含了生物进化中所必需的选择操作、进化操作和适应度评价等过程。105.1遗传算法遗传算法于1962年被提出1989年形成其基本框架遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。

115.1遗传算法遗传算法中的基本概念种群（Population）指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。个体（Individual）指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。例如，可以用0、1组成的长度为l的串来表示个体。染色体（Chromos）指对个体进行编码后所得到的编码串。染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。125.1遗传算法遗传算法中的基本概念适应度（Fitness）函数适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的主要依据遗传操作（GeneticOperator）遗传操作是指作用于种群而产生新的种群的操作选择（Selection）交叉（Crosssover）变异（Mutation）135.1.1遗传算法的基本机理霍兰德的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。

编码与解码适应度函数

遗传操作145.1.2遗传算法的求解步骤遗传算法的特点

遗传算法是对参数集合的编码而非针对参数本身进行进化；遗传算法是从问题解的编码组开始而非从单个解开始搜索；遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。15基本思想 按预定的目标函数对每个染色体进行评价，计算其适应度，剔除适应度低的，留下适应度高的步骤(1)初始化群体;(2)计算群体上每个个体的适应度值;(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;(4)按概率Pc进行交叉操作;(5)按概率Pm进行突变操作;(6)若没有满足某种停止条件，则转第(2)步，否则进入下一步。(7)输出群体中适应度值最优的染色体作为问题的满意解或最优解。5.1.2遗传算法的求解步骤16问题的候选解编码为染色体种群P(t)计算各染色体的适应度通过遗传算法存优去劣种群P(t+1)种群满足指标种群P(t+1)→种群P(t)解码染色体问题解答空间NY选择交叉变异17遗传编码常用编码霍兰德二进制码格雷码（GrayCode）实数编码字符编码18遗传编码二进制码（Binaryencoding）二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度l，该长度与变量的定义域和所求问题的计算精度有关。

262144=218<500000<219=524288这样，对应于区间[5，10]内满足精度要求的每个值x，都可用一个19位编码的二进制串<b18,b17,…,b0>来表示。例：假设变量x的定义域为[5，10]，要求的计算精度为10-5，则需要将[5，10]至少分为500000个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于1951019遗传编码二进制码解码AB 设参数取值范围[A,B]，用长度为l的二进制串来表示，将[A,B]等分成2l－1份，每等份的长度为 δ＝(B-A)/(2l－1)

则0000000…0000000=0 →A

0000000…0000001=1 →A＋δ

… 1111111…1111111=1 →B

设个体编码为X:xlxl-1xl-2…x2x1，则对应的十进制数为：20遗传编码二进制码优点编码、解码操作简单易行交叉、变异等遗传操作便于实现符合最小字符集编码原则便于利用模式定理对算法进行理论分析缺点Hamming悬崖，如，7和8的二进制数分别为0111和1000，当算法从7改进到8时，就必须改变所有的位连续函数离散化时的映射误差维数灾，精度要求越高，所需维数越大对于一些连续函数的优化问题，由于其随机性使得其局部搜索能力较差当解迫近于最优解后，由于其变异后表现型变化很大，不连续，所以会远离最优解，达不到稳定21遗传编码格雷编码（Grayencoding）对二进制编码进行变换后所得到的编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的格雷编码有效地解决了二进制编码存在的海明悬崖问题

设有二进制串b1,b2,…,bn，对应的格雷串为a1,a2,…,an，则从二进制编码到格雷编码的变换为：其中，⊕表示模2加法。而从一个格雷串到二进制串的变换为：例：

十进制数7和8的二进制编码分别为0111和1000，而其格雷编码分别为0100和1100。22遗传编码格雷编码优点便于提高遗传算法的局部搜索能力交叉、变异等遗传操作便于实现符合最小字符集编码原则便于利用模式定理对算法进行理论分析缺点是二进制码的变形，精度和二进制码一样连续函数离散化时的映射误差

维数灾23遗传编码实数编码（Realencoding）将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。适应于那种多维、高精度要求的连续函数优化问题24遗传编码实数编码适用于在遗传算法中表示范围较大的数适用于精度要求较高的遗传算法便于较大空间的遗传搜索改善了遗传算法的计算复杂性，提高了运算速度便于遗传算法与经典优化方法的混合使用便于设计针对问题的专门知识的知识型遗传算子便于处理复杂的决策变量约束条件变异需要另行定义25遗传编码符号编码法指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集如｛A,B,C…｝。优点符合有意义积术块编码原则便于在遗传算法中利用所求解问题的专门知识便于遗传算法与相关近似算法之间的混合使用。但对于使用符号编码方法的遗传算法，一般需要认真设计交叉、变异等遗传运算的操作方法，以满足问题的各种约束要求，这样才能提高算法的搜索性能例：TSP问题采用符号编码，按一条回路中城市的次序进行编码

26适应度函数用于对个体的适应性进行度量的函数个体的适应度值越大，它被遗传到下一代种群中的概率也就越大常用的适应度函数原始适应度函数直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函数。例如，在求解极值问题

max

f(x) x∈[a,b]

f(x)即为x的原始适应度函数。优点：能够直接反映出待求解问题的最初求解目标缺点：有可能出现适应度值为负的情况。27适应度函数常用的适应度函数标准适应度函数一般要求适应度函数非负并其适应度值越大越好需要对原始适应函数进行变换，将其转换为标准的度量方式，以满足进化操作的要求例：极小化问题例：极大化问题28适应度函数适应度函数的加速变换在某些情况下，适应度函数在极值附近的变化可能会非常小，以至于不同个体的适应值非常接近，使得难以区分出哪个染色体更占优势。对此，最好能定义新的适应度函数，使该适应度函数既与问题的目标函数具有相同的变化趋势，又有更快的变化速度。适应度函数的加速变换有两种基本方法线性加速

f‘(x)=αf(x)+β 其中，f(x)是加速转换前的适应度函数；f‘(x)是加速转换后的适应度函数；α和β是转换系数。非线性加速幂函数变换方法 f’(x)=f(x)k

指数变换方法 f’(x)=exp(-βf(x))29基本遗传操作选择（Selection）根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。常用的选择策略可分为比例选择、排序选择和竞技选择三种类型比例选择方法（ProportionalModel）的基本思想是：各个个体被选中的概率与其适应度大小成正比。常用的比例选择策略包括轮盘赌选择繁殖池选择30基本遗传操作选择轮盘赌选择（适应度比例法、轮转法）基本思想是：个体被选中的概率取决于该个体的相对适应度圆周——染色体适应度总和Pt=f(xt)/∑f(xi)Pt：选择概率xi

：第i个染色体对应的编码f(xi)：第i个染色体的适应度31基本遗传操作选择轮盘赌选择算法计算f(xi)

求和：SUM=∑f(xi)

，记录每个染色体的中间累加值S-mid产生随机数N，0<N<SUM选择S-mid≥N的第一个染色体进入交换集重复3)、4)，直到交换集中包含足够多的染色体32基本遗传操作交叉操作（Crossover）指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型。二进制交叉（BinaryValuedCrossover）指二进制编码情况下所采用的交叉操作，它主要包括单点交叉、两点交叉、多点交叉和均匀交叉等方法。33基本遗传操作二进制交叉单点交叉（简单交叉，One-pointCrossover）先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体假设两个父代的个体串分别是：

X=x1x2…xkxk+1…xnY=y1y2…ykyk+1…yn

随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将X中的xk+1到xn部分与Y中的yk+1到yn部分进行交叉，交叉后生成的两个新的个体是：

X’=x1x2…xkyk+1…yn

Y’=y1y2…ykxk+1…xn

例：设有两个父代的个体串A=001101和B=110010，若随机交叉点为4，则交叉后生成的两个新的个体是：A’=001110

B’=110001

34基本遗传操作二进制交叉两点交叉（Two-pointCrossover） 指先在两个父代个体的编码串中随机设定两个交叉点，然后再按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。假设两个父代的个体串分别是：

X=x1x2…xi…xj…xnY=y1y2…yi…yj…,yn

随机设定第i、j位为两个交叉点（其中i<j<n），两点交叉是将X中的xi+1到xj部分与Y中的yi+1到yj部分进行交换，交叉后生成的两个新的个体是：

X’=x1x2…xiyi+1…yjxj+1…xn

Y’=y1y2…yixi+1…xjyj+1

…yn

例：设有两个父代的个体串A=001101和B=110010，若随机交叉点为3和5，则交叉后的两个新的个体是：A’=001011B’=11010135基本遗传操作二进制交叉多点交叉（Multiple-pointCrossover）均匀交叉（UniformCrossover）实值交叉（RealValuedCrossover）实数编码情况下所采用的交叉操作包括离散交叉和算术交叉部分离散交叉是先在两个父代个体的编码向量中随机选择一部分分量，然后对这部分分量进行交换，生成子代中的两个新的个体。整体离散交叉则是对两个父代个体的编码向量中的所有分量，都以1/2的概率进行交换，从而生成子代中的两个新的个体。部分离散交叉例： 设有两个父代的个体向量A=201619321826和B=362538122130，若随机选择对第3个分量以后的所有分量进行交叉，则交叉后的两个新的个体向量是：A’=201619122130B’=36253832182636基本遗传操作变异（Mutation）指对选中个体的染色体中的某些基因进行变动，以形成新的个体变异也是生物遗传和自然进化中的一种基本现象，它可增强种群的多样性遗传算法中的变异操作增加了算法的局部随机搜索能力，从而可以维持种群的多样性根据个体编码方式的不同，变异操作可分为二进制变异和实值变异两种类型37基本遗传操作变异二进制变异 随机地产生一个变异位，然后将该变异位置上的基因值由“0”变为“1”，或由“1”变为“0”，产生一个新的个体。例：设变异前的个体为 A=001101 若随机产生的变异位置是2，则该个体的第2位由“0”变为“1”。变异后的新的个体： A’=01110138基本遗传操作变异实值变异 用另外一个在规定范围内的随机实数去替换原变异位置上的基因值，产生一个新的个体基于位置的变异方法 先随机地产生两个变异位置，然后将第二个变异位置上的基因移动到第一个变异位置的前面。 例：设选中的个体向量 C=201619122130 随机产生的两个变异位置分别时2和4，则变异后的新的个体向量是：C’=201216192130基于次序的变异先随机地产生两个变异位置，然后交换这两个变异位置上的基因例：设选中的个体向量 D=201216192130若随机产生的两个变异位置分别时2和4，则变异后的新的个体向量是： D’=20191612213039基本遗传操作变异连续域的变异

xi(t+1)=xi(t)+RAND

其中RAND为服从某概率分布函数的随机量高斯分布与柯西分布40基本遗传操作变异连续域的变异高斯分布与柯西分布的采样点41遗传算法求解举例例1：用遗传算法求解下列函数的最大值

f(x)=log(1+x*x)最大值,其中x取[0,15]中整数.其最大值=5.42.参数设置二进制编码种群大小为4染色体长为4位42运行结果EC.1遗传算法运行80代的结果43函数曲线和种群示意图EC.1遗传算法44结果分析种群中的染色体有沿着曲线向上走的现象；有时能够达到最大值5.42,但也经常不能达到；有时图像上没有四个染色体，甚至只能看到一个染色体，这时是染色体重合；45可以发现SGA具有求解最值问题的能力SGA不能保证全局收敛性SGA中染色体经常出现重合或非常相近的现象46遗传算法的收敛性一些研究人员对进化算法的运行机理进行过研究，雷多夫（Radolph）证明了一般遗传算法不一定收敛，只有每代保存了最优个体时才收敛。在实际应用中，使用了上述结论来保证收敛性。采用优秀个体保护法就是将每一代中的最优个体，直接进入子代，相应淘汰其子代中适应度最差的个体，使种群规模不变。当遗传算法收敛时，求到的解一般只是所要解决问题的最优解的一个近似解，或者叫满意解。47例遗传算法求最大值z=f(x,y)=1*x*sin(4*pi*x)-1*y*sin(4*pi*y+pi)+1定义域:-1<x<1-1<y<148运行参数种群规模=100交叉率=0.5变异率=0.01每个变量的编码长度=44运行代数=25采用优秀个体保护法49控制参数并不是所有被选择了的染色体都要进行交叉操作和变异操作，而是以一定的概率进行，一般在程序设计中交叉发生的概率要比变异发生的概率选取得大若干个数量级，交叉概率取0.6至0.95之间的值；变异概率取0.001至0.01之间的值。种群的染色体总数叫种群规模，它对算法的效率有明显的影响，规模太小不利于进化，而规模太大将导致程序运行时间长。对不同的问题可能有各自适合的种群规模，通常种群规模为30至100。50算法参数群体规模最大代数复制概率交叉概率变异概率515.2进化策略进化策略(EvolutionStrategies，ES)是一类模仿自然进化原理以求解参数优化问题的算法。它是由雷切伯格（Rechenberg）、施韦费尔（Schwefel）和彼得·比纳特（PeterBienert）于1964年提出的，并在德国共同建立的。52中南大学智能系统与智能软件研究所535.2.1进化策略的算法模型寻求与函数极值关联的实n维矢量x。随机选择父矢量的初始群体。父矢量xi,i=1,…,p产生子代矢量xi。对误差(i=1,…,p)排序以选择和决定保持哪些矢量。继续产生新的试验数据以及选择最小误差矢量。5.2进化策略53中南大学智能系统与智能软件研究所545.2.2进化策略和遗传算法的区别进化策略和遗传算法有着很强的相似性，它们都是一类模仿自然进化原理的算法。两者也存在着区别，其中最基本的区别是它们的研究领域不同。进化策略是一种数值优化的方法，它采用一个具有自适应步长和倾角的特定爬山方法。遗传算法从广义上说是一种自适应搜索技术。5.2进化策略54中南大学智能系统与智能软件研究所555.3进化编程进化编程(EvolutionaryProgramming，EP)，又称为进化规划（EvolutionaryPlanning），是由福格尔（Fogel）在1962年提出的一种模仿人类智能的方法。进化编程根据正确预测的符号数来度量适应值。通过变异，为父代群体中的每个机器状态产生一个子代。父代和子代中最好的部分被选择生存下来。它的提出是受自然生物进化机制的启发。55中南大学智能系统与智能软件研究所565.3.1进化编程的机理与表示进化编程的过程，可理解为从所有可能的计算机程序形成的空间中，搜索具有高的适应度的计算机程序个体。进化编程设计强调群体行为的变化。进化编程系统的表示自然地面向任务级。一旦选定一种适应性表示，就可以定义依赖于该表示的变异操作，在具体的父辈行为上创建后代。

5.3进化编程56中南大学智能系统与智能软件研究所575.3.2进化编程的步骤进化编程分为三个步骤：产生出初始群体。迭代完成下述子步骤，直至满足选种标准为止：执行群体中的每个程序。应用变异等操作创造新程序群体。在后代中适应值最高的计算机程序个体被指定为进化编程的结果。5.3进化编程57中南大学智能系统与智能软件研究所58变异和创造子代评估已存在的FSM用最好的状态机预测和添加符号选择父代初始化观测顺序是否是否预测初始化群体图5.6进化编程的基本过程5.3进化编程58中南大学智能系统与智能软件研究所595.4人工生命

自然界是生命之源。自然生命千千万万，千姿百态，千差万别，巧夺天工，奇妙无穷。人工生命（ArtificialLife，AL）试图通过人工方法建造具有自然生命特征的人造系统。人工生命是生命科学、信息科学和系统科学等学科交叉研究的产物，其研究成果必将促进人工智能的发展。

59中南大学智能系统与智能软件研究所605.4.1人工生命研究的起源和发展

人类长期以来一直力图用科学技术方法模拟自然界，包括人脑本身。1943年麦卡络奇和皮茨提出了M－P神经学网络模型。人工生命的许多早期研究工作也源于人工智能。

20世纪70年代以来，康拉德（Conrad）等提出不断完善的“人工世界”模型。

80年代90年代5.4人工生命60中南大学智能系统与智能软件研究所615.4.2人工生命的定义和研究意义人工生命是一项抽象地提取控制生物现象的基本动态原理，并且通过物理媒介（