文档介绍：第四章遗传算法
目录
引言
GA的基本概念
Darwin进化论及进化系统模型
Mendel的遗传学说
GA的基本概念与术语
GA的原理
GA的目的
GA的基本原理
GA的算法过程
目录
GA的应用
GA的特点
GA应用的关键
GA在函数优化中的应用
GA在组合优化中的应用
GA的理论分析
GA在智能控制中的应用
GA的发展展望
参考文献
引言
生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种.
例如,在人类的进化过程中,通过“物竞天择、适者生存”自然的选择和淘汰,人类的身、心不断得到进化,逐渐进化成为这地球上的具有最高等智慧的主宰者.
在这个进化过程中,不仅人的身体得到进化,而且人的智慧、智能也在得到进化.
因此,生物的进化过程其实也是一种智能的进化、优化过程,也是一种智能行为.“物竞天择、适者生存”中蕴涵了智能的光辉、蕴涵了优化的思想.
遗传算法(ic Algorithm,GA)就是根据生物进化思想而启发得出的一种智能理论和方法.
它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法,是通过对生物进化的归纳和模拟得到的一种仿生算法.
GA在本质上是一种不依赖具体问题的直接搜索方法,是一种具有普适性的优化方法.
GA的发展历程为:
1965年,Michigan大学的Holland首次提出了人工遗传操作的重要性,并把这些应用于自然系统和人工系统中.
1967年,,并讨论了GA在自动博弈中的应用.
引言
1970年,hio把GA应用于模式识别中.
第一个把GA应用于函数优化的是Hollstien.
而GA的理论和方法的系统性研究开始于1975年,.
这一年是GA研究的历史上十分重要的一年.
Holland在他的著名专著《Adaptation in Natural and Artificial Systems》中系统地阐述了GA的基本理论和方法,并提出了对GA的理论研究和发展极为重要的模式理论(schemata theory).
该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性.
引言
同年,DeJong完成了他的重要论文《遗传自适应系统的行为分析》.
他在该论文中所做的研究工作可看作是GA发展过程中的一个里程碑,这是因为他把Holland的模式理论与他的计算使用结合起来.
1989年Goldberg对GA从理论上,方法上和应用上作了系统的总结.
1990年代以来,,欣起了进化类算法研究和应用的热潮.
引言
GA与其它优化方法相比,具有如下特点:
GA不是直接作用在参变量集上, 而是利用参变量集的某种编码;
GA不是从单个点, 而是在群体中从多个点开始搜索;
GA利用适应值信息, 无需导数或其它辅助信息;
因此对优化问题(函数)的限制较弱,灵活,通用性(普适性)强,有着较广泛的应用领域.
GA利用概率转移规则, 而非确定性规则.
GA在解空间内不是盲目的穷举或完全随机测试,而是一种启发式搜索,效率优于其它算法。
引言
GA的优点:
较容易的和其它方法结合
避免陷入局部最优解
即使在较短的有限时间内,也能获得较好的次优解、满意解.
鲁棒性佳
对优化问题的初始条件(状态)依赖性小。
抗干扰性强。
具有并行计算的特点,可提高计算速度
引言
GA的不足:
No guarantee for optimal solution within finite time
Weak theoretical basis
GA能解决的问题:
优化
NP完全
高度复杂的非线性问题
引言