数学建模常用算法:变邻域搜索算法(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城市


目录
相关文章
|
16天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
49 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
17天前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
29 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
26天前
|
算法 决策智能
基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
该程序基于禁忌搜索算法求解车辆路径问题(VRP),使用MATLAB2022a版本实现,并带有GUI界面。用户可通过界面设置参数并查看结果。禁忌搜索算法通过迭代改进当前解,并利用记忆机制避免陷入局部最优。程序包含初始化、定义邻域结构、设置禁忌列表等步骤,最终输出最优路径和相关数据图表。
|
22天前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
50 2
|
2月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
49 2
|
26天前
|
存储 算法 C++
【搜索算法】 跳马问题(C/C++)
【搜索算法】 跳马问题(C/C++)
|
26天前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)
|
26天前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
15 0
|
3月前
|
算法
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
62 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
3月前
|
安全 应用服务中间件 网络安全
Python 渗透测试:漏洞的批量搜索与利用.(GlassFish 任意文件读取)
Python 渗透测试:漏洞的批量搜索与利用.(GlassFish 任意文件读取)
47 11