求解旅行商问题：蚁群优化与遗传算法效率对比实验数据采集问询

核心采集指标 #

• 运行时间：用Java的System.currentTimeMillis()或Instant类精确统计算法从启动到输出结果的总耗时，记录单次运行的绝对时长。
• 解的质量：计算最终路径的总长度，对比两种算法找到的最优解与TSPLIB标准数据集的已知最优解的偏差率。
• 收敛速度：每一代遗传算法（GA）或每一轮蚁群迭代（ACO）后，记录当前最优解的长度，用于绘制收敛曲线，评估算法逼近最优解的快慢。

控制变量与数据可靠性 #

• 固定数据集：使用TSPLIB的标准实例（如eil51、berlin52），确保实验基准一致，避免自定义数据集的随机性干扰。
• 统一硬件环境：关闭后台无关程序，固定JVM参数（如-Xmx2G），消除硬件波动对性能的影响。
• 标准化参数配置：为两种算法设置合理参数（如GA的种群大小设为100、交叉率0.7；ACO的蚂蚁数量20、信息素挥发系数0.1），尽量让参数处于各自的最优区间，保证对比公平性。
• 重复实验统计：对每个数据集重复运行5-10次，取结果的平均值和标准差，降低随机因素的影响。

• 数据集工具：TSPLIB，提供大量标准化TSP实例，可直接读取其.tsp格式文件，Java中可自行编写解析器处理坐标数据。
• 性能分析工具：
  • JProfiler：分析Java程序的CPU、内存占用，定位算法中的性能瓶颈。
  • VisualVM：JDK自带工具，实时监控程序运行时的线程、内存指标，适合快速排查问题。
• 数据可视化工具：
  • Excel：处理实验数据的均值、标准差，生成收敛曲线和性能对比柱状图。
  • Matplotlib：若熟悉Python，可实现更灵活的专业可视化，生成高精度对比图表。

基础城市类 #

public class City {
    private double x;
    private double y;

    public City(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double distanceTo(City other) {
        double dx = this.x - other.x;
        double dy = this.y - other.y;
        return Math.sqrt(dx*dx + dy*dy);
    }

    public double getX() { return x; }
    public double getY() { return y; }
}

遗传算法（GA）实现 #

import java.util.*;

public class GeneticAlgorithmTSP {
    private List<City> cities;
    private int populationSize;
    private double mutationRate;
    private double crossoverRate;
    private int elitismCount;

    public GeneticAlgorithmTSP(List<City> cities, int populationSize, double mutationRate, double crossoverRate, int elitismCount) {
        this.cities = cities;
        this.populationSize = populationSize;
        this.mutationRate = mutationRate;
        this.crossoverRate = crossoverRate;
        this.elitismCount = elitismCount;
    }

    public List<List<City>> initPopulation() {
        List<List<City>> population = new ArrayList<>();
        for (int i = 0; i < populationSize; i++) {
            List<City> individual = new ArrayList<>(cities);
            Collections.shuffle(individual);
            population.add(individual);
        }
        return population;
    }

    public double calculateFitness(List<City> individual) {
        double totalDistance = 0;
        for (int i = 0; i < individual.size() - 1; i++) {
            totalDistance += individual.get(i).distanceTo(individual.get(i+1));
        }
        totalDistance += individual.get(individual.size()-1).distanceTo(individual.get(0));
        return 1 / totalDistance;
    }

    public List<City> selectParent(List<List<City>> population, double[] fitnesses) {
        double totalFitness = Arrays.stream(fitnesses).sum();
        double randomValue = new Random().nextDouble() * totalFitness;
        double currentSum = 0;
        for (int i = 0; i < population.size(); i++) {
            currentSum += fitnesses[i];
            if (currentSum >= randomValue) {
                return population.get(i);
            }
        }
        return population.get(population.size()-1);
    }

