文档介绍：第10章智能算法及其应用
随着优化理论的发展,一些智能算法成为解决传统系统辨识问题的新方法,如遗传算法、蚁群算法、粒子群算法、差分进化算法等。
都是通过模拟揭示自然现象来实现的。
本章介绍遗传算法的基本概念和方法。
2
遗传算法的基本原理
遗传算法简称GA(ic Algorithms)是1962年由美国Holland教授提出的模拟自然界生物进化机制的一种并行随机搜索最优化方法。
遗传算法是以达尔文的自然选择学说为基础,包括以下三个方面:
3
(1)遗传:亲代把生物信息交给子代,子代总是和亲代具有相同或相似的性状。生物有了这个特征,物种才能稳定存在。
(2)变异:亲代和子代之间以及子代的不同个体之间的差异,称为变异。变异是随机发生的,变异的选择和积累是生命多样性的根源。
(3)生存斗争和适者生存:具有适应性变异的个体被保留下来,不具有适应性变异的个体被淘汰,通过一代代的生存环境的选择作用,性状逐渐与祖先有所不同,演变为新的物种。
4
遗传算法引入“优胜劣汰,适者生存”的生物进化机制,按所选择的适应度函数对个体进行筛选。
适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。
周而复始,使群体中个体适应度不断提高,直到满足一定的条件。
遗传算法可并行处理,得到全局最优解。
5
遗传算法的基本操作为:
(1)复制(Reproduction Operator)
从旧种群中选择生命力强的个体产生新种群。
通过随机方法实现。若设定复制概率阈值为40%,~1之间时,该个体被复制到子代,否则该个体被淘汰。
6
(2)交叉(Crossover Operator)
通过两个染色体的交换组合产生新的优良个体。
任选两个染色体,随机选择一点或多点交换点位置;交换双亲染色体在交换点右边的部分,即可得到两个新的染色体数字串。
有一点交叉、多点交叉等。
一点交叉:染色体断点仅有一处,例:
7
一点交叉示意图
8
(3)变异(Mutation Operator)
模拟基因突变现象,以小概率随机改变遗传基因的值。
在染色体以二进制编码的系统中,它随机地将染色体的某一个基因位由1变为0,或由0变为1。
优点:可使进化过程逃离局部最优解。
1011 0011 1011 1011
9
遗传算法的特点
(1)对参数编码进行操作,而非对参数本身。因此,在参数优化过程中可借鉴生物学中染色体和基因等概念,模仿生物进化等机理;
(2)同时使用多个搜索点的搜索信息。传统方法往往是从解空间的单个初始点开始最优解的迭代搜索过程,效率不高,有时甚至会陷入局部最优解而停滞不前。以群体为基础进行搜索,效率高。
10
(3)遗传算法直接以目标函数作为搜索信息,无需目标函数的导数值等其他一些辅助信息。适用于目标函数无法求导数或导数不存在的优化问题,或者组合优化问题等。
(4)遗传算法使用概率搜索技术。各种操作:选择、交叉、变异等都是以概率的方式进行的。
(5)遗传算法在解空间进行高效启发式搜索,而非盲目地穷举或完全随机搜索;