文档介绍：遗传算法原理与应用
吴君
2009 年 5 月
提纲
1、遗传算法介绍
2、遗传算法原理及数学基础
3、遗传算法应用
遗传算法起源
遗传算法是由美国的J. Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的,它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
遗传算法介绍
1、智能优化算法
智能优化算法又称为现代启发式算法,是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验,理论上可以在一定的时间内找到最优解或近似最优解。
遗传算法介绍
常用的智能优化算法
(1)遗传算法
(ic Algorithm, 简称GA)
(2)模拟退火算法
(Simulated Annealing, 简称SA)
(3)禁忌搜索算法
(Tabu Search, 简称TS)
……
遗传算法介绍
传统的优化方法(局部优化)
(1)共轭梯度法
(Conjugate Gradient, 简称CG)
(2)拟牛顿法
(Quasi-Newton , 简称QN)
(3)单纯形方法
(Simplex Method)
……
遗传算法介绍
遗传算法介绍
比较:
传统的优化方法
1)依赖于初始条件。
2)与求解空间有紧密关系,促使较快地收敛到局部解,但同时对解域有约束,如可微或连续。利用这些约束,收敛快。
3)有些方法,如Davison-Fletcher-Powell直接依赖于至少一阶导数; 共轭梯度法隐含地依赖于梯度。
全局优化方法
1)不依赖于初始条件;
2)不与求解空间有紧密关系,对解域,无可微或连续的要求。求解稳健,但收敛速度慢。能获得全局最优。适合于求解空间不知的情况
遗传算法介绍
⑴选择运算
⑵交换操作
⑶变异
遗传算法的基本运算
遗传算法原理
模拟自然界优胜劣汰的进化现象,把搜索空间映射为遗传
空间,把可能的解编码成一个向量——染色体,向量的每个
元素称为基因。
通过不断计算各染色体的适应值,选择最好的染色体,获
得最优解。
●选择运算
——从旧的种群中选择适应度高的染色体,放入匹配集(缓冲
区),为以后染色体交换、变异,产生新的染色体作准备。
选择方法——适应度比例法(转轮法)
按各染色体适应度大小比例来决定其被选择数目的多少。
某染色体被选的概率:Pc
xi 为种群中第i个染色体,