人工智能入门 课件 4.进化计算 .ppt

AI:EC*达尔文进化多样性引起变化:如果表现特征:有更高的概率被繁殖下去可以继承则他们往往会形成更多的后代，从而导致新的组合特征.随机性的作用最优的解不一定都能生存下去AI:EC*自然遗传学遗传信息需要通过有机体的DNA编码遗传下去基因的微小变化导致生物体的微小变化(如身高,头发，颜色)对于一个特定的物种，其遗传物质是基本相同的AI:EC*基因和基因组由DNA链编码的基因称为染色体在大多数细胞中，有两条染色体排成双螺旋结构(diploidy)一个个体的全部遗传物质的集合称为基因组AI:EC*个体遗传物质改变的主要手段:重组从至少两个父代个体中获得遗传物质产生新的个体,如,在一对染色体的交叉点上连接交换染色体: 重组前 重组后图片来源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC*个体遗传物质改变的主要手段:突变一些遗传物质会发生轻微的改变，这个过程偶尔发生这意味着子代个体可能拥有父代个体所没有的遗传物质这种改变极有可能是灾难性的AI:EC*进化理论突变,重组?新的遗传物质或者新的组合.繁殖的越多则基因的性能可以得到更多的改进好的基因得到更多被遗传的机会坏的基因则会在遗传的过程中减少在其生存环境中，有机体作为一个整体得到进化.采用进化的方法计算或求解问题能够帮助我们找到问题的最优解：进化计算AI:EC*PartⅡ:什么是进化计算?AI:EC*以这样的方式放置8皇后一个8x8的棋盘上，他们不能互相卡到对方，例子:8皇后问题

[AfterA.E.EibenandJ.E.Smith,IntroductiontoEvolutionaryComputing]

AI:EC*12345678遗传物质:一列数字1-8表现特性:一个棋局配置Obviousmapping8皇后问题:表示AI:EC*一个皇后的惩罚: 它能卡住的皇后个数.一种棋局的惩罚: 对每一个皇后的惩罚值求和.目标:使得惩罚值最小最优棋局: 惩罚值的倒数最大时8皇后问题:适应度评价AI:EC*突变:交换两个随机选择的点(概率:80%)1234567812345678重组:交叉(概率:100%)876425311352467887645123135628748皇后问题:遗传算子5432126478AI:EC*父代选择:挑选五个父代个体，并选择其中最优的两个执行重组操作生存选择(替换策略)当一个新的子代个体要插入种群中时，选择种群中将被替换的一个个体，选择规则为:将种群中的个体按适应度降序排列将个体由高到低列举替换排列中第一个适应度比当前子代适应度低的个体8皇后问题:选择AI:EC*初始化:随机终止:根据适应度的评价问题得到了解决或者循环迭代次数达到最大（比如10，000）8皇后问题:初始化\终止条件AI:EC*8皇后问题:总结注意：操作和参数的选择不只有这一种可能AI:EC*生物进化与有哪些信誉好的足球投注网站的类比进化个体适应度环境有哪些信誉好的足球投注网站候选解解的质量待求解的问题AI:EC*进化算法构成tt+1突变重组繁殖选择图片来源IdaSprinkhuizen-Kuyper:Introductionto

EvolutionaryComputation,2000.AI:EC*进化机制遗传增加了多样性突变重组选择减少了多样性父代选择：选择用于繁殖的父代子代选择：选择保留下来的子代AI:EC*进化中的循环过程重组突变种群子代父代父代选择子代选择图片来源BenPaechter:EvolutionaryComputing–APracticalIntroductionAI:EC*表示基因表示:编码:表型=基因(不一定是一一对应的)解码:基因=表型(必须是一一对应的)表型表示:问题的特定编码AI:EC*进化(适应度)函数表示对种群（解）的要求，即质量函数或目标函数为每一个表型计算一个代表其适应度的实数，这样构成了遗传选择的基础因此该函数的判断能力越大越好AI:EC