进化算法的寻优技术应用探索

进化算法（Evolutionary Algorithms，简称EA）泛指基于生物进化原理的各种仿真计算方法的总称，它体现了生物进化中繁殖、变异、竞争和自然选择等四个特征，前述智能优化算法中的遗传算法和免疫进化算法都属于进化算法。

按照达尔文的进化论，地球上每一物种从诞生开始就进入了漫长的进化历程，具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；而具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少，直至消亡。达尔文把这一过程叫做“自然选择，适者生存”。进化论揭示了生物种群从低级到高级、从简单到复杂的进化规律，提出了对物种多样性的动态解释，它是19世纪生物学的重大成就，与之有关的生物进化的研究结论，已得到广泛的接受和应用。

按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性，不同基因组合产生的个体对环境的适应性是不一样，通过基因杂交和突变可以产生对环境适应性更强的后代。经过优胜劣汰的自然选择，适应能力高的基因结构得以保留下来，从而逐渐形成了经典的遗传学染色体理论，它揭示了遗传和变异的基本规律。在一定的环境影响下，生物物种通过自然选择、基因交换和变异等过程进行繁殖生长，构成了生物的整个进化过程。

遗传物质是细胞核中染色体上的有效基因，其中包含了大量的遗传物质。染色体上携带着关于生物性状的物质元素，生物体表现出来的外在特征是对其染色体构成的一种体现。生物进化的本质体现在染色体的改变和改进上，生物体自身形态的变换是染色体结构变化的表现形式。基因组合的特异性决定了生物体的多样性，基因结构的稳定性保证了生物物种的稳定性，而基因的杂交和变异使生物进化成为可能。生物遗传是通过父代向子代传递基因来实现的，而这种遗传信息的改变决定了生物体的变异。

从上述分析可知，生物进化过程的发生需要四个基本条件：

（1）存在有多个生物个体组成的种群。

（2）生物个体之间存在着差异。

（3）生物能够自我繁殖。

（4）不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。

生物群体的进化机制可以分为以下三种基本形式：

（1）自然选择。控制生物体群体行为的发展方向，能够适应环境变化的生物个体具有较高的生存能力，使得它们在种群中的数量不断增加，同时，该生物个体所具有的染色体性状特征在自然选择中得以保留。

（2）杂交。通过杂交随机组合来自父代染色体上的遗传物质，产生不同于它们父代的染色体。

（3）突变。随机改变父代个体的染色体上的基因结构，产生具有新染色体的子代个体。

自然界的生物进化是一个不断循环的过程。在这一过程中，生物群体的自身也在不断完善和发展。可见，生物进化过程的本质是一种优化过程，这给计算科学提供了直接的借鉴。在计算机技术迅猛发展的时代，可以模拟进化过程，创立新的优化计算方法，并把其应用到复杂的领域当中。20世纪60年代以来，生物学的进化论被推广应用于工程领域，形成了一种新型的计算方法——进化算法。进化算法仿效生物学中的进化和遗传的过程，遵循“生存竞争，优胜劣汰”的原则，同时考察多个候选解，淘汰劣质解，鼓励发展优质解，逐步提高解群体的质量，从而逼近所研究问题的最优解。

进化计算包括遗传算法（GA）、进化规划（EP）和进化策略（EP），它们用不同的进化控制模式模拟了生物进化过程，从而形成了这三种具有普遍影响的模拟进化优化计算方法，它们都是以借鉴自然界中生物的进化过程的自适应全局优化搜索过程，三者之间既有相似之处，也有不同之处。表5-1总结了这三种进化算法的主要特点[24]。

表5-1　遗传算法、进化策略、进化规划的主要特点

现有进化计算方法与模型按性质可分为如下几个分支[28，29，55～60]：

（1）用于优化计算的遗传算法，即遗传计算。

（2）偏向以程式表现人工智能行为的遗传编程，它是采用动态的树结构对计算机程序进行编码的一种遗传算法。

（3）基于遗传算法的机器学习，称为遗传学习。目前主要的成果是适应动态环境学习的分类器系统，它是指利用遗传算法进行学习和分类（如故障的实时诊断和系统的实时监控等）的一种方法。

（4）进化神经网络。(www.xing528.com)

（5）偏向数值分析的进化策略。

（6）介于数值分析与人工智能之间的进化规划。

（7）偏向进化的自组织和系统动力学特性的进化动力学。

（8）用于观察复杂系统互动的各种生态模拟系统。

（9）研究人工生命的细胞自动机。

（10）模拟蚂蚁群体行为的蚁元系统。

进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜索算法，其求解的一般过程包括以下步骤[61]：

（1）随机给定一组初始解。

（2）评价当前这组解的性能。

（3）根据（2）的评价结果，从当前解中选择一定数量的解作为基因操作对象。

（4）对所选择的基因进行操作（交叉、变异），得到一组新的解。

（5）返回到（2）对该组新的解进行评价。

（6）若当前解满足要求或进化达到一定的代数，计算结束，否则转向（3）循环进行。

与其他搜索技术（如梯度搜索技术、随机搜索技术、启发式搜索技术和枚举技术）相比，进化算法具有以下特点：

（1）进化算法的搜索过程是从一群初始点开始搜索，而不是从单一的初始点开始搜索。这样大大提高了获得全局最优解的概率。

（2）进化算法使用的是目标函数的评价信息，其具有良好的普适性。

（3）进化算法具有显著的隐式并行性。

（4）进化算法具有很强的鲁棒性。

目前，进化算法作为一种具有自适应调节功能的寻优技术，其独特的性能已在众多领域内获得了成功的应用，着重用于解决结构性优化、非线性优化、并行计算等复杂问题，其中遗传算法的研究最为深入、持久、应用面也最广。