加速优化的两种遗传算法1.ppt

1、加速优化的两种遗传算法,0 引言 1 猴王遗传算法 2 最优子种群遗传算法 3 改进的猴王遗传算法 4 结论,2,0 引言,标准遗传算法在换代时将父代个体全部由子代个体代替，这样父代中有较高适应值的个体不能保留下来，会出现进化时的振荡现象。 改进方法一：高适应值个体保留法，即将父代和子代的适应值进行排序，固定种群大小，保留适应值最高的部分个体组成。 改进方法二：最优个体保护策略法，即规定父代的最优个体总是可以生存到下一代，这样以前的最优解不至于丧失。,3,1 猴王遗传算法,连续非线性规划的猴王遗传算法 猴王遗传算法是一种最优个体保护策略法。 生物现象：猴群竞争产生猴王，猴王在猴群中拥有基因遗传

2、绝对优先权。 基本思想：将种群中的个体按目标函数值的大小排序，保留最优个体（猴王）和部分较优个体，引入部分变异染色体更换部分较劣个体，并让最优个体依次与种群中的其他个体进行交叉变异得到下代种群中的新个体。 与传统遗传算法的不同：无需计算适应度函数；无需计算每个个体参与交叉变异的概率。,4,1 猴王遗传算法,优化问题： 适应度函数越大越好，目标函数越小越好； 适应度函数必须是非负的，目标函数没有限制。,5,遗传算法流程图,1 猴王遗传算法,初始化： 产生初始种群：在可行域内随机产生个体，直至初始种群中个体数达到预定的种群规模。 计算初始种群中各个体对应的目标函数值。 初始种群排序：将初始种群内个

3、体按目标函数值升序排列。,6,1 猴王遗传算法,世代进化过程： 复制：设复制概率为r，令k为不超过r N的最大整数，将父代升序序列中的前k个个体直接复制到子代种群，得到子代种群的前k个点。,7,1 猴王遗传算法,世代进化过程： 交叉变异：猴王分别与第(k+1)至第N个个体交叉变异得到子代，并计算各个体对应的目标函数值。,8,1 猴王遗传算法,世代进化过程： 选择：将子代种群内的个体按目标函数值升序排列。,9,1 猴王遗传算法,世代进化过程： 变异：将子代升序序列中排在后面的ib个较劣个体用随机产生的新个体置换，并计算新个体对应的目标函数值；重新将子代个体排序。,10,1 猴王遗传算法,世代进化

4、过程： 变异：将子代升序序列中排在后面的个较劣个体用随机产生的新个体置换，并计算新个体对应的目标函数值；重新将子代个体排序。,11,遗传算法流程图,2 最优子种群遗传算法,12,高适应值个体保留法和最优个体保护策略法（如猴王遗传算法）对于复杂优化问题，容易使种群收敛到局部最优解。 为了提高精度，加快较优个体的产生，并且避免落入局部最优解，提出最优子种群遗传算法。,2 最优子种群遗传算法,13,最优子种群实数编码遗传算法的研究 基本思想： 从某代种群中选出目标函数值最优的若干数量的个体，组成该代最优子种群，并完全复制到子代。子代的最优目标函数值总不高于父代，进化时不会出现振荡现象。 父代中目标函

5、数值较劣的个体与父代中最优子种群中随机选取的个体进行交叉与变异，产生子代的部分个体。 在最优子种群的个体间进行交叉和变异，产生部分个体。,初始化： 与猴王遗传算法相似，但排序产生的是最优子种群而不是猴王。,14,2 最优子种群遗传算法,世代进化过程： 最优子种群的子代的产生： 方法一（复制）：将最优子种群的个体全部复制到子代中。 方法二（复制+交叉变异）：将最优子种群中的最优个体复制到子代；将最优子种群中其余个体分别与最优个体进行交叉变异，得到对应的子代个体。,15,2 最优子种群遗传算法,世代进化过程： 最优子种群的子代的产生：对于简单问题采用方法二可进一步加快得到最优目标的速度。,16,2

6、 最优子种群遗传算法,17,2 最优子种群遗传算法,世代进化过程： 非最优子种群的子代的产生：顺序取出非最优子种群的个体与最优子种群中随机取出的个体交叉变异，得到对应的子代个体。,18,2 最优子种群遗传算法,世代进化过程： 选择：将子代种群内的个体按目标函数值升序排列。,3 改进的猴王遗传算法,19,猴王遗传算法是一种很新颖的遗传算法，对其初步的研究已经显示出一定优越性和潜力。 猴王遗传算法尚存在的不足或待改进的地方是： 有些参数（复制概率、变异调整系数、变异染色体引入比例）要靠人为确定，不够方便； 猴王点附近没有专门的局部寻优机制，影响了整体寻优能力。,3 改进的猴王遗传算法,20,猴王遗

7、传算法的改进 采用精英保留策略代替遗传选择算子，并设计了微爬山算子增强了算法的局部搜索能力，使算法性能有针对性的进一步提高。,3 改进的猴王遗传算法,21,改进的自适应猴王遗传算法 采用自适应的引进随机个体，并且提出了以群体间距方差做为自适应判据，从而在适当的时候引进随机个体。,4 结论,22,对多种测试函数的计算表明： 猴王遗传算法直观易懂、程序简单、参数少、计算量小，是解连续非线性规划问题的有效方法。 最优子种群遗传算法对于多极值问题非常有效，收敛速度快，计算精度高，可得到全局最优解。 但同时，这两种方法选择不同的参数会影响优化问题的求解效果，需要不断地改进。,附录：参考文献,23,郭晨海，谢俊，刘军，等连续非线性规划的猴王遗传算法J江苏大学学报(自然科学版)，2002，23(4)：87-90 黄隽，谢俊最优子种群实数编码遗传算法的研究J徐州师范大学学报(自然科学版)，2005，23(2)：53-56 李宇中，刘红星，张胜猴