文档介绍：现代机械设计概论 ——遗传算法
2008年12月
1遗传算法概述
2遗传算法基本原理与方法
3遗传算法的应用

遗传算法的概念
遗传算法(ic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最佳解。
遗传算法操作使用适者生存的原则,在潜在的解决方案种群中逐次产生一个近似最优的方案。在遗传算法的每一代中,根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择,产生一个新的近似解。这个过程导致种群中个体的进化,得到的新个体比原个体更能适应环境,就像自然界中的改造一样。
遗传算法的特点
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索法。它与传统的算法不同,大多数古典的优化算法是基于一个单一的度量函数的梯度或较高次统计,以产生一个确定性的试验解序列;遗传算法不依赖于梯度信息,而是通过模拟自然进化过程来搜索最优解,它利用某种编码技术,作用于称为染色体的数字串,模拟由这些串组成的群体的进化过程。
遗传算法的优点
(1)对可行解表示的广泛性。
(2)群体搜索特性。
(3)不需要辅助信息。
(4)内在启发式随机搜索特性。
(5)遗传算法在搜索过程中不容易陷入局部最优,即使在所定义的适应度函数是不连续的、不规则的或有噪声的情况下,也能以很大的概率找到全局最优解。
(6)遗传算法采用自然进化机制来表现复杂的现象,能够快速可靠地解决求解非常困难的问题。
(7)遗传算法具有固有的并行性和并行计算的能力。
(8)遗传算法具有可扩展性,易于同别的技术混合。
遗传算法的缺点
(1)编码不规范及编码存在表示的不准确性。
(2)单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值,这样,计算的时间必然增加。
(3)遗传算法通常的效率比其他传统的优化方法低。
(4)遗传算法容易出现过早收敛。
(5)遗传算法对算法的精度、可信度、计算复杂性等方面,还没有有效的定量分析方法。
遗传算法与传统方法的比较
传统算法
起始于单个点
改善
(问题特有的)
终止?
结束
是
否
遗传算法
起始于群体
改善
(独立于问题的)
终止?
结束
是
否

启发式算法是通过寻求一种能产生可行解的启发式规则,找到问题的一个最优解或近似最优解。该方法求解问题的效率较高,但是具有唯一性,不具有通用性,对每个所求问题必须找出其规则。但遗传算法采用的是不是确定性规则,而是强调利用概率转换规则来引导搜索过程。