遗传算法及其应用.ppt

* 第9章 遗传算法及其应用 9.1 遗传算法的产生与发展 9.2 遗传算法的基本算法 9.3 遗传算法的改进算法 9.4 基于遗传算法的生产调度方法 第五十二页，共88页。 * 9.3 遗传算法的改进算法 9.3.1 双倍体遗传算法 9.3.2 双种群遗传算法 9.3.3 自适应遗传算法 第五十三页，共88页。 * 9.3.1 双倍体遗传算法 1. 基本思想 双倍体遗传算法采用显性和隐性两个染色体同时进行进化，提供了一种记忆以前有用的基因块的功能。 双倍体遗传算法采用显性遗传。 双倍体遗传延长了有用基因块的寿命，提高了算法的收敛能力，在变异概率低的情况下能保持一定水平的多样性。 第五十四页，共88页。 * 9.3.1 双倍体遗传算法 2. 双倍体遗传算法的设计 （1）编码/解码：两个染色体（显性、隐性） （2）复制算子：计算显性染色体的适应度，按照显性染色体 的复制概率将个体复制到下一代群体中。 （3）交叉算子：两个个体的显性染色体交叉、隐性染色体也同时交叉。 （4）变异算子：个体的显性染色体按正常的变异概率变异；隐性染色体按较大的变异概率变异。 （5）双倍体遗传算法显隐性重排算子：个体中适应值较大的染色体设为显性染色体，适应值较小的染色体设为隐性染色体。 第五十五页，共88页。 * 双种群遗传算法程序流程图 第五十六页，共88页。 * 9.3.2 双种群遗传算法 基本思想 在遗传算法中使用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态达到更高的平衡态，有利于算法跳出局部最优。 多种群遗传算法：建立两个遗传算法群体，分别独立地运行复制、交叉、变异操作，同时当每一代运行结束以后，选择两个种群中的随机个体及最优个体分别交换。 第五十七页，共88页。 * 9.3.2 双种群遗传算法 2. 双种群遗传算法的设计 （1）编码/解码设计 （2）交叉算子、变异算子 （3）杂交算子 设种群A与种群B，当A与B种群都完成了选择、交叉、变异算子后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，以打破平衡态。 第五十八页，共88页。 * 双种群遗传算法程序流程图 第五十九页，共88页。 * 9.3.3 自适应遗传算法 1. 基本思想 Srinvivas M.，Patnaik L. M.等在1994年提出一种自适应遗传算法(adaptive genetic algorithms，AGA)： 能随适应度自动改变。 AGA：当种群各个体适应度趋于一致或者趋于局部最优时，使 增加，以跳出局部最优；而当群体适应度比较分散时，使 减少，以利于优良个体的生存。 同时，对于适应度高于群体平均适应值的个体，选择较低的 ，使得该解得以保护进入下一代；对低于平均适应值的个体，选择较高的 值，使该解被淘汰。 第六十页，共88页。 * 9.3.3 自适应遗传算法 2. 自适应遗传算法的步骤 （1） 编码/解码设计。 （2） 初始种群产生：N（N 是偶数）个候选解，组成初始解集。 （3） 定义适应度函数为 ，计算适应度 。 （4） 按轮盘赌规则选择N 个个体，计算 。 （5）将群体中的各个个体随机搭配成对，共组成N/2对， 对每一对个体，按照自适应公式计算自适应交叉概率 ，随机产生R(0,1)，如果 则对该对染色体进行交叉操作。 第六十一页，共88页。 * 2. 自适应遗传算法的步骤（续） （6）对于群体中的所有个体，共N个，按照自适应变异公式计算自适应变异概率 ，随机产生 R(0,1)，如果 则对该染色体进行交叉操作。 （7）计算由交叉和变异生成新个体的适应度，新个体与父代一起构成新群体。 （8）判断是否达到预定的迭代次数，是则结束；否则转 （4）。 9.3.3 自适应遗传算法 第六十二页，共88页。 * 将目标函数映射成适应度函数的方法(续） 9.2.3 适应度函数 存在界限值预选估计困难或者不能精确估计的问题！ 若目标函数为最大化问题，则 若目标函数为最小化问题，则 ：目标函数界限的保守估计值。 第二十页，共88页。 * 适应度函数的尺度变换 在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题（deceptive problem）。 9.2.3