变邻域搜索算法(VNS)求解TSP（附Java详细代码及注释）
变邻域搜索算法(VNS)求解TSP（附Java详细代码及注释）
用户1621951
发布于 2021-09-02 11:41:32
发布于 2021-09-02 11:41:32
文章被收录于专栏：数据魔术师
前言
各位读者大家好
近期疫情反复
希望大家注意身体哟
变邻域搜索科普
今天小编要讲一讲，变邻域搜索算法（VNS）。
这是一种改进型的局部搜索算法。它利用不同的动作构成的邻域结构进行交替搜索，在集中性和疏散性之间达到很好的平衡。
在之前的推文干货 | 变邻域搜索算法(Variable Neighborhood Search,VNS)超详细一看就懂中，对VNS算法已经有了详细的介绍。
其核心思想就是如果在一次领域搜索中找不到比全局最优解更优的解，就跳到下一个邻域继续进行搜索；若找到了更优解，就以此为最好解进行新的变领域搜索。
下图非常形象地说明了变邻域搜索算法的核心思想：
算子及去重过程
简要说说本文中运用的算子：
two_opt_swap
区间反转:
two_h_opt_swap
随机产生两点，塞进新排列头部。其余的按第一个被选中点开始的顺序往后逐个排列：
需要特别关注的是算子的去重过程。
首先要介绍一下优化值delta是如何计算的：
有城市序列 1-2-3-4-5 总距离 = d[1][2] + d[2][3] + d[3][4] + d[4][5] +
d[5][1] = A
翻转后的序列 1-4-3-2-5 总距离 = d[1][4] + d[4][3] + d[3][2] + d[2][5] + d[5][1] = B
由于 d[i][j] 与 d[j][i]是一样的，所以B也可以表示成 B = A - d[1][2] - d[4][5] + d[1][4] + d[2][5]
故优化值delta[i][j]=B-A
在一次大规模搜索后，会对每一次邻域动作所得的值记录在delta二维数组里。接下来对delta数组进行遍历，若优化值小于0，说明新解比当前解更优，则接受该解，否则继续比较。
若当前解改变，则不需要改变整个delta数组，只需改变部分收到影响的区间的优化值即可。
例如，对于城市序列1-2-3-4-5-6-7-8-9-10，如果对3-5应用了邻域操作two_opt _swap， 事实上对于7-10之间的翻转是不需要重复计算的，因为根本没有影响到7-10之间的节点。因此需要用Delta提前预处理一下。
这样就不用每次搜索前都重新赋值一边delta数组了。
代码展示
本文所用代码是小编根据指导老师的要求从 干货 | 变邻域搜索算法(VNS)求解TSP（附C++详细代码及注释） 的C++版本改编成java版本的。
package VariableNeighborhoodSearch;
import java.util.ArrayList;
import java.util.Collections;
public class Search {
int[][] Delta1 = new int[TSPData.CITY_SIZE][TSPData.CITY_SIZE];
int currentvalue;
int bestvalue;
int distance_2city(int[] city1, int[] city2) {
int distance = 0;
distance = (int) Math.sqrt((double) Math.pow(city1[0] - city2[0], 2) + Math.pow(city1[1] - city2[1], 2));
return distance;
}
int cost_total(int[] cities_permutation, int[][] cities) {
int total_distance = 0;
int c1, c2;
// 逛一圈，看看最后的总距离是多少
for (int i = 0; i < TSPData.CITY_SIZE; i++) {
c1 = cities_permutation[i];
if (i == TSPData.CITY_SIZE - 1) // 最后一个城市和第一个城市计算距离
c2 = cities_permutation[0];
else
c2 = cities_permutation[i + 1];
total_distance += distance_2city(cities[c1], cities[c2]);
}
return total_distance;
}
int[] random_permutation() {
int[] route = new int[TSPData.CITY_SIZE];
ArrayList<Integer> cities = new ArrayList<>();
for (int i = 0; i < TSPData.CITY_SIZE; i++)
cities.add(i);
Collections.shuffle(cities);//核心
Integer[] routefake = cities.toArray(new Integer[cities.size()]);
for (int i = 0; i < routefake.length; i++) {
route[i] = routefake[i];
}
return route;
}
//对应two_opt_swap的去重
int calc_delta1(int i, int k, int[] tmp, int[][] cities) {
int delta = 0;//优化值
if (i == 0) {
if (k == TSPData.CITY_SIZE - 1)
delta = 0;
else {
delta = 0 - distance_2city(cities[tmp[k]], cities[tmp[k + 1]])
+ distance_2city(cities[tmp[i]], cities[tmp[k + 1]])
- distance_2city(cities[tmp[TSPData.CITY_SIZE - 1]], cities[tmp[i]])
+ distance_2city(cities[tmp[TSPData.CITY_SIZE - 1]], cities[tmp[k]]);
}
} else {
if (k == TSPData.CITY_SIZE - 1)
delta = 0 - distance_2city(cities[tmp[i - 1]], cities[tmp[i]])
+ distance_2city(cities[tmp[i - 1]], cities[tmp[k]])
- distance_2city(cities[tmp[0]], cities[tmp[k]])
+ distance_2city(cities[tmp[i]], cities[tmp[0]]);
else
delta = 0 - distance_2city(cities[tmp[i - 1]], cities[tmp[i]])
+ distance_2city(cities[tmp[i - 1]], cities[tmp[k]])
- distance_2city(cities[tmp[k]], cities[tmp[k + 1]])
+ distance_2city(cities[tmp[i]], cities[tmp[k + 1]]);
}
return delta;
}
/*
去重处理，对于Delta数组来说，对于城市序列1-2-3-4-5-6-7-8-9-10，如果对3-5应用了邻域操作two_opt _swap，
事实上对于7-10之间的翻转是不需要重复计算的。 所以用Delta提前预处理一下。
当然由于这里的计算本身是O（1） 的，事实上并没有带来时间复杂度的减少（更新操作反而增加了复杂度）
如果delta计算 是O（n）的，这种去重操作效果是明显的。
*/
void Update1(int i, int k, int[] tmp, int[][] cities, int[][] Delta) {//k>i
if (i != 0 && (k != (TSPData.CITY_SIZE - 1))) {
i--;
k++;
for (int j = i; j <= k; j++)
for (int l = j + 1; l < TSPData.CITY_SIZE; l++)//确保l>j
Delta[j][l] = calc_delta1(j, l, tmp, cities);
for (int j = 0; j < k; j++)
for (int l = i; l <= k; l++) {
if (l>j)
Delta[j][l] = calc_delta1(j, l, tmp, cities);
}// 如果不是边界，更新(i-1, k + 1)之间的
} else {
for (i = 0; i < TSPData.CITY_SIZE - 1; i++)
for (k = i + 1; k < TSPData.CITY_SIZE; k++)
Delta[i][k] = calc_delta1(i, k, tmp, cities);
}// 边界要特殊更新
}
void two_opt_swap(int[] solution, int i, int k) {//将b,c之间的所有节点顺序颠倒，k>i
ArrayList<Integer> cities = new ArrayList<>();
for (int j = 0; j < i; j++)
cities.add(solution[j]);
for (int j = k; j >= i; j--)
cities.add(solution[j]);
for (int j = k + 1; j < TSPData.CITY_SIZE; j++)
cities.add(solution[j]);
for (int j = 0; j < TSPData.CITY_SIZE; j++)
solution[j] = cities.get(j);
}
void neighborhood_one(int[] solution, int[][] cities) {//solution就是mainvariable_neighborhood_descent里的current_solution
int i, k, count = 0;
int max_no_improve = 60;
int inital_cost = cost_total(solution, cities); // 初始花费
int now_cost = 0;
for (i = 0; i < TSPData.CITY_SIZE - 1; i++)
for (k = i + 1; k < TSPData.CITY_SIZE; k++)//确保k>i
Delta1[i][k] = calc_delta1(i, k, solution, cities);
do {
count++;
for (i = 0; i < TSPData.CITY_SIZE - 1; i++) {
for (k = i + 1; k < TSPData.CITY_SIZE; k++) {//确保k>i
if (Delta1[i][k] < 0) {
two_opt_swap(solution, i, k);
now_cost = inital_cost + Delta1[i][k];
this.currentvalue = now_cost;
inital_cost = this.currentvalue;
Update1(i, k, solution, cities, Delta1);
count = 0; // count复位
}
}
}
} while (count <= max_no_improve);
}
int calc_delta2(int i, int k, int[] cities_permutation, int[][] cities) {
int delta = 0;
if (i == 0) {
if (k == i + 1)
delta = 0;
else if (k == TSPData.CITY_SIZE - 1)
delta = 0 - distance_2city(cities[cities_permutation[i]], cities[cities_permutation[i + 1]])
- distance_2city(cities[cities_permutation[k]], cities[cities_permutation[k - 1]])
+ distance_2city(cities[cities_permutation[k]], cities[cities_permutation[i + 1]])
+ distance_2city(cities[cities_permutation[k - 1]], cities[cities_permutation[i]]);
else
delta = 0 - distance_2city(cities[cities_permutation[i]], cities[cities_permutation[i + 1]])
- distance_2city(cities[cities_permutation[k]], cities[cities_permutation[k - 1]])
- distance_2city(cities[cities_permutation[k]], cities[cities_permutation[k + 1]])
+ distance_2city(cities[cities_permutation[k - 1]], cities[cities_permutation[k + 1]])
+ distance_2city(cities[cities_permutation[i]], cities[cities_permutation[k]])
+ distance_2city(cities[cities_permutation[k]], cities[cities_permutation[i + 1]]);
} else {
if (k == i + 1)
delta = 0;
else if (k == TSPData.CITY_SIZE - 1)
delta = 0 - distance_2city(cities[cities_permutation[i]], cities[cities_permutation[i + 1]])
- distance_2city(cities[cities_permutation[0]], cities[cities_permutation[k]])
- distance_2city(cities[cities_permutation[k]], cities[cities_permutation[k - 1]])
+ distance_2city(cities[cities_permutation[k]], cities[cities_permutation[i + 1]])
+ distance_2city(cities[cities_permutation[k - 1]], cities[cities_permutation[0]])
+ distance_2city(cities[cities_permutation[i]], cities[cities_permutation[k]]);
else
delta = 0 - distance_2city(cities[cities_permutation[i]], cities[cities_permutation[i + 1]])
- distance_2city(cities[cities_permutation[k]], cities[cities_permutation[k + 1]])
- distance_2city(cities[cities_permutation[k]], cities[cities_permutation[k - 1]])
+ distance_2city(cities[cities_permutation[i]], cities[cities_permutation[k]])
+ distance_2city(cities[cities_permutation[k]], cities[cities_permutation[i + 1]])
+ distance_2city(cities[cities_permutation[k - 1]], cities[cities_permutation[k + 1]]);
}
return delta;
}
void two_h_opt_swap(int[] cities_permutation, int a, int d) {//d>a
int n = TSPData.CITY_SIZE;
ArrayList<Integer> cities = new ArrayList<>();
cities.add(cities_permutation[a]);
cities.add(cities_permutation[d]);
for (int i = 1; i < n; i++) {
int idx = (a + i) % n;
if (idx != d)// ignore d which has been added already
cities.add(cities_permutation[idx]);
}
for (int i = 0; i < cities.size(); i++)
cities_permutation[i] = cities.get(i);
}
void neighborhood_two(int[] solution, int[][] cities) {
int i, k, count = 0;
int max_no_improve = 60;
int inital_cost = cost_total(solution, cities);
; // 初始花费
int now_cost = 0;
int delta = 0;
do {
count++;
for (i = 0; i < TSPData.CITY_SIZE - 1; i++)
for (k = i + 1; k < TSPData.CITY_SIZE; k++) {//k>i
delta = calc_delta2(i, k, solution, cities);
if (delta < 0) {
two_h_opt_swap(solution, i, k);
now_cost = inital_cost + delta;
currentvalue = now_cost;
inital_cost = currentvalue;
count = 0; // count复位
}
}
} while (count <= max_no_improve);
}
int[] variable_neighborhood_descent(int[] solution, int[][] cities) {//solution就是main里的current_solution
int[] current_solution = solution;
int l = 1;
System.out.println("=====================VariableNeighborhoodDescent=====================");
while (true) {
if (l == 1) {
neighborhood_one(current_solution, cities);
System.out.println("Now in neighborhood_one , current_solution = "
+ cost_total(current_solution, cities) + " solution = " + cost_total(solution, cities));
if (cost_total(current_solution, cities) < cost_total(solution, cities)) {
solution = current_solution;
l = 0;
}
} else if (l == 2) {
neighborhood_two(current_solution, cities);
System.out.println("Now in neighborhood_two , current_solution = "
+ cost_total(current_solution, cities) + " solution = " + cost_total(solution, cities));
if (cost_total(current_solution, cities) < cost_total(solution, cities)) {
solution = current_solution;
l = 0;
}
} else
return solution;// 跳出循环体所在的方法，相当于结束该方法;
l++;
}
}
//将节点顺序分成四块，打乱四块的顺序
void double_bridge_move(int[] cities_permutation) {
int pos1 = 1 + (int) Math.random() * (TSPData.CITY_SIZE / 4);
int pos2 = pos1 + 1 + (int) Math.random() * (TSPData.CITY_SIZE / 4);
int pos3 = pos2 + 1 + (int) Math.random() * (TSPData.CITY_SIZE / 4);
int i;
ArrayList<Integer> cities = new ArrayList<>();
for (i = 0; i < pos1; i++)
cities.add(cities_permutation[i]);
for (i = pos3; i < TSPData.CITY_SIZE; i++)
cities.add(cities_permutation[i]);
for (i = pos2; i < pos3; i++)
cities.add(cities_permutation[i]);
for (i = pos1; i < pos2; i++)
cities.add(cities_permutation[i]);
for (i = 0; i < (int) cities.size(); i++)
cities_permutation[i] = cities.get(i);
}
// 抖动
void shaking(int[] solution, int[][] cities) {
double_bridge_move(solution);
currentvalue = cost_total(solution, cities);
}
void variable_neighborhood_search(int[] best_solution, int[][] cities) {
int max_iterations = 20;
int count = 0, it = 0;
int[] current_solution = best_solution;
// 算法开始
do {
System.out.println("Algorithm VNS iterated " + (it + 1) + "times");// \t是补全当前字符串长度到8的整数倍
count++;
it++;
shaking(current_solution, cities);
current_solution = variable_neighborhood_descent(current_solution, cities);
bestvalue = cost_total(current_solution, cities);
if (currentvalue < bestvalue) {
best_solution = current_solution;
count = 0;
}
System.out.println("全局best_solution = " + bestvalue);
} while (count <= max_iterations);//共搜索count次
}
}
package VariableNeighborhoodSearch;
public class MainRun {
public static void main(String[] args) {
Search abc = new Search();
int[] best_solution = new int[TSPData.CITY_SIZE];
best_solution = abc.random_permutation();
abc.bestvalue = abc.cost_total(best_solution, TSPData.berlin52);
System.out.println("初始总路线长度 = " + abc.bestvalue);
abc.variable_neighborhood_search(best_solution, TSPData.berlin52);
System.out.println("搜索完成！ 最优路线总长度 = " + abc.bestvalue);
System.out.println("最优访问城市序列如下：");
for (int i = 0; i < TSPData.CITY_SIZE; i++)
System.out.print(best_solution[i] + " ");
}
}
package VariableNeighborhoodSearch;
public class TSPData {
static int[][] berlin52={ { 565,575 },{ 25,185 },{ 345,750 },{ 945,685 },{ 845,655 },{ 880,660 },{ 25,230 },{ 525,1000 },{ 580,1175 },{ 650,1130 },{ 1605,620 },
{ 1220,580 },{ 1465,200 },{ 1530,5 },{ 845,680 },{ 725,370 },{ 145,665 },{ 415,635 },{ 510,875 },{ 560,365 },{ 300,465 },{ 520,585 },{ 480,415 },
{ 835,625 },{ 975,580 },{ 1215,245 },{ 1320,315 },{ 1250,400 },{ 660,180 },{ 410,250 },{ 420,555 },{ 575,665 },{ 1150,1160 },{ 700,580 },{ 685,595 },
{ 685,610 },{ 770,610 },{ 795,645 },{ 720,635 },{ 760,650 },{ 475,960 },{ 95,260 },{ 875,920 },{ 700,500 },{ 555,815 },{ 830,485 },{ 1170,65 },
{ 830,610 },{ 605,625 },{ 595,360 },{ 1340,725 },{ 1740,245 } };
static int CITY_SIZE=berlin52.length;
}
- END -
文案&排版：王思涵（华中科技大学管理学院本科一年级）
指导老师：秦虎老师（华中科技大学管理学院）
审稿：周航（华中科技大学管理学院本科二年级）
如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。
如有需求，可以联系：
秦虎老师（华中科技大学管理学院：professor.qin@qq.com）
王思涵（华中科技大学管理学院本科一年级：2278159431@qq.com）
周航（华中科技大学管理学院本科二年级：zh20010728@126.com）
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-08-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
