试谈高职高职常用优化算法对比分析

摘要：智能优化在现代决策中发挥着越来越重要的作用，本文介绍了四种适合高职学生使用的智能优化算法，并对这四种算法的性能进行了比较分析，以便决策时可以根据实际问题选择合适的算法。
关键词：高职；优化算法；粒子群；禁忌
1672-5727（2013）11-0142-02
最优化问题是在有限或无限种可行方案（决策）中挑选最优的方案（决策）。随着高新技术、计算机及信息技术的不断发展，优化在工农业、国防、交通、金融、能源、通信等众多领域的应用越来越广泛。优化方法也得到了长足发展，从传统的利用梯度信息计算最优值，到现代启迪式算法计算最优值，优化算法的种类越来越多，解决的问题越来越复杂，在实际问题的解决中发挥的作用也越来越大。
高职学生对优化算法的接触普遍较少，但是在实际问题的解决中，一些较简单的优化算法不仅能较好地解决复杂问题，而且可以提高问题的解决效率。笔者拟介绍几种常用的比较简单的优化算法，并对其性能进行比较分析。
几种优化算法的基本思想
对于多元函数而言，最优值一般都会取在梯度为零的点附近。因此，传统的优化算法就是利用梯度信息来求函数的最优值，常用的方法有最速下降法、牛顿法等。随着实际问题规模的扩大、复杂程度的增加，很多问题的梯度比较难计算，随之产生了启迪算法，如遗传算法、粒子群算法、禁忌搜索算法、模拟退火算法等。

(一)最速下降算法

(二)阻尼牛顿法

(三)粒子群算法

标准粒子群优化算法的计算步骤如下：（1）在可行域内，对粒子群进行随机初始化，包括随机初始位置和速度。（2）计算每个粒子的适应度值。（3）对于每个粒子，将其适应度值与所经历过最好位置的适应度值进行比较，如果更好，则将其作为粒子的个体历史最优值，用当前位置更新个体历史最好位置。（4）对每个粒子，将其历史最优适应度值与群体内或邻域内所经历的最好位置的适应度值进行比较，若更好，则将其作为当前的全局最好位置。（5）根据式子（1）、（2）对粒子的速度和位置进行更新。（6）若达到终止条件，则停，否则，转（2）。一般将终止条件设定为一个足够好的适应值或达到一个预设的最大迭代次数。

(四)禁忌搜索算法

禁忌搜索算法是一种亚启发式搜索算法，所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次的搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。就好比人的短时记忆，走过的路不再重复或有选择地重复；同时“遗忘”又使得这些禁止是弱禁止，即在一定的时间之后这些禁止将失效，最终达到全局优化之目的。
几种算法的比较分析

(一)最速下降算法

该算法是1847年由著名数学家柯西（Cauchy）给出的。它是解析法中最古老的一种，其他解析方法或是它的变形，或是受它的启发而得到的。它的优点在于操作简单，所需存储空间少，对初始点要求较低，在最初阶段的搜索速度快，可以很快到达函数极值附近。但在搜索的最后阶段，由于步长的影响，算法的搜索路线常呈现“锯齿状”，使得算法不能很快达到最优值，而且由于该算法是按照负梯度的方向不断搜索的，当达到函数的某一极值点后，算法很难跳出极值点，从而会使得找到的点只是某个极值点，并不是函数的整体最优点，即算法容易陷入局部最优。该算法是以一次近似来逼近函数的，因此得到的最优解精度不高。因此该算法常用于比较简单的、连续的、单极值目标函数，这一类函数用该算法通常会在很短的迭代次数后产生最优点。或者可以在搜索的初始阶段使用该算法，并在后期结合另一种算法计算。

(二)阻尼牛顿法

该算法是牛顿法的改进。它以函数的二次逼近为基础，因此较之最速下降算法，其搜索精度较高。而且对于严格凸函数，该算法可以搜索到其全局最优解，且有较快的收敛速度。但是该算法对目标函数要求较高，一般需要具有一阶、二阶偏导数，同时其海森阵必须正定且非奇异，在每次迭代中，计算量较大，对于较复杂的目标函数而言，搜索速度会受到严重影响。因而，此算法适用于一些精度要求较高，目标函数的梯度较简单的问题，是传统优化算法中性能较好的一种。

