数学建模常用算法:变邻域搜索算法(VNS)求解tsp问题+att48算例测试【java实现--详细注释】

简介: 数学建模常用算法:变邻域搜索算法(VNS)求解tsp问题+att48算例测试【java实现--详细注释】

代码

package com.dam.heuristic.algorithm.vns.dam.v2;
import java.util.*;
public class VnsApiV2 {
    //迭代次数
    private int GEN_NUM;
    //变领域下降搜索时,每种领域搜索方式的搜索次数
    private int SEARCH_NUM;
    //城市数量
    private int CITY_NUM;
    //多少次没有找到更优解退出迭代
    private int NUM_OF_NOT_FIND_BETTER_SOLUTION;
    //距离矩阵
    private double[][] distanceMatrix;
    public VnsApiV2(int genNum, int searchNum, int numOfNotFindBetterSolution, double[][] distanceMatrix) {
        this.GEN_NUM = genNum;
        this.SEARCH_NUM = searchNum;
        this.NUM_OF_NOT_FIND_BETTER_SOLUTION = numOfNotFindBetterSolution;
        this.distanceMatrix = distanceMatrix;
        this.CITY_NUM = distanceMatrix[0].length;
    }
    /**
     * 求解
     */
    public int[] solve() {
        声明变量
        //开始求解时间
        long startTime = System.currentTimeMillis();
        ///最优解
        //序列
        int[] localSequence = new int[this.distanceMatrix[0].length];
        //最优序列
        int[] bestSequence;
        //最优序列对应的目标函数值
        double bestObjectValue;
        生成初始序列
        this.generateInitialSequence(localSequence);
        //初始化bestSequence,刚开始的最优序列为初始序列
        bestSequence = localSequence.clone();
        bestObjectValue = this.getObjectValue(bestSequence);
        迭代优化
        int numOfNotFindBetterSolution = 0;
        for (int iterations = 0; iterations < this.GEN_NUM; iterations++) {
            if (numOfNotFindBetterSolution>this.NUM_OF_NOT_FIND_BETTER_SOLUTION){
                //很长时间都找不到更优解了,说明解已经相对稳定了,牺牲解质量换取更短的求解时间
                break;
            }
            int k = 1;
            boolean isFindBetterSolution = false;
            while (true) {
                ///扰动序列(SHAKING PROCEDURE)
                //扰动最优解产生新解
                if (k == 1) {
                    //随机翻转最优解的一段序列来生成新解
                    localSequence = this.generateNewSequenceByReverseTwoElement(bestSequence);
                } else if (k == 2) {
                    //扰动最优解产生新解
                    localSequence = this.perturbation(bestSequence);
                } else {
                    break;
                }
                ///变邻域下降搜索(VARIABLE NEIGHBORHOOD DESCENT)
                localSequence = this.variableNeighborhoodDescent(localSequence);
                double localObjectValue = this.getObjectValue(localSequence);
                ///更新最优解(tsp问题:优化目标为总距离越短越好)
                if (localObjectValue < bestObjectValue) {
                    bestObjectValue = localObjectValue;
                    bestSequence = localSequence.clone();
                    k = 0;
                    isFindBetterSolution = true;
                    System.out.println("最优目标函数值:" + bestObjectValue);
                    System.out.println("计算时间为:" + (System.currentTimeMillis() - startTime) * 1.0 / 1000 + "s");
                }
                k++;
            }
            if (isFindBetterSolution == true) {
                numOfNotFindBetterSolution = 0;
            } else {
                numOfNotFindBetterSolution++;
            }
        }
        System.out.println("最优目标函数值:" + bestObjectValue);
        System.out.println("最优解对应序列:" + Arrays.toString(bestSequence));
        System.out.println("计算时间为:" + (System.currentTimeMillis() - startTime) * 1.0 / 1000 + "s");
        return bestSequence;
    }
    /**
     * 变邻域下降搜索
     *
     * @param localSequence
     * @return
     */
    private int[] variableNeighborhoodDescent(int[] localSequence) {
        //定义初始解
        double localObjectValue = this.getObjectValue(localSequence);
        //使用领域动作类型
        int l = 1;
        while (true) {
            if (l == 1) {
                //第一种邻域搜索方式:随机交换两个元素的位置
                for (int i = 0; i < SEARCH_NUM; i++) {
                    //找localSequence对应的比较好的邻居序列
                    int[] tempSequence = this.generateNewSequenceBySwapTwoElement(localSequence);
                    double tempObjectValue = this.getObjectValue(tempSequence);
                    //更新localSequence及其对应的解
                    if (tempObjectValue < localObjectValue) {
                        localSequence = tempSequence.clone();
                        localObjectValue = tempObjectValue;
                        //当在本邻域搜索找不出一个比当前解更优的解的时候,我们就跳到下一个邻域继续进行搜索;
                        //当在本邻域搜索找到了一个比当前解更优的解的时候,我们就跳回第一个邻域重新开始搜索
                        l = 0;
                    }
                }
            } else if (l == 2) {
                //第二种邻域搜索方式:将一个元素取出来,插入到另一个位置
                for (int i = 0; i < SEARCH_NUM; i++) {
                    //找localSequence对应的比较好的邻居序列
                    int[] tempSequence = this.insertElementToAnotherPosition(localSequence);
                    double tempObjectValue = this.getObjectValue(tempSequence);
                    //更新localSequence及其对应的解
                    if (tempObjectValue < localObjectValue) {
                        localSequence = tempSequence.clone();
                        localObjectValue = tempObjectValue;
                        //当在本邻域搜索找不出一个比当前解更优的解的时候,我们就跳到下一个邻域继续进行搜索;
                        //当在本邻域搜索找到了一个比当前解更优的解的时候,我们就跳回第一个邻域重新开始搜索
                        l = 0;
                    }
                }
            } else {
                break;
            }
            l++;
        }
        return localSequence;
    }
    /**
     * 通过反转indexI和indexJ之间的元素,产生新的序列
     *
     * @param sequence
     */
    private int[] generateNewSequenceByReverseTwoElement(int[] sequence) {
        //克隆出新序列
        int[] newSequence = sequence.clone();
        int temp;
        Random random = new Random();
        int indexI = random.nextInt(sequence.length);
        int indexJ = random.nextInt(sequence.length);
        while (indexI == indexJ) {
            indexJ = random.nextInt(sequence.length);
        }
        //当indexJ更小时,将indexI和indexJ的数值进行交换
        if (indexJ < indexI) {
            temp = indexI;
            indexI = indexJ;
            indexJ = temp;
        }
        //不但交换indexI和indexJ对应的元素
        while (indexI < indexJ) {
            temp = newSequence[indexI];
            newSequence[indexI] = newSequence[indexJ];
            newSequence[indexJ] = temp;
            indexI++;
            indexJ--;
        }
        return newSequence;
    }
    /**
     * 随机交换两个元素的位置
     *
     * @param sequence
     * @return
     */
    private int[] generateNewSequenceBySwapTwoElement(int[] sequence) {
        int[] sequenceClone = sequence.clone();
        //对序列中的元素进行打乱,即可产生新的序列
        Random random = new Random();
        int i = random.nextInt(sequence.length);
        int j = random.nextInt(sequence.length);
        while (i == j) {
            j = random.nextInt(sequence.length);
        }
        int temp = sequenceClone[i];
        sequenceClone[i] = sequenceClone[j];
        sequenceClone[j] = temp;
        return sequenceClone;
    }
    /**
     * 将index1的元素插入到index2的位置
     *
     * @param sequence 序列
     * @param sequence
     */
    private int[] insertElementToAnotherPosition(int[] sequence) {
        变量声明
        //随机生成两个索引
        Random random = new Random();
        int index1 = random.nextInt(sequence.length);
        int index2 = random.nextInt(sequence.length);
        //判断是前面插到后面还是后面插到前面 type 0:前面插到后面 1:后面插到前面
        int type = index1 < index2 ? 0 : 1;
        //克隆一份序列出来
        int[] sequenceClone = sequence.clone();
        执行插入
        if (type == 0) {
            //--if--将前面的元素插到后面
            //取出要迁移的元素
            int moveElement = sequenceClone[index1];
            //从index1+1开始,将后面的元素分别向前挪动1位
            for (int i = index1 + 1; i <= index2; i++) {
                sequenceClone[i - 1] = sequenceClone[i];
            }
            //将moveElement插入到index2
            sequenceClone[index2] = moveElement;
        } else {
            //--if--将后面的元素插到前面
            //取出要迁移的元素
            int moveElement = sequenceClone[index1];
            //从index1开始,将元素分别向后挪动1位
            for (int i = index1; i > index2; i--) {
                sequenceClone[i] = sequenceClone[i - 1];
            }
            //将moveElement插入到index2
            sequenceClone[index2] = moveElement;
        }
        return sequenceClone;
    }
    /**
     * 扰动序列
     * 通过将bestSequence的元素分为四组,然后改变四个组的组序,获得新序列
     *
     * @param bestSequence
     */
    private int[] perturbation(int[] bestSequence) {
        Random random = new Random();
        int[] newSequence = new int[bestSequence.length];
        获取五个index,这五个index将bestSequence划分为四组(并非均分)
        //this.cityNum - 2的原因是:indexArr[0]和indexArr[4]都已经确定
        int elementNumInOneGroup = (this.CITY_NUM - 2) / 3;
        int[] indexArr = new int[5];
        indexArr[0] = 0;
        indexArr[1] = random.nextInt(elementNumInOneGroup) + 1;
        indexArr[2] = random.nextInt(elementNumInOneGroup) + elementNumInOneGroup + 1;
        indexArr[3] = random.nextInt(elementNumInOneGroup) + elementNumInOneGroup * 2 + 1;
        indexArr[4] = this.CITY_NUM;
        将组别[0,1,2,3]对应的元素赋值给newSequence
        ///将组序打乱
        List<Integer> groupCodeList = new ArrayList<>();
        //将[0,1,2,3]赋值给集合
        Collections.addAll(groupCodeList, 0, 1, 2, 3);
        //随机打乱
        Collections.shuffle(groupCodeList);
        ///赋值
        int index = 0;
        for (int i = 0; i < groupCodeList.size(); i++) {
            for (int j = indexArr[groupCodeList.get(i)]; j < indexArr[groupCodeList.get(i) + 1]; j++) {
                newSequence[index] = bestSequence[j];
                index++;
            }
        }
        return newSequence;
    }
    /**
     * 生成初始序列
     */
    private void generateInitialSequence(int[] sequence) {
        HashSet<Integer> sequenceSet = new HashSet<>();
        for (int i = 1; i < sequence.length; i++) {
            sequenceSet.add(i);
        }
        //贪婪算法获取初始序列,从城市0开始旅行,即城市0为起点城市
        sequence[0] = 0;
        //每次获取离当前城市最近的城市,并加入到sequence
        for (int i = 1; i < sequence.length; i++) {
            //寻找离i-1城市最近的城市,即确定第i个城市是哪个
            double smallDistance = Double.MAX_VALUE;
            int curCity = 0;
            for (Integer j : sequenceSet) {
                if (this.distanceMatrix[sequence[i - 1]][j] < smallDistance && j != sequence[i - 1]) {
                    smallDistance = this.distanceMatrix[sequence[i - 1]][j];
                    curCity = j;
                }
            }
            sequence[i] = curCity;
            sequenceSet.remove(curCity);
        }
      /*  for (int i = 0; i < sequence.length; i++) {
            sequence[i] = i;
        }*/
    }
    /**
     * 根据当前序列获取目标函数值
     *
     * @param sequence
     * @return
     */
    private double getObjectValue(int[] sequence) {
        double objectValue = 0;
        //计算从第0个城市到最后一个城市的路程
        for (int i = 0; i < sequence.length - 1; i++) {
            objectValue += this.distanceMatrix[sequence[i]][sequence[i + 1]];
        }
        //计算最后一个城市到第0个城市的路程
        objectValue += this.distanceMatrix[sequence[0]][sequence[sequence.length - 1]];
        return objectValue;
    }
}


