以下文章作者向柯瑋
前言
各位看客老爺們瓜客，大家好~
今天要為大家?guī)淼?code>干貨是multi-start local search算法解決TSP問題（Java的實(shí)現(xiàn)）俭正。
大家可不要因?yàn)檫@個(gè)算法的名字比較長(zhǎng),就覺得這個(gè)這個(gè)算法很難奸鬓，其實(shí)沒有哦-
這個(gè)算法還是非常簡(jiǎn)單的，希望大家能夠通過這個(gè)簡(jiǎn)單的算法來了解面對(duì)NP-hard問題掸读，我們可以采取的策略是什么串远。
算法簡(jiǎn)介
這個(gè)算法，其實(shí)大家通過名字就可以知道儿惫，一定和Iterated local search（迭代局部搜索算法）存在一定的聯(lián)系澡罚。
（這是當(dāng)然呀，名字都差不多肾请，還需要你說嗎留搔？）
迭代局部搜索算法公眾號(hào)在之前已經(jīng)介紹過了，有興趣的小伙伴可以再看看~
干貨|迭代局部搜索算法(Iterated local search)探幽（附C++代碼及注釋）
這兩個(gè)算法相似的地方我們就不多說了铛铁。我們主要介紹這個(gè)算法優(yōu)勢(shì)之處隔显。
優(yōu)勢(shì)
這種算法却妨，他是多起點(diǎn)的，初始解的生成和遺傳算法挺類似的括眠。
通過隨機(jī)打亂彪标，生成多個(gè)隨機(jī)新解，以此來增大達(dá)到最優(yōu)解的目的掷豺。
可能大家光這么看捞烟，沒啥感覺，我們可以通過數(shù)學(xué)公式來讓大家直觀的感受一下萌业。
我們認(rèn)為有N個(gè)城市坷襟，令傳統(tǒng)的LS搜索的次數(shù)為A，傳統(tǒng)的MLS搜索次數(shù)為A',改進(jìn)過的MLS搜索次數(shù)為A'',可以容易得出下面的公式生年。
現(xiàn)在讓我們?cè)賮砜纯磳?shí)際的程序跑出來的結(jié)果婴程。
這是傳統(tǒng)的LS。
這是傳統(tǒng)的MLS抱婉。
這是咱們優(yōu)化過的MLS档叔。
從以上兩個(gè)例子我們可以看出，MLS確實(shí)能夠提高單次程序運(yùn)行獲得優(yōu)質(zhì)解的概率蒸绩。
那么衙四，下面就讓我們簡(jiǎn)單地總結(jié)一下MLS的一些優(yōu)點(diǎn)。
- 如果是在多線程情況下進(jìn)行探索患亿，那么速度和LS是差不多的
- 探尋到最優(yōu)解的概率更大了
- 對(duì)于新手來說传蹈，也可以更好的學(xué)習(xí)這種多個(gè)初始解的思想，便于以后GA等算法的學(xué)習(xí)
雖然本次代碼的展示仍然是采用單線程步藕，但是只要單線程的明白了惦界，多線程其實(shí)很容易就變過去了。
算法流程分析
現(xiàn)在我們先來介紹介紹最普遍的一種multi-start local search（多起點(diǎn)的局部搜索算法）咙冗。
大致的流程就是上面這副圖一樣沾歪，在讀取數(shù)據(jù)之后生成第一個(gè)解，即按照0-1-2-3……排序的解雾消。
然后將這個(gè)解進(jìn)行打亂灾搏，生成N組解，然后分別對(duì)這N組解利用2-opt算子進(jìn)行鄰域搜索立润。
我個(gè)人感覺這一種multi-start local search算法并不是很好狂窑。
- 都是采用的多線程操作，對(duì)于新手都不是很友好桑腮，代碼不大看得明白
- 算子太少蕾域，單一的2-opts算子很難找到較好的解
- 對(duì)一些比較差的初始解（通過鄰域搜索都無法找到更好的解），沒有進(jìn)行一些處理
鑒于上面的不足，我對(duì)這個(gè)算法進(jìn)行了一定程度的改進(jìn)旨巷。如下圖巨缘。
代碼解析
在上面，我們大致的介紹了本次算法的大致實(shí)現(xiàn)過程采呐。
接下來若锁，我們對(duì)部分代碼進(jìn)行解讀
啟動(dòng)函數(shù)
這個(gè)函數(shù)是我們的main函數(shù)，我們?cè)谶@里完成我們所有的操作斧吐。
我們?cè)趇ter函數(shù)中完成我們的搜索過程又固。
public class launch {
public static void main(String[] args) {
mls my_solution=new mls(); //生成mls對(duì)象
readfile my_file=new readfile(); //讀取文件
my_file.buildInstance("F:\\mls\\data\\uy734.tsp.txt"); //讀取文件
my_solution.setiLSInstance(my_file.getInstance()); //設(shè)置好距離矩陣
my_solution.setsolution(); //設(shè)置好初始解
my_solution.iter(); //開始迭代
my_solution.print_best(); //輸出最優(yōu)解
System.out.println("最佳適應(yīng)度為："+my_solution.print_of()); //輸出最佳適應(yīng)度
}
}
iter函數(shù)
這個(gè)函數(shù)就是最主要的函數(shù)，相當(dāng)于整個(gè)搜索的過程的啟動(dòng)器煤率。
我們?cè)谶@個(gè)函數(shù)中仰冠，每次生成一個(gè)新的隨機(jī)解，然后進(jìn)行鄰域搜索蝶糯。這個(gè)就是區(qū)別于LS的根本之處洋只。
并用'tihuan'作為改隨機(jī)解是否為一個(gè)較好解的標(biāo)志。
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函數(shù)
LS函數(shù)昼捍，即local search函數(shù)识虚，我們通過這個(gè)函數(shù)，完成我們對(duì)每組解的每個(gè)位置的城市的鄰域搜索操作妒茬。
并用‘tihuan’作為是否生成更好的解（這里是指生成比當(dāng)前隨機(jī)解好的解）的標(biāo)志担锤。
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函數(shù)
這個(gè)是我們用來生成隨機(jī)新解的函數(shù)。
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;
}
小結(jié)
好了乍钻，我們現(xiàn)在把算法的大致流程肛循，主要的代碼都展示了一下，大家可以把自己的data輸進(jìn)去银择，看看結(jié)果怎么樣育拨，T^T，小瑋得到的結(jié)果都不是很理想--
該算法的隨機(jī)性很大欢摄，獲得優(yōu)質(zhì)解的難度還是蠻大的。
但是我覺得這個(gè)算法從傳統(tǒng)LS變過來給了我們很多啟發(fā)笋粟，比如說怀挠，在尋求最優(yōu)解的時(shí)候，我們可以采用多線程來提高尋求最優(yōu)解的效率等等害捕。
我希望大家通過本次推文绿淋，能夠了解到鄰域解是如何產(chǎn)生的，以及算法不夠好時(shí)的我們可以采用哪些改進(jìn)吞滞。
那么在下一次的推文中，會(huì)介紹一種船新的組合優(yōu)化解決VRPTW的算法~讓我們一起期待吧！
