局部搜索

局部搜索是一种用于解决计算上难以优化的问题(NP Problem)的启发式方法.

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

• 只用很少的内存
• 对于状态空间很大，连续的问题也适用(系统(全局)算法就不太适合这类问题)

局部搜索的优化思路

• 局部最优问题即考虑到算法在搜索过程中陷入到局部极值点而结束的情况。设想我们去攀登一座山群的最高峰，而此山群有很多的小山峰，且我们对此山群一无所知，那么当我们按照算法的步骤来到一座小山峰（局部极值点）时，我们会错误的判断这就是最高峰，事实上这有可能是一个很糟糕的解（即与最高峰还差很远）。
• 步长问题为便于理解，我们考虑用此局部搜索算法寻找一开口向下的抛物线的顶点：设此顶点的x坐标为10，求领域的映射N定义为N：$x\in R,N(x)=x\pm 3$（即给定点x的领域仅有在其两边相距为3的两个点），指标函数$f(x)=-y(x)$（为使指标函数值小的解为较优解，我们让其取相反数）；那么当我们所选取的初始解为3时，无论如何算法都将不能在顶点（最优解）处结束。根本原因就是我们的步长固定，所以能够搜索到的也仅为一些固定的点。解决此问题可以在搜索的过程中改变步长（本质为改变映射函数N）。
• 起始点问题在上面步长问题的讨论中，我们发现起始点的选择也对问题的求解有很大的影响，选择不好可能会导致得不出最优解的情况。一种很自然的解决方案就是随机的选择一些可能解，分别以这些可能解为初始解进行搜索，最后将这些搜索得到的解进行比较从而选出最优解。

爬山法

探索和利用

• 探索：可理解为随机找点或初始化状态，保障在局部最优中能够找到全局最优
• 利用：保障能通过一个初始状态， 够找到他的局部最优

最陡爬山法

思路其实很简单, 不断在向值增加的方向移动. 而且移动时只会考虑与相邻的位置(纯利用， 类似与贪心的思想).

n’ <- argmax{f(m)|m belong to neighbor(m)}
n <- n’
for i in range(100): #侧移100次
k=0
n <- n’ if f(n’) > f(n) or (f(n’)=f(n) and k+1 < 100)

随机爬山法

随机选取下一步， 选中的概率和上山移动的陡峭程度不同而不同。 随机选一个点探索， 结合了探索+利用，比起最陡爬山会增加找到全局最优解的概率。

Expansion <- { m | m belongs to neighbor(n), f(m) > f(n) }
P(m_i) = softmax(f(mi)) # 计算周围权值大的概率
r <- rand(0,1) # 为了能随机选取一个点
if p(m_i) =< r < p(m_{i+1}): n <- m_i # 随机选取一个点探索

首选爬山法

类似于随机爬山的思想， 随机生成一个后继结点， 直到生成一个优于当前结点的后继。

for m in neighbor(n):
if f(m) > f(n): n <- m

随机重爬法

上面说的三种算法实际上都是不完备的， 有很大可能卡在局部极大值

随机生成一个初始状态， 再利用爬山法达到最优值。

一般来说， 在搜索一段时间重新开始一个算法比漫无目的搜索销量要高， 主要利用限制侧移或者不进行侧移。时间上， 对于300万皇后的问题， 随机重爬找到解时间也不超过1分钟(但肯定还是没有普通爬山快的， 随机重爬=进行了多次爬山)， 空间上所需是常数级别的。

模拟退火算法

爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火结合了爬山法和随机重爬的优点， 在保证效率的同时又具备完备性。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以下图为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。
[image:42B962C2-EA80-4783-9BE9-F3F9331E20AE-1185-00000078E9F3C225/2010122016525713.png]
模拟退火每次移动时， 并不是选择最好的移动方式， 而是进行随机移动

• 如果移动使得情况改善 -> 总是接受移动（利用）
• 未改善 -> 随机接受（探索）， 产生一个随机数$r\in (0,1)$， 和$p=e^{\frac{f(i+1)-f(i)}{T}}$ 比较

伪代码如下

/*
* 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 ++ ;
}

束搜索

原理很简单， 类似于宽度有限算法， 只不过对于每一层都会选出前K个最优的结点进行拓展， 其余的就直接进行剪枝， 直到找到目标结点。（局部束搜索或贪婪束搜索）

[image:99E0AA9A-6711-436D-908C-C693A59D1072-1185-000000841B967BF0/FullSizeRender.jpg]

对于随机束搜索， 每次不是选择最优， 而是随机选取k个， 选取的概率和结点的状态值有关（值越大选取的几率越大）。

遗传算法

遗传算法实际上是随机束搜索的变形, 通过吧两个父状态结合生成后继。

• 种群：种群中的每个个体都是潜在解
• 个体表示： 染色体， 实际就是状态的表示
• 适应度函数：表示解的好坏程度
• 选择（利用）：根据适应度选取比较好的解优先进行两两繁殖
• 交叉（利用为主+探索）： 选取一个杂交点， 两边染色体互相交换
• 变异（探索）：每个位置都会小概率发生变异
  [image:40FF2AED-CA16-450B-96E7-980588F957FE-1185-000000A087755CE8/IMG_0848.JPG]

参考

1. 局部优化算法详解
2. 大白话解析模拟退火算法(转载)
3. Beam Search（集束搜索/束搜索）# 局部搜索
   局部搜索是一种用于解决计算上难以优化的问题(NP Problem)的启发式方法.

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

• 只用很少的内存
• 对于状态空间很大，连续的问题也适用(系统(全局)算法就不太适合这类问题)

爬山法

探索和利用

• 探索： 可理解为随机找点或初始化状态，保障在局部最优中能够找到全局最优
• 利用： 保障能通过一个初始状态， 够找到他的局部最优

最陡爬山法

思路其实很简单, 不断在向值增加的方向移动. 而且移动时只会考虑与相邻的位置(纯利用， 类似与贪心的思想).

n’ <- argmax{f(m)|m belong to neighbor(m)}
n <- n’
for i in range(100): #侧移100次
k=0
n <- n’ if f(n’) > f(n) or (f(n’)=f(n) and k+1 < 100)

随机爬山法

随机选取下一步， 选中的概率和上山移动的陡峭程度不同而不同。 随机选一个点探索， 结合了探索+利用，比起最陡爬山会增加找到全局最优解的概率。

Expansion <- { m | m belongs to neighbor(n), f(m) > f(n) }
P(m_i) = softmax(f(mi)) # 计算周围权值大的概率
r <- rand(0,1) # 为了能随机选取一个点
if p(m_i) =< r < p(m_{i+1}): n <- m_i # 随机选取一个点探索

首选爬山法

类似于随机爬山的思想， 随机选取一个

随机重爬法

最后

以上就是温婉月饼为你收集整理的局部搜索局部搜索的全部内容，希望文章能够帮你解决局部搜索局部搜索所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。