- 代码
- 求解结果
代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
public class VNS_TSP {
// 城市坐标<[x,y]>
List locationList;
// 距离矩阵
double[][] dist;
// 城市数量
int cityNum;
// 不同邻域的迭代次数(如果有3个以上的邻域,则需要对此数组进行扩充)
public int[] maxGenEachN = new int[]{10000,10000};
public int[] currGh;//存放当前编码
public int[] bestGh;//最好的路径编码
public int bestT;// 最佳的迭代次数
public int bestN; // 最佳领域
public double tempEvaluation;//临时解
public double currEvaluation;//当前解
public double bestEvaluation;//最优解
public Random random;//随机函数对象
public VNS_TSP(List locationList) {
this.locationList = locationList;
}
public void solve() {
initVar();
solver();
}
public void solver() {
variableNeighborhoodDescent();
System.out.println("最佳迭代次数:" + bestT);
System.out.println("最佳邻域:"+bestN);
System.out.println("最短路程为:" + bestEvaluation);
int[] bestPath = new int[cityNum + 1];
System.arraycopy(bestGh, 0, bestPath, 0, bestGh.length);
bestPath[cityNum] = bestPath[0];
System.out.println("最佳路径为:" + Arrays.toString(bestPath));
}
// 变领域下降搜索 VND(VARIABLE NEIGHBORHOOD DESCENT)
public void variableNeighborhoodDescent(){
for (int n = 0; n < maxGenEachN.length; n++) {
for (int i = 0; i < maxGenEachN[n]; i++) {
switch (n){
case 0:
// 领域动作:两点互换
currGh = generateNewGh(bestGh);
break;
case 1:
// 领域动作:两点间反转
currGh = reserve(bestGh);
break;
default:break;
}
double evaluate = evaluate(currGh);
if(evaluate
bestEvaluation = evaluate;
bestGh = currGh.clone();
bestT = i;
bestN = n;
}
}
}
}
// 领域动作:两点互换
public int[] generateNewGh(int[] Gh) {
int temp;
//将Gh复制到tempGh
int[] tempGh = Gh.clone();
int r1 = 0;
int r2 = 0;
while (r1 == r2) {
r1 = random.nextInt(cityNum);
r2 = random.nextInt(cityNum);
}
// 交换
temp = tempGh[r1];
tempGh[r1] = tempGh[r2];
tempGh[r2] = temp;
return tempGh;
}
// 领域动作:两点间反转
public int[] reserve(int[] Gh){
int[] newArr = Gh.clone();
double currEvaluation = evaluate(Gh);
for (int j = 0; j < cityNum - 1; j++) {
for (int k = j + 1; k < cityNum; k++) {
// 反转j和k之间的元素
int[] newGh = reserveTwoPoint(Gh, j, k);
double evaluate = evaluate(newGh);
if (evaluate < currEvaluation) {
currEvaluation = evaluate;
newArr = newGh.clone();
break;
}
}
}
return newArr;
}
// 给定两点,将数组两点间的元素反转
private int[] reserveTwoPoint(int[] currGh, int begin, int end) {
int[] newArr = currGh.clone();
for (int i = begin; i <= (begin + end) / 2; i++) {
int temp = newArr[i];
newArr[i] = newArr[end - (i - begin)];
newArr[end - (i - begin)] = temp;
}
return newArr;
}
// 初始化变量
public void initVar() {
cityNum = locationList.size();//城市数量为点的数量
bestGh = new int[cityNum];//最好的路径编码
currGh = new int[cityNum];//当前编码
dist = new double[cityNum][cityNum];//距离矩阵
random = new Random(System.currentTimeMillis());
//初始化距离矩阵
for (int i = 0; i < dist.length; i++) {
for (int j = i; j < dist[i].length; j++) {
if (i == j) {
//对角线为0
dist[i][j] = 0.0;
} else {
//计算i到j的距离
dist[i][j] = getDistance(locationList.get(i), locationList.get(j));
dist[j][i] = dist[i][j];
}
}
}
//初始化参数
bestT = 0;
random = new Random(System.currentTimeMillis());
//随机创造初始解
currGh[0] = 0;
List pathList = new ArrayList<>();
pathList.add(0);
int index = 1;
while (index < cityNum) {
int r1 = random.nextInt(cityNum);
if (!pathList.contains(r1)) {
currGh[index++] = r1;
pathList.add(r1);
}
}
System.out.println("初始解为:" + Arrays.toString(currGh));
//复制当前路径编码给最优路径编码
bestGh = currGh.clone();
currEvaluation = evaluate(currGh);
bestEvaluation = currEvaluation;
tempEvaluation = currEvaluation;
}
// 计算两点之间的距离(使用伪欧氏距离,可以减少计算量)
public double getDistance(double[] place1, double[] place2) {
// 伪欧氏距离在根号内除以了一个10
return Math.sqrt((Math.pow(place1[0] - place2[0], 2) + Math.pow(place1[1] - place2[1], 2)) / 10.0);
// return Math.sqrt((Math.pow(place1[0] - place2[0], 2) + Math.pow(place1[1] - place2[1], 2)));
}
// 评价函数
public double evaluate(int[] path) {
double pathLen = 0.0;
for (int i = 1; i < path.length; i++) {
// 起点到终点途径路程累加
pathLen += dist[path[i - 1]][path[i]];
}
// 然后再加上返回起点的路程
pathLen += dist[path[0]][path[path.length - 1]];
return pathLen;
}
}
求解结果
变领域搜索算法求解tsp问题:48个城市... 初始解为:[0, 33, 40, 8, 7, 29, 6, 46, 36, 38, 12, 43, 24, 21, 1, 25, 5, 10, 34, 42, 11, 45, 15, 23, 19, 18, 28, 16, 27, 39, 20, 31, 13, 30, 14, 37, 2, 4, 47, 3, 17, 26, 41, 32, 9, 44, 22, 35] 最佳迭代次数:14 最佳邻域:1 最短路程为(伪欧氏距离):10601.12744990602 最佳路径为:[12, 10, 11, 14, 39, 8, 0, 7, 37, 30, 43, 17, 6, 27, 5, 36, 18, 26, 16, 42, 29, 35, 45, 32, 19, 46, 20, 31, 38, 47, 4, 41, 23, 9, 44, 34, 3, 25, 1, 28, 33, 40, 15, 21, 2, 22, 13, 24, 12] 求解用时:1.028 s ------------------------------------------------------------------------- 变领域搜索算法求解tsp问题:48个城市... 初始解为:[0, 8, 15, 43, 1, 31, 6, 32, 17, 41, 23, 12, 42, 25, 18, 11, 47, 39, 16, 44, 26, 19, 21, 29, 37, 28, 10, 7, 13, 33, 38, 4, 20, 9, 5, 46, 22, 40, 14, 2, 27, 45, 36, 3, 24, 35, 30, 34] 最佳迭代次数:17 最佳邻域:1 最短路程为(欧氏距离):34672.496967443556 最佳路径为:[39, 0, 7, 8, 37, 30, 43, 17, 6, 27, 5, 36, 18, 26, 16, 42, 29, 35, 45, 32, 19, 46, 12, 20, 38, 31, 23, 9, 44, 34, 3, 25, 1, 41, 47, 4, 28, 40, 15, 21, 2, 33, 13, 24, 22, 10, 11, 14, 39] 求解用时:0.983 s -------------------------------------------------------------------------
补充:以上使用的是tsplib上的数据att48,这是一个对称TSP问题,城市规模为48,其最优值为10628(取整的伪欧氏距离)。tsplib地址:http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/



