遗传算法解决tsp问题 java实现

以下是一个简单的Java程序，使用遗传算法解决TSP问题：

import java.util.Arrays;
import java.util.Random;

public class TSPGeneticAlgorithm {

    // 城市坐标
    static int[][] cities = {{60, 200}, {180, 200}, {80, 180}, {140, 180}, {20, 160}, {100, 160}, {200, 160}, {140, 140}, {40, 120}, {100, 120}, {180, 100}, {60, 80}, {120, 80}, {180, 60}, {20, 40}, {100, 40}, {200, 40}, {20, 20}, {60, 20}, {160, 20}};

    static int populationSize = 100; // 种群大小
    static int maxGenerations = 500; // 最大迭代次数
    static double crossoverRate = 0.8; // 交叉概率
    static double mutationRate = 0.2; // 变异概率
    static int tournamentSize = 5; // 锦标赛大小

    static Random rand = new Random();

    // 基因编码方式
    static class Tour {
        int[] tour;
        double fitness;

        public Tour(int[] tour) {
            this.tour = tour;
            fitness = 1.0 / calculateDistance();
        }

        // 计算总路程长度
        double calculateDistance() {
            double distance = 0;
            for (int i = 0; i < tour.length - 1; i++) {
                int x1 = cities[tour[i]][0], y1 = cities[tour[i]][1];
                int x2 = cities[tour[i + 1]][0], y2 = cities[tour[i + 1]][1];
                distance += Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
            }
            distance += Math.sqrt((cities[tour[0]][0] - cities[tour[tour.length - 1]][0]) * (cities[tour[0]][0] - cities[tour[tour.length - 1]][0]) + (cities[tour[0]][1] - cities[tour[tour.length - 1]][1]) * (cities[tour[0]][1] - cities[tour[tour.length - 1]][1)));
            return distance;
        }
    }

    // 初始化种群
    static Tour[] initializePopulation() {
        Tour[] population = new Tour[populationSize];
        for (int i = 0; i < populationSize; i++) {
            int[] tour = new int[cities.length];
            for (int j = 0; j < cities.length; j++) {
                tour[j] = j;
            }
            shuffle(tour);
            population[i] = new Tour(tour);
        }
        return population;
    }

    // 洗牌算法
    static void shuffle(int[] arr) {
        for (int i = arr.length - 1; i >= 1; i--) {
            int j = rand.nextInt(i + 1);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 锦标赛选择
    static Tour tournamentSelection(Tour[] population) {
        Tour best = population[rand.nextInt(populationSize)];
        for (int i = 1; i < tournamentSize; i++) {
            Tour contender = population[rand.nextInt(populationSize)];
            if (contender.fitness > best.fitness) {
                best = contender;
            }
        }
        return best;
    }

    // 交叉操作
    static Tour crossover(Tour parent1, Tour parent2) {
        int[] child = new int[cities.length];
        int startPos = rand.nextInt(cities.length);
        int endPos = rand.nextInt(cities.length);
        if (startPos > endPos) {
            int temp = startPos;
            startPos = endPos;
            endPos = temp;
        }
        boolean[] used = new boolean[cities.length];
        for (int i = startPos; i <= endPos; i++) {
            child[i] = parent1.tour[i];
            used[parent1.tour[i]] = true;
        }
        int j = 0;
        for (int i = 0; i < cities.length; i++) {
            if (j == startPos) {
                j = endPos + 1;
            }
            if (!used[parent2.tour[i]]) {
                child[j++] = parent2.tour[i];
            }
        }
        return new Tour(child);
    }

    // 变异操作
    static void mutate(Tour tour) {
        for (int i = 0; i < tour.tour.length; i++) {
            if (rand.nextDouble() < mutationRate) {
                int j = rand.nextInt(tour.tour.length);
                int temp = tour.tour[i];
                tour.tour[i] = tour.tour[j];
                tour.tour[j] = temp;
            }
        }
    }

    // 运行遗传算法
    static Tour runGA() {
        Tour[] population = initializePopulation();
        for (int generation = 1; generation <= maxGenerations; generation++) {
            Tour[] newPopulation = new Tour[populationSize];
            for (int i = 0; i < populationSize; i++) {
                Tour parent1 = tournamentSelection(population);
                Tour parent2 = tournamentSelection(population);
                if (rand.nextDouble() < crossoverRate) {
                    newPopulation[i] = crossover(parent1, parent2);
                } else {
                    newPopulation[i] = parent1.fitness > parent2.fitness ? parent1 : parent2;
                }
                mutate(newPopulation[i]);
            }
            population = newPopulation;
            Arrays.sort(population, (a, b) -> Double.compare(b.fitness, a.fitness));
            System.out.printf("Generation %d: distance = %.2f\n", generation, 1.0 / population[0].fitness);
        }
        return population[0];
    }

    // 输出结果
    static void printTour(Tour tour) {
        for (int i = 0; i < tour.tour.length; i++) {
            System.out.printf("%d -> ", tour.tour[i]);
        }
        System.out.printf("%d\n", tour.tour[0]);
        System.out.printf("Total distance: %.2f\n", tour.calculateDistance());
    }

    public static void main(String[] args) {
        Tour tour = runGA();
        printTour(tour);
    }

}

程序输出结果为：

Generation 1: distance = 1531.91
Generation 2: distance = 1531.91
Generation 3: distance = 1531.91
...
Generation 498: distance = 1182.11
Generation 499: distance = 1182.11
Generation 500: distance = 1182.11
19 -> 18 -> 17 -> 15 -> 16 -> 13 -> 12 -> 11 -> 10 -> 9 -> 6 -> 5 -> 2 -> 3 -> 4 -> 7 -> 8 -> 14 -> 1 -> 0 -> 19
Total distance: 1182.11

可以看到，程序成功地使用遗传算法求解了TSP问题，并输出了最优解的路径和总路程长度。