package com.dam.heuristic.aco.test;
import java.util.*;
public class Ant {
    //蚂蚁所走的城市序列
    private List<Integer> sequence;
    //未访问的城市
    private LinkedHashSet<Integer> unVisitedCities;
    //信息素变化矩阵
    private double[][] delta;
    //距离矩阵
    private double[][] distanceMatrix;
    //信息素重要程度因子，其值越大，表示信息素的浓度在转移中起的作用越大
    private double alpha;
    //启发函数重要程度因子，其值越大，表示启发函数在转移中的作用越大，即蚂蚁会以较大的概率转移到距离短的城市
    private double beta;
    //城市数量
    private int cityNum;
    //蚂蚁的起始城市
    private int firstCity;
    //蚂蚁当前所在城市
    private int currentCity;
    public Ant(double[][] distanceMatrix, double alpha, double beta) {
        this.distanceMatrix = distanceMatrix;
        this.alpha = alpha;
        this.beta = beta;
        this.cityNum = distanceMatrix[0].length;
        this.unVisitedCities = new LinkedHashSet<>();
        this.sequence = new ArrayList<>();
        this.delta = new double[cityNum][cityNum];
    }
    /**
     * 初始化蚂蚁，随机选择起始位置
     */
    public void initAntMessage() {
        this.unVisitedCities.clear();
        this.sequence.clear();
        //初始化信息素变化矩阵为0
        for (int i = 0; i < cityNum; i++) {
            for (int j = 0; j < cityNum; j++) {
                this.delta[i][j] = 0;
            }
            this.unVisitedCities.add(i);
        }
        //随机挑选一个城市作为起始城市
        this.firstCity = new Random().nextInt(cityNum);
        //未访问城市集合中移除起始城市
        this.unVisitedCities.remove(this.firstCity);
        //将起始城市添加至序列中
        this.sequence.add(this.firstCity);
        //设置蚂蚁当前所在城市为起始城市
        this.currentCity = firstCity;
    }
    /**
     * 结合蚂蚁当前所在城市和信息素矩阵选择蚂蚁下一个要访问的城市
     *
     * @param pheromone 信息素矩阵
     */
    public void selectNextCity(double[][] pheromone) {
        计算从当前城市去往未访问城市的概率
        double[] p = new double[this.cityNum];
        //分母
        double denominator = 0;
        //计算分母部分
        for (Integer cityIndex : this.unVisitedCities) {
            denominator += Math.pow(pheromone[this.currentCity][cityIndex], alpha) * Math.pow(1.0 / distanceMatrix[this.currentCity][cityIndex], beta);
        }
        //计算去未访问的城市的概率矩阵，去过的城市概率为0，不用设置
        for (Integer cityIndex : this.unVisitedCities) {
            //除以分母，求概率，同时也是归一化的一种方式
            p[cityIndex] = (Math.pow(pheromone[this.currentCity][cityIndex], alpha) * Math.pow(1.0 / distanceMatrix[this.currentCity][cityIndex], beta)) / denominator;
        }
        轮盘赌选择下一个城市
        //指针指向的概率
        double selectP = new Random().nextDouble();
        //下一个要访问的城市
        int nextCity = -1;
        //存储最后一个未访问的城市，防止浮点数精度原因，没有选择到城市
        int lastAllowedCity = -1;
        double sum = 0;
        for (Integer city : this.unVisitedCities) {
            lastAllowedCity = city;
            sum += p[city];
            //找到指针指向的城市，退出循环
            if (sum >= selectP) {
                nextCity = city;
                break;
            }
        }
        //当没有选择到城市时，选择未访问城市中的最后一个城市
        nextCity = nextCity == -1 ? lastAllowedCity : nextCity;
        //从允许选择的城市中去除selectCity
        this.unVisitedCities.remove(nextCity);
        //在sequence中添加nextCity
        this.sequence.add(nextCity);
        //将当前城市改为选择的城市
        this.currentCity = nextCity;
    }
    /**
     * 计算路径长度
     *
     * @return 路径长度
     */
    private double getObjectValue() {
        double objectValue = 0;
        //sequence最终样式：起始城市,城市1,城市2，... ,结尾城市，起始城市
        //this.sequence.size() - 1的原因，两点之间有一段距离，三点之间有两端距离
        for (int i = 0; i < this.sequence.size() - 1; i++) {
            objectValue += distanceMatrix[this.sequence.get(i)][this.sequence.get(i + 1)];
        }
        return objectValue;
    }
    public List<Integer> getSequence() {
        return sequence;
    }
    public void setSequence(List<Integer> sequence) {
        this.sequence = sequence;
    }
    public LinkedHashSet<Integer> getUnVisitedCities() {
        return unVisitedCities;
    }
    public void setUnVisitedCities(LinkedHashSet<Integer> unVisitedCities) {
        this.unVisitedCities = unVisitedCities;
    }
    public double[][] getDelta() {
        return delta;
    }
    public void setDelta(double[][] delta) {
        this.delta = delta;
    }
    public double[][] getDistanceMatrix() {
        return distanceMatrix;
    }
    public void setDistanceMatrix(double[][] distanceMatrix) {
        this.distanceMatrix = distanceMatrix;
    }
    public double getAlpha() {
        return alpha;
    }
    public void setAlpha(double alpha) {
        this.alpha = alpha;
    }
    public double getBeta() {
        return beta;
    }
    public void setBeta(float beta) {
        this.beta = beta;
    }
    public double getBestObjectValue() {
        return this.getObjectValue();
    }
    public int getCityNum() {
        return cityNum;
    }
    public void setCityNum(int cityNum) {
        this.cityNum = cityNum;
    }
    public int getFirstCity() {
        return firstCity;
    }
    public void setFirstCity(int firstCity) {
        this.firstCity = firstCity;
    }
    public int getCurrentCity() {
        return currentCity;
    }
    public void setCurrentCity(int currentCity) {
        this.currentCity = currentCity;
    }
}

