《遗传算法》PPT课件.ppt

1、遗传算法遗传算法 遗传算法是一种通过模拟自然进化过程搜索最优解遗传算法是一种通过模拟自然进化过程搜索最优解 的方法。的方法。 遗传算法是一类随机算法通过作用于染色体上的基遗传算法是一类随机算法通过作用于染色体上的基 因，寻找好的染色体来求解问题。因，寻找好的染色体来求解问题。 遗传算法对求解问题的本身一无所知，它所需要的遗传算法对求解问题的本身一无所知，它所需要的 仅是对算法所产生的每个染色体进行评价，并基于适仅是对算法所产生的每个染色体进行评价，并基于适 应值来选择染色体，使适应性好的染色体比适应性差应值来选择染色体，使适应性好的染色体比适应性差 的染色体有更多的繁殖机会。的染色体有更多的繁

2、殖机会。 遗传算法通过有组织地而且是随机地信息交换来重遗传算法通过有组织地而且是随机地信息交换来重 新结合那些适应性好的串，在每一个新的串的群体中新结合那些适应性好的串，在每一个新的串的群体中 作为额外增添，偶尔也要在串结构中尝试用新的位和作为额外增添，偶尔也要在串结构中尝试用新的位和 段来代替原来的部分。段来代替原来的部分。 遗传算法遗传算法 遗传算法从初始串群体开始，按照下面的步骤迭代搜索：遗传算法从初始串群体开始，按照下面的步骤迭代搜索： 使用目标函数计算每个串的适应度。使用目标函数计算每个串的适应度。 使用选择策略，选择一些适应度最高的串。使用选择策略，选择一些适应度最高的串。 按照步

3、骤按照步骤的选择策略，应用遗传算子生成新的串。的选择策略，应用遗传算子生成新的串。 随机变异这些新串。变异一个串的方法是，随机选择随机变异这些新串。变异一个串的方法是，随机选择 单个位，然后按随机取样方式反转该位，换句话说，单个位，然后按随机取样方式反转该位，换句话说， 就是使用随机方式决定选择的位是否被求反。就是使用随机方式决定选择的位是否被求反。 使用再插入策略，将步骤使用再插入策略，将步骤与步骤与步骤生成的新串替换生成的新串替换 存在的一些串生成下一代群体。存在的一些串生成下一代群体。 若得到解，则停止；否则返回步骤若得到解，则停止；否则返回步骤。 遗传算法遗传算法 一个假设表示为一个二

4、进制串一个假设表示为一个二进制串 这些串通常称为染色体这些串通常称为染色体 染色体含有称为基因的子串，基因表染色体含有称为基因的子串，基因表 示属性值示属性值 染色体的集合构成一个群体染色体的集合构成一个群体 010110111000010000 基因基因0表示年龄表示年龄 基因基因1表示高度表示高度 遗传算法遗传算法 群体是染色体的集合群体是染色体的集合 染色体表示求解问题的当前假设染色体表示求解问题的当前假设 从群体中提取父代染色体进行运算，从群体中提取父代染色体进行运算， 通过应用遗传算子达到运算目的通过应用遗传算子达到运算目的 010001110010 010001110111 011

5、100110111 011100110010 遗传算法遗传算法 选择：其目的是为了从当前群体中选出优良的个选择：其目的是为了从当前群体中选出优良的个 体，使它们有机会作为父代产生后代个体体，使它们有机会作为父代产生后代个体 交叉：随机地选取一个截断点，将父代的染色体交叉：随机地选取一个截断点，将父代的染色体 在截断点断开，并交换其后半部分在截断点断开，并交换其后半部分 变异：对于群体中的某个染色体，随机选取某一变异：对于群体中的某个染色体，随机选取某一 位，将该位取反位，将该位取反 适应度：每个个体对应于优化问题的一个解，每适应度：每个个体对应于优化问题的一个解，每 个解对应于一个函数值，函数

6、值越大（小），则个解对应于一个函数值，函数值越大（小），则 表明该解越好表明该解越好 遗传算法遗传算法 设想一个游戏。你必须进入地牢解救一位公主。为设想一个游戏。你必须进入地牢解救一位公主。为 了进入地牢，你必须闯过几道难关，其中一道关口是一了进入地牢，你必须闯过几道难关，其中一道关口是一 扇很重的大门，要求必须将其抬起，而唯一可以抬起这扇很重的大门，要求必须将其抬起，而唯一可以抬起这 扇门的是一种称为扇门的是一种称为“citegen”的生物。现在有很多的生物。现在有很多citegen 陪伴着你，每个陪伴着你，每个citegen都试图抬起这扇门，抬起这扇门都试图抬起这扇门，抬起这扇门 最高的最

