基于Springboot+Mybatis+Mysql的网盘文件管理系统
一、算法介绍
具体百度
1.1 三个重要式子
（1）每条路选中概率
其中alpha 和 beta 参数自定义
alpha为信息因子占的权重，权重过高，蚂蚁选中已走的路概率越高，开始走新路概率低
beta为两点距离的权重（能见度），权重过高，蚂蚁优先走两点最短距离的路
{% asset_img rate.png %}
（2）信息素更新
信息素更新包括：信息素挥发 以及 信息素新增
蚂蚁走完一遍所有城市后，就开始先计算挥发，再计算新增
{% asset_img sub.png %}
{% asset_img add.png %}
二、Java实现代码（TSP问题）
2.1 TSP问题
- 简单来说，就是寻找一条访问所有城市，最短的一条路线
- 前提：所有城市之间是互通的，任意两个城市可以来往
2.2 Java实现代码
//创建一个蚂蚁类 Ant.java public class Ant { private List<Integer> route = new ArrayList<Integer>(); //路线：记录蚂蚁行走的路线 private Integer currentCity; //当前城市：记录蚂蚁当前所在城市的ID private List<Integer> citys = new ArrayList<Integer>(); //城市：记录需要行走的城市ID private double[][] pheromoneMatrix; //信息素矩阵 private int[][] distanceMatrix; //距离矩阵（整型方便查看） //构造器 public Ant(List<Integer> citys, double[][] pheromoneMatrix, int[][] distanceMatrix) { this.citys = citys; this.pheromoneMatrix = pheromoneMatrix; this.distanceMatrix = distanceMatrix; } /** * 添加路线 * @param cityId */ private void addRoute(Integer cityId) { route.add(cityId); //路线中添加城市ID currentCity = cityId; //当前城市修改为城市ID citys.remove(cityId); //需要行走的城市移除当前城市ID } /** * 随机选择初始城市 */ private void randomSelectCity() { Random random = new Random(); Integer cityId = random.nextInt(citys.size())+1; addRoute(cityId); } /** * 选择下一个城市 */ private void selectNextCity() { if(citys.size() == 1) { addRoute(citys.get(0)); addRoute(route.get(0)); //路线添加最开始的城市 return; } Double alpha = 1.0; //信息素因子权重 Double beta = 2.0; //路线距离权重 Map<Integer, Double> molecules = new HashMap<Integer, Double>(); //计算选路概率公式中的分子 for (Integer city : citys) { //城市从1开始数，数组从0开始数，所以涉及数组都要‘-1’ Double molecule = Math.pow(pheromoneMatrix[currentCity-1][city-1], alpha) * Math.pow(1.0 / distanceMatrix[currentCity-1][city-1], beta); molecules.put(city, molecule); } //计算选路概率公式中的分母 Double totalMolecule = 0.0; for(Integer city : molecules.keySet()) { totalMolecule += molecules.get(city); } //轮盘赌选择下一个城市 double random = Math.random(); Double temp = 0.0; for(Integer city : molecules.keySet()) { temp += molecules.get(city) / totalMolecule; if(temp >= random) { addRoute(city); break; } } } /** * 蚂蚁开始旅行所有城市 */ public void tour() { int cityQuantity = citys.size(); randomSelectCity(); for(int i=0; i<cityQuantity; i++) { selectNextCity(); } } /** * 获取路线 * @return */ public List<Integer> getRoute() { return route; } /** * 计算路线总距离 * @return */ public Integer getRouteLength() { Integer length = 0; for(int i=0; i<route.size()-1; i++) { length += distanceMatrix[route.get(i)-1][route.get(i+1)-1]; } return length; } }
//创建一个AOC类：是蚁群优化算法主要实现类 public class ACO { List<Integer> citys = new ArrayList<Integer>(); //城市集合 private double[][] pheromoneMatrix; //信息素矩阵 private int[][] distanceMatrix; //距离矩阵 private int times; //运行次数 private int antQuantity; // 蚂蚁数量 private List<Integer> bestRoute; //最佳路线 private Integer bestLength = -1; //最佳距离 //构造器 public ACO(List<Integer> citys, double[][] pheromoneMatrix, int[][] distanceMatrix, int times, int antQuantity) { this.citys = citys; this.pheromoneMatrix = pheromoneMatrix; this.distanceMatrix = distanceMatrix; this.times = times; this.antQuantity = antQuantity; } /** * 更新信息素 * @param ants 蚂蚁群 */ private void update(List<Ant> ants) { //信息素挥发 double volatilizationRate = 0.5; //挥发率 for(int i=0; i<citys.size(); i++) { for(int j=0; j<citys.size(); j++) { pheromoneMatrix[i][j] = pheromoneMatrix[i][j] * (1.0-volatilizationRate); } } //信息素新增 for(Ant ant : ants) { List<Integer> route = ant.getRoute(); for(int i=0; i<route.size()-1; i++){ pheromoneMatrix[route.get(i)-1][route.get(i+1)-1] += 1.0 / ant.getRouteLength(); } } } /** * 记录最佳路径和最佳距离 */ private void recordBest(List<Ant> ants) { //给bestLength赋予初始值 if(bestLength == -1.0) { bestLength = ants.get(0).getRouteLength(); bestRoute = ants.get(0).getRoute(); } //遍历比较最佳 for(Ant ant : ants) { if(bestLength > ant.getRouteLength()) { bestLength = ant.getRouteLength(); bestRoute = ant.getRoute(); } } } /** * 运行蚁群优化算法 */ private void runAlgorithm(){ //创建蚂蚁集合存储蚂蚁 List<Ant> ants = new ArrayList<Ant>(); for(int i=0; i<antQuantity; i++){ //复制城市集合(集合为地址引用，为了不影响原参数，复制一个新集合) List<Integer> cityCopy = new ArrayList<Integer>(); for (Integer city : citys) { cityCopy.add(city); } //创建蚂蚁，并开始旅行所有城市 Ant ant = new Ant(cityCopy, pheromoneMatrix, distanceMatrix); ant.tour(); ants.add(ant); } update(ants); //更新信息素 recordBest(ants); //记录最佳路线与距离 } /** * 多次运行蚁群优化算法（蚂蚁算法的运行入口） */ public void run() { for(int i=0; i<times; i++){ runAlgorithm(); } } /** * 获取最佳路线 */ public List<Integer> getBestRoute() { return bestRoute; } /** * 获取最佳距离 */ public Integer getBestLength() { return bestLength; } }
针对TSP问题的蚂蚁优化算法就写好了，只要创建AOC，传入对应的参数，运行run()方法就会跑起来，通过getXxxx获取路线以及路线长度
//主程序代码演示 public class Main { public static void main(String[] args) { //自定义距离矩阵 int[][] distanceMatrix = new int[][]{{0, 1, 3, 1}, {1, 0, 3, 2}, {3, 3, 0, 2}, {1, 2, 2, 0}}; //创建信息素矩阵并赋初值 double[][] pheromoneMatrix = new double[4][4]; for(int i=0; i<distanceMatrix.length; i++) { for(int j=0; j<distanceMatrix.length; j++) { pheromoneMatrix[i][j] = 0.1; } } //创建城市集合 List<Integer> citys = new ArrayList<Integer>(); for(int i=0; i<4; i++) { citys.add(i+1); } //运行蚁群优化算法 ACO aco = new ACO(citys, pheromoneMatrix, distanceMatrix, 50, 6); aco.run(); System.out.println(aco.getBestRoute()); System.out.println(aco.getBestLength()); } }
2.3 自定义工具类
- 由于自己定义距离矩阵，信息素矩阵觉得麻烦，就创建一个工具类实现创建
- （1）将城市信息存储在一个txt文件中
- 城市ID X轴 Y轴
源码+数据库：https://download.csdn.net/download/wyn_365/85430779
