遗传算法：种群演化求解优化问题

在20世纪60年代末到20世纪70年代初这短短几年的时间里，来自美国密歇根大学的John Holland教授在其同事、学生们的共同协助下将遗传算法发展为一套较为完整的理论体系和计算方法。自1980年起，随着并行计算机不断普及且计算速度大幅度提高，计算机的计算速度已不再是制约遗传算法发展的主要因素，传统人工智能算法的局限性逐渐显现出来。John Holland教授以解释自然系统中生物复杂的适应过程为切入点，通过模拟生物进化机制建造出人工系统模型，并在随后的二十多年中在理论和实践方面均获得了巨大的进步［165，166］。

随着近几年进化计算的热潮席卷全球以及人工生命研究的兴起，遗传算法被普遍地接受与关注，其在过程控制、工程优化、机器学习、经济预测等方向均获得了成功，引起各领域专家极大的兴趣。

生命的基本特征包括生长、繁殖、新陈代谢和遗传与变异，生命是进化的产物，现代的生物是在长期进化过程中发展起来的。

遗传即人们通常所说的“种瓜得瓜，种豆得豆”，子代根据亲代传递的信息发育、生长，最终其性状将与亲代保持相同或者相似。遗传作为生物的普遍特征保证了物种存在的稳定性。然而子代之间、子代与亲代之间不总是完全相同，这些差异的存在即为变异。变异是随机发生的，变异的累积导致了生命的多样性。自然选择来自繁殖过剩和生存斗争。在生存环境的选择作用和弱肉强食的生存斗争下，适应自然环境的物种得以生存下来，物种的变异朝着适者生存的方向定向地发展，因此其性状也渐渐区别于祖先，最终衍变成新的物种。这种自然选择是一个缓慢、连续且非短期的过程。

现实世界中有许多民族，每个民族都有各自的优缺点。在历史的长河里，通过不断地交流沟通，每个民族打破了自己的平衡态，从而到达各民族之间更高层次的平衡态。

种群由若干染色体带有特征的实体经基因编码后构成，染色体包含多个基因，是遗传物质的主要载体，这些基因的自由组合决定了个体的外观表现。遗传算法即开始于一个可能具有潜在解集的种群。(www.xing528.com)

根据适者生存、优胜劣汰的原理，初代种群会逐代演化，得出更好的近似解，这个过程可以得到与前代种群相比更适应环境的后生代种群。在演化的每一代中，以问题域中个体适应度的大小为依据选择个体，同时通过遗传算子进行组合交叉和变异，得出代表新的解集的种群。最终，寻找到存在于末代种群中的最优个体，将其解码后可获得问题的近似最优解。

遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要的形式。遗传算法的过程如图5－7所示。

图5-7　遗传算法的过程

简单遗传算法的操作主要有3种：选择（selection）、交叉（crossover）、变异（mutation）。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；计算种群中每个个体的适应度值，淘汰低适应度的个体，选择高适应度的个体应用复制、交叉和变异等遗传算子产生下一代种群。再对这个新种群进行下一轮进化，直到满足停止准则。输出种群中适应度值最优的染色体作为问题的解。