遗传算法基本原理

遗传算法(Genetic Algorithms简称GA)是由美国Michigan大学的John Holland教授于20 世纪 60 年代末创建的。70 年代De  Jong基于遗传算法的思想在计算机上进行了大量 的纯数值优化计算实验。在一系列研究工作的基础上，80 年代由Goldberg进行归纳总结， 形成了遗传算法的基本框架。它来源于达尔文(Charles  Darwin)的进化论和孟德尔 (G.Mendel)、摩尔根(T.H.Morgan)的遗传学理论，通过模拟自然界遗传机制和生物进化而 形成的一种过程搜索最优解的算法。其特点是几乎不需要所求问题的任何信息而仅需要 目标函数的信息，不受搜索空间是否连续或可微的限制就可找到最优解。依据它的并行 性，非常适用于大规模并行计算机。因此，遗传算法广泛的应用于自动控制、计算科学、 模式识别、工程设计、智能故障诊断、管理科学和社会科学领域，适用于解决复杂的非 线性和多维空间寻优问题。

与许多现有的优化算法相比，遗传算法具有以下优点：

(1) 遗传算法直接以目标函数值为搜索信息，直接处理的对象是决策变量的编码集而 不是决策变量的实际值本身，对函数的性态无要求，搜索过程既不受优化函数连 续性的约束，也没有优化函数必须可导的要求，具有较好的普适性和易扩充性。 同时，我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜 索效率。

(2) 遗传算法采用多点搜索或者说是群体搜索，具有显著的隐含并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。它的并行性表现在两个方面：一 是遗传算法是内在并行的、二是遗传算法的内含并行性。

(3) 遗传算法是一种自适应搜索技术，具有自组织、自适应和学习性(智能性)。遗传 算法消除了算法设计中的一个最大障碍，即需要事先描述问题的全部特点，并要 说明针对问题的不同特点算法应采取的措施，因此，它可用来解决复杂的非结构 化问题，具有很强的鲁棒性。其选择、交叉、变异等运算都是以一种概率方式来 进行，从而增加了搜索过程的灵活性，同时能以很大的概率收敛于最优解，具有 较好的全局优化求解能力

(4) 遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。

基本遗传算法的形式化定义 基本遗传算法可定义为一个 8 元组： SGA = (C, E, P0 , M, Φ, Γ, Ψ, T)式中

C——个体的编码方法； 

E——个体适应度评价函数；

P0 ——初始群体； 

M——群体大小； 

Φ——选择算子； 

Γ——交叉算子； 

Ψ——变异算子； 

T——遗传算法终止条件。