测试

package com.dam.heuristic.algorithm.vns.dam;
import com.dam.heuristic.algorithm.vns.dam.v1.VnsApiV1;
import com.dam.heuristic.algorithm.vns.dam.v2.VnsApiV2;
import java.io.File;
import java.io.FileInputStream;
public class VnsMainRun {
    public static void main(String[] args) throws Exception {
        声明变量
        //距离矩阵,可以直接获取任意两个编号城市的距离
        double[][] distanceMatrix;
        //存储每个城市对应的x,y坐标
        double[][] cityPositionArr;
        读取数据
        String data = read(new File("src/main/java/com/data/tsp/att48.txt"), "GBK");
        String[] cityDataArr = data.split("\n");
        //初始化数组
        distanceMatrix = new double[cityDataArr.length][cityDataArr.length];
        cityPositionArr = new double[cityDataArr.length][2];
        for (int i = 0; i < cityDataArr.length; i++) {
            String[] city1Arr = cityDataArr[i].split(" ");
            cityPositionArr[i][0] = Double.valueOf(city1Arr[1]);
            cityPositionArr[i][1] = Double.valueOf(city1Arr[2]);
            int cityOne = Integer.valueOf(city1Arr[0]);
            for (int j = 0; j < i; j++) {
                String[] city2Arr = cityDataArr[j].split(" ");
                int cityTwo = Integer.valueOf(city2Arr[0]);
                if (cityOne == cityTwo) {
                    distanceMatrix[cityOne - 1][cityTwo - 1] = 0;
                } else {
                    distanceMatrix[cityOne - 1][cityTwo - 1] = getDistance(Double.valueOf(city1Arr[1]), Double.valueOf(city1Arr[2]), Double.valueOf(city2Arr[1]), Double.valueOf(city2Arr[2]));
                    //对称赋值
                    distanceMatrix[cityTwo - 1][cityOne - 1] = distanceMatrix[cityOne - 1][cityTwo - 1];
                }
            }
        }
/*        VnsApiV1 vnsApiV1 = new VnsApiV1(1000, 40, 500, 50, distanceMatrix);
        vnsApiV1.solve();*/
        VnsApiV2 vnsApiV2 = new VnsApiV2(3000, 100, 100000, distanceMatrix);
        vnsApiV2.solve();
    }
    /**
     * 给定两个城市坐标,获取两个城市的直线距离
     *
     * @param x1
     * @param y1
     * @param x2
     * @param y2
     * @return
     */
    private static double getDistance(double x1, double y1, double x2, double y2) {
        return Math.sqrt((Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2)) / 10);
    }
    private static String read(File f, String charset) throws Exception {
        FileInputStream fstream = new FileInputStream(f);
        try {
            int fileSize = (int) f.length();
            if (fileSize > 1024 * 512) {
                throw new Exception("File too large to read! size=" + fileSize);
            }
            byte[] buffer = new byte[fileSize];
            fstream.read(buffer);
            return new String(buffer, charset);
        } finally {
            try {
                fstream.close();
            } catch (Exception e) {
            }
        }
    }
}


