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

【运筹优化】ACO蚁群算法求解TSP问题(Java实现)

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

【运筹优化】ACO蚁群算法求解TSP问题(Java实现)

文章目录
  • 代码
    • Ant蚂蚁类
    • AntColonyOptimization_TSP蚁群算法类
  • 运行结果


代码 Ant蚂蚁类
import lombok.Data;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;


@Data
public class Ant implements Cloneable {
    // 禁忌表 
    private HashMap tabu;
    // 允许搜索的城市
    private List allowedCities;
    // 信息素变化矩阵
    private double[][] delta;
    // 距离矩阵
    private double[][] distance;
    private double alpha;
    private double beta;
    // 路径长度
    private int tourLength;
    // 城市数量
    private int cityNum;
    // 起始城市
    private int firstCity;
    // 当前城市
    private int currentCity;

    // 构造函数
    public Ant(int cityNum) {
        this.cityNum = cityNum;
        this.tourLength = 0;
    }

    // 初始化
    public void initAnt(double[][] distance, double a, double b) {
        alpha = a;
        beta = b;
        // 初始允许搜索的城市集合
        allowedCities = new ArrayList<>();
        // 初始禁忌表
        tabu = new HashMap<>();
        // 初始距离矩阵
        this.distance = distance;
        // 初始信息数变化矩阵为0
        delta = new double[cityNum][cityNum];
        for (int i = 0; i < cityNum; i++) {
            Integer integer = i;
            allowedCities.add(integer);
            for (int j = 0; j < cityNum; j++) {
                delta[i][j] = 0.f;
            }
        }
        // 设置起始城市
        Random random = new Random(System.currentTimeMillis());
        firstCity = random.nextInt(cityNum); // 随机选取第一个城市
        // 允许搜索的城市集合中移除起始城市
        for (Integer i : allowedCities) {
            if (i == firstCity) {
                allowedCities.remove(i);
                break;
            }
        }
        // 将起始城市添加至禁忌表
        tabu.put(tabu.size(), firstCity);
        // 当前城市为起始城市
        currentCity = firstCity;
    }

    //选择下一个城市
    public void selectNextCity(double[][] pheromone) {
        double[] p = new double[cityNum];
        double sum = 0d;
        // 计算分母部分
        for (Integer i : allowedCities) {
            sum += Math.pow(pheromone[currentCity][i], alpha)
                    * Math.pow(1.0 / distance[currentCity][i], beta);
        }
        // 计算概率矩阵
        for (int i = 0; i < cityNum; i++) {
            boolean flag = false;
            for (Integer j : allowedCities) {
                if (i == j) {
                    p[i] = (double) (Math.pow(pheromone[currentCity][i], alpha) * Math
                            .pow(1.0 / distance[currentCity][i], beta)) / sum;
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                p[i] = 0.f;
            }
        }
        // 轮盘赌选择下一个城市
        Random random = new Random();
        double sleectP = random.nextDouble();
        int selectCity = 0;
        double sum1 = 0d;
        for (int i = 0; i < cityNum; i++) {
            sum1 += p[i];
            if (sum1 >= sleectP) {
                selectCity = i;
                break;
            }
        }
        // 从允许选择的城市中去除select city
        for (Integer i : allowedCities) {
            if (i == selectCity) {
                allowedCities.remove(i);
                break;
            }
        }
        // 在禁忌表中添加select city
        tabu.put(tabu.size(), selectCity);
        // 将当前城市改为选择的城市
        currentCity = selectCity;
    }

    //计算路径长度
    public double calculateTourLength() {
        double len = 0.0;
        //禁忌表tabu最终形式:起始城市,城市1,城市2...城市n,起始城市
        for (int i = 0; i < cityNum; i++) {
            len += distance[this.tabu.get(i)][this.tabu.get(i + 1)];
        }
        return len;
    }

    //获取路径长度
    public double getTourLength() {
        return calculateTourLength();
    }

}
AntColonyOptimization_TSP蚁群算法类
import lombok.Data;

import java.util.Arrays;
import java.util.List;


@Data
public class AntColonyOptimization_TSP {

    public Ant[] ants; // 蚂蚁数组
    public int antNum = 15; // 蚂蚁数量
    public int cityNum; // 城市数量
    public int MAX_GEN = 500; // 运行代数
    public double[][] pheromone; // 信息素矩阵
    public double[][] distance; // 距离矩阵
    public double bestLength; // 最佳长度
    public int[] bestTour; // 最佳路径
    public int bestT; //最佳迭代数
    public List locationList;

    // 三个参数
    private double alpha = 1; //信息素重要程度
    private double beta = 5; //启发式因子重要程度
    private double rho = 0.5; //信息素挥发速率

    //构造函数
    public AntColonyOptimization_TSP(List locationList) {
        this.locationList = locationList;
        cityNum = locationList.size();
        ants = new Ant[antNum];
    }

    //外部调用窗口
    public void solve() {
        initVar();
        solver();
    }

