随机本地搜索

随机局部搜索时解决难得组合问题的算法combinatorial problems。

随机局部搜索是解决许多艰难组合问题的一种方法。

组合问题的例子 Combinatorial Problems and Search :

• (TSP)：找到最短/最便宜的路径，旅行商问题：从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？
• 规划，调度，时间表
• 资源分配： 一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？
• 蛋白质结构的预测
• 基因序列的整合
• 0-1背包问题： 设有一个容积为b的背包，n个体积分别为ai(i=1,2,… n),价值分别为ci ( i=1,2,… n)的物品，如何以最大的价值装包？
• SAT（The Propositional Satisfiability Problem）问题：称 判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。

Combinatorial Decision Problems:是指在给定的问题中，是否存在满足条件的解决方案。

局部搜索算法

局部搜索算法是从爬山法改进而来的。爬山法：在没有任何有关山顶的其他信息的情况下，沿着最陡的山坡向上爬。局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。随机局部搜索是从局部搜索算法中衍生。因为局部搜索的计算量太大。

随机局部搜索算法的回顾：

Parameterised local search extensions 局部搜索的衍生:

• Simulated Annealing 模拟退火
• Tabu Search 禁忌搜索

Hybrid SLS strategies 混合SLS策略:

• Iterated Local Search 迭代局部搜索
• Evolutionary Algorithms 进化算法-遗传算法
• Ant Colony Optimization 蚁群算法

【出处：STOCHASTIC LOCAL SEARCH FOUNDATIONS AND APPLICATIONS ，URL：https://www.cs.put.poznan.pl/mkomosinski/materialy/optymalizacja/extras/StochasticLocalSearch.pdf】

模拟退火算法（Simulated Annealing)

“模拟退火”算法是源于对热力学中退火过程的模拟，在某一给定初温下，通过缓慢下降温度参数，使算法能够在多项式时间内给出一个近似最优解。

爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法与爬山法类似，但是它没有选择最佳的移动，而是选择随机的移动。如果该移动使情况得到改善，那么接受该移动；否则，算法以某个概率接受该移动。因此有可能会跳出这个局部的最优解，达到全局的最优解。以上图为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。

模拟退火的原理：我们将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。可以证明，模拟退火算法所得解依概率收敛到全局最优解。

当陷入局部最优之后，模拟退火算法要求概率根据算法进行过程中，逐步降低（逐渐降低才能趋向稳定）其跳出局部最优的概率，使其越来越趋于稳定。这一特性增加也同样存在缺陷，即对于全局最优解，也存在一定概率跳出，从而使得求解过程不稳定。

随着邻域的范围的增大，跳出局部极小区域,最终进入全局极小区域的概率越来越大，但是代价是总的迭代次数增加。但是随着邻域范围的增大，会出现所谓的在极值附近来回”振荡”而无法落入极值点的现象。可以推测,随着邻域范围的进一步增大及其随机特性，模拟退火算法将退化到随机寻找极值并进行记录极值的算法。当然这种算法也存在问题，即对于某些情况下，也不易达到全局最优。例如，解空间中仅有两个局部最优，其中一个是全局最优，那么模拟退火似乎并不一定总能进入到全局最优解当中。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。

示例代码

/* * J(y)：在状态y时的评价函数值 * Y(i)：表示当前状态 * Y(i+1)：表示新的状态 * r： 用于控制降温的快慢 * T： 系统的温度，系统初始应该要处于一个高温的状态 * T_min ：温度的下限，若温度T达到T_min，则停止搜索 */ while( T > T_min ) { dE = J( Y(i+1) ) - J( Y(i) ) ; if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动 Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动 else { // 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也 if ( exp( dE/T ) > random( 0 , 1 ) ) Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动 } T = r * T ; //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快 /* * 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值 */ i ++ ; }

发展历史

1962年由Spendley, Hext和Himsworth提出，80年代得到证明。单纯形搜索法是一种无约束最优化的直接方法。单纯形法是求解非线性多元函数、无约束最小化问题的有效方法之一。在许多技术领域内，都取得了有效的成果。

1964年由Powell提出，后经Zangwoll（1967年）和Brent（1973年）改进。该算法有效地利用了迭代过程中的历史信息，建立起能加速收敛的方向。

梯度法， 又名最速下降法，求解无约束多元函数极值的数值方法，早在1847年就已由柯西(Cauchy))提出。它是导出其他更为实用、更为有效的优化方法的理论基础。因此，梯度法是无约束优化方法中最基本的方法之一。

共轭梯度法最早是又Hestenes和Stiefle（1952）提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves （1964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中。

Kirkpatrick et al. 1983, Cerny 1985都提出了组合搜索技术模拟退火算法。Johnson & McGeoch 也将该算法在1997来解决tsp旅行商问题。

Glover 1989, 1990提到组合搜索技术严重依赖于使用的搜索过程的外存储空间。Hansen & Jaumard 1990; Selman & Kautz 1994提出禁忌搜索来解决SAT / MAX-SAT问题。Battiti & Tecchiolli 1994–1997也对禁忌搜索进行改进提出 Reactive Tabu Search。

随机局部搜索的两大山脉遗传算法和蚁群算法。遗传算法兴起于Holland 1975; Goldberg 1989，著名的算法有Evolutionary Algorithm Genetic algorithms 进化算法中的遗传算法。Fogel et al. 1966提出 Evolutionary Programmin；Koza 1992提出Genetic Programming。Rechenberg 1973; Schwefel 1981提出各种进化策略Evolution strategies。

蚁群算法（Ant Colony Optimization, ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出。一份从论文中提取的技术报告五年后出版，由V. Maniezzo和A.Colorni合著。1996年，蚂蚁系统的文章出版。1996年，Hoos与Stützle发明了最大最小蚂蚁系统。1997年，Dorigo和Gambardella发布了蚁群系统。

主要事件

发展分析

瓶颈

SLS算法并不能保证能够找出一个可行解，即使这个可行解存在于状态空间。

• 大多数SLS算法会突然停滞不前
• 而且算法的事件消耗是巨大的，在保证找到全局最小值的条件是时间趋于无穷大。

未来发展方向

局部搜索问题解决优化问题，计算量太过复杂，因此，随机局部搜索问题就是解决组合优化问题，能尽量使得计算量变小，而蚁群算法和遗传算法也已经广泛运用到学术当中。但是如何尽可能的扩大搜索范围，避免陷入局部最小值，如何确定步长等问题使得启发式搜索一直是研究人员的热门问题。

Contributor：Cai Ruiying