一种函数优化的新算法

柯金霖　付宗涛

【摘 要】在多变量函数优化问题中，使用遗传算法可能出现优化结果不收敛的问题。针对此问题本文提出了一种新的算法，它模仿的是落体碰撞的过程。此算法全局搜索能力较强，且具有强收敛性，可以解决其他算法在特定算例中出现的不收敛问题。

【关键词】函数优化；落体碰撞算法；遗传算法；收敛性

0 引言

利用遗传算法进行优化时，其局部搜索能力较弱[1]，收敛性速度慢[2]是常见问题。在研究多变量函数优化时，常常会碰到不收敛的情况。针对这个问题，本文提出了一个优化算法——落体算法，该算法模拟落体碰撞过程。本文先介绍新算法的思路和原理，其次通过经典算法测试函数，对算法的正确性和效率性进行验证；最后，通过对比展示新算法的特性以及优缺点。

1 落体碰撞算法优化

1.1 物理解释

通常多变量函数存在非常多的峰值与谷值。函数优化的目的便是寻找最小或最大值的数值和对应自变量。若把函数的极大值和极小值视为“山峰”与“山谷”，则落体在重力和碰撞的作用下会自然趋近于最低点：自由落体过程中机械能守恒，高度不断降低，速度不断增加；而每次碰撞，由于存在机械能损耗，落体会逐渐静止，停止于“谷”中。

1.2 主要参数

以上过程涉及几个参数：

a）落体个数：即选取初始点，其参考标准是函数的“谷”的数目，如果定义域只有一个谷，理论上只需取一个点数。而实际情况较为复杂，可以采用试取的方式，选定初始点数进行计算，若是结果较好且基本不变化，则可基本认定试取数目得当，否则需要加大点个数；

b） 时间步长：当一次碰撞完成后，落体何时何地达到下一碰撞点，这个判断过程采用的是以时间步长为参考的运动积累过程；

c） 碰撞次数：整个寻优过程中的碰撞次数，即算法的收敛性；

d） 重力加速度：决定碰撞速度的一个重要参数；

e）法向和切向速度恢复系数：每次碰撞过程中，速度的两个方向分量的恢复系数，不宜小于0.9，否则碰撞会过早停止，但是亦不能太接近于1，否则会增加计算量。

f） “碰壁”和“触地”：这两个过程是算法核心步骤，而且必须要先判断“碰壁”再判断“触地”。“碰壁”不是一次落体碰撞过程的结束，而只是中间过程，“触地”才是一次落体碰撞过程结束。“碰壁”过程中可认为是完全弹性碰撞，不需要追究能量损耗的问题，可以把这个过程的恢复系数设为1。

1.3 算法测试

本文选取了三个测试函数编写相应MATLAB程序来验证其正确性[3]，并与遗传算法进行对比。表1所列为测试结果的主要内容。

上述遗传算法结果是利用MATLAB遗传算法工具箱获得，初始个数大部分采用默认，小部分则根据函数情况进行了调整。从上表可以看出，落体算法能收敛到最优解附近，但是收敛精度不一定够高，而遗传算法如果能够收敛，则其收敛精度会好很多。但是从Schwefel函数看出，遗传算法存在收敛到局部最优解的问题。

从表中还可以看出各个参数对运行结果的影响。

（1）点个数：通常情况下个体越多越容易得到全局最优解，但同时数目大小与运算耗时基本呈正比关系。Rastrigin Fuction和Hump Function函数中，个体数目为100，基本可以满足结果收敛于最优解的要求。

（2）最大碰撞次数：从表中可以看出，Schwefe Function在50次碰撞左右，其收敛状况就很好，其余两例在150次后也趋向收敛。这是由于在后期的落体碰撞过程中，法向速度趋近于竖直方向，水平方向的运动较少。随着碰撞速度的减小，落体过程的时间也在缩短，这代表程序耗时逐渐减少。

2 总结

落体算法的主要优点除了其有较好的全局搜索能力之外，还有就是其克服了收敛性问题。这些优点很好地弥补了很多优化方法。但是该算法也存在着缺点，主要为收敛精度不高和计算效率低两个问题，有待后续进一步研究。

【参考文献】

[1]Prügel-Bennett.A.：When a Genetic Algorithm Outperforms Hill-Climbing. Theoretical Computer Science.Vol. 320.（2004）135-153.

[2]王銀年.遗传算法的研究与应用——基于3PM交叉算子的退火遗传算法及应用.江南大学硕士论文.2009.

[3]陈杰，等.MATLAB宝典[M].北京：电子工业出版社，2010.

[责任编辑：朱丽娜]