遗传算法与局域搜索法对数值优化性能之比

摘 要：简要阐述了遗传算法及局域搜索法的基本原理，采用MATLAB语言编制的程序来实现遗传算法和局域搜索法，并通过实例比较了两种优化方法对数值优化性能的优劣。
关键词： 遗传算法； 局域搜索法； MATLAB

1 引言
局域搜索算法是基于贪婪思想利用领域函数进行搜索的，它通常可描述为：从一个初始解出发，利用领域函数持续地在当前解的领域中搜索比它好的解。若找到这样的解，用其替代当前解作为新的当前解，继续同样的搜索行为。爬山方法就是一种典型的局域搜索技术[1，2]。
遗传算法是以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的搜索算法。选择、交叉和变异是遗传算法的三个主要操作算子。其操作步骤[3]如下：
（1）在一定编码方案下，随机产生一个初始种群；
（2） 用相应的解码方法将编码后的个体转换成问题空间的决策变量，并求个体的适应值；
（3） 按照个体适应值的大小，从种群中选出适应值较大的一些个体构成交配池；
（4）由交叉和变异这两个遗传算子对交配池中的个体进行操作，并形成新一代的种群；
（5） 反复执行步骤2~4，直至满足收敛判据为止。
基本流程如图1所示：

分析上面原理可见，局域搜索法具有较好的通用性，适用于各种优化问题的求解。但对于求解多峰函数优化问题，能否搜索到全局最优解，以及算法计算效率等问题与初始解的选择和领域结构的设计存在着直接关系。而遗传算法使用的是随机操作，同时搜索过程是从问题解的一个集合开始的，而不是从单个个体开始的，具有隐含并行搜索特性，从而大大减小了陷入局部极小值的可能。
2 基于MATLAB的遗传算法和局域搜索法的 实现
本文采用的遗传算法的主程序gasim.m[4]由Juha Haataja编制，它是借助于MATLAB语言实现的。其中主程序中包含了遗传算法的三个主要操作算子(选择、交叉和变异)的实现。编码采用实数编码方式。在具体运用中，只要用户输入种群大小(npop)、变量个数(nvar)、进化最大代数(genNr)、交叉率(crossProb)、变异率(mutProb)等参数就可以开始运行。
为了验证基于MATLAB设计的遗传算法比局域搜索法具有更强的全局寻优能力，现举例验证。考虑二维Rosenbrock性能测试函数：

其最优解x*＝(1 ，1)，最优值f （x）＝0。
程序编制如下：
（1） 首先编制目标函数文件rosenbrock.m；
（2）调用主程序gasim.m进行遗传算法运算；
（3）编制局域搜索法程序，以便进行比较。
3 结果与比较
图2~5为遗传算法的结果示意图。其中图2表示在所有运行次数（n =100）中，最终种群为最好结果时，其最佳个体的适应度值与平均适应度值随进化代数变化的情况；图4则用立体图表示了这一情况，其中左图表示初始种群中个体的分布情况，右图则为最终种群的个体分布情况。而图3和图5分别对应于图2和图4，表示最终种群为最差时的示意图。

分别分析图2~5，可以看出在最好情况下(图2，4)，在第15代时就已接近找到了全局最优点；而对于最差情况下(图3，5)，经过200次遗传代数后，其能达到的最优函数值接近5000，与实际最优函数值0相差甚远，因此在最差情况下未能找到全局最优点。但最后运行结果显示，遗传算法的寻优成功率为94%(即在运行100次中有94次能找到函数的全局最优点)，因而其可信度还是非常高的。可以想象，如果增加每一次运行时的最大进化代数(genNr)，成功率还会更大，但所需时间也会更长。表1列出了遗传算法和局域搜索法对Rosenbrock函数进行优化计算的性能比较表。

从表1可以看出，在寻优方面，遗传算法所能达到的最优函数值比局域搜索法高出近6个数量级；成功率也多于50个百分点；而且耗时更少。因此，遗传算法要比局域搜索法具有更佳的优化性能。
4 结语
本文介绍了遗传算法和局域搜索法的基本原理，并通过实例比较了两种方法的优劣。结果显示遗传算法具有更好的全局寻优能力、更快的运算速率和更高的成功率，是实际工程优化中强有力的优化方法。

参考文献

[1] 王凌.智能化算法及其应用[M].北京：清华大学出版社，2001.
[2] 李敏强，等.遗传算法的基本理论与应用[M].北京：科学出版社，2002.
[3] 韩帧祥，文福栓，模拟进化优化方法及其应用----遗传算法[J].计算机科学，1995，22(2)：47-56.
[4] JUHA HATAJA.Using genetic algorithms for optimization:Technology transfer in action [M] . Eurogen99 short Course in Jyvaskyla,1999.

本文关键字：暂无联系方式经验交流，电工技术 - 经验交流