遗传算法简述.ppt

对编码方式的改进二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题，浮点数编码改善了遗传算法的计算复杂性。第63页,共80页，星期六，2024年，5月对遗传算子的改进排序选择均匀交叉逆序变异（1）对群体中的所有个体按其适应度大小进行降序排序；（2）根据具体求解问题，设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体；（3）以各个个体所分配到的概率值作为其遗传到下一代的概率，基于这些概率用赌盘选择法来产生下一代群体。第64页,共80页，星期六，2024年，5月对遗传算子的改进排序选择均匀交叉逆序变异（1）随机产生一个与个体编码长度相同的二进制屏蔽字P=W1W2…Wn；（2）按下列规则从A、B两个父代个体中产生两个新个体X、Y：若Wi=0，则X的第i个基因继承A的对应基因，Y的第i个基因继承B的对应基因；若Wi=1，则A、B的第i个基因相互交换，从而生成X、Y的第i个基因。第65页,共80页，星期六，2024年，5月对遗传算子的改进排序选择均匀交叉逆序变异变异前：348|7965|21变异前：348|5697|21第66页,共80页，星期六，2024年，5月对控制参数的改进Schaffer建议的最优参数范围是：M=20-100，T=100-500，Pc=0.4-0.9，Pm=0.001-0.01。第67页,共80页，星期六，2024年，5月对控制参数的改进Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰。第68页,共80页，星期六，2024年，5月对执行策略的改进混合遗传算法免疫遗传算法小生境遗传算法单亲遗传算法并行遗传算法第69页,共80页，星期六，2024年，5月分层遗传算法分层遗传算法基本流程框图初始化N个子种群N个子种群独立运行遗传算法一定代数N个结果种群及平均适应度值记录到R[1...N,1...n]及A[i]对R[1...N,1...n]进行选择和交叉对R[1...N,1...n]进行变异操作对新的N个子种群重新开始遗传算法操作性能满足?结束第70页,共80页，星期六，2024年，5月并行遗传算法（parallelGA，PGA）遗传算法中适应度的计算最费时间，再加上需要不断产生新一代，而每一代又有若干个个体，随意如何提高遗传算法的运行速率显得尤为突出。由于遗传算法的内在并行机制，其并行处理是很自然的解决途径。并行遗传算法的实现方案全局型——主从式模式（master-slavemodel）独立型——粗粒度模型（coarse-grainedmodel）；孤岛模型；分布式遗传算法分散型——细粒度模型（fine-grainedmodel）第71页,共80页，星期六，2024年，5月全局型处理方式：并行系统分为一个主处理器和若干个从处理器主处理器监控整个染色体种群，并基于全局统计执行选择操作；各个从处理器接受来自主处理器的个体进行重组交叉和变异，产生新一代个体，并计算适应度，再把计算结果传给主处理器。缺点：适应度评价很费时且远远超过通信时间有效的情况下才有效，否则通信时间超过计算时间，反而会降低速度。这种方法要求同步机制，会导致主进程忙二子进程闲置或反之，引起负载不平衡，效率不高。第72页,共80页，星期六，2024年，5月独立型处理方式：将种群分成若干个子种群并分配给各自对应的处理器，每个处理器不仅独立计算适应度，而且独立进行选择、重组交叉和变异操作，还要定期地相互传送适应度最好的个体，从而加快满足终止条件的要求。特点：基于粗粒度模型的遗传算法也称之为分布式遗传算法，是目前应用最广泛的一种并行遗传算法。第73页,共80页，星期六，2024年，5月分散型处理方式：为种群中的每一个个体分配一个处理器，每个处理器进行适应度