第六章 演化规划

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

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

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

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

5、l当输入序列为当输入序列为 时，有限状态时，有限状态 自动机产生一个输出序列自动机产生一个输出序列 其中其中 是对是对 的预测。的预测。 , 21 aa ), 2 , 1(, 21 naaa n 1 n ), 2 , 1(, 21 naaa n , 21n bbb )1, 2 , 1( nibi 1 i a 6.1 演化规划的基本结构演化规划的基本结构 l一个执行这种预测任务的自动机如图一个执行这种预测任务的自动机如图6.26.2所示。所示。 l当输入序列为当输入序列为011101011101时，所产生的输出序列为时，所产生的输出序列为 110111110111。这时，当。这时，当n=1，2，

6、5时，机器作出了准时，机器作出了准 确的预测，预测准确率为确的预测，预测准确率为60%。 图图6.2 作为预测器的有限状态自动机作为预测器的有限状态自动机 AC B 0/0 1/1 0/1 1/0 0/11/1 开始开始 6.1 演化规划的基本结构演化规划的基本结构 l用演化规划求解上述问题的方法是：保持一个用演化规划求解上述问题的方法是：保持一个 具有具有 个有限状态自动机的种群，对种群中的个有限状态自动机的种群，对种群中的 每个自动机进行变异得到每个自动机进行变异得到 个后代。变异通常个后代。变异通常 有改变输出符号、改变状态转移、添加一个状有改变输出符号、改变状态转移、添加一个状 态、删

7、除一个状态和改变初始状态五种方式。态、删除一个状态和改变初始状态五种方式。 然后根据对有限状态自动机的某种适应值度量，然后根据对有限状态自动机的某种适应值度量， 从个从个 父体和父体和 个后代中选取个后代中选取 个个体作为下个个体作为下 一代种群。一代种群。 6.1演化规划的基本结构演化规划的基本结构 end solution;best the return while end ; 1 );(,),( )(elect survivor_s ) 1( for; end );)(evaluate( );(mutate()( do to 1for do condition) nterminatio(

8、not while );(evaluate( );(,),(),()(initialize ; 0 begin mingry_ProgramEvolutiona procedure 1 21 tt tototPtP to tato i tPtatatatP t i ii 6.2 演化规划的实现技术演化规划的实现技术 l表示表示 (1)(1)标准演化规划标准演化规划 (2)(2)元演化规划元演化规划 (3)(3)旋转演化规划旋转演化规划 ),( 21n xxxx ),(),( 2121nn xxxx ),(),( 212121mnn xxxx 6.2 演化规划的实现技术演化规划的实现技术 l其中

9、其中 表示表示 与与 之间的相关之间的相关 系数，系数， 表示表示 与与 之间的相关系数，之间的相关系数， 表示表示 与与 之间的相关系数。之间的相关系数。 l若若 表示变量表示变量 与与 之间的相关系数，则之间的相关系数，则 与与 之间的协方差由下式确定：之间的协方差由下式确定： . 2/ )1( nnm 1 1 x 2 x 2 1 x 3 xm n x 1 n x k i x j x i x j x , ji ij k c 1 , 1 k 6.2 演化规划的实现技术演化规划的实现技术 l由协方差由协方差 可以构可以构 成协方差矩阵成协方差矩阵C，而，而 其中其中 lC用于产生服从用于产生服

10、从n n维正态分布的随机向量维正态分布的随机向量 ), 1; 1, 2 , 1(nijnicij nnn n n cc cc cc C 21 2221 1121 )(jicc jiij ), 0(CN 6.2 演化规划的实现技术演化规划的实现技术 l变异变异 (1) 标准演化规划标准演化规划 这时个体的表示为这时个体的表示为 变异操作为：变异操作为： 其中其中 为个体为个体x x的适应值，的适应值， 为为 待定的参数。通常取待定的参数。通常取 ).,( 21n xxxx iii iiii xF Nxx )( )1 , 0( )(xF ), 2 , 1(,ni ii , 1 i . 0 i 6.

11、2 演化规划的实现技术演化规划的实现技术 l(2) 元演化规划元演化规划 这时个体的表示为这时个体的表示为 变异操作为：变异操作为： 其中其中 为常系数为常系数. . ),(),( 11nn xxx )1 , 0( )1 , 0( iiii iiii N Nxx 6.2 演化规划的实现技术演化规划的实现技术 l(3) 旋转演化规划旋转演化规划 这时个体的表示为这时个体的表示为 变异操作为：变异操作为： 其中其中 为常系数。为常系数。 ),(),( 111mnn xxx )1 , 0( )1 , 0( ), 0( jjjj iiii N N CNxx , 6.2 演化规划的实现技术演化规划的实现

12、技术 l目前已经提出多种变异算子。这些变异算子的目前已经提出多种变异算子。这些变异算子的 区别主要在于：区别主要在于： (1) (1) 修改变异步长公式的不同；修改变异步长公式的不同； (2) (2) 在公式中使用方差而不是标准差；在公式中使用方差而不是标准差； (3) (3) 和和x x被变异的次序不同。被变异的次序不同。 l譬如，对元演化规划，有人提出下面的变异公譬如，对元演化规划，有人提出下面的变异公 式：式： )1 , 0( )1 , 0(1( iiii ii Nxx N 2 . 0 6.2 演化规划的实现技术演化规划的实现技术 l父体选择父体选择 演化规划中的父体选择非常简单。在演化

13、规划演化规划中的父体选择非常简单。在演化规划 中，种群中的每个个体经过变异恰好产生一个后中，种群中的每个个体经过变异恰好产生一个后 代。种群中的每个个体都是一个父体，无需进行代。种群中的每个个体都是一个父体，无需进行 专门选择。专门选择。 l存活选择存活选择 存活选择从存活选择从 个父体和个父体和 个后代中选取个后代中选取 个作个作 为下一代种群为下一代种群。 l通常演化规划采用随机型竞争选择。在这种方法通常演化规划采用随机型竞争选择。在这种方法 中，对每个个体中，对每个个体 其中其中 为为 个个 后代的集合，从后代的集合，从 中随机地选取中随机地选取q q个个个个 体。然后将个体体。然后将个

14、体a a的适应值分别与这的适应值分别与这q q个个体的适个个体的适 应值进行比较，并记录个体应值进行比较，并记录个体a a的适应值优于或等的适应值优于或等 于所比较个体适应值的次数，该次数称为个体于所比较个体适应值的次数，该次数称为个体a a 的得分。最后，将的得分。最后，将 中的个个体按照它中的个个体按照它 们的得分按降序排序，并选择前们的得分按降序排序，并选择前 个个体作为个个体作为 ),()(tPtPa )(t P )()(tPtP )()(tPtP 6.2 演化规划的实现技术演化规划的实现技术 6.2 演化规划的实现技术演化规划的实现技术 下一代种群下一代种群. . lq- -竞争选择

15、是一种随机选择。总的来说，优良竞争选择是一种随机选择。总的来说，优良 个体进入下一代种群的机会较大，但较差个体个体进入下一代种群的机会较大，但较差个体 也有进入下一代种群的机会。随着也有进入下一代种群的机会。随着q q值的增加，值的增加， 较差个体进入下一代种群的机会减小。当较差个体进入下一代种群的机会减小。当q q增加增加 到其最大值到其最大值 时，竞争选择演变为演化策略时，竞争选择演变为演化策略 中的中的 确定性确定性 选择。选择。 2 )( 6.3 应用实例应用实例 l作为演化规划的一个应用实例，我们还是考虑作为演化规划的一个应用实例，我们还是考虑 下面的下面的AckleyAckley函

16、数的优化问题：函数的优化问题： l用元演化规划求解该问题，其设计如下：用元演化规划求解该问题，其设计如下： (1)(1)表示：个体的表示为如下形式表示：个体的表示为如下形式 71282. 2;30, 2 , 1 ,3030 20)2cos( 30 1 exp 30 1 2 . 0exp20),(min 30 1 30 1 2 3021 eix exxxxxf i i i i i ),( 30213021 xxx 6.3 应用实例应用实例 (2) 适应函数：适应函数取为目标函数。适应函数：适应函数取为目标函数。 (3) 参数设置：参数设置： (4) 终止准则：当进行终止准则：当进行2000002

17、00000次函数值计算或发现次函数值计算或发现 最优解后终止算法。最优解后终止算法。 (5) 种群初始化：初始种群中每个个体的变量部分种群初始化：初始种群中每个个体的变量部分 随机地产生，每个变量均匀地分布在区间随机地产生，每个变量均匀地分布在区间 内。每个个体的变异步长都相同，设为内。每个个体的变异步长都相同，设为 运行上述算法运行上述算法1010次，每次找到的最好解都位于全次，每次找到的最好解都位于全 局最优峰上。最好解的平均函数值为局最优峰上。最好解的平均函数值为 ,200 ,10 q6 30 ,30 . 3 .1039. 1 2 演化计算课程论文题目演化计算课程论文题目( (下列题目选

18、择之一下列题目选择之一) ) 1 用遗传算法用遗传算法求解下列约束优化问题：求解下列约束优化问题： 其中其中 )( )2sin()2(sin ),(max 21 3 1 21 3 21 xxx xx xxf 0)4(1 01 2 2 2 1 2 2 1 xx xx 100 ,100 21 xx 演化计算课程论文题目演化计算课程论文题目( (下列题目选择之一下列题目选择之一) ) 2 用遗传算法求解下列优化问题用遗传算法求解下列优化问题(n=2,4,6,8,10,20) 并研究问题的维数对算法性能的影响并研究问题的维数对算法性能的影响。 71828. 2;, 2 , 1 ,3030 20)2cos( 1 exp 1 2 . 0exp20),.,(min 11 2 1 eni