    public List<City> crossover(List<City> parent1, List<City> parent2) {
        if (new Random().nextDouble() >= crossoverRate) {
            return new ArrayList<>(parent1);
        }
        List<City> child = new ArrayList<>(Collections.nCopies(cities.size(), null));
        int start = new Random().nextInt(cities.size());
        int end = new Random().nextInt(cities.size());
        if (start > end) {
            int temp = start;
            start = end;
            end = temp;
        }
        for (int i = start; i <= end; i++) {
            child.set(i, parent1.get(i));
        }
        int currentPos = (end + 1) % cities.size();
        for (City city : parent2) {
            if (!child.contains(city)) {
                child.set(currentPos, city);
                currentPos = (currentPos + 1) % cities.size();
            }
        }
        return child;
    }

    public void mutate(List<City> individual) {
        if (new Random().nextDouble() >= mutationRate) {
            return;
        }
        int pos1 = new Random().nextInt(cities.size());
        int pos2 = new Random().nextInt(cities.size());
        Collections.swap(individual, pos1, pos2);
    }

    public List<List<City>> evolvePopulation(List<List<City>> population) {
        List<List<City>> newPopulation = new ArrayList<>();
        population.sort((a, b) -> Double.compare(calculateFitness(b), calculateFitness(a)));
        for (int i = 0; i < elitismCount; i++) {
            newPopulation.add(population.get(i));
        }
        double[] fitnesses = population.stream().mapToDouble(this::calculateFitness).toArray();
        for (int i = elitismCount; i < populationSize; i++) {
            List<City> parent1 = selectParent(population, fitnesses);
            List<City> parent2 = selectParent(population, fitnesses);
            List<City> child = crossover(parent1, parent2);
            mutate(child);
            newPopulation.add(child);
        }
        return newPopulation;
    }

    public List<City> run(int generations) {
        List<List<City>> population = initPopulation();
        List<City> bestIndividual = population.get(0);
        double bestFitness = calculateFitness(bestIndividual);
        for (int i = 0; i < generations; i++) {
            population = evolvePopulation(population);
            List<City> currentBest = population.stream()
                    .max(Comparator.comparingDouble(this::calculateFitness))
                    .orElse(null);
            double currentFitness = calculateFitness(currentBest);
            if (currentFitness > bestFitness) {
                bestFitness = currentFitness;
                bestIndividual = currentBest;
            }
        }
        return bestIndividual;
    }
}

蚁群优化（ACO）实现 #

import java.util.*;

public class AntColonyOptimizationTSP {
    private List<City> cities;
    private int antCount;
    private double alpha;
    private double beta;
    private double evaporationRate;
    private double Q;
    private double[][] pheromone;
    private double[][] distance;

    public AntColonyOptimizationTSP(List<City> cities, int antCount, double alpha, double beta, double evaporationRate, double Q) {
        this.cities = cities;
        this.antCount = antCount;
        this.alpha = alpha;
        this.beta = beta;
        this.evaporationRate = evaporationRate;
        this.Q = Q;
        int cityCount = cities.size();
        pheromone = new double[cityCount][cityCount];
        distance = new double[cityCount][cityCount];
        for (int i = 0; i < cityCount; i++) {
            Arrays.fill(pheromone[i], 1.0 / cityCount);
            for (int j = 0; j < cityCount; j++) {
                if (i != j) {
                    distance[i][j] = cities.get(i).distanceTo(cities.get(j));
                } else {
                    distance[i][j] = Double.MIN_VALUE;
                }
            }
        }
    }

    public List<Integer> constructSolution(int antIndex) {
        int cityCount = cities.size();
        List<Integer> path = new ArrayList<>();
        boolean[] visited = new boolean[cityCount];
        int startCity = new Random().nextInt(cityCount);
        path.add(startCity);
        visited[startCity] = true;
        for (int i = 1; i < cityCount; i++) {
            int currentCity = path.get(path.size()-1);
            int nextCity = selectNextCity(currentCity, visited);
            path.add(nextCity);
            visited[nextCity] = true;
        }
        return path;
    }

