局部搜索算法

来源：今日头条

一、定义

局部搜索算法(Local Search Algorithm)是一种用于解决最优化问题的启发式算法，是一类近似算法（Approximate Algorithms）的通称。它从一个(或一组)初始解出发,通过邻域函数生成解的邻域,再在邻域中搜索出更优的解来替换当前解, 使目标函数逐步优化，通过不断地迭代过程实现解的最优化。

二、基本思想与分类

图2-1

局部搜索算法是一种启发式搜索算法，在搜索过程中，始终选择当前点的邻居中向着离目标最接近的方向搜索。目标可以是最大值，也可以是最小值。如果存在解，最优的局部搜索算法总能找到全局最大/最小值。如图2-1，我们的目标是搜索全局最大值。

启发式搜索是与盲目搜索相比而言的，盲目搜索采用的方法，如穷举法、全局随机法等。考察一个算法的性能通常用局部搜索能力和全局收敛能力这两个指标。局部搜索能力是指能够无穷接近最优解的能力，而全局收敛能力是指找到全局最优解所在大致位置的能力。局部搜索能力和全局收敛能力，缺一不可。

不同局部搜索算法的区别就在于：邻域动作的定义和选择邻居解的策略。这也是决定搜索算法集中性和发散性（Intensification and Diversification）好坏的关键。

局部搜索算法分类：

1> 爬山法（Hill-climbing）。其主要缺点是可能会陷入局部最优解，而不一定能搜索到全局最优解。

针对局部邻域搜索，为了实现全局优化，有：

2> 模拟退火法（Simulated annealing）。以可控性概率接受劣解来逃逸局部极小。

3> 禁忌搜索法（Tabu/Taboo Search, TS）。确定性的局部极小跳跃策略。

4> 变邻域搜索法（Variable neighborhood search，VNS）。

采用多个不同的邻域进行系统搜索。首先采用最小的邻域搜索，如果无法改进解，则切换到稍大一点的邻域。如果能继续改进解，则退回到最小的邻域，否则继续切换到更大的邻域。

5> 局部剪枝搜索法。

6> 进化算法。多点并行搜索。

7> 遗传算法等。

三、局部搜索算法优点

局部搜索从当前结点出发，通常只移动到它的邻近状态，不保留路径，根据目标函数寻找最优的状态。局部搜索算法的优点有：

• 将指数时间化为确定性时间，寻求近似解逼近最优解。
• 只用很少的内存。通常情况下，局部搜索不保留搜索过程中经过的路径，换句话说，它不关心实现的路径，而全局搜索则必须保留路径。
• 可对大量NP问题求近似解。
• 在连续的并且状态空间很大甚至无限的问题中，局部搜索通常都可以找到足够好的解，但是这样的问题不适合用全局搜索算法解决。
• 算法通用易实现，且容易理解。

四、对NP问题求近似解

在计算机领域，一般可以将问题分为可解问题和不可解问题。不可解问题也可以分为两类：一类如停机问题，的确无解；另一类虽然有解，但时间复杂度很高。可解问题也分为P问题(Polynomial Problem，多项式问题)和NP问题(Nondeterministic Polynomial Problem，非确定性多项式问题)。

P问题成了区别问题是否可以被计算机求解的一个重要标志。

NP问题是指一个复杂问题不能确定是否在多项式时间内找到答案，但是可以在多项式时间内验证答案是否正确。NP类问题数量很大，如完全子图问题、图着色问题、旅行商问题等。

对NP问题找最优解很困难，时间复杂度都很高，即求解需要大量时间。通常它们的时间复杂度都是指数变量，如

常见的算法时间复杂度由小到大依次为：

时间复杂性函数比较（10亿次/秒）

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

五、邻域的概念

局部搜索算法，依赖于对解空间进行按邻域搜索。

描述算法时需用到邻域的概念。所谓邻域，简单地说就是一个点附近的其它点的集合。

在距离空间，邻域就是以某一点为中心的圆。

在组合优化问题中，邻域一般定义为由给定转化规则对给定的问题域上每结点进行转化所得到的问题域上结点的集合。公式描述如下：

