6 遗传算法.pptVIP

遗传算法 遗传算法是一种通过模拟自然进化过程有哪些信誉好的足球投注网站最优解的方法。 遗传算法是一类随机算法通过作用于染色体上的基因，寻找好的染色体来求解问题。 遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。 遗传算法通过有组织地而且是随机地信息交换来重新结合那些适应性好的串，在每一个新的串的群体中作为额外增添，偶尔也要在串结构中尝试用新的位和段来代替原来的部分。 遗传算法 遗传算法从初始串群体开始，按照下面的步骤迭代有哪些信誉好的足球投注网站： 使用目标函数计算每个串的适应度。 使用选择策略，选择一些适应度最高的串。 按照步骤②的选择策略，应用遗传算子生成新的串。 随机变异这些新串。变异一个串的方法是，随机选择单个位，然后按随机取样方式反转该位，换句话说，就是使用随机方式决定选择的位是否被求反。 使用再插入策略，将步骤③与步骤④生成的新串替换存在的一些串生成下一代群体。 若得到解，则停止；否则返回步骤①。 遗传算法 一个假设表示为一个二进制串 这些串通常称为染色体 染色体含有称为基因的子串，基因表示属性值 染色体的集合构成一个群体 010110111000010000 基因[0]表示年龄 基因[1]表示高度 遗传算法 群体是染色体的集合 染色体表示求解问题的当前假设 从群体中提取父代染色体进行运算，通过应用遗传算子达到运算目的 010001110010 010001110111 011100110111 011100110010 遗传算法 选择：其目的是为了从当前群体中选出优良的个体，使它们有机会作为父代产生后代个体 交叉：随机地选取一个截断点，将父代的染色体在截断点断开，并交换其后半部分 变异：对于群体中的某个染色体，随机选取某一位，将该位取反 适应度：每个个体对应于优化问题的一个解，每个解对应于一个函数值，函数值越大（小），则表明该解越好 遗传算法 设想一个游戏。你必须进入地牢解救一位公主。为了进入地牢，你必须闯过几道难关，其中一道关口是一扇很重的大门，要求必须将其抬起，而唯一可以抬起这扇门的是一种称为“citegen”的生物。现在有很多citegen陪伴着你，每个citegen都试图抬起这扇门，抬起这扇门最高的citegen产生新的后代，这些后代也试图抬起这扇门，重复这个过程。在规定的时间内，若这扇门没有被抬起，游戏将结束。 遗传算法 所有的染色体都用4位数表示，每位数字表示一个基因，可以是{0,1,2,3}中之一。 抬门获得成功的citegen具有编码为0133的染色体。所有其他citegen具有其他的编码，它们要么抬起一点，要么完全抬不动，因此编码表示citegen的力气，即适应度。 建模 遗传算法 适应度按照下面的规则计算： 适应度←0 若染色体含有0，则适应度←适应度+ 1 若染色体含有1，则适应度←适应度+ 1 若染色体含有3，则适应度←适应度+ 1 若gene[0]具有0，则适应度←适应度+ 1 若gene[1]具有1，则适应度←适应度+ 1 若gene[2]具有3，则适应度←适应度+ 1 若gene[3]具有3，则适应度←适应度+ 1 遗传算法 要做的第一件事是将染色体转换成二进制串， 00表示0 01表示1 10表示2 11表示3 交叉位置：6，即父代染色体被复制下来产生两个后代 然后两个后代交换他们的最后两位 变异：由随机选择一位、求反 遗传算法 例如，染色体0223的适应度为4。 若所有7个规则都满足（也就是当染色体是0133），则适应度为7。 适应度值可以求负操作，以使任务成为最小化有哪些信誉好的足球投注网站。 因此，目标染色体具有-7的适应度。 要做的第一件事是将染色体转换成二进制串， 这可通过由00表示0，01表示1，10表示2，11表示3来完成。现在每个基因由两位表示，目标染色体示。 为了简化例子，总是在位置6处应用单点交叉。 父染色体被复制下来产生两个后代，然后两个后代交换他们的最后两位。 变异由随机选择一位且对他求反组成。 遗传算法 学习过程如下： 生成一个初始随机群体01101101000011000110111001101101 1 2 5 6 8 9 10 11 -2 -3 -4 -4 -6 -3 -3 -3 每个染色体给一个标号（左边的整数值），最右边的列显示的是适应度。当具有相同的适应度时，采用任意方式选择父代 遗传算法 学习过程如下： 选择适应度最好的4个 00111