marquee
  • 2018上半年将更新数据库、C++、计算机组成原理、操作系统等文章,谢谢关注~
  • 由于算法限制,搜索时注意简化关键字,谢谢支持~
  • 网站不兼容IE5.0及以下,请使用主流浏览器访问.
  • 试用搜索、标签、分类目录功能发现更多。
  • 变邻域搜索算法(Variable Neighborhood Search,VNS)

    先说一下局部搜索:

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

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

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

    过程描述如下:

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

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

    伪代码:

    读者评分
    [评分人数: 0 平均分: 0]

    评论

    OmegaXYZ