第五章计算智能

第5章计算智能(2):进化计算人工生命2进化计算包括：–遗传算法(geneticalgorithms，GA)–进化策略(evolutionstrategies)–进化编程(evolutionaryrogramming)–遗传编程(geneticprogramming)人类不满足于模仿生物进化行为，希望能够建立具有自然生命特征的人造生命和人造生命系统。人工生命是人工智能和计算智能的一个新的研究热点。3英国的博物学家达尔文通过研究提出了被恩格斯赞誉为“19世纪自然科学三大发现”之一的生物进化学说。4达尔文的“贝格尔号”考察路线太平洋印度洋亚洲欧洲非洲南美洲北美洲大洋州大西洋5生物进化的过程和原因取食果实取食昆虫取食仙人掌取食种子取食昆虫喙凿状喙不变喙尖而长喙粗而尖加拉帕戈斯雀的进化6长颈鹿的进化示意图7环境实验灰色桦尺蛾黑色桦尺蛾未污染区放出只数496473重新捕捉只数6230重新捕捉百分比12.5%6.3%污染区放出只数201601重新捕捉只数32205重新捕捉百分比15.9%34.1%85.1遗传算法遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。9遗传算法（GeneticAlgorithm，简称GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算机算法，它由美国Holland教授1975年提出。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。一、遗传学概述10基本思想：基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。11与传统的优化算法相比，遗传算法主要有以下几个不同之处遗传算法不是直接作用在参变量集上而是利用参变量集的某种编码遗传算法不是从单个点，而是从一个点的群体开始搜索；遗传算法利用适应值信息，无须导数或其它辅助信息；遗传算法利用概率转移规则，而非确定性规则。12遗传算法的优越性主要表现在：首先，它在搜索过程中不容易陷入局部最优，即使所定义的适应函数是不连续的、非规则的或有噪声的情况下，它也能以很大的概率找到整体最优解；其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算机。135.1.1遗传算法的基本机理霍兰德的遗传算法通常称为简单遗传算法（SGA）。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构和机理。编码与解码适应度函数遗传操作5.1遗传算法14遗传学相关概念个体与种群个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。15适应度与适应度函数适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。适应度函数——为了体现染色体的适应能力，所引入的对问题中每一个染色体都能进行度量的函数。例如，TSP的目标是路径总长度为最短，路径总长度的倒数就可以作为TSP的适应度函数：16编码与译码编码——将问题结构变换为位串形式。译码——将位串形式变换为原问题结构。把位串形式编码表示叫染色体，有时也叫个体。17染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体染色体9----1001（2，5，6）----01010111018亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:●选择-复制(selection-reproduction)●交叉(crossover，亦称交换、交配或杂交)●变异(mutation，亦称突变)19选择操作（复制操作）——根据个体的适应度函数值所度量的优、劣程度决定它在下一代是被淘汰还是被遗传。一般使适应度较大(优良)个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。20选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xi∈S的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。NjjiixfxfxP1)()()(这里的选择概率P(xi)的计算公式为21比例选择的具体执行过程：最后再根据个体总数N，来决定各个个体进入下一代的个数。其中，Ni是个体Xi进入下一代的期望个数，是平均适应度。fXfNXfXfNXfXfNiNjjiNjjii)(/)()()()(11f22交叉：就是互换两个染色体某些位上的基因。一种简单方式是将被选择出的两个个体和作为父母个体，将两者的部分码值进行交换。…s1′=01000101,s2′=10011011可以看做是原染色体s1和s2的子代染色体。例如,设染色体s1=01001011,s2=10010101,交换其后4位基因,即23变异：一种简单方式是改变数码串的某个位置上的数码。例如,设染色体s=11001101，将其第三位上的0变为1,即s=11001101→11101101=s′。s′也可以看做是原染色体s的子代染色体。24遗传学遗传算法数学1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解25遗传学遗传算法数学9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值,一般为0.001~0.0113进化、适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解264.控制参数（1）实施交叉、变异操作的概率并非所有被选择了的染色体都要进行交叉操作和变异操作，而是按一定的概率进行。一般在程序设计中选择：交叉操作概率变异操作概率（2）种群规模27三、简单遗传算法遗传算法基本步骤：把这些可行解置于问题的“环境”中，按适者生存的原则，选取较适应环境的“染色体”进行复制，并通过交叉、变异过程产生更适应环境的新一代“染色体”群把问题的解表示成“染色体”，在算法中就是以二进制编码的串，给出一群“染色体”，也就是假设的可行解经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解285.1.2遗传算法的求解步骤1.基本遗传算法的特点(1)遗传算法是对参数集合的编码而非针对参数本身进行进化；(2)遗传算法是从问题解的编码组开始而非从单个解开始搜索；(3)遗传算法利用目标函数的适应度这一信息而非利用导数或其它辅助信息来指导搜索；(4)遗传算法利用选择、交叉、变异等算子而不是利用确定性规则进行随机操作。5.1遗传算法29基本遗传算法的基本步骤基本遗传算法（SimpleGeneticAlgorithms,简称SGA）是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。302.遗传算法的框图(图5.2)(1)初始化群体;(2)计算群体上每个个体的适应度值;(3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;(4)按概率Pc进行交叉操作;(5)按概率Pc进行突变操作;(6)若没有满足某种停止条件，则转第(2)步，否则进入下一步。(7)输出群体中适应度值最优的染色体作为问题的满意解或最优解。5.1遗传算法31初始化种群变异操作计算适应度值选择操作交叉操作初始化种群终止条件开始图5.2算法框图5.1遗传算法323一般遗传算法的主要步骤如下：(1)随机产生一个由确定长度的特征字符串组成的初始群体。(2)对该字符串群体迭代的执行下面的步①和②，直到满足停止标准：①计算群体中每个个体字符串的适应值；②应用复制、交叉和变异等遗传算子产生下一代群体。(3)把在后代中出现的最好的个体字符串指定为遗传算法的执行结果，这个结果可以表示问题的一个解。5.1遗传算法33产生初始群体是否满足停止准则计算每个个体的适应值i=M?GEN:=GEN+1依概率选择遗传操作执行复制选择一个个体i:=i+1选择两个个体选择一个个体执行变异i:=0GEN:=0复制到新群体i:=i+1将两个后代插入新群体插入到新群体执行杂交指定结果结束是否是否变异复制交叉5.1遗传算法34遗传算法的一般结构表示Procedure:GeneticAlgorithmsbegint←0;initializeP(t);evaluateP(t);while(notterminationcondition)dobeginrecombineP(t)toyieldC(t);evaluateC(t);selectP(t+1)fromP(t)andC(t);t←t+1;endend5.1遗传算法354.遗传算法应用举例1例1利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。y=x231XY36GA的基本流程根据问题编码，并初始化种群计算群体适应度选择操作交叉操作变异操作满足收敛条件否N输出计算结果Y37分析原问题可转化为在区间［0,31］中搜索能使y取最大值的点a的问题。那么，［0,31］中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间［0,31］就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。38(1)设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x239(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。40首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si)。容易求得f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=36141再计算种群S1中各个体的选择概率。NjjiixfxfxP1)()()(选择概率的计算公式为由此可求得P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(