《遗传算法》ppt课件

《《遗传算法》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法遗传算法是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是一类随机算法通过作用于染色体上的基因，寻找好的染色体来求解问题。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。遗传算法通过有组织地而且是随机地信息交换来重新结合那些适应性好的串，在每一个新的串的群体中作为额外增添，偶尔也要在串结构中尝试用新的位和段来代替原来的部分。遗传算法遗传算法从初始串群体开始，按照下面的步骤迭代搜索：使用目标函数计算每个串的适应度。使用选择策略，选择一些适应度最高的串。按照

2、步骤②的选择策略，应用遗传算子生成新的串。随机变异这些新串。变异一个串的方法是，随机选择单个位，然后按随机取样方式反转该位，换句话说，就是使用随机方式决定选择的位是否被求反。使用再插入策略，将步骤③与步骤④生成的新串替换存在的一些串生成下一代群体。若得到解，则停止；否则返回步骤①。遗传算法一个假设表示为一个二进制串这些串通常称为染色体染色体含有称为基因的子串，基因表示属性值染色体的集合构成一个群体010110111000010000基因[0]表示年龄基因[1]表示高度遗传算法群体是染色体的集合染色体表示求解问题的当前假设从群体中提取父代染色体进行运算，通过应用遗传算子达到运算目

3、的010001110010010001110111011100110111011100110010遗传算法选择：其目的是为了从当前群体中选出优良的个体，使它们有机会作为父代产生后代个体交叉：随机地选取一个截断点，将父代的染色体在截断点断开，并交换其后半部分变异：对于群体中的某个染色体，随机选取某一位，将该位取反适应度：每个个体对应于优化问题的一个解，每个解对应于一个函数值，函数值越大（小），则表明该解越好遗传算法设想一个游戏。你必须进入地牢解救一位公主。为了进入地牢，你必须闯过几道难关，其中一道关口是一扇很重的大门，要求必须将其抬起，而唯一可以抬起这扇门的是一种称为“citeg

4、en”的生物。现在有很多citegen陪伴着你，每个citegen都试图抬起这扇门，抬起这扇门最高的citegen产生新的后代，这些后代也试图抬起这扇门，重复这个过程。在规定的时间内，若这扇门没有被抬起，游戏将结束。遗传算法所有的染色体都用4位数表示，每位数字表示一个基因，可以是{0,1,2,3}中之一。抬门获得成功的citegen具有编码为0133的染色体。所有其他citegen具有其他的编码，它们要么抬起一点，要么完全抬不动，因此编码表示citegen的力气，即适应度。建模遗传算法适应度按照下面的规则计算：适应度←0若染色体含有0，则适应度←适应度+1若染色体含有1，则适应

5、度←适应度+1若染色体含有3，则适应度←适应度+1若gene[0]具有0，则适应度←适应度+1若gene[1]具有1，则适应度←适应度+1若gene[2]具有3，则适应度←适应度+1若gene[3]具有3，则适应度←适应度+1遗传算法要做的第一件事是将染色体转换成二进制串，00表示001表示110表示211表示3交叉位置：6，即父代染色体被复制下来产生两个后代然后两个后代交换他们的最后两位变异：由随机选择一位、求反遗传算法例如，染色体0223的适应度为4。若所有7个规则都满足（也就是当染色体是0133），则适应度为7。适应度值可以求负操作，以使任务成为最小化搜索。因此，目标染色

6、体具有-7的适应度。要做的第一件事是将染色体转换成二进制串，这可通过由00表示0，01表示1，10表示2，11表示3来完成。现在每个基因由两位表示，目标染色体有00011111表示。为了简化例子，总是在位置6处应用单点交叉。父染色体被复制下来产生两个后代，然后两个后代交换他们的最后两位。变异由随机选择一位且对他求反组成。遗传算法学习过程如下：生成一个初始随机群体00001010011011010011100100001100000110110110111000111000011011011256891011-2-3-4-4-6-3-3-3每个染色体给一个标号（左边的整数值），最

7、右边的列显示的是适应度。当具有相同的适应度时，采用任意方式选择父代遗传算法学习过程如下：选择适应度最好的4个0011100100001100000110110110110156811-4-4-6-35与6交叉00111000000011011213-3-58与11交叉00011001011011111415-4-4遗传算法学习过程如下：整个群体变异0011100100001100000110110110110100111000000011010001100101101111568111213