7、高的citegen产生新的后代，这些后代也试图抬起这扇产生新的后代，这些后代也试图抬起这扇 门，重复这个过程。在规定的时间内，若这扇门没有被门，重复这个过程。在规定的时间内，若这扇门没有被 抬起，游戏将结束。抬起，游戏将结束。 遗传算法遗传算法 所有的染色体都用所有的染色体都用4位数表示，每位数字表示一个位数表示，每位数字表示一个 基因，可以是基因，可以是0,1,2,3中之一。中之一。 抬门获得成功的抬门获得成功的citegen具有编码为具有编码为0133的染色体。的染色体。 所有其他所有其他citegen具有其他的编码，它们要么抬起一点，具有其他的编码，它们要么抬起一点， 要么完全抬不动，因

8、此编码表示要么完全抬不动，因此编码表示citegen的力气，即适应的力气，即适应 度。度。 建模建模 遗传算法遗传算法 适应度按照下面的规则计算：适应度按照下面的规则计算： 适应度适应度0 若染色体含有若染色体含有0，则适应度，则适应度适应度适应度+ 1 若染色体含有若染色体含有1，则适应度，则适应度适应度适应度+ 1 若染色体含有若染色体含有3，则适应度，则适应度适应度适应度+ 1 若若gene0具有具有0，则适应度，则适应度适应度适应度+ 1 若若gene1具有具有1，则适应度，则适应度适应度适应度+ 1 若若gene2具有具有3，则适应度，则适应度适应度适应度+ 1 若若gene3具有具

9、有3，则适应度，则适应度适应度适应度+ 1 遗传算法遗传算法 要做的第一件事是将染色体转换成二进制串，要做的第一件事是将染色体转换成二进制串， 00表示表示0 01表示表示1 10表示表示2 11表示表示3 交叉交叉位置：位置：6，即父代染色体被复制下来产生两个后代，即父代染色体被复制下来产生两个后代 然后两个后代交换他们的最后两位然后两个后代交换他们的最后两位 变异：由随机选择一位、求反变异：由随机选择一位、求反 遗传算法遗传算法 例如，染色体例如，染色体0223的适应度为的适应度为4。 若所有若所有7个规则都满足（也就是当染色体是个规则都满足（也就是当染色体是0133），则），则 适应度为

10、适应度为7。 适应度值可以求负操作，以使任务成为最小化搜索。适应度值可以求负操作，以使任务成为最小化搜索。 因此，目标染色体具有因此，目标染色体具有-7的适应度。的适应度。 要做的第一件事是将染色体转换成二进制串，要做的第一件事是将染色体转换成二进制串， 这可通过由这可通过由00表示表示0，01表示表示1，10表示表示2，11表示表示3来完来完 成。现在每个基因由两位表示，目标染色体有成。现在每个基因由两位表示，目标染色体有00011111 表示。表示。 为了简化例子，总是在位置为了简化例子，总是在位置6处应用单点交叉。处应用单点交叉。 父染色体被复制下来产生两个后代，然后两个后代交换父染色体

11、被复制下来产生两个后代，然后两个后代交换 他们的最后两位。他们的最后两位。 变异由随机选择一位且对他求反组成。变异由随机选择一位且对他求反组成。 遗传算法遗传算法 学习过程如下：学习过程如下： 生成一个初始随机群体生成一个初始随机群体 00001010 01101101 00111001 00001100 00011011 01101110 00111000 01101101 1 2 5 6 8 9 10 11 -2 -3 -4 -4 -6 -3 -3 -3 每个染色体给一个每个染色体给一个 标号（左边的整数标号（左边的整数 值），最右边的列值），最右边的列 显示的是适应度。显示的是适应度。

12、当具有相同的适应当具有相同的适应 度时，采用任意方度时，采用任意方 式选择父代式选择父代 遗传算法遗传算法 学习过程如下：学习过程如下： 选择适应度最好的选择适应度最好的4个个 00111001 00001100 00011011 01101101 5 6 8 11 -4 -4 -6 -3 5与与6交叉交叉 00111000 00001101 12 13 -3 -5 8与与11交叉交叉 00011001 01101111 14 15 -4 -4 遗传算法遗传算法 学习过程如下：学习过程如下： 整个群体变异整个群体变异 00111001 00001100 00011011 01101101 00

13、111000 00001101 00011001 01101111 5 6 8 11 12 13 14 15 -4 -4 -6 -3 -3 -5 -4 -4 00101001 01001100 00111011 01001101 00111010 01001101 00111001 00101111 5 6 8 11 12 13 14 15 -3 -4 -4 -4 -3 -4 -4 -5 遗传算法遗传算法 学习过程如下：学习过程如下： 选择适应度最好的选择适应度最好的4个个 01001101 01001101 00111001 00101111 11 13 14 15 -4 -4 -4 -5

14、11与与13交叉交叉 01001101 01001101 16 17 -4 -4 14与与15交叉交叉 00111011 00101101 18 19 -4 -5 遗传算法遗传算法 学习过程如下：学习过程如下： 整个群体变异整个群体变异 01001101 01001101 00111001 00101111 01001101 01001101 00111011 00101101 11 13 14 15 16 17 18 19 -4 -4 -4 -5 -4 -4 -4 -5 01011101 00001101 00011001 00001111 01001111 00001101 0001101

