干货|多起点的局部搜索算法(multi-start local search)解决TSP问题（附Java代码及注释）
干货|多起点的局部搜索算法(multi-start local search)解决TSP问题（附Java代码及注释）
前言
各位看客老爷们，大家好~
今天要为大家带来的干货是multi-start local search算法解决TSP问题（Java的实现）。
大家可不要因为这个算法的名字比较长,就觉得这个这个算法很难，其实没有哦-
这个算法还是非常简单的，希望大家能够通过这个简单的算法来了解面对NP-hard问题，我们可以采取的策略是什么。
算法简介
这个算法，其实大家通过名字就可以知道，一定和Iterated local search（迭代局部搜索算法）存在一定的联系。
（这是当然呀，名字都差不多，还需要你说吗？）
迭代局部搜索算法公众号在之前已经介绍过了，有兴趣的小伙伴可以再看看~
干货|迭代局部搜索算法(Iterated local search)探幽（附C++代码及注释）
这两个算法相似的地方我们就不多说了。我们主要介绍这个算法优势之处。
优势
这种算法，他是多起点的，初始解的生成和遗传算法挺类似的。
通过随机打乱，生成多个随机新解，以此来增大达到最优解的目的。
可能大家光这么看，没啥感觉，我们可以通过数学公式来让大家直观的感受一下。
我们认为有N个城市，令传统的LS搜索的次数为A，传统的MLS搜索次数为A',改进过的MLS搜索次数为A'',可以容易得出下面的公式。
现在让我们再来看看实际的程序跑出来的结果。
这是传统的LS。
这是传统的MLS。
这是咱们优化过的MLS。
从以上两个例子我们可以看出，MLS确实能够提高单次程序运行获得优质解的概率。
那么，下面就让我们简单地总结一下MLS的一些优点。
- 如果是在多线程情况下进行探索，那么速度和LS是差不多的
- 探寻到最优解的概率更大了
- 对于新手来说，也可以更好的学习这种多个初始解的思想，便于以后GA等算法的学习
虽然本次代码的展示仍然是采用单线程，但是只要单线程的明白了，多线程其实很容易就变过去了。
算法流程分析
现在我们先来介绍介绍最普遍的一种multi-start local search（多起点的局部搜索算法）。
大致的流程就是上面这副图一样，在读取数据之后生成第一个解，即按照0-1-2-3……排序的解。
然后将这个解进行打乱，生成N组解，然后分别对这N组解利用2-opt算子进行邻域搜索。
我个人感觉这一种multi-start local search算法并不是很好。
- 都是采用的多线程操作，对于新手都不是很友好，代码不大看得明白
- 算子太少，单一的2-opts算子很难找到较好的解
- 对一些比较差的初始解（通过邻域搜索都无法找到更好的解），没有进行一些处理
鉴于上面的不足，我对这个算法进行了一定程度的改进。如下图。
代码解析
在上面，我们大致的介绍了本次算法的大致实现过程。
接下来，我们对部分代码进行解读
启动函数
这个函数是我们的main函数，我们在这里完成我们所有的操作。
我们在iter函数中完成我们的搜索过程。
public class launch {
public static void main(String[] args) {
mls my_solution=new mls(); //生成mls对象
readfile my_file=new readfile(); //读取文件
my_file.buildInstance("F:\\mls\\data\\uy734.tsp.txt"); //读取文件
my_solution.setiLSInstance(my_file.getInstance()); //设置好距离矩阵
my_solution.setsolution(); //设置好初始解
my_solution.iter(); //开始迭代
my_solution.print_best(); //输出最优解
System.out.println("最佳适应度为："+my_solution.print_of()); //输出最佳适应度
}
}
iter函数
这个函数就是最主要的函数，相当于整个搜索的过程的启动器。
我们在这个函数中，每次生成一个新的随机解，然后进行邻域搜索。这个就是区别于LS的根本之处。
并用'tihuan'作为改随机解是否为一个较好解的标志。
public void iter() {
for(int c=0;c<this.iLSInstance.getN();c++)
{
Solution localsolution2 = this.currBest.clone();
for (int j = c; j < this.iLSInstance.getN(); j++) {
Solution now = ls(localsolution2.clone(), j);
if (now.getOF() < this.dLSGlobalBest.getOF())
this.dLSGlobalBest = now.clone();
}
}
for (int i = 0; i < this.iLSInstance.getN(); i++) {
tihuan=false;
Solution localsolution = this.currBest.clone();
localsolution=restart(localsolution);
for (int j = 0; j < this.iLSInstance.getN(); j++) {
Solution now = ls(localsolution.clone(), j);
if (now.getOF() < this.dLSGlobalBest.getOF())
this.dLSGlobalBest = now.clone();
}
for(int m=0;m<this.iLSInstance.getN()-1;m++)
System.out.print(localsolution.getsolution().get(m)+"-->");
System.out.println(localsolution.getsolution().get(this.iLSInstance.getN()-1));
if(!tihuan)
step++;
if(step==50)
{
i--;
step=0;
}
}
}
LS函数
LS函数，即local search函数，我们通过这个函数，完成我们对每组解的每个位置的城市的邻域搜索操作。
并用‘tihuan’作为是否生成更好的解（这里是指生成比当前随机解好的解）的标志。
public Solution ls(Solution ssolution,int i) {
Solution best = ssolution.clone();
for (int j = i + 1; j < this.iLSInstance.getN() +i; j++) {
Solution now=ssolution.clone();
if(j<this.iLSInstance.getN()){
now.swap(i, j);
now.setOF(this.cLSCalculator.calc(this.iLSInstance, now));
if (now.getOF() < best.getOF()) {
best = now.clone();
tihuan=true;
}
if(!tihuan){
now.swap(i,j);
now.relocate(i,j);
now.setOF(this.cLSCalculator.calc(this.iLSInstance, now));
if (now.getOF() < best.getOF()) {
best = now.clone();
tihuan=true;
}
}
}
else if(j-this.iLSInstance.getN()<i){
now.relocate(i,j-i);
now.setOF(this.cLSCalculator.calc(this.iLSInstance, now));
if (now.getOF() < best.getOF()) {
best = now.clone();
tihuan=true;
}
}
}
return best;
}
restart函数
这个是我们用来生成随机新解的函数。
public Solution restart(Solution solution){
int[]haveset=new int[iLSInstance.getN()];
haveset[0]=0;
for(int i=0;i<iLSInstance.getN();i++){
int n=rLSRandom.nextInt(iLSInstance.getN());
while (haveset[n]!=0)
n=rLSRandom.nextInt(iLSInstance.getN());
solution.getsolution().set(i,n);
haveset[n]=1;
}
solution.setOF(this.cLSCalculator.calc(this.iLSInstance, solution));
return solution;
}
小结
好了，我们现在把算法的大致流程，主要的代码都展示了一下，大家可以把自己的data输进去，看看结果怎么样，T^T，小玮得到的结果都不是很理想--
该算法的随机性很大，获得优质解的难度还是蛮大的。
但是我觉得这个算法从传统LS变过来给了我们很多启发，比如说，在寻求最优解的时候，我们可以采用多线程来提高寻求最优解的效率等等。
我希望大家通过本次推文，能够了解到邻域解是如何产生的，以及算法不够好时的我们可以采用哪些改进。
那么在下一次的推文中，会介绍一种船新的组合优化解决VRPTW的算法~让我们一起期待吧！
本篇推文代码请在公众号后台回复【MLS代码】获取（不用输入【】）