package com.dam.heuristic.aco.test;
import java.util.Arrays;
/**
 * 蚁群算法
 */
public class AcoApi {
    //蚂蚁数组
    private Ant[] antArr;
    //蚂蚁数量
    private int antNum;
    //城市数量
    private int cityNum;
    //迭代次数
    private int MAX_GEN;
    //信息素矩阵
    private double[][] pheromone;
    //最短回路长度
    private double bestObjectValue;
    //最佳路径
    private int[] bestSequence;
    //信息素挥发程度参数
    private double rho;
    public AcoApi(int antNum, int MAX_GEN, double alpha, double beta, double rho, double[][] distanceMatrix) {
        this.antNum = antNum;
        this.cityNum = distanceMatrix[0].length;
        this.MAX_GEN = MAX_GEN;
        this.rho = rho;
        //初始化信息素矩阵
        this.pheromone = new double[this.cityNum][this.cityNum];
        for (int i = 0; i < this.cityNum; i++) {
            for (int j = 0; j < this.cityNum; j++) {
                this.pheromone[i][j] = 0.1f; //初始化为0.1
            }
        }
        //初始化最优路径长度
        bestObjectValue = Integer.MAX_VALUE;
        //初始化最优序列
        bestSequence = new int[cityNum];
        //随机放置蚂蚁
        this.antArr =new Ant[antNum];
        for (int i = 0; i < antNum; i++) {
            this.antArr[i] = new Ant(distanceMatrix, alpha, beta);
            this.antArr[i].initAntMessage();
        }
    }
    public void solve() {
        long startTime = System.currentTimeMillis();
        //迭代MAX_GEN次
        for (int t = 0; t < this.MAX_GEN; t++) {
            //让所有蚂蚁都从自己的起点出发，完整走一个回路
            for (int i = 0; i < this.antNum; i++) {
                //让第i只蚂蚁走完所有城市，形成一个回路，j从1开始是因为蚂蚁本身已在起点城市
                for (int j = 1; j < this.cityNum; j++) {
                    this.antArr[i].selectNextCity(this.pheromone);
                }
                //把这只蚂蚁起始城市加入序列中
                this.antArr[i].getSequence().add(this.antArr[i].getFirstCity());
                //查看蚂蚁i所走的路径距离是否比当前最优解更好
                if (this.antArr[i].getBestObjectValue() < this.bestObjectValue) {
                    //更新最优解
                    this.bestObjectValue = this.antArr[i].getBestObjectValue();
                    for (int j = 0; j < this.cityNum; j++) {
                        this.bestSequence[j] = this.antArr[i].getSequence().get(j);
                    }
                    System.out.println("----------------------------------------------------------------------------------------------------------------");
                    System.out.println("当前代数：" + t);
                    System.out.println("当前最优解为：" + bestObjectValue);
                    System.out.println("当前计算时间为：" + (System.currentTimeMillis() - startTime) + "ms");
                    System.out.println("----------------------------------------------------------------------------------------------------------------");
                }
                //更新这只蚂蚁的信息数变化矩阵，对称矩阵
                for (int j = 0; j < this.cityNum; j++) {
                    this.antArr[i].getDelta()[this.antArr[i].getSequence().get(j)][this.antArr[i].getSequence().get(j + 1)]
                            = (1.0 / this.antArr[i].getBestObjectValue());
                    this.antArr[i].getDelta()[this.antArr[i].getSequence().get(j + 1)][this.antArr[i].getSequence().get(j)]
                            = (1.0 / this.antArr[i].getBestObjectValue());
                }
            }
            //更新信息素
            this.updatePheromone();
            //将蚂蚁放到不同的位置，重新初始化蚂蚁
            for (int i = 0; i < this.antNum; i++) {
                this.antArr[i].initAntMessage();
            }
        }
        System.out.println("最优解："+this.bestObjectValue);
        System.out.println("最优序列："+ Arrays.toString(this.bestSequence));
        System.out.println("计算时间："+(System.currentTimeMillis()-startTime)+"ms");
    }
    /**
     * 更新信息素
     */
    private void updatePheromone() {
        //信息素挥发
        for (int i = 0; i < this.cityNum; i++) {
            for (int j = 0; j < this.cityNum; j++) {
                this.pheromone[i][j] = this.pheromone[i][j] * (1 - this.rho);
            }
        }
        //信息素更新
        for (int i = 0; i < this.cityNum; i++) {
            for (int j = 0; j < this.cityNum; j++) {
                for (int k = 0; k < this.antNum; k++) {
                    this.pheromone[i][j] += this.antArr[k].getDelta()[i][j];
                }
            }
        }
    }
}

package com.dam.heuristic.aco.test;
import com.dam.heuristic.aco.csdn.Aco;
import com.dam.heuristic.ts.test.TsApi;
import java.io.File;
import java.io.FileInputStream;
public class AcoMainRun {
    public static void main(String[] args) throws Exception {
        声明变量
        //距离矩阵，可以直接获取任意两个编号城市的距离
        double[][] distanceMatrix;
        读取数据
        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];
        for (int i = 0; i < cityDataArr.length; i++) {
            String[] city1Arr = cityDataArr[i].split(" ");
            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];
                }
            }
        }
     /*   System.out.println("输出距离矩阵-------------------------------------------------------------------");
        for (double[] matrix : distanceMatrix) {
            System.out.println(Arrays.toString(matrix));
        }*/
        AcoApi acoApi = new AcoApi(15,500, 1.0,5.0, 0.5, distanceMatrix);
        acoApi.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) {
            }
        }
    }
}