第六章-演化规划

第6章演化规划武汉大学计算机学院6.1演化规划的基本结构演化规划是由L.J.Fogel等在20世纪60年代提出的。当时演化规划的目标是通过模拟进化来获得智能行为。他们将智能视为能够预测其所在环境的状态，并按照预定目标作出适当响应的能力。对环境的预测能力是智能行为的一个重要特征。6.1演化规划的基本结构Fogel将环境描述为由有限字符集中的符号所组成的序列，而预测器则用有限状态自动机来表示。一个有限状态自动机是一个五元组其中S是状态的集合，I是输入符号的集合，O是输出符号的集合，是转移函数，是初始状态。图6.1给出了有限状态机的一个简单的例子。),,,,(0sOISOSIS:Ss06.1演化规划的基本结构图6.1一个有限状态自动机ACB0/c1/b0/b1/c0/b1/a开始6.1演化规划的基本结构在图6.1所示的有限状态自动机中，两个状态之间的一条有向边指示一个状态转移，而状态转移函数由边上形如的标记所指明。譬如，从状态A到状态B之间的有向边的标记为则该标记所表示的状态转移为即若当前状态为A且输入符号为0时，机器转移到状态B且输出符号b。初始状态为A。},,,{CBAS},1,0{I},,,{cbaOOSIS:),,())0,((bBA,/0b6.1演化规划的基本结构一个简单的预测任务是：给定一个序列在观察到前n个符号的基础上，预测第个符号。演化规划就是通过模拟生物进化的方式演化出能够执行预测任务的有限状态自动机.当输入序列为时，有限状态自动机产生一个输出序列其中是对的预测。,,,21aa),2,1(,,,21naaan1n),2,1(,,,21naaan,,,,21nbbb)1,,2,1(nibi1ia6.1演化规划的基本结构一个执行这种预测任务的自动机如图6.2所示。当输入序列为011101时，所产生的输出序列为110111。这时，当n=1，2，5时，机器作出了准确的预测，预测准确率为60%。图6.2作为预测器的有限状态自动机ACB0/01/10/11/00/11/1开始6.1演化规划的基本结构用演化规划求解上述问题的方法是：保持一个具有个有限状态自动机的种群，对种群中的每个自动机进行变异得到个后代。变异通常有改变输出符号、改变状态转移、添加一个状态、删除一个状态和改变初始状态五种方式。然后根据对有限状态自动机的某种适应值度量，从个父体和个后代中选取个个体作为下一代种群。6.1演化规划的基本结构endsolution;bestthereturnwhileend;1)});(,),({)((electsurvivor_s)1(for;end);)(evaluate());(mutate()(doto1fordocondition)nterminatio(notwhile));(evaluate()});(,),(),({)((initialize;0beginmingry_ProgramEvolutionaprocedure121tttototPtPtotatoitPtatatatPtiii6.2演化规划的实现技术表示(1)标准演化规划(2)元演化规划(3)旋转演化规划),,,(21nxxxx),,,,,,,(),(2121nnxxxx),,,,,,,,,,,(),,(212121mnnxxxx6.2演化规划的实现技术其中表示与之间的相关系数，表示与之间的相关系数，…，表示与之间的相关系数。若表示变量与之间的相关系数，则与之间的协方差由下式确定：.2/)1(nnm11x2x21x3xmnx1nxkixjxixjx,jiijkc]1,1[k6.2演化规划的实现技术由协方差可以构成协方差矩阵C，而其中C用于产生服从n维正态分布的随机向量),,1;1,,2,1(nijnicijnnnnnccccccC2122211121)(jiccjiij),0(CN6.2演化规划的实现技术变异(1)标准演化规划这时个体的表示为变异操作为：其中为个体x的适应值，为待定的参数。通常取).,,,(21nxxxxiiiiiiixFNxx)()1,0()(xF),,2,1(,niii,1i.0i6.2演化规划的实现技术(2)元演化规划这时个体的表示为变异操作为：其中为常系数.),,,,,(),(11nnxxx)1,0()1,0(iiiiiiiiNNxx6.2演化规划的实现技术(3)旋转演化规划这时个体的表示为变异操作为：其中为常系数。),,,,,,,,(),,(111mnnxxx)1,0()1,0(),0(jjjjiiiiNNCNxx,6.2演化规划的实现技术目前已经提出多种变异算子。这些变异算子的区别主要在于：(1)修改变异步长公式的不同；(2)在公式中使用方差而不是标准差；(3)和x被变异的次序不同。譬如，对元演化规划，有人提出下面的变异公式：)1,0())1,0(1(iiiiiiNxxN2.06.2演化规划的实现技术父体选择演化规划中的父体选择非常简单。在演化规划中，种群中的每个个体经过变异恰好产生一个后代。种群中的每个个体都是一个父体，无需进行专门选择。存活选择存活选择从个父体和个后代中选取个作为下一代种群。通常演化规划采用随机型竞争选择。在这种方法中，对每个个体其中为个后代的集合，从中随机地选取q个个体。然后将个体a的适应值分别与这q个个体的适应值进行比较，并记录个体a的适应值优于或等于所比较个体适应值的次数，该次数称为个体a的得分。最后，将中的个个体按照它们的得分按降序排序，并选择前个个体作为),()(tPtPa)(tP)()(tPtP)()(tPtP6.2演化规划的实现技术6.2演化规划的实现技术下一代种群.q-竞争选择是一种随机选择。总的来说，优良个体进入下一代种群的机会较大，但较差个体也有进入下一代种群的机会。随着q值的增加，较差个体进入下一代种群的机会减小。当q增加到其最大值时，竞争选择演变为演化策略中的确定性选择。2)(6.3应用实例作为演化规划的一个应用实例，我们还是考虑下面的Ackley函数的优化问题：用元演化规划求解该问题，其设计如下：(1)表示：个体的表示为如下形式71282.2;30,,2,1,303020)2cos(301exp3012.0exp20),,,(min30130123021eixexxxxxfiiiii),,,,,,,(30213021xxx6.3应用实例(2)适应函数：适应函数取为目标函数。(3)参数设置：(4)终止准则：当进行200000次函数值计算或发现最优解后终止算法。(5)种群初始化：初始种群中每个个体的变量部分随机地产生，每个变量均匀地分布在区间内。每个个体的变异步长都相同，设为运行上述算法10次，每次找到的最好解都位于全局最优峰上。最好解的平均函数值为,200,10q6]30,30[.3.1039.12演化计算课程论文题目(下列题目选择之一)1用遗传算法求解下列约束优化问题：其中)()2sin()2(sin),(max213121321xxxxxxxf0)4(1012221221xxxx100,10021xx演化计算课程论文题目(下列题目选择之一)2用遗传算法求解下列优化问题(n=2,4,6,8,10,20)并研究问题的维数对算法性能的影响。71828.2;,,2,1,303020)2cos(1exp12.0exp20),...,(min1121enixexnxnxxfiniiniin演化计算课程论文题目(下列题目选择之一)3使用路径表示设计并实现一个求解具有30个城市的旅行商问题的遗传算法,假定问题的距离矩由平面上随机生成的30个点之间的距离给定。并比较PMX杂交算子和OX杂交算子对算法性能的影响。4学习演化计算的心得体会。