结果

att48

最优目标函数值:10745.961500968939
最优解对应序列:[19, 11, 14, 32, 45, 35, 29, 42, 16, 26, 18, 36, 5, 27, 6, 17, 43, 30, 37, 7, 0, 8, 39, 2, 21, 15, 40, 33, 47, 4, 28, 1, 41, 25, 3, 34, 44, 9, 23, 31, 38, 20, 12, 24, 13, 22, 10, 46]
计算时间为:0.688s

随机生成500城市


目录
相关文章
|
13天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
17天前
|
Java 测试技术 Maven
Java一分钟之-PowerMock:静态方法与私有方法测试
通过本文的详细介绍,您可以使用PowerMock轻松地测试Java代码中的静态方法和私有方法。PowerMock通过扩展Mockito,提供了强大的功能,帮助开发者在复杂的测试场景中保持高效和准确的单元测试。希望本文对您的Java单元测试有所帮助。
32 2
|
24天前
|
Java 程序员 测试技术
Java|让 JUnit4 测试类自动注入 logger 和被测 Service
本文介绍如何通过自定义 IDEA 的 JUnit4 Test Class 模板,实现生成测试类时自动注入 logger 和被测 Service。
22 5
|
29天前
|
存储 人工智能 Java
将 Spring AI 与 LLM 结合使用以生成 Java 测试
AIDocumentLibraryChat 项目通过 GitHub URL 为指定的 Java 类生成测试代码,支持 granite-code 和 deepseek-coder-v2 模型。项目包括控制器、服务和配置,能处理源代码解析、依赖加载及测试代码生成,旨在评估 LLM 对开发测试的支持能力。
36 1
|
1月前
|
算法 决策智能
基于GA-PSO遗传粒子群混合优化算法的TSP问题求解matlab仿真
本文介绍了基于GA-PSO遗传粒子群混合优化算法解决旅行商问题(TSP)的方法。TSP旨在寻找访问一系列城市并返回起点的最短路径,属于NP难问题。文中详细阐述了遗传算法(GA)和粒子群优化算法(PSO)的基本原理及其在TSP中的应用,展示了如何通过编码、选择、交叉、变异及速度和位置更新等操作优化路径。算法在MATLAB2022a上实现,实验结果表明该方法能有效提高求解效率和解的质量。
|
1月前
|
分布式计算 Java 大数据
大数据-122 - Flink Time Watermark Java代码测试实现Tumbling Window
大数据-122 - Flink Time Watermark Java代码测试实现Tumbling Window
33 0
|
10天前
|
安全 Java 测试技术
Java并行流陷阱:为什么指定线程池可能是个坏主意
本文探讨了Java并行流的使用陷阱,尤其是指定线程池的问题。文章分析了并行流的设计思想,指出了指定线程池的弊端,并提供了使用CompletableFuture等替代方案。同时,介绍了Parallel Collector库在处理阻塞任务时的优势和特点。
|
19天前
|
安全 Java
java 中 i++ 到底是否线程安全?
本文通过实例探讨了 `i++` 在多线程环境下的线程安全性问题。首先,使用 100 个线程分别执行 10000 次 `i++` 操作,发现最终结果小于预期的 1000000,证明 `i++` 是线程不安全的。接着,介绍了两种解决方法:使用 `synchronized` 关键字加锁和使用 `AtomicInteger` 类。其中,`AtomicInteger` 通过 `CAS` 操作实现了高效的线程安全。最后,通过分析字节码和源码,解释了 `i++` 为何线程不安全以及 `AtomicInteger` 如何保证线程安全。
java 中 i++ 到底是否线程安全?
|
6天前
|
安全 Java 开发者
深入解读JAVA多线程:wait()、notify()、notifyAll()的奥秘
在Java多线程编程中,`wait()`、`notify()`和`notifyAll()`方法是实现线程间通信和同步的关键机制。这些方法定义在`java.lang.Object`类中,每个Java对象都可以作为线程间通信的媒介。本文将详细解析这三个方法的使用方法和最佳实践,帮助开发者更高效地进行多线程编程。 示例代码展示了如何在同步方法中使用这些方法,确保线程安全和高效的通信。
27 9
|
9天前
|
存储 安全 Java
Java多线程编程的艺术:从基础到实践####
本文深入探讨了Java多线程编程的核心概念、应用场景及其实现方式,旨在帮助开发者理解并掌握多线程编程的基本技能。文章首先概述了多线程的重要性和常见挑战,随后详细介绍了Java中创建和管理线程的两种主要方式:继承Thread类与实现Runnable接口。通过实例代码,本文展示了如何正确启动、运行及同步线程,以及如何处理线程间的通信与协作问题。最后,文章总结了多线程编程的最佳实践,为读者在实际项目中应用多线程技术提供了宝贵的参考。 ####