文档介绍：硕士研究生课程?信息学院遗遗传传算算法法 0871-5031301 January 19, 2017 智能控制 2 / 16 ******@ynu. ?信息学院遗传算法简称 GA( ic Algorithms )是1962 年由美国 Michigan 大学的 Holland 教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。遗传算法是以达尔文的自然选择学说为基础发展起来的。遗传算法的基本原理遗传算法的基本原理简简介介遗传算法 0871-5031301 January 19, 2017 智能控制 3 / 16 ******@ynu. ?信息学院自然选择学说包括以下三个方面: (1 )遗传:这是生物的普遍特征,亲代把生物信息交给子代,子代总是和亲代具有相同或相似的性状。生物有了这个特征,物种才能稳定存在。(2 )变异:亲代和子代之间以及子代的不同个体之间的差异,称为变异。变异是随机发生的,变异的选择和积累是生命多样性的根源。(3 )生存斗争和适者生存:具有适应性变异的个体被保留下来,不具有适应性变异的个体被淘汰,通过一代代的生存环境的选择作用,性状逐渐逐渐与祖先有所不同, 演变为新的物种。遗传算法的基本原理遗传算法的基本原理简简介介遗传算法 0871-5031301 January 19, 2017 智能控制 4 / 16 ******@ynu. ?信息学院遗传算法将“优胜劣汰,适者生存”的生物进化原理引入优化参数形成的编码串联群体中,按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使适适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。遗传算法的算法简单,可并行处理,并能到全局最优解。遗传算法的基本原理遗传算法的基本原理基本思想基本思想遗传算法 0871-5031301 January 19, 2017 智能控制 5 / 16 ******@ynu. ?信息学院遗传算法的基本操作为: (1)复制( Reproduction Operator ) 复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。复制操作可以通过随机方法来实现。首先产生 0~1 之间均匀分布的随机数,若某串的复制概率为 40% ,则当产生的随机数在 ~ 之间时,该串被复制,否则被淘汰。遗传算法的基本操作遗传算法的基本操作操操作作遗传算法 0871-5031301 January 19, 2017 智能控制 6 / 16 ******@ynu. ?信息学院(2)交叉( Crossover Operator ) 复制操作能从旧种群中选择出优秀者,但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象,通过两个染色体的交换组合,来产生新的优良品种。交叉的过程为:在匹配池中任选两个染色体,随机选择一点或多点交换点位置;交换双亲染色体交换点右边的部分,即可得到两个新的染色体数字串。遗传算法遗传算法的基本操作遗传算法的基本操作操操作作 0871-5031301 January 19, 2017 智能控制 7 / 16 ******@ynu. ?信息学院交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法,应用较广。它是指染色体切断点有一处,例: 0101 01100 1 1110 101100 :? A 1110 001010 0101 001010 :? B 遗传算法遗传算法的基本操作遗传算法的基本操作操操作作 0871-5031301 January 19, 2017 智能控制 8 / 16 ******@ynu. ?信息学院(3)变异(Mutation Operator) 变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变, 它以很小的概率随机地改变遗传基因(表示染色体的符号串的某一位)的值。在染色体以二进制编码的系统中,它随机地将染色体的某一个基因由 1 变为 0 ,或由 0 变为 1。遗传算法遗传算法的基本操作遗传算法的基本操作操操作作 0871-5031301 January 19, 2017 智能控制 9 / 16 ******@ynu. ?信息学院若只有选择和交叉,而没有变异,则无法在初始基因组合以外的空间进行搜索,使进化过程在早期就陷入局部解而进入终止过程,从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解,必须采用变异操作。遗传算法遗传算法的基本操作遗传算法的基本操作操操作作 0871-5031301 January 19, 2017 智能控制 10