遗传算法的实例精品文稿.ppt
遗传算法的实例第1页，本讲稿共19页遗传算法(GA)的肇始“活的有机体是解决问题的专家。它们所表现出来的各种才能足以使最好的计算机程序自惭形秽。这种现象尤其令计算机科学家们感到痛楚。计算机科学家们为了某种算法可能花费数月乃至数年的脑力劳动，而有机体则能通过进化和自然选择这样一种显然并非定向进行的机制获得这种能力。”-John Holland第2页，本讲稿共19页遗传算法的思想Darwin的进化论 -“自然选择、适者生存”特定环境的考验种群中个体的选择选择种群中的交叉交叉繁殖种群中个体的变异变异 上述操作反复执行，个体逐渐优化第3页，本讲稿共19页遗传算法的手工模拟计算示例遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各 个主要执行步骤。个主要执行步骤。例：求下述二元函数的最大值：例：求下述二元函数的最大值：max f(x1,x2)=x12+x22 s.t.x1 1,2,3,4,5,6,7 x2 1,2,3,4,5,6,7 (1)(1)个体编码个体编码个体编码个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1,x2 编码为一种编码为一种 符号串。符号串。本题中，用无符号二进制整数来表示。本题中，用无符号二进制整数来表示。因因 x1,x2 为为 1 7之间的整数，所以分别用之间的整数，所以分别用3位无符号二进制整数来表示，将它位无符号二进制整数来表示，将它 们连接在一起所组成的们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可位无符号二进制数就形成了个体的基因型，表示一个可 行解。行解。例如，基因型例如，基因型 X101110 所对应的表现型是：所对应的表现型是：x 5，6。个体的表现型个体的表现型x和基因型和基因型X之间可通过编码和解码程序相互转换。之间可通过编码和解码程序相互转换。第4页，本讲稿共19页(2)(2)初始群体的产生初始群体的产生初始群体的产生初始群体的产生 遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始 群体数据。群体数据。本例中，群体规模的大小取为本例中，群体规模的大小取为4，即群体由，即群体由4个个体组成，每个个体可通过随机个个体组成，每个个体可通过随机 方法产生。方法产生。如：如：011101，101011，011100，111001 (3)(3)适应度汁算适应度汁算适应度汁算适应度汁算 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传 机会的大小。机会的大小。本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接 利用目标函数值作为个体的适应度。利用目标函数值作为个体的适应度。(4)(4)选择运算选择运算选择运算选择运算 选择运算选择运算(或称为复制运算或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代一般要求适应度较高的个体将有更多的机会遗传到下一代 群体中。群体中。第5页，本讲稿共19页 本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中 的数量。其具体操作过程是：的数量。其具体操作过程是：先计算出群体中所有个体的适应度的总和先计算出群体中所有个体的适应度的总和 fi (i=1.2,M);其次计算出每个个体的相对适应度的大小其次计算出每个个体的相对适应度的大小 fi/fi，它即为每个个体被遗传，它即为每个个体被遗传 到下一代群体中的概率，到下一代群体中的概率，每个概率值组成一个区域，全部概率值之和为每个概率值组成一个区域，全部概率值之和为1；最后再产生一个最后再产生一个0到到1之间的随机数，依据该随机数出现在上述哪一个概率区之间的随机数，依据该随机数出现在上述哪一个概率区 域内来确定各个个体被选中的次数。域内来确定各个个体被选中的次数。0124%24%17%35%1#2#3#4#个体编号个体编号初始群体初始群体p(0)适值适值占总数的百分比占总数的百分比总和总和1234011101101011011100111001343425500.240.240.170.351431选择次数选择次数选择结果选择结果1102011101111001101011111001 x1 x2 3 5 5 3 3 4 7 1第6页，本讲稿共19页(5)(5)交叉运算交叉运算交叉运算交叉运算 交叉运算是遗传算法中交叉运算是遗传算法中产生新个体产生新个体的主要操作过程，它以某一概率相互交换某的主要操作过程，它以某一概率相互交换某 两个个体之间的部分染色体。两个个体之间的部分染色体。本例采用单点交叉的方法，其具体操作过程是：本例采用单点交叉的方法，其具体操作过程是：先对群体进行随机配对；先对群体进行随机配对；其次随机设置交叉点位置；其次随机设置交叉点位置；最后再相互交换配对染色体之间的部分基因。最后再相互交换配对染色体之间的部分基因。选择结果选择结果01 110111 10011010 111110 01配对情况配对情况交叉点位置交叉点位置个体编号个体编号12341-23-41-2：23-4：4交叉结果交叉结果011001 111101101001111011 可以看出，其中新产生的个体可以看出，其中新产生的个体“111101”、“111011”的适应度较原来两个个体的适应度较原来两个个体 的适应度都要高。的适应度都要高。第7页，本讲稿共19页(6)(6)变异运算变异运算变异运算变异运算 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进 行改变，它行改变，它也是产生新个体也是产生新个体的一种操作方法。的一种操作方法。本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，其中的数字表示变异点设置在该基因座处；其中的数字表示变异点设置在该基因座处；然后依照某一概率将变异点的原有基因值取反。然后依照某一概率将变异点的原有基因值取反。对群体对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。个体编号个体编号1234交叉结果交叉结果011001 111101101001111011变异结果变异结果变异点变异点4526011101 111111111001111010子代群体子代群体p(1)011101 111111111001111010第8页，本讲稿共19页 从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得 到了明显的改进。事实上，这里已经找到了最佳个体到了明显的改进。事实上，这里已经找到了最佳个体“111111”。注意注意注意注意 需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中 有可能需要一定的循环次数才能达到这个最优结果。有可能需要一定的循环次数才能达到这个最优结果。个体编号个体编号子群体子群体p(1)适值适值占总数的百分比占总数的百分比总和总和1234011101 111111111001111010349850530.140.420.210.232351 x1 x2 3 5 7 7 7 1 7 2第9页，本讲稿共19页算法流程图算法流程图第10页，本讲稿共19页TSP问题的遗传算法求解步骤一：个体编码及种群初始化步骤二：适应度选择步骤三：交叉操作步骤四：变异操作步骤五：重复二、三、四步，直至结束 令城市(点)数目为 N第11页，本讲稿共19页个体编码 取长度为N的数字串，串中数字互不重复，取值范围为1,N之间的整数。则每一个数字串代表一个个体，个体中数字出现的位置表征路径中城市出现的顺序。初始种群 令种群中有 M 个个体，可随机产生 M 个数字 串构成初始种群。例如：将数字串 1234N 上的数字进行随机的交换步骤一：初始化第12页，本讲稿共19页适应度的计算步骤二：适应度选择12345对于个体 ，适应度为：被选中作为父个体的概率：第13页，本讲稿共19页TSP中交叉算子的特点 要保证生成的解为有效解 从一个父个体中随机选取一段子串A，在另一个父个体中将A中出现的数字去掉形成串B，AB为一个子串步骤三：交叉操作此外还有多种交叉算子第14页，本讲稿共19页常用的变异操作：随机选取两个相邻位置的数字，交换其顺序。51243(5)51234(5)步骤四：变异操作1234512345交换3,4此外还有多种变异算子第15页，本讲稿共19页反复执行步骤二、三、四结束判定：步骤五：第16页，本讲稿共19页仿真运行结果第17页，本讲稿共19页遗传算法的总体评价优点 解决问题的方法具有普适性 全局收敛性（依概率收敛）能解决的问题范围很广不足 求得的解为近似的数值解 对于经典数学可以解决的问题，效率较低第18页，本讲稿共19页谢谢老师的指导！第19页，本讲稿共19页