设D是问题的定义域，若存在一个映射N，使得：

则称P= N(S)为S的邻域。 A∈2^D为S的邻居。

邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。

例子1：bool型问题

对解空间进行编码，当前解为s = 1001，当将邻域动作定义为翻转其中一个bit时，得到当前解的邻域N(s)={0001,1101,1011,1000}，其中N(s) ∈ 2^D。同理，当将邻域动作定义为互换相邻bit时，得到当前解的邻域P = N(s)={0101,1001,1010}。

例子2：4皇后问题

如何将 4 个皇后放置在 4×4 的棋盘上，并且使皇后彼此之间不能相互攻击？（在4×4格的国际象棋上摆放4个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。）

如图5-1所示。

图5-1

S={Si}表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。

如四皇后问题的一个解：S=(4, 3, 1, 2)。（这里S表示第1行第4列有一个皇后；第2行第3列有一个皇后；第3行第1列有一个皇后；第4行第2列有一个皇后。）

定义映射N为棋盘上任意两个皇后的所在行或列进行交换，即S中任意两个元素交换位置。

例：当S = (4, 3, 1, 2)时，其邻域为：

P = N(S) = {(3, 4, 1, 2), (1, 3, 4, 2), (2, 3, 1, 4), (4, 1, 3, 2), (4, 2, 1, 3), (4, 3, 1, 2)}

例子3：旅行商问题(TSP, Traveling Salesman Problem)

一个商品推销员要去9个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短？

对解空间按城市编号进行编码，设初始解为s = {2，8，3，5，9，1，4，6，7}。

当前状态的状态产生函数N(S),即邻域可以定义为任意一种方式：

1）互换操作，随机交换两个城市的顺序；

如图5-2所示。新解s = {2，8，1，5，9，3，4，6，7}

图5-2

2）逆序操作，两个随机位置间的城市逆序；

如图5-3所示。新解s = {2，8，3，4，1，9，5，6，7}

图5-3

3）插入操作，随机选择某点插入某随机位置。

如图5-4所示。新解s = {2，3，5，9，9，1，4，6，7}

图5-4

六、局部搜索法具体步骤

普通局部搜索算法-爬山法

1，随机的选择一个初始的可能解X0∈D，Xb=X0，P=N(Xb)，f(X)为目标函数。
2，如果不满足结束条件，则
3，Begin
4，   选择P的一个子集P'，Xn为P'中的最优解
5，   如果f(Xn) < f(Xb)，则Xb ＝ Xn，P = N(Xb)，
          转2；
6，   否则P = P – P'，转2。
7，End
8，输出计算结果
9，结束

该算法缺点：该局部最优问题，也叫局部峰值局部陷井。

现实问题中，f在D上往往有多个局部的极值点。

一般的局部搜索算法一旦陷入局部极值点，算法就在该点处结束，这时得到的可能是一个糟糕的结果。如图6-1中的A点。

图6-1

解决方法：

每次并不一定选择邻域内最优的点，而是依据一定的概率，从邻域内选择一个点。

目标函数优的点，被选中的概率大，目标函数差的点，被选中的概率小。

考虑归一化问题，使得邻域内所有点被选中的概率和为1。

如图6-2，以概率选择邻域的点，有机会跳出局部极值点。

图6-2

局部搜索算法1

1，随机的选择一个初始的可能解X0∈D，Xb=X0，P=N(Xb)，f(X)为目标函数。
2，如果不满足结束条件，则
3，Begin
4，   对于所有的X∈P计算目标函数f(X)，
         并选择适当的概率公式计算每一个点X的概率
5，   依计算的概率值，从P中随机选择一个点
         Xn，Xb ＝ Xn，P = N(Xb)，转2
6，End
7，输出计算结果
8，结束

该算法缺点：步长问题

解决办法

改变步长

局部搜索算法2

1，随机的选择一个初始的可能解X0∈D，Xb=X0，，f(X)为目标函数。
      确定一个初始步长计算P=N(Xb)
