文档介绍：第6章演化规划
武汉大学计算机学院
演化规划的基本结构
。当时演化规划的目标是通过模拟进化来获得智能行为。他们将智能视为能够预测其所在环境的状态,并按照预定目标作出适当响应的能力。对环境的预测能力是智能行为的一个重要特征。
演化规划的基本结构
Fogel将环境描述为由有限字符集中的符号所组成的序列,而预测器则用有限状态自动机来表示。一个有限状态自动机是一个五元组其中S是状态的集合,I是输入符号的集合,O是输出符号的集合, 是转移函数, 是初始状态。。
演化规划的基本结构
一个有限状态自动机
A
C
B
0/c
1/b
0/b
1/c
0/b
1/a
开始
演化规划的基本结构
,
两个状态之间的一条有向边指示一个状态转移,而状态转移函数由边上形如的标记所指明。譬如,从状态A到状态B之间的有向边的标记为则该标记所表示的状态转移为即若当前状态为A且输入符号为0时,机器转移到状态B且输出符号b。初始状态为A。
演化规划的基本结构
一个简单的预测任务是:给定一个序列在观察到前n个符号的基础上,预测第个符号。
演化规划就是通过模拟生物进化的方式演化出能够执行预测任务的有限状态自动机.
当输入序列为时,有限状态自动机产生一个输出序列其中
是对的预测。
演化规划的基本结构
。
当输入序列为011101时,所产生的输出序列为110111。这时,当n=1,2,5时,机器作出了准确的预测,预测准确率为60%。
作为预测器的有限状态自动机
A
C
B
0/0
1/1
0/1
1/0
0/1
1/1
开始
演化规划的基本结构
用演化规划求解上述问题的方法是:保持一个具有个有限状态自动机的种群,对种群中的每个自动机进行变异得到个后代。变异通常有改变输出符号、改变状态转移、添加一个状态、删除一个状态和改变初始状态五种方式。然后根据对有限状态自动机的某种适应值度量,从个父体和个后代中选取个个体作为下一代种群。
演化规划的实现技术
表示
(1)标准演化规划
(2)元演化规划
(3)旋转演化规划