-
前言：很久没有写博文了，两个字
——“
穷忙<
/p>
”
，这一段时间里收到了很多老师、学生和业
界人员的问题，
有些回答的稍显草率，
请谅解，
其中的一些问题
（比如
QCQP
< br>中的
semidefinite
的相关问题及讨论）很想
写写，但一想到写这些东西需要认真捋清思路、小心措辞、辅助
作图等，又想到自己
research
进展跟狗屎一样，就实在没有心情写了。其实，青
年教师的
科研压力不比在读博士生小，老师们应该都能理解，所以请学生们和业界人员原
谅我这一
段时间问题回答上的草率。
今天选择
Local
Search
（
LS
）这个话题，一来是最近看到很多
Papers
在使用这些方
法，
二来是看到最近优化软件
LocalSolver(
官网
，
中国代理商
)
火爆的不行。
LocalSolver
是基于
local
search
方法
（而非
Branch
and Cut
方法和
Constraint Program
ming
方法）
求解
Mathemat
ical
Programming
模型的，所以非线性算子（
floor, ceil, log, exp, pow, cos, sin, t
an
）就完全不在话
下了，当您的
mo
del
有大量非线性和非凸性的时候，您就别再一边又一边给杜老师发
< br>Email
了（杜老师，我用
Gurobi
和
CPLEX
怎么都不行？）
，也别苦逼地去尝试
IBM
ILOG
CP
Opitimizer
了，
因为
CP
虽然也能处理这些，
但毕竟设计的初衷不是为了求
Mathematical Model
的，所以这时候大胆尝试一下
LocalSolver
吧。我以后再也不会说：你的
Model
非线性和非<
/p>
凸性都很强，有点没治
~
；我会说：
Pls Try LocalSolver
（对学术界免费开放）<
/p>
。
Local
Search
详
细的基本知识我就不说了，说实在的，我掌握的也不是很系统，不过
LocalSolv
er
团队提供了供课堂教学用的资料，
让老师教学生系统学习<
/p>
LS
技术
（我在内蒙古
< br>大学还没有资格给研究生上课，
所以暂时不会把
LS
技术系统地带入课堂
,
这一点也令我有些<
/p>
沮丧
)
，有需要教学的老师可向
LocalSolver
开发团队协商索要教学资料。下面我简单地把跟
Local
Search
紧密相关的
一些算法（这里，我无意全面地介绍跟
LS
相关的各种算法）介
绍
给大家，让大家对
LS
技术有个相对
直观和略显高级的理解，也能大致洞察清楚优化软件
LocalSolver
后面的东东，
主要包括：
Variable
Neighborhood Descent(VND),Iterated Local Search
(ILS)
，
Variable
Neighborhood
Search
(VNS)
，
Variable
Neighborhood
Decompostion
Search
(VNDS)
，
Large
Neighborhood Search (LNS)
等。算法详细的细节我不再披露
，请大家
google
里找相应的
Pa
pers
阅读，我只简单给出算法的主要伪代码（主要的来源是
Thomas Stutzle
在
2003
年一个暑期学校上的讲义即
Blum
在
Applied Soft Computing
上写的一篇综
述论文
）
，并着重分析各算法的核心思想以及各算法的区别
。
--------------------------
-----------
博主
2013
年
8
月
31
日
注：开始
--------------------------
Local Search
也是一种顺序化的搜索方法，
搜索路径形成一个轨迹，针对当前点（解）
，
< br>从其邻域
中试图找到一个更好的解来代替当前解（找不到时当然要停止搜索）
。
问题一
：基本的
Local Sear
ch
常常能到达局部最优，若算法不再配备克服局部极优的机制，常常
< br>称这种
Local
Search
为
Hill
Climbing
（爬山法）
；若配备了
克服局部极优的机制，就形成更为
复杂的算法，如利用
< br>iteration
机制的
Iterated
Local
Search
算法，利用
memory(
记忆
)
机制的
reactive
search
optimization
算法，利用
memor
y-less
stochastic
modificati
on
机制的
Simulated
An
nealing
算法。我们这里提到的
Local
Search
主要指的是
Hill
Climbing
。
问题二
：若定义邻居（邻域）的方法是最多不超过
k
个
Solution Component
发生改变（其余
n-k
个
component
不变）
，这种
Local
S
earch
成为
k-OPT
。例子：<
/p>
求解
TSP
的
2
-OPT
即是一
种
Local
Search
。在这一算法中，常常把定义邻居的交换两条弧的操作成
为
2-OPT
Swap,
可
用函数
2OptSwap(route,i,k)
。如对于解
A->B->C->D->E->F->G->H->A
< br>，指定
i=3,k=6
，即针
对
弧
C-D
和
G-H
进行交换，交换为
C-G
和
D-H
,
即
(A->B->C)
和（
H->A
）片段不变（也即
H->A->B->
C
不变）
，片段（
D->E->F->
G
）元素也不变，只是两个片段原来靠弧
C-D
和
G-H
连接，
现在靠弧
C-G
和
D-H
连
接
（两个片段连接的首尾交换了一下）
，
考虑到这里是有方向
的，
故将片段
（
D->E->F->G
）
在元素连接方
式不变的情况下方向变一下，
即为
（
G
->F->E->D
）
，
这就构造除了
新的邻居
A->B->C->G->F->E->D->H->A
。所以每次给定一个
i
、
k
的具体值，
2OptSwap(route,i,k)
< br>就会给出一个具体的邻居。这就有了下面的问题三。
问
题三：
对于当前解
S
，有很多邻居（对
于上面的
2-OPT
，每个不同的
组合都将是一个
邻居）
，
也即它的邻域中有很多解，
如何搜索它的邻域？也即，
如何在邻域中找到更好的解？
一种简单粗暴的思路是
“
系统化的搜索
”
，
利用两次
for
循环来枚举不同的
组合，
当在某
个
找到更好解时，替代当前解
S
，否则继续枚举
见下面的代码；
另一
种策略常常用到，即
< br>“
随机化的搜索
”
方法
，每次随机地选取
S
的一个邻居（即
）
，找到
更好
的解时替代当前解，否则继续随机选取
S
的一个邻居，当在给定
随机尝试次数内找不
到更好解时，算法停止。
---------------------------
----------
博主
2013
年
8
月
31
日注
：结束
--------------------------
1. Variable
Neighborhood Descent(VND)
每次在一个邻域
N_k
中找不到一个更好的解时，就仍然从当前解
s
出发，换一个领域结
构（常常是在一个更大的领域中）搜索，
看是否能找到更好的解；当找到一个更好的解
s’
时，
从这一新的解出发，
重新返回第一个领域结构开始搜索。
这里变换邻域结构时的初衷是
当前邻域结构找不到更好的解，而变换（常常为扩
大）邻域结构能带来找到更优解的希望，
但变换邻域结构时，要保持搜索的初始解（当前
解）不变。但值得注意的是：对不同领域结
构尝试搜索的算法可能不一样。
2. Iterated Local Search
(ILS)
Local Search
是在一个领域结构（通常
较小，如
TSP
问题的
2-OPT
，
3-OPT
邻域，并行机
调度问题的
insert
邻域）中从一个最优解出发试
图找到最好的解，
local
search
的搜索往往是
-
-
-
-
-
-
-
-
-
上一篇：LOCAL BUS
下一篇：Android中LocalSocket使用