2，如果不满足结束条件，则
3，Begin
4，    选择P的一个子集P'，Xn为P'中的最优解
5，    如果f(Xn) < f(Xb)，则Xb ＝ Xn
6，    按照某种策略改变步长，计算P = N(Xb)，
           转2
7，    否则P = P – P'，转2。
8，End
9，输出计算结果
10，结束

该算法缺点：起始点问题

解决办法：

随机的生成一些初始点，从每个初始点出发进行搜索，找到各自的最优解。再从这些最优解中选择一个最好的结果作为最终的结果。

局部搜索算法3

1，k = 0
2，随机的选择一个初始的可能解X0∈D，
     Xb=X0，P=N(Xb)，f(X)为目标函数。
3，如果不满足结束条件，则
4，Begin
5，   选择P的一个子集P'，Xn为P'中的最优解
6，   如果f(Xn) < f(Xb)，则Xb ＝ Xn，P = N(Xb)，转3
7，   否则P = P – P'，转3。
8，End
9，k = k+1
10，如果k达到了指定的次数，则从k个结果中选
        择一个最好的结果输出，否则转2
11，输出结果
12,  结束

小结：

以上几种解决方法可以结合在一起使用，比如第一、第二种方法的结合，就产生了模拟退火方法。

七、案例说明

例1：5城市TSP旅行商问题。

一个商品推销员要去5个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短？

如图7-1所示。

图7-1

设初始的可能解：X0 = (a, b, c, d, e) , f(Xb) = f(X0) = ab+bc+cd+de+ea=7+7+5+6 +13 = 38

通过交换两个城市获得邻域

P = {(a, c, b, d, e), (a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)}

设每次随机从P中选择一个邻居。

第1步，从P中选择一个元素Xn = (a, c, b, d, e), f(Xn) = 42, f(Xn) > f(Xb),

P = P – {Xn}

= {(a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)}

第2步，从P中选择一个元素Xn = (a, d, c, b, e), f(Xn) = 45, f(Xn) > f(Xb),

P = P – {Xn}

= {(a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)}

第3步，从P中选择一个元素Xn = (a, e, c, d, b), f(Xn) = 44, f(Xn) > f(Xb),

P = P – {Xn}

= {(a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)}

第4步，从P中选择一个元素Xn = (a, b, d, c, e), f(Xn) = 44, f(Xn) > f(Xb),

P = P – {Xn} = {(a, b, e, d, c), (a, b, c, e, d)}

第5步，从P中选择一个元素Xn = (a, b, e, d, c), f(Xn) = 34, f(Xn) < f(Xb),

更新当前解Xb=Xn , Xb = (a, b, e, d, c),

按照新解，更新邻域空间P’ = {(a, e, b, d, c), (a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)}

第6步，从P’中选择一个元素Xn = (a, e, b, d, c), f(Xn) = 44, f(Xn) > f(Xb),

P’ = P’ – {Xn}

= {(a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)}

第7步，从P’中选择一个元素Xn = (a, d, e, b, c), f(Xn) = 39, f(Xn) > f(Xb),

P’ = P’ – {Xn}

= {(a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)}

第8步，从P’中选择一个元素Xn = (a, c, e, d, b), f(Xn) = 38, f(Xn) > f(Xb),

P’ = P’ – {Xn}

= {(a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)}

第9步，从P’中选择一个元素Xn = (a, b, d, e, c), f(Xn) = 38, f(Xn) > f(Xb),

P’ = P’ – {Xn} = {(a, b, c, d, e), (a, b, e, c, d)}

第10步，从P中选择一个元素Xn = (a, b, c, d, e), f(Xn) = 38, f(Xn) > f(Xb),

P’ = P’ – {Xn} = {(a, b, e, c, d)}

第11步，从P中选择一个元素Xn = (a, b, e, c, d), f(Xn) = 41, f(Xn) > f(Xb),

P = P – {Xn} = {}

P等于空，算法结束。

得到最终结果为Xb = (a, b, e, d, c), f(Xb) = 34。如图7-2所示，红色标记为最短路径。

图7-2

例子2 皇后搜索算法（Queen Search）

如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击？（在n×n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。）

