遗传算法的实例.pptVIP

Part 1 Part 1 Part 2 Part 3 Part 4 * Part 2 Part 1 Part 2 Part 3 Part 4 * Part 3 Part 1 Part 2 Part 3 Part 4 * Part 4 Part 1 Part 2 Part 3 Part 4 * Part 5 遗传算法在tsp问题中的应用 汇报人： 老师 ：陈辉 专业 ：计算机技术 遗传算法(GA)的肇始 “ 活的有机体是解决问题的专家。它们所表现出来的各种才能足以使最好的计算机程序自惭形秽。这种现象尤其令计算机科学家们感到痛楚。计算机科学家们为了某种算法可能花费数月乃至数年的脑力劳动，而有机体则能通过进化和自然选择这样一种显然并非定向进行的机制获得这种能力。” --- John Holland 遗传算法的思想 Darwin的进化论 ---- “自然选择、适者生存” 特定环境的考验 种群中个体的选择 种群中的交叉繁殖 种群中个体的变异 上述操作反复执行，个体逐渐优化 遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各 个主要执行步骤。 例：求下述二元函数的最大值： 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) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种 符号串。本题中，用无符号二进制整数来表示。 因 x1, x2 为 1 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它 们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可 行解。 例如，基因型 X＝101110 所对应的表现型是：x＝[ 5，6 ]。 个体的表现型x和基因型X之间可通过编码和解码程序相互转换。 (2) 初始群体的产生 遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始有哪些信誉好的足球投注网站点的初始 群体数据。 本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机 方法产生。 如：011101，101011，011100，111001 (3) 适应度汁算 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传 机会的大小。 本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接 利用目标函数值作为个体的适应度。 (4) 选择运算 选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代 群体中。 本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中 的数量。其具体操作过程是： ? 先计算出群体中所有个体的适应度的总和 ?fi ( i=1.2,…,M ); ? 其次计算出每个个体的相对适应度的大小 fi / ?fi ，它即为每个个体被遗传 到下一代群体中的概率， ? 每个概率值组成一个区域，全部概率值之和为1； ? 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区 域内来确定各个个体被选中的次数。 0 1 24% 24% 17% 35% 1# 2# 3# 4# 个体编号 初始群体p(0) 适值 占总数的百分比 总和 1 2 3 4 011101 101011 011100 111001 34 34 25 50 0.24 0.24 0.17 0.35 143 1 选择次数 选择结果 1 1 0 2 011101 111001 101011 111001 x1 x2 3 5 5 3