【算法】迭代局部搜索(Iterated local search)探幽
原创【算法】迭代局部搜索(Iterated local search)探幽
原创
迭代局部搜索（Iterated Local Search, ILS）
00 目录
- 局部搜索算法
- 简单局部搜索
- 迭代局部搜索
01 局部搜索算法
1.1 什么是局部搜索算法？
局部搜索是解决最优化问题的一种启发式算法。因为对于很多复杂的问题，求解最优解的时间可能是极其长的。因此诞生了各种启发式算法来退而求其次寻找次优解，局部搜索就是其中一种。它是一种近似算法（Approximate algorithms）。
局部搜索算法是从爬山法改进而来的。简单来说，局部搜索算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。局部搜索从一个初始解出发，然后搜索解的邻域，如有更优的解则移动至该解并继续执行搜索，否则返回当前解。
1.2 算法思想过程
局部搜索会先从一个初始解开始，通过邻域动作。产生初始解的邻居解，然后根据某种策略选择邻居解。一直重复以上过程，直到达到终止条件。
不同局部搜索算法的区别就在于：邻域动作的定义以及选择邻居解的策略。这也是决定算法好坏的关键之处。
1.3 什么又是邻域动作？
其实邻域动作就是一个函数。那么，通过这个函数，对当前的最优解s，产生s对应的邻居解的一个集合。比如：
对于一个bool型问题，其当前解为：s = 1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，当将邻域动作定义为互换相邻bit时，得到的邻居解的集合N(s)={0101,1001,1010}.
02 简单局部搜索
在开始我们的迭代局部搜索之前，还是先来给大家科普几个简单局部搜索算法。他们也是基于个体的启发式算法（Single solution）。
2.1 爬山法（HILL-CLIMBING）
干货 | 用模拟退火(SA, Simulated Annealing)算法解决旅行商问题
2.2 模拟退火（SIMULATED ANNEALING）
干货 | 用模拟退火(SA, Simulated Annealing)算法解决旅行商问题
2.3 模拟退火（SIMULATED ANNEALING）
干货|十分钟快速复习禁忌搜索(c++版)
干货 | 十分钟掌握禁忌搜索算法求解带时间窗的车辆路径问题(附C++代码和详细代码注释)
03 迭代局部搜索（Iterated Local Search, ILS）
3.1 介绍
迭代局部搜索属于探索性局部搜索方法（EXPLORATIVE LOCAL SEARCH METHODS）的一种。它在局部搜索得到的局部最优解上，加入了扰动，然后再重新进行局部搜索。
3.2 过程描述
注：下文的局部搜索(或者LocalSearch)指定都是简单局部搜索。指上文介绍的三种中的任意一种。
- 从初始解s中进行局部搜索，找到一个局部最优解s1。
- 扰动s1，获得新的解s2。
- 从新解s2中进行局部搜索，再次找到一个局部最优解s3。
- 基于判断策略，对s3好坏进行判断。选择接受s3作为新解或者回退s2。
- 直到找到满足条件的最优解，不然跳回第二步。
其图解如下：
伪代码如下：
关于其中的接受判断准则，这里采用了模拟退火中的概率函数：
04 代码时间
以下C++代码还是用于求解TSP旅行商问题。至于什么是旅行商问题，读者可以从爬山算法那篇文章了解。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。