栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【运筹优化&数学建模】VNS变邻域搜索算法求解TSP问题(Java实现)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【运筹优化&数学建模】VNS变邻域搜索算法求解TSP问题(Java实现)

文章目录
  • 代码
  • 求解结果


代码
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/

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/956285.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号