用遗传算法解旅行商TSP问题C++

TSP问题是一个经典的组合优化问题，遗传算法是一种常用的求解优化问题的方法。下面是一个基于遗传算法的TSP问题求解程序的C++代码示例：

#include <iostream>
#include <algorithm>
#include <vector>
#include <random>

using namespace std;

const int POPULATION_SIZE = 100;
const int GENERATION_NUM = 1000;
const double CROSSOVER_PROBABILITY = 0.9;
const double MUTATION_PROBABILITY = 0.05;

default_random_engine generator(random_device{}());

// 旅行商TSP问题的距离矩阵
const int N = 5;
int dist[N][N] = {
    {0, 2, 3, 4, 5},
    {2, 0, 6, 7, 8},
    {3, 6, 0, 9, 10},
    {4, 7, 9, 0, 11},
    {5, 8, 10, 11, 0}
};

// 基因型
struct Chromosome {
    vector<int> genes;
    int fitness;

    Chromosome() {
        genes.resize(N);
        for (int i = 0; i < N; i++) {
            genes[i] = i;
        }
        shuffle(genes.begin(), genes.end(), generator);
        fitness = calculate_fitness();
    }

    Chromosome(const vector<int>& genes) {
        this->genes = genes;
        fitness = calculate_fitness();
    }

    int calculate_fitness() const {
        int res = 0;
        for (int i = 0; i < N - 1; i++) {
            res += dist[genes[i]][genes[i+1]];
        }
        res += dist[genes[N-1]][genes[0]];
        return res;
    }

    bool operator < (const Chromosome& other) const {
        return fitness < other.fitness;
    }

    Chromosome crossover(const Chromosome& other) const {
        Chromosome child;
        uniform_int_distribution<int> dis(0, N-1);
        int r = dis(generator);
        for (int i = 0; i < N; i++) {
            if (i < r) {
                child.genes[i] = genes[i];
            } else {
                if (find(child.genes.begin(), child.genes.end(), other.genes[i]) == child.genes.end()) {
                    child.genes[i] = other.genes[i];
                } else {
                    for (int j = 0; j < N; j++) {
                        if (find(child.genes.begin(), child.genes.end(), genes[j]) == child.genes.end()) {
                            child.genes[i] = genes[j];
                            break;
                        }
                    }
                }
            }
        }
        return child;
    }

    void mutate() {
        uniform_int_distribution<int> dis(0, N-1);
        int r1 = dis(generator), r2 = dis(generator);
        swap(genes[r1], genes[r2]);
        fitness = calculate_fitness();
    }
};

// 种群
struct Population {
    vector<Chromosome> chromosomes;

    Population() {
        for (int i = 0; i < POPULATION_SIZE; i++) {
            chromosomes.emplace_back();
        }
        sort(chromosomes.begin(), chromosomes.end());
    }

    void evolve() {
        vector<Chromosome> new_chromosomes;
        // 选择
        for (int i = 0; i < POPULATION_SIZE * CROSSOVER_PROBABILITY; i++) {
            uniform_int_distribution<int> dis(0, POPULATION_SIZE-1);
            Chromosome parent1 = chromosomes[dis(generator)];
            Chromosome parent2 = chromosomes[dis(generator)];
            Chromosome child = parent1.crossover(parent2);
            new_chromosomes.push_back(child);
        }
        // 变异
        uniform_real_distribution<double> mutation_dis(0, 1);
        for (int i = 0; i < POPULATION_SIZE; i++) {
            if (mutation_dis(generator) < MUTATION_PROBABILITY) {
                new_chromosomes[i].mutate();
            }
        }
        // 替换
        sort(chromosomes.begin(), chromosomes.end());
        sort(new_chromosomes.begin(), new_chromosomes.end());
        for (int i = 0; i < POPULATION_SIZE * (1 - CROSSOVER_PROBABILITY); i++) {
            chromosomes[i] = new_chromosomes[i];
        }
        sort(chromosomes.begin(), chromosomes.end());
    }

    Chromosome get_best_chromosome() const {
        return chromosomes[0];
    }
};

int main() {
    Population population;
    for (int i = 0; i < GENERATION_NUM; i++) {
        population.evolve();
    }
    Chromosome best_chromosome = population.get_best_chromosome();
    cout << "Best solution: ";
    for (int i = 0; i < N; i++) {
        cout << best_chromosome.genes[i] << " ";
    }
    cout << "\nBest fitness: " << best_chromosome.fitness << endl;
    return 0;
}

该代码实现了一个基于遗传算法的TSP问题求解程序。在程序中，首先定义了遗传算法的一些参数，如种群大小、迭代次数、交叉概率、变异概率等。然后定义了基因型 `Chromosome` 和种群 `Population`，并实现了基因型的计算适应度函数、交叉、变异等操作，以及种群的进化操作。最后，在主函数中进行了遗传算法的迭代，并输出了最优解和最优适应度。