遗传算法简述.ppt

于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）第30页，共80页，星期日，2025年，2月5日第三代种群S3中各染色体的情况染色体适应度选择概率积累概率估计的选中次数s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001第31页，共80页，星期日，2025年，2月5日设这一轮的选择-复制结果为：s1’=11100（28）,s2’=11100（28）s3’=11000（24）,s4’=10011（19）做交叉运算，让s1’与s4’，s2’与s3’分别交换后两位基因，得s1’’=11111（31）,s2’’=11100（28）s3’’=11000（24）,s4’’=10000（16）这一轮仍然不会发生变异。第32页，共80页，星期日，2025年，2月5日于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）第33页，共80页，星期日，2025年，2月5日显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。第34页，共80页，星期日，2025年，2月5日YYy=x28131924X第一代种群及其适应度y=x212162527XY第二代种群及其适应度y=x29192428XY第三代种群及其适应度y=x216242831X第四代种群及其适应度第35页，共80页，星期日，2025年，2月5日例1.2用遗传算法求解TSP。分析由于其任一可能解——一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中有哪些信誉好的足球投注网站最佳解。这正适合用遗传算法求解。第36页，共80页，星期日，2025年，2月5日（1）定义适应度函数我们将一个合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是第37页，共80页，星期日，2025年，2月5日（2）对个体s=（c1,c2,…,cn,cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。第38页，共80页，星期日，2025年，2月5日然后进行遗传操作。设s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）实施常规的交叉或变异操作，如交换后三位，得s1’=（A,C,B,C,B,A），s2’=（A,E,D,E,D,A）或者将染色体s1第二位的C变为E，得s1’’=（A,E,B,E,D,A）可以看出，上面得到的s1’，s2’和s1’’都是非法的城市序列。第39页，共80页，星期日，2025年，2月5日为此，对TSP必须设计合适的染色体和相应的遗传运算。事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异