第六章 演化规划

1、第第6章演化规划章演化规划 武汉大学计算机学院武汉大学计算机学院6.1 演化规划的基本结构演化规划的基本结构l演化规划是由演化规划是由L.J.FogelL.J.Fogel等在等在2020世纪世纪6060年代提出年代提出的。当时演化规划的目标是通过模拟进化来获的。当时演化规划的目标是通过模拟进化来获得智能行为。他们将智能视为能够预测其所在得智能行为。他们将智能视为能够预测其所在环境的状态，并按照预定目标作出适当响应的环境的状态，并按照预定目标作出适当响应的能力。对环境的预测能力是智能行为的一个重能力。对环境的预测能力是智能行为的一个重要特征。要特征。6.1 演化规划的基本结构演化规划的基本结构l

2、FogelFogel将环境描述为由有限字符集中的符号所组将环境描述为由有限字符集中的符号所组成的序列，而预测器则用有限状态自动机来表示。成的序列，而预测器则用有限状态自动机来表示。一个有限状态自动机是一个五元组一个有限状态自动机是一个五元组 其中其中S S是状态的集合，是状态的集合，I I是输入符号的集合，是输入符号的集合，O O是是输出符号的集合，输出符号的集合， 是转移函数，是转移函数， 是初始状态。图是初始状态。图6.16.1给出了有限状态机的一个简给出了有限状态机的一个简单的例子。单的例子。),(0sOIS OSIS : Ss 06.1 演化规划的基本结构演化规划的基本结构图图6.1

3、一个有限状态自动机一个有限状态自动机ACB0/c1/b0/b1/c0/b1/a开始开始6.1 演化规划的基本结构演化规划的基本结构l在图在图6.16.1所示的有限状态自动机中，所示的有限状态自动机中， 两个状态之间的一条有向边两个状态之间的一条有向边指示一个状态转移，而状态转移函数指示一个状态转移，而状态转移函数 由边上形如的标记所指明。譬如，从状态由边上形如的标记所指明。譬如，从状态A A到状态到状态B B之间的有向边的标记为之间的有向边的标记为 则该标记所表示的则该标记所表示的状态转移为状态转移为 即若当前状态为即若当前状态为A A且且输入符号为输入符号为0 0时，机器转移到状态时，机器转

4、移到状态B B且输出符号且输出符号b b。初始状态为初始状态为A A。,CBAS ,1 , 0 I,cbaO OSIS : ),()0 ,(bBA ,/0 b6.1 演化规划的基本结构演化规划的基本结构l一个简单的预测任务是：给定一个序列一个简单的预测任务是：给定一个序列 在观察到前在观察到前n n个符号个符号 的基础的基础上，预测第上，预测第 个符号。个符号。l演化规划就是通过模拟生物进化的方式演化出能演化规划就是通过模拟生物进化的方式演化出能够执行预测任务的有限状态自动机够执行预测任务的有限状态自动机. .l当输入序列为当输入序列为 时，有限状态时，有限状态自动机产生一个输出序列自动机产生

5、一个输出序列 其中其中 是对是对 的预测。的预测。,21aa), 2 , 1(,21 naaan1 n), 2 , 1(,21 naaan,21nbbb)1, 2 , 1( nibi1 ia6.1 演化规划的基本结构演化规划的基本结构l一个执行这种预测任务的自动机如图一个执行这种预测任务的自动机如图6.26.2所示。所示。l当输入序列为当输入序列为011101011101时，所产生的输出序列为时，所产生的输出序列为110111110111。这时，当。这时，当n=1，2，5时，机器作出了准时，机器作出了准确的预测，预测准确率为确的预测，预测准确率为60%。 图图6.2 作为预测器的有限状态自动机

6、作为预测器的有限状态自动机ACB0/01/10/11/00/11/1开始开始6.1 演化规划的基本结构演化规划的基本结构l用演化规划求解上述问题的方法是：保持一个用演化规划求解上述问题的方法是：保持一个具有具有 个有限状态自动机的种群，对种群中的个有限状态自动机的种群，对种群中的每个自动机进行变异得到每个自动机进行变异得到 个后代。变异通常个后代。变异通常有改变输出符号、改变状态转移、添加一个状有改变输出符号、改变状态转移、添加一个状态、删除一个状态和改变初始状态五种方式。态、删除一个状态和改变初始状态五种方式。然后根据对有限状态自动机的某种适应值度量，然后根据对有限状态自动机的某种适应值度量

7、，从个从个 父体和父体和 个后代中选取个后代中选取 个个体作为下个个体作为下一代种群。一代种群。 6.1演化规划的基本结构演化规划的基本结构 endsolution;best the return while end ; 1 );(,),( )(elect survivor_s ) 1( for; end );)(evaluate( );(mutate()( do to 1for do condition) nterminatio(not while );(evaluate( );(,),(),()(initialize ; 0 begin mingry_ProgramEvolutiona p

8、rocedure121 tttototPtPtotatoitPtatatatPtiii 6.2 演化规划的实现技术演化规划的实现技术l表示表示 (1)(1)标准演化规划标准演化规划 (2)(2)元演化规划元演化规划 (3)(3)旋转演化规划旋转演化规划 ),(21nxxxx ),(),(2121nnxxxx ),(),(212121mnnxxxx 6.2 演化规划的实现技术演化规划的实现技术l其中其中 表示表示 与与 之间的相关之间的相关系数，系数， 表示表示 与与 之间的相关系数，之间的相关系数， 表示表示 与与 之间的相关系数。之间的相关系数。l若若 表示变量表示变量 与与 之间的相关系数

9、，则之间的相关系数，则 与与 之间的协方差由下式确定：之间的协方差由下式确定：. 2/ )1( nnm1 1x2x2 1x3xm nx1 nxk ixjxixjx,jiijkc 1 , 1 k 6.2 演化规划的实现技术演化规划的实现技术l由协方差由协方差 可以构可以构成协方差矩阵成协方差矩阵C，而，而 其中其中 lC用于产生服从用于产生服从n n维正态分布的随机向量维正态分布的随机向量 ), 1; 1, 2 , 1(nijnicij nnnnnccccccC 2122211121)(jiccjiij ), 0(CN6.2 演化规划的实现技术演化规划的实现技术l变异变异 (1) 标准演化规划标

10、准演化规划 这时个体的表示为这时个体的表示为 变异操作为：变异操作为： 其中其中 为个体为个体x x的适应值，的适应值， 为为待定的参数。通常取待定的参数。通常取 ).,(21nxxxx iiiiiiixFNxx )()1 , 0()(xF), 2 , 1(,niii , 1 i . 0 i 6.2 演化规划的实现技术演化规划的实现技术l(2) 元演化规划元演化规划 这时个体的表示为这时个体的表示为 变异操作为：变异操作为： 其中其中 为常系数为常系数. . ),(),(11nnxxx )1 , 0()1 , 0(iiiiiiiiNNxx 6.2 演化规划的实现技术演化规划的实现技术l(3)

11、旋转演化规划旋转演化规划 这时个体的表示为这时个体的表示为 变异操作为：变异操作为： 其中其中 为常系数。为常系数。 ),(),(111mnnxxx )1 , 0()1 , 0(), 0(jjjjiiiiNNCNxx ,6.2 演化规划的实现技术演化规划的实现技术l目前已经提出多种变异算子。这些变异算子的目前已经提出多种变异算子。这些变异算子的区别主要在于：区别主要在于： (1) (1) 修改变异步长公式的不同；修改变异步长公式的不同； (2) (2) 在公式中使用方差而不是标准差；在公式中使用方差而不是标准差； (3) (3) 和和x x被变异的次序不同。被变异的次序不同。l譬如，对元演化规

12、划，有人提出下面的变异公譬如，对元演化规划，有人提出下面的变异公式：式： )1 , 0()1 , 0(1(iiiiiiNxxN 2 . 0 6.2 演化规划的实现技术演化规划的实现技术l父体选择父体选择 演化规划中的父体选择非常简单。在演化规划演化规划中的父体选择非常简单。在演化规划中，种群中的每个个体经过变异恰好产生一个后中，种群中的每个个体经过变异恰好产生一个后代。种群中的每个个体都是一个父体，无需进行代。种群中的每个个体都是一个父体，无需进行专门选择。专门选择。l存活选择存活选择 存活选择从存活选择从 个父体和个父体和 个后代中选取个后代中选取 个作个作为下一代种群为下一代种群。 l通常

13、演化规划采用随机型竞争选择。在这种方法通常演化规划采用随机型竞争选择。在这种方法中，对每个个体中，对每个个体 其中其中 为为 个个后代的集合，从后代的集合，从 中随机地选取中随机地选取q q个个个个体。然后将个体体。然后将个体a a的适应值分别与这的适应值分别与这q q个个体的适个个体的适应值进行比较，并记录个体应值进行比较，并记录个体a a的适应值优于或等的适应值优于或等于所比较个体适应值的次数，该次数称为个体于所比较个体适应值的次数，该次数称为个体a a的得分。最后，将的得分。最后，将 中的个个体按照它中的个个体按照它们的得分按降序排序，并选择前们的得分按降序排序，并选择前 个个体作为个个

14、体作为 ),()(tPtPa )(tP )()(tPtP )()(tPtP 6.2 演化规划的实现技术演化规划的实现技术6.2 演化规划的实现技术演化规划的实现技术 下一代种群下一代种群. .lq- -竞争选择是一种随机选择。总的来说，优良竞争选择是一种随机选择。总的来说，优良个体进入下一代种群的机会较大，但较差个体个体进入下一代种群的机会较大，但较差个体也有进入下一代种群的机会。随着也有进入下一代种群的机会。随着q q值的增加，值的增加，较差个体进入下一代种群的机会减小。当较差个体进入下一代种群的机会减小。当q q增加增加到其最大值到其最大值 时，竞争选择演变为演化策略时，竞争选择演变为演化

15、策略中的中的 确定性确定性 选择。选择。 2)( 6.3 应用实例应用实例l作为演化规划的一个应用实例，我们还是考虑作为演化规划的一个应用实例，我们还是考虑下面的下面的AckleyAckley函数的优化问题：函数的优化问题：l用元演化规划求解该问题，其设计如下：用元演化规划求解该问题，其设计如下： (1)(1)表示：个体的表示为如下形式表示：个体的表示为如下形式71282. 2;30, 2 , 1 ,3030 20)2cos(301exp3012 . 0exp20),(min30130123021 eixexxxxxfiiiii ),(30213021 xxx6.3 应用实例应用实例 (2)

16、适应函数：适应函数取为目标函数。适应函数：适应函数取为目标函数。 (3) 参数设置：参数设置： (4) 终止准则：当进行终止准则：当进行200000200000次函数值计算或发现次函数值计算或发现最优解后终止算法。最优解后终止算法。 (5) 种群初始化：初始种群中每个个体的变量部分种群初始化：初始种群中每个个体的变量部分随机地产生，每个变量均匀地分布在区间随机地产生，每个变量均匀地分布在区间 内。每个个体的变异步长都相同，设为内。每个个体的变异步长都相同，设为 运行上述算法运行上述算法1010次，每次找到的最好解都位于全次，每次找到的最好解都位于全局最优峰上。最好解的平均函数值为局最优峰上。最

17、好解的平均函数值为,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 ,3030 20)2cos(1exp12 . 0exp20),.,(min1121