    private int selectNextCity(int currentCity, boolean[] visited) {
        int cityCount = cities.size();
        double[] probabilities = new double[cityCount];
        double totalProbability = 0;
        for (int i = 0; i < cityCount; i++) {
            if (!visited[i]) {
                probabilities[i] = Math.pow(pheromone[currentCity][i], alpha) * Math.pow(1 / distance[currentCity][i], beta);
                totalProbability += probabilities[i];
            }
        }
        for (int i = 0; i < cityCount; i++) {
            if (!visited[i]) {
                probabilities[i] /= totalProbability;
            }
        }
        double randomValue = new Random().nextDouble();
        double currentSum = 0;
        for (int i = 0; i < cityCount; i++) {
            if (!visited[i]) {
                currentSum += probabilities[i];
                if (currentSum >= randomValue) {
                    return i;
                }
            }
        }
        for (int i = 0; i < cityCount; i++) {
            if (!visited[i]) {
                return i;
            }
        }
        return -1;
    }

    private void updatePheromone(List<List<Integer>> paths, double[] pathLengths) {
        int cityCount = cities.size();
        for (int i = 0; i < cityCount; i++) {
            for (int j = 0; j < cityCount; j++) {
                pheromone[i][j] *= (1 - evaporationRate);
            }
        }
        for (int k = 0; k < antCount; k++) {
            List<Integer> path = paths.get(k);
            double delta = Q / pathLengths[k];
            for (int i = 0; i < path.size() - 1; i++) {
                int city1 = path.get(i);
                int city2 = path.get(i+1);
                pheromone[city1][city2] += delta;
                pheromone[city2][city1] += delta;
            }
            int lastCity = path.get(path.size()-1);
            int firstCity = path.get(0);
            pheromone[lastCity][firstCity] += delta;
            pheromone[firstCity][lastCity] += delta;
        }
    }

    public double calculatePathLength(List<Integer> path) {
        double totalDistance = 0;
        for (int i = 0; i < path.size() - 1; i++) {
            totalDistance += distance[path.get(i)][path.get(i+1)];
        }
        totalDistance += distance[path.get(path.size()-1)][path.get(0)];
        return totalDistance;
    }

    public List<Integer> run(int iterations) {
        List<Integer> bestPath = null;
        double bestPathLength = Double.MAX_VALUE;
        for (int iter = 0; iter < iterations; iter++) {
            List<List<Integer>> paths = new ArrayList<>();
            double[] pathLengths = new double[antCount];
            for (int k = 0; k < antCount; k++) {
                List<Integer> path = constructSolution(k);
                paths.add(path);
                pathLengths[k] = calculatePathLength(path);
                if (pathLengths[k] < bestPathLength) {
                    bestPathLength = pathLengths[k];
                    bestPath = new ArrayList<>(path);
                }
            }
            updatePheromone(paths, pathLengths);
        }
        return bestPath;
    }
}

测试主类 #

import java.util.ArrayList;
import java.util.List;

public class TSPTest {
    public static void main(String[] args) {
        // 测试城市集合（可替换为TSPLIB数据集）
        List<City> cities = new ArrayList<>();
        cities.add(new City(1, 2));
        cities.add(new City(3, 4));
        cities.add(new City(5, 1));
        cities.add(new City(2, 5));
        cities.add(new City(4, 3));

        // 运行GA
        long gaStart = System.currentTimeMillis();
        GeneticAlgorithmTSP ga = new GeneticAlgorithmTSP(cities, 100, 0.01, 0.7, 2);
        List<City> gaBest = ga.run(500);
        long gaEnd = System.currentTimeMillis();
        double gaLength = 1 / ga.calculateFitness(gaBest);
        System.out.println("GA最优路径长度: " + gaLength);
        System.out.println("GA运行时间: " + (gaEnd - gaStart) + "ms");

        // 运行ACO
        long acoStart = System.currentTimeMillis();
        AntColonyOptimizationTSP aco = new AntColonyOptimizationTSP(cities, 20, 1.0, 2.0, 0.1, 100.0);
        List<Integer> acoBest = aco.run(100);
        long acoEnd = System.currentTimeMillis();
        double acoLength = aco.calculatePathLength(acoBest);
        System.out.println("ACO最优路径长度: " + acoLength);
        System.out.println("ACO运行时间: " + (acoEnd - acoStart) + "ms");
    }
}

内容的提问来源于stack exchange，提问作者Zahra Zams