    //
    public void solver() {
        // 迭代MAX_GEN次
        for (int g = 0; g < MAX_GEN; g++) {
            // antNum只蚂蚁
            for (int i = 0; i < antNum; i++) {
                // i这只蚂蚁走cityNum步,完整一个TSP
                for (int j = 1; j < cityNum; j++) {
                    ants[i].selectNextCity(pheromone);
                }
                // 把这只蚂蚁起始城市加入其禁忌表中
                // 禁忌表最终形式:起始城市,城市1,城市2...城市n,起始城市
                ants[i].getTabu().put(ants[i].getTabu().size(), ants[i].getFirstCity());
                // 查看这只蚂蚁行走路径距离是否比当前距离优秀
                if (ants[i].getTourLength() < bestLength) {
                    // 比当前优秀则拷贝优秀TSP路径
                    bestLength = ants[i].getTourLength();
                    for (int k = 0; k < cityNum + 1; k++) {
                        bestTour[k] = ants[i].getTabu().get(k);
                    }
                    bestT = g;
                }
                // 更新这只蚂蚁的信息数变化矩阵,对称矩阵
                for (int j = 0; j < cityNum; j++) {
                    ants[i].getDelta()[ants[i].getTabu().get(j)][ants[i]
                            .getTabu().get(j + 1)] = (double) (1.0 / ants[i]
                            .getTourLength());
                    ants[i].getDelta()[ants[i].getTabu().get(j + 1)][ants[i]
                            .getTabu().get(j)] = (1.0 / ants[i]
                            .getTourLength());
                }
            }
            // 更新信息素
            updatePheromone();
            // 重新初始化蚂蚁
            for (int i = 0; i < antNum; i++) {
                ants[i].initAnt(distance, alpha, beta);
            }
        }
        // 输出结果
        System.out.println("最佳迭代次数:" + bestT);
        System.out.println("最短路程为:" + bestLength);
        int[] bestPath = new int[cityNum + 1];
        System.arraycopy(bestTour, 0, bestPath, 0, bestTour.length);
        bestPath[cityNum] = bestPath[0];
        System.out.println("最佳路径为:" + Arrays.toString(bestPath));
    }

    //初始化
    public void initVar() {
        //初始化距离矩阵
        distance = new double[cityNum][cityNum];
        for (int i = 0; i < cityNum; i++) {
            for (int j = i; j < cityNum; j++) {
                if (i == j) {
                    distance[i][j] = 0.0;
                } else {
                    distance[i][j] = getDistance(locationList.get(i), locationList.get(j));
                    distance[j][i] = distance[i][j];
                }
            }
        }
        //初始化信息素矩阵
        pheromone = new double[cityNum][cityNum];
        for (int i = 0; i < cityNum; i++) {
            for (int j = 0; j < cityNum; j++) {
                pheromone[i][j] = 0.1; // 初始化为0.1
            }
        }
        bestLength = Integer.MAX_VALUE;
        bestTour = new int[cityNum + 1];
        // 放置蚂蚁
        for (int i = 0; i < antNum; i++) {
            ants[i] = new Ant(cityNum);
            ants[i].initAnt(distance, alpha, beta);
        }
    }

    // 更新信息素
    private void updatePheromone() {
        // 信息素挥发
        for (int i = 0; i < cityNum; i++) {
            for (int j = 0; j < cityNum; j++) {
                pheromone[i][j] = pheromone[i][j] * (1 - rho);
            }
        }
        // 信息素更新
        for (int i = 0; i < cityNum; i++) {
            for (int j = 0; j < cityNum; j++) {
                for (int k = 0; k < antNum; k++) {
                    pheromone[i][j] += ants[k].getDelta()[i][j];
                }
            }
        }
    }

    //计算两点之间的距离(如果使用伪欧氏距离,可以减少计算量)
    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)));
    }

}
运行结果
蚁群算法求解tsp问题:48个城市...
最佳迭代次数:156
最短路程为(伪欧氏距离):11107.778186984036
最佳路径为:[46, 12, 24, 13, 22, 10, 11, 14, 45, 32, 19, 16, 42, 26, 18, 36, 5, 29, 35, 27, 6, 17, 43, 30, 37, 7, 0, 8, 39, 2, 21, 15, 40, 33, 47, 4, 28, 1, 25, 3, 34, 44, 9, 41, 23, 31, 38, 20, 46]
求解用时:2.885 s
-------------------------------------------------------------------------
蚁群算法求解tsp问题:48个城市...
最佳迭代次数:44
最短路程为(欧氏距离):35156.69540961502
最佳路径为:[39, 8, 37, 30, 43, 17, 6, 27, 35, 29, 5, 36, 18, 26, 42, 16, 19, 32, 45, 14, 11, 10, 22, 13, 24, 12, 46, 20, 31, 38, 47, 4, 41, 9, 23, 44, 34, 3, 25, 1, 28, 40, 33, 2, 21, 15, 0, 7, 39]
求解用时:2.781 s
-------------------------------------------------------------------------

补充:以上使用的是tsplib上的数据att48,这是一个对称TSP问题,城市规模为48,其最优值为10628(伪欧氏距离)。tsplib地址:http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

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

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

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