变邻域搜索算法(Variable Neighborhood Search,VNS)

先说一下局部搜索:

局部搜索是解决最优化问题的一种启发式算法。对于某些计算起来非常复杂的最优化问题,比如各种NP完全问题,要找到最优解需要的时间随问题规模呈指数增长,因此诞生了各种启发式算法来退而求其次寻找次优解,是一种近似算法(Approximate algorithms),以时间换精度的思想。局部搜索就是其中的一种方法。

变邻域搜索算法的主要思想是:采用多个不同的邻域进行系统搜索。首先采用最小的邻域搜索,当无法改进解时,则切换到稍大一点的邻域。如果能继续改进解,则退回到最小的邻域,否则继续切换到更大的邻域。

变邻域搜索的特点是利用不同的动作构成的邻域结构进行交替搜索,在集中性和疏散性之间达到很好的平衡。其思想可以概括为“变则通”。

过程描述如下:

每变换一次邻域,相对于切换了搜索的地形(landscape)。效果如下:

下面提供两个版本的伪代码:

伪代码:

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注