于继江

(菏泽学院 计算机与信息工程系，山东 菏泽 274015)

0 引言

变邻域搜索算法（VNS, Variable Neighborhood Search）是一种求解优化问题的启发式算法，是有 Hansen 和Mladenovic´首次提出。它的基本思想在搜索过程中系统地改变邻域结构集来拓展搜索范围，获得局部最优解，再基于此局部最优解重新系统地改变邻域结构集拓展搜索范围找到另一个局部最优解的过程。由于VNS在简易性、时效性、人性化和创新性等方面表现突出，若干改进算法已应用于NP难问题的求解中[1-4]。

VNS提出后被应用于很多组合优化问题的求解，许多应用实例也表明了VNS对解决组合优化问题的优越性能[5-7]。对于组合优化问题，一个邻域内的可行解是有限的，因此在局部搜索过程中，是可以计算出邻域内的所有可行解的目标函数值，进而找到邻域内的最优解，即局部最优解。区别于组合优化问题，连续优化问题中的可行解空间是连续的，因此无法找到邻域内所有可行解，也就无法找到局部最优解。

针对上述问题，提出了一种结合序列二次规划法(SQP,Sequential Quadratic Programming)的变邻域搜索方法，并将其应用到无约束连续优化问题中。

1 结合SQP的变邻域搜索算法

SQP是当前公认的处理中、小规模非线性规划问题最优秀的算法之一，它具有良好的局部收敛性和较强的超线性收敛速度。它能快速精确地获取当前点附近的局部极小点。为了较好处理VNS中的局部搜索过程，更快速、更精确得到局部最优解，将SQP结合到VNS中，即应用SQP求解局部搜索过程中的局部最优解。……