算法设计与分析_[04] 天牛须算法设计思想分析

原文链接：

/abs/1710.10724​

算法实现：

首先，初始化参数

，分别代表初始解，初始的搜索范围，以及更新步长，且通过原文我们知道：

在迭代求解过程中，首先完全随机地确定一个搜索方向：

（1）

然后沿着该方向及其反方向进行试探：(2)

沿着较好的解的方向更新一定的步长：(3)

这样一次搜索过程就完成了。然后更新下一次迭代使用的搜索范围和步长：(4)(5)

算法流程：

天牛须算法设计思想分析：

首先给出关于下降方向的定义和定理[1]：定义1若存在

，使得对任意的 和 有 ，则称 为 在 处的一个下降方向定理1设函数 在开集 上一阶连续可微，则 为 在 处的一个下降方向的充要条件是

推论1

和至少有一个是下降方向。证明：通过公式（1），我们随机生成了一个搜索方向 ，若 是下降方向，则有 。否则有 ，即 是一个下降方向。同时注意到， 的概率为0。

推论2若

是下降方向，则存在 ，使得 ，有 ，反之，有 成立。证明：在 处做泰勒展开，得到 。当 充分小时，有 成立。

对比推论2和公式(4)(5)， 会比 略大一点。

基于local search思想的迭代过程：

将上述两个公式统一书写，就可以得到公式（3）。

天牛须算法的创新点：

在有理论保证的 local search过程中， 要保证步长

足够小，才能收敛到局部极小点。如果允许 足够大，就有可能跳出局部极小点。天牛须算法破坏了这种步长限制，失去了理论保证，但是也因此具有了全局搜索能力。

天牛须算法可能的改进点：

收敛速度慢：因为下降方向是随机选取的，可以定义一个更高效的搜索的方向。局部搜索能力不足：尤其是在最开始的迭代过程中，不断跳出局部极小，但是并没有对这些局部极小区域进行充分探索，会遗漏发现更好的解的可能性。

参考

^马昌凤 . 《最优化方法及其matlab程序设计》