【智能算法】蚁群优化算法

智能算法之一：蚁群优化算法初步了解以及Java实现

一、算法介绍

具体百度

1.1 三个重要式子

• （1）每条路选中概率
  • 其中alpha 和 beta 参数自定义
  • alpha为信息因子占的权重，权重过高，蚂蚁选中已走的路概率越高，开始走新路概率低
  • beta为两点距离的权重（能见度），权重过高，蚂蚁优先走两点最短距离的路

• （2）信息素更新
  • 信息素更新包括：信息素挥发 以及 信息素新增
  • 蚂蚁走完一遍所有城市后，就开始先计算挥发，再计算新增

二、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轴

48
1 6734 1453
2 2233 10
3 5530 1424
4 401 841
5 3082 1644
6 7608 4458
7 7573 3716
8 7265 1268
9 6898 1885
10 1112 2049
11 5468 2606
12 5989 2873
13 4706 2674
14 4612 2035
15 6347 2683
16 6107 669
17 7611 5184
18 7462 3590
19 7732 4723
20 5900 3561
21 4483 3369
22 6101 1110
23 5199 2182
24 1633 2809
25 4307 2322
26 675 1006
27 7555 4819
28 7541 3981
29 3177 756
30 7352 4506
31 7545 2801
32 3245 3305
33 6426 3173
34 4608 1198
35 23 2216
36 7248 3779
37 7762 4595
38 7392 2244
39 3484 2829
40 6271 2135
41 4985 140
42 1916 1569
43 7280 4899
44 7509 3239
45 10 2676
46 6807 2993
47 5185 3258
48 3023 1942

• （2）创建工具类来读取txt信息

public class Utils {
    /**
     * 读取文件内容，将每一行文本封装为字符串集合
     * @return
     * @throws Exception
     */
    private static List<String> readFile(){
        //文件路径，按照自己情况进行修改
        String filePath = "D:\\WorkSpace\\IDEA_workspace\\智能算法\\蚁群优化算法\\src\\main\\java\\data\\position.txt";
        List<String> texts = null;
        BufferedReader br = null;
        //异常处理
        try {
            br = new BufferedReader(new InputStreamReader(new FileInputStream(filePath))); //创建读取文件流
            texts = new ArrayList<String>(); //创建集合存储字符串

            while(true) {
                String text = br.readLine();
                if(text == null) { //直到下一行没有内容，退出循环
                    break;
                }
                texts.add(text);
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                br.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return texts;
    }

    /**
     * 创建城市Id集合
     * @return
     */
    public static List<Integer> getCitys() {
        Integer cityQuantity = Integer.valueOf(readFile().get(0));
        List<Integer> citys = new ArrayList<Integer>();
        for(int i=0; i<cityQuantity; i++) {
            citys.add(i+1);
        }
        return citys;
    }

    /**
     * 创建距离矩阵
     * @return
     */
    public static int[][] getDistanceMatrix() {
        List<String> texts = readFile();
        Integer cityQuantity = Integer.valueOf(texts.get(0));
        int[][] distanceMatrix = new int[cityQuantity][cityQuantity];

        for(int i=0; i<cityQuantity; i++) {
            distanceMatrix[i][i] = 0;
            for (int j=i+1; j<cityQuantity; j++) {
                //按空格分割字符串
                String[] city1 = texts.get(i + 1).split(" ");
                String[] city2 = texts.get(j + 1).split(" ");
                //两点距离公式（整数方便查看）
                double distance = Math.pow((Integer.valueOf(city1[1]) - Integer.valueOf(city2[1])), 2) + Math.pow((Integer.valueOf(city1[2]) - Integer.valueOf(city2[2])), 2);
                distanceMatrix[i][j] = (int) Math.sqrt(distance);
                distanceMatrix[j][i] = distanceMatrix[i][j];
            }
        }
        return distanceMatrix;
    }


    /**
     * 初始化信息素矩阵
     * @param value 初始值
     * @return
     */
    public static double[][] getPheromoneMatrix(double value) {
        Integer cityQuantity = Integer.valueOf(readFile().get(0));
        double[][] pheromoneMatrix = new double[cityQuantity][cityQuantity];
        for(int i=0; i<cityQuantity; i++) {
            for(int j=0; j<cityQuantity; j++) {
                pheromoneMatrix[i][j] = value; //赋予初始信息素值
            }
        }
        return pheromoneMatrix;
    }
}

• （3）通过使用工具类的主程序

public class Main {
    public static void main(String[] args) {
        List<Integer> citys = Utils.getCitys(); //城市集合
        double[][] pheromoneMatrix = Utils.getPheromoneMatrix(1.0); //信息素矩阵
        int[][] distanceMatrix = Utils.getDistanceMatrix(); //距离矩阵

        ACO aco = new ACO(citys, pheromoneMatrix, distanceMatrix, 150, 72);
        aco.run();
        System.out.println(aco.getBestRoute());
        System.out.println(aco.getBestLength());
    }
}