15、1 01101101 11 13 14 15 16 17 18 19 -4 -5 -4 -5 -5 -5 -6 -3 遗传算法遗传算法 学习过程如下：学习过程如下： 选择适应度最好的选择适应度最好的4个个 00001111 01001111 00001101 00011011 15 16 17 18 -5 -5 -5 -6 15与与16交叉交叉 00001111 01001111 20 21 -5 -5 17与与18交叉交叉 00001111 00011001 22 23 -5 -4 遗传算法遗传算法 学习过程如下：学习过程如下： 整个群体变异整个群体变异 00001111 01001111

16、00001101 00011011 00001111 01001111 00001111 00011001 15 16 17 18 20 21 22 23 -5 -5 -5 -6 -5 -5 -5 -4 00011111 00001111 00101101 00111011 00001101 00001111 00101111 01011001 15 16 17 18 20 21 22 23 -7 -5 -5 -4 -5 -5 -5 -2 遗传算法遗传算法 对于单点交叉，对于单点交叉，掩码掩码是一系列连续是一系列连续1直到交换点，串直到交换点，串 的剩余部分为的剩余部分为0，掩码与父串的长度相

17、同。，掩码与父串的长度相同。 若掩码中的位为若掩码中的位为0，则在，则在parent1中相应的位传递给中相应的位传递给 offspring1，在在parent2中相应的位传递给中相应的位传递给offspring2。 若掩码中的位为若掩码中的位为1，则在，则在parent1中相应的位传递给中相应的位传递给 offspring2，在在parent2中相应的位传递给中相应的位传递给offspring1。 010001110010 010001110111011100110111 011100110010 111111110000掩码掩码 遗传算法遗传算法 两点交叉使用的掩码具有指定数目的前导两点交叉

18、使用的掩码具有指定数目的前导0， 跟随指定数目的前导跟随指定数目的前导1，剩余的为，剩余的为0。 010001110010 011001110111011100110111 010100110010 000111100000掩码掩码 遗传算法遗传算法 均匀交叉，使用随机的、独立于其它位的方均匀交叉，使用随机的、独立于其它位的方 法来设置每位从而构造掩码。法来设置每位从而构造掩码。 010001110010 010001110011011100110111 011100110110 101101010100掩码掩码 遗传算法遗传算法 000101110101111100011100 练习练习 给

19、给12位串两点交叉的一个掩码，位串两点交叉的一个掩码， 000111111000 使用这个掩码计算下面父代的两个后代使用这个掩码计算下面父代的两个后代 遗传算法遗传算法 A 0110010101100000 B 0111110110011010 练习练习 若最优染色体的适应度由如下表示，若最优染色体的适应度由如下表示， 0111010111100010 使用汉明距离计算下面各串的适应度使用汉明距离计算下面各串的适应度 C 1111010101100010 D 0010111101101010 E 0111110010101110 遗传算法遗传算法 遗传算法求解旅行商问题遗传算法求解旅行商问题(

20、TSP) 问题描述：已知问题描述：已知n个城市的地理位置个城市的地理位置(x,y)， 求经过所有城市、回到出发城市，并且求经过所有城市、回到出发城市，并且 每个城市只访问一次的最短路径。每个城市只访问一次的最短路径。 遗传算法遗传算法 1、编码编码 每条路经对应一个个体，个体表示为每条路经对应一个个体，个体表示为 R=CityNoCityNo互不重复互不重复n，n为城市数。为城市数。 例如，例如，n=10，其中一个个体，其中一个个体3 1 5 7 8 9 10 4 2 6 2、适应函数：评估路径的长度，越短越好适应函数：评估路径的长度，越短越好 3.1 交叉采用交叉采用部分匹配交叉部分匹配交叉

21、策略策略 例如，对个体例如，对个体A和和B: A= 9 8 4 5 6 7 1 3 2 10 B= 8 7 1 4 10 3 2 9 6 5 两个个体交叉段互换，而且对个体两个个体交叉段互换，而且对个体A，交叉段中由，交叉段中由 B换来的数，如换来的数，如4 10 3，在，在A中其它位相同的数进行中其它位相同的数进行 反换位，即反换位，即4换为换为5，10换为换为6，3换为换为7；对个体；对个体B， 交叉段中由交叉段中由A换来的数，如换来的数，如5 6 7，在，在B中其它位相同中其它位相同 的数进行反换位，即的数进行反换位，即5换为换为4，6换为换为10，7换为换为3。这。这 样，得到：样，得到： A= 9 8 5 4 10 3 1 7 2 6 B= 8 3 1 5 6 7 2 9 10 4 遗传算法遗传算法 3.2 交叉采用交叉采用有序交叉有序交叉策略策略 例如