Java实现TSP旅行商问题

蚁群算法是一种用于解决TSP问题的启发式算法，它模拟了蚂蚁在寻找食物时的行为，通过不断地迭代和信息素更新，最终找到一条较优的路径。以下是Java实现TSP旅行商问题的步骤：

1. 定义城市类City，包含城市的名称和坐标信息。

public class City {
    private String name;
    private double x;
    private double y;
    //构造函数
    public City(String name, double x, double y) {
        this.name = name;
        this.x = x;
        this.y = y;
    }
    //get方法
    public String getName() {
        return name;
    }
    public double getX() {
        return x;
    }
    public double getY() {
        return y;
    }
}

2. 定义蚂蚁类Ant，包含蚂蚁的编号、当前所在城市、已访问城市列表、未访问城市列表、路径长度等信息。

public class Ant {
    private int id;
    private City currentCity;
    private List<City> visitedCities;
    private List<City> unvisitedCities;
    private double pathLength;
    //构造函数
    public Ant(int id, City startCity, List<City> cities) {
        this.id = id;
        this.currentCity = startCity;
        this.visitedCities = new ArrayList<>();
        this.visitedCities.add(startCity);
        this.unvisitedCities = new ArrayList<>(cities);
        this.unvisitedCities.remove(startCity);
        this.pathLength = 0;
    }
    //get方法
    public int getId() {
        return id;
    }
    public City getCurrentCity() {
        return currentCity;
    }
    public List<City> getVisitedCities() {
        return visitedCities;
    }
    public List<City> getUnvisitedCities() {
        return unvisitedCities;
    }
    public double getPathLength() {
        return pathLength;
    }
    //选择下一个城市
    public City selectNextCity(double[][] pheromone, double alpha, double beta) {
        double[] probabilities = new double[unvisitedCities.size()];        double sum = 0;
        for (int i = 0; i < unvisitedCities.size(); i++) {
            City city = unvisitedCities.get(i);
            double pheromoneLevel = pheromone[currentCity.getName()][city.getName()];
            double distance = getDistance(currentCity, city);
            probabilities[i] = Math.pow(pheromoneLevel, alpha) * Math.pow(1 / distance, beta);
            sum += probabilities[i];
        }
        for (int i = 0; i < probabilities.length; i++) {
            probabilities[i] /= sum;
        }
        double random = Math.random();
        double p = 0;
        for (int i = 0; i < probabilities.length; i++) {
            p += probabilities[i];
            if (random < p) {
                City nextCity = unvisitedCities.get(i);
                visitedCities.add(nextCity);
                unvisitedCities.remove(nextCity);
                pathLength += getDistance(currentCity, nextCity);
                currentCity = nextCity;
                return nextCity;
            }
        }
        return null;
    }
    //计算两个城市之间的距离
    private double getDistance(City city1, City city2) {
        double x1 = city1.getX();
        double y1 = city1.getY();
        double x2 = city2.getX();
        double y2 = city2.getY();
        return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    }
}

3. 定义蚁群类AntColony，包含城市列表、蚂蚁列表、信息素矩阵、信息素挥发率、信息素增强系数等信息。

public class AntColony {
    private List<City> cities;
    private List<Ant> ants;
    private double[][] pheromone;
    private double evaporationRate;
    private double alpha;
    private double beta;
    private double Q;
    //构造函数
    public AntColony(List<City> cities, int antCount, double evaporationRate, double alpha, double beta, double Q) {
        this.cities = cities;
        this.ants = new ArrayList<>();
        for (int i = 0; i < antCount; i++) {
            Ant ant = new Ant(i, cities.get(0), cities);
            ants.add(ant);
        }
        this.pheromone = new double[cities.size()][cities.size()];
        for (int i = 0; i < cities.size(); i++) {
            for (int j = 0; j < cities.size(); j++) {
                pheromone[i][j] = 1;
            }
        }
        this.evaporationRate = evaporationRate;
        this.alpha = alpha;
        this.beta = beta;
        this.Q = Q;
    }
    //运行蚁群算法
    public List<City> run(int maxIterations) {
        List<City> bestTour = null;
        double bestLength = Double.MAX_VALUE;
        for (int i = 0; i < maxIterations; i++) {
            for (Ant ant : ants) {
                while (!ant.getUnvisitedCities().isEmpty()) {
                    ant.selectNextCity(pheromone, alpha, beta);
                }
                ant.getPathLength() += getDistance(ant.getCurrentCity(), ant.getVisitedCities().get(0));
                if (ant.getPathLength() < bestLength) {
                    bestLength = ant.getPathLength();
                    bestTour = new ArrayList<>(ant.getVisitedCities());
                }
                for (int j = 0; j < ant.getVisitedCities().size() - 1; j++) {
                    int city1 = ant.getVisitedCities().get(j).getName();
                    int city2 = ant.getVisitedCities().get(j + 1).getName();
                    pheromone[city1][city2] = (1 - evaporationRate) * pheromone[city1][city2] + evaporationRate * Q / ant.getPathLength();
                    pheromone[city2][city1] = pheromone[city1][city2];
                }
                ant.getVisitedCities().clear();
                ant.getVisitedCities().add(cities.get(0));
                ant.getUnvisitedCities().clear();
                ant.getUnvisitedCities().addAll(cities);
                ant.getUnvisitedCities().remove(cities.get(0));
                ant.setPathLength(0);
            }
        }
        return bestTour;
    }
    //计算两个城市之间的距离
    private double getDistance(City city1, City city2) {
        double x1 = city1.getX();
        double y1 = city1.getY();
        double x2 = city2.getX();
        double y2 = city2.getY();
        return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    }
}

4. 在主函数中读取城市信息，创建AntColony对象并运行蚁群算法，输出最优路径和路径长度。

public static void main(String[] args) {
    List<City> cities = new ArrayList<>();
    try {
        BufferedReader reader = new BufferedReader(new FileReader("cities.txt"));
        String line;
        while ((line = reader.readLine()) != null) {
            String[] parts = line.split(",");
            String name = parts[0];
            double x = Double.parseDouble(parts[1]);
            double y = Double.parseDouble(parts[2]);
            City city = new City(name, x, y);
            cities.add(city);
        }
        reader.close();
    } catch (IOException e) {
        e.printStackTrace();
    }
    AntColony antColony = new AntColony(cities, 50, 0.5, 1, 5, 100);
    List<City> bestTour = antColony.run(1000);
    System.out.println("Best tour: " + bestTour);
    double bestLength = 0;
    for (int i = 0; i < bestTour.size() - 1; i++) {
        bestLength += antColony.getDistance(bestTour.get(i), bestTour.get(i + 1));
    }
    System.out.println("Best length: " + bestLength);
}