解：用局部搜索法。

定义S={Si}表示一个可能解，其中Si表示在第i行，第Si列有一个皇后。

如4皇后问题， 设一个初始解：S=(4, 3, 1, 2)。（这里S表示第1行第4列有一个皇后；第2行第3列有一个皇后；第3行第1列有一个皇后；第4行第2列有一个皇后。）

定义映射N为棋盘上任意两个皇后的所在行或列进行交换，即S中任意两个元素交换位置。

随机创建初始解S = (4, 3, 1, 2)，依据映射N，其邻域为：

P = N(S) = {(3, 4, 1, 2), (1, 3, 4, 2), (2, 3, 1, 4), (4, 1, 3, 2), (4, 2, 1, 3), (4, 3, 1, 2)}

任选一个子集P’= {(3, 4, 1, 2)}, 如果没有发生冲突，则P=P-P’ （如果P=0, 冲突仍然不能下降，则重新创建初始解）；否则，更新冲突数，接受新解，获取新解的邻域，再次选择子集。直到冲突数为0，算法结束。

对于n皇后，具体步骤如下

1，随机地将n个皇后分布在棋盘上，使得棋盘
     的每行、每列只有一个皇后。
2，计算皇后间的冲突数conflicts。
3，如果冲突数conflicts等于0，则转6
4，对于棋盘上的任意两个皇后，交换他们的行
      或者列，如果交换后的冲突数conflicts减少，
      则接受这种交换，更新冲突数conflicts，转3。
5，如果陷入了局部极小，既交换了所有的皇后
      后，冲突数仍然不能下降，则转1。
6，输出结果
7，结束。

最终结果，n个皇后中任意两个皇后不在同一斜线上。

其它例子，如模拟退火算法、遗传算法等局部搜索再另行介绍。

八、在具体设计算法时的细节考虑

搜索机制的选择

搜索机制是构造算法框架和实现优化的关键，是决定算法搜索行为的根本点。比如爬山法是基于局部贪婪的搜索机制，而模拟退火算法时基于概率分布的搜索机制，禁忌搜索采用避免迂回的策略进行搜索。

邻域函数的设计

邻域函数决定了邻域结构和邻域解的产生方式。算法对问题解的不同描述方式，会直接影响邻域函数的设计，进而影响算法的搜索行为。同时，即使在编码机制确定的情况下，邻域结构也可以采用不同的形式，以考虑新状态产生的可行性、合法性和对搜索效率的影响。在确定邻域结构后，当前状态邻域中候选解的产生方式即可以是确定的，也可以是随机性地。

状态更新方式的设计

更新方式是指以何种策略在新旧状态中确定新的当前状态，是决定算法整体优化特性的关键步骤之一。基于确定性地状态更新方式的搜索，容易陷入局部最优；而随机性地状态更新方式，尤其是概率性劣向转移，往往取得较好的全局优化解，但是计算时间也比较长。

参数的控制方式

控制参数是决定算法搜索进程和行为的又一关键因素。合适的参数控制有助于增强算法在邻域中的优化能力和效率，同时也必须以一定的准则和方式进行修改以适应算法性能的动态变化。

终止准则的设计

终止准则是判断算法是否收敛的标准，决定了算法的最终优化性能。算法收敛理论为终止理论提供了明确的设计方案，但是基于理论分析所得的收敛准则往往很苛刻的，甚至难以应用。实际设计时，应兼顾算法的优化质量和搜索效率等多方面性能，或根据问题需要着重强调算法的某方面性能。

九、应用

主要应用于组合优化问题。

组合优化所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通讯网络等诸多领域。这是几个最经典的应用：

1. TSP问题：从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
2. 约束机器排序问题：n 个加工量为di(i=1,2,… n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。
3. 指派问题： 一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
4. 0-1背包问题： 设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci ( i=1,2,… n)的物品，如何以最大的价值装包？
5. 装箱问题： 如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？
6. SAT问题：称 判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。
7. 皇后问题： 在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？

应用于各种NP问题。

计算量呈指数时间复杂度的应用，均可考虑此算法。