常见的遗传算法.ppt

现代机械设计概论 ——遗传算法 2008年12月 1遗传算法概述 2遗传算法基本原理与方法 3遗传算法的应用 1.遗传算法概述 1.1 遗传算法的概念 遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。 遗传算法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境，就像自然界中的改造一样。 1.2 遗传算法的特点 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索法。它与传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数的梯度或较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程。 1.2.1 遗传算法的优点 （1）对可行解表示的广泛性。 （2）群体搜索特性。 （3）不需要辅助信息。 （4）内在启发式随机搜索特性。 （5）遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、不规则的或有噪声的情况下，也能以很大的概率找到全局最优解。 （6）遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题。 （7）遗传算法具有固有的并行性和并行计算的能力。 （8）遗传算法具有可扩展性，易于同别的技术混合。 1.2.2 遗传算法的缺点 （1）编码不规范及编码存在表示的不准确性。 （2）单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。 （3）遗传算法通常的效率比其他传统的优化方法低。 （4）遗传算法容易出现过早收敛。 （5）遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效的定量分析方法。 1.3 遗传算法与传统方法的比较 1.3.1遗传算法与启发式算法的比较 启发式算法是通过寻求一种能产生可行解的启发式规则，找到问题的一个最优解或近似最优解。该方法求解问题的效率较高，但是具有唯一性，不具有通用性，对每个所求问题必须找出其规则。但遗传算法采用的是不是确定性规则，而是强调利用概率转换规则来引导搜索过程。 1.3.2 遗传算法与爬山法的比较 爬山法是直接法、梯度法和Hessian法的通称。爬山法首先在最优解可能存在的地方选择一个初始点，然后通过分析目标函数的特性，由初始点移到一个新的点，然后再继续这个过程。爬山法的搜索过程是确定的，容易产生局部最优解；而遗传算法是随机的。其主要差别为： （1）爬山法的初始点仅一个，由决策者给出；遗传算法的初始点有多个，是随机产生的。 （2）爬山法由上一个点产生一个新的点；遗传算法在当前的种群中经过交叉、变异和选择产生下一代种群。对同一问题，遗传算法花费的机时少。 1.3.3 遗传算法与穷举法的比较 穷举法就是对解空间内的所有可行解进行搜索，但是通常的穷举法并不是完全穷举法，即不是对所有解进行尝试，而是有选择地尝试，如动态规划法、限界剪枝法。对于特殊的问题，穷举法有时也表现出很好的性能。但一般情况下，对于完全穷举法，方法简单可行，但求解效率太低；对于动态规划法、限界剪枝法，则鲁棒性不强。相比较而言，遗传算法具有较高的搜索能力和极强的鲁棒性。 1.3.4 遗传算法与盲目随机法的比较 与上述的搜索法相比，盲目随机搜索法有所改进，但是它的搜索效率仍然不高，并且只有解在搜索空间中形成紧致分布时，它的搜索才有效。而遗传算法为导向随机搜索方法，是对一个被编码的参数空间进行高效搜索。 经上面的探讨，可以看到遗传算法与传统优化方法在本质上有着不同之处，主要有以下几点： （1）遗传算法搜索种群中的点是并行的，而不是单点。 （2）遗传算法并不需要辅助信息或辅助知识，只需要影响搜索方向的目标函数和相应的适应度。 （3）遗传算法使用概率变换规则，而不是确定的变换规则。 （4）遗传算法工作使用编码参数集，而不是自身的参数集（除了在实值个体中使用