(三)粒子群算法

该算法是由肯尼迪（Kennedy）和埃伯哈特（Eber-hart）于1995年提出的。它操作简单，不需要目标函数的梯度信息，甚至不要求目标函数的连续性，对于复杂函数有很好的优化能力，有较快的收敛速度，且该算法所需参数少，易于实现，是最常用的优化算法之一。通过给定不同的参数值，可以灵活修正算法的搜索速度和收敛精度，且其搜索机制简单，可以很容易地进行算法改进或者与其他算法结合解决大型复杂问题。目前，该算法已广泛应用于函数优化、神经网络训练、模式分类、模糊系统控制，在其他应用领域也受到广泛欢迎。但是基本粒子群算法的稳定性和全局搜索能力较差，很多学者从不同方面对基本粒子群算法进行了改进，如马翠、周先东等人的分层粒子群优化算法，将搜索分为局部和全局同时并行进行；褚国娟、马春丽等人的基于差分及模拟退火的混合粒子群算法，将模拟退火算法与粒子群算法结合，可以更好地提高算法的全局搜索能力。另外，粒子群算法的理论证明较少，参数对算法性能的影响、算法对不同问题解决能力的差异等问题都是通过实验检验的，理论的证明几乎没有，这也是该算法未来研究的方向之一。

(四)禁忌搜索算法

禁忌搜索算法最早由美国工程院院士，科罗拉多大学教授福瑞德·格洛弗（Fred Glover）提出，它是一种亚启发式算法，它在搜索过程中避免重复工作，禁忌当前较优解，可以很好地跳出局部最优，提高算法的搜索精度。同时，该算法所需参数少，操作简单，适合求解较复杂的多极值函数最优值。禁忌搜索算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究。但是，该算法对初始解的依赖性较强，初始解的选取会影响到算法的搜索速度甚至精度。同时，该算法更新机制不是很完善，理论证明方面也很欠缺，因而单独使用时灵活度较差，成功率也较低，通常可以将该算法与其他算法（如粒子群算法）结合，在每次迭代的后期使用禁忌搜索算法，既可保证算法的灵活度，提高其搜索速度，又可提高算法的收敛精度。
综上所述，前两种是传统优化算法，利用梯度信息进行求解，操作简单，经理论证明，对于连续函数有较好的收敛性，但对于梯度信息较复杂甚至无法求梯度的目标函数而言，这两种算法较难实现。后两种算法属于随机搜索的启迪式智能算法，通常是模拟自然界中动物的习性进行优化搜索，算法操作简单，不需要梯度信息，易于实现，较易与其他算法结合，且有很强的解决大型复杂问题的能力，是目前工程、通信等领域广泛使用的智能优化算法。但是现代的很多智能优化算法理论研究方面较薄弱，没有办法严格说明其收敛速度和精度的依赖因素，只能通过大量实验进行验证，这也极大地限制了算法的发展。
参考文献：
陈开周.最优化计算方法[M].西安：西安交通大学出版社，2003：53-55.
徐成贤，陈志平，李乃成.近代优化方法[M].北京：科学出版社，2002：85-88.
[3]Kennedy J，Eberhart R C. Particle swarm optimization[J].Proceedings of IEEE international Conference on Neural Networks，1995：1942-1948.
[4]陈冬芳，薛继伟，张漫.全局最优化算法及其应用[J].大庆石油学院学报，2005（1）：23-25.
[5]马翠，周先东，杨大地.分层粒子群优化算法[J].计算机工程，2009（20）：194-196.
[6]褚国娟，马春丽，宁必锋.基于差分及模拟退火的混合粒子群算法[J].计算机与现代化，2010（5）：19-20.
[7]刘嘉敏，董宗然，马广焜.基于禁忌搜索算法求解集装箱装载问题[J].沈阳工业大学学报，2009（2）：212-216.
[8]张玉芳，薛青松，熊忠阳.基于禁忌搜索的动态粒子群算法[J].计算机工程与应用，2008（24）：56-58.
作者简介：
李辉（1981—），女，陕西宝鸡人，硕士，福建水利电力职业技术学院助教，主要从事基础数学教学及智能优化方面的研究。 摘自：学年论文www.618jyw.com