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

好的，下面是一个用遗传算法解决TSP问题的C++代码，供您参考：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 100; // 最大城市数
const int MAX_GEN = 1000; // 最大迭代次数
const int POP_SIZE = 100; // 种群大小
const double MUTATION_RATE = 0.1; // 变异概率
const double CROSSOVER_RATE = 0.9; // 交叉概率
const double PI = 3.1415926535897932384626433832795;

int n; // 城市数
int dist[MAXN][MAXN]; // 城市间距离矩阵
int pop[POP_SIZE][MAXN]; // 种群
int fitness[POP_SIZE]; // 种群适应度
int best[MAX_GEN]; // 每代最优解
int best_distance = 0x7fffffff; // 最优路径长度
int best_path[MAXN]; // 最优路径

// 生成初始种群
void init_pop() {
    for (int i = 0; i < POP_SIZE; i++) {
        for (int j = 0; j < n; j++) {
            pop[i][j] = j;
        }
        random_shuffle(pop[i], pop[i] + n);
    }
}

// 计算城市间距离矩阵
void calc_dist() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
}

// 计算路径长度
int calc_distance(int *path) {
    int res = 0;
    for (int i = 0; i < n; i++) {
        res += dist[path[i]][path[(i + 1) % n]];
    }
    return res;
}

// 计算适应度
void calc_fitness() {
    for (int i = 0; i < POP_SIZE; i++) {
        fitness[i] = 1.0 / calc_distance(pop[i]);
    }
}

// 选择
int select() {
    double p = (double)rand() / RAND_MAX;
    int res = 0;
    while (p > 0) {
        p -= fitness[res];
        res++;
    }
    return res - 1;
}

// 交叉
void crossover(int *parent1, int *parent2, int *child1, int *child2) {
    int p1 = rand() % n;
    int p2 = rand() % n;
    if (p1 > p2) {
        swap(p1, p2);
    }
    for (int i = p1; i <= p2; i++) {
        child1[i] = parent1[i];
        child2[i] = parent2[i];
    }
    int k1 = p2 + 1, k2 = p2 + 1;
    while (k1 != p1 && k2 != p1) {
        if (find(child1, child1 + n, parent2[k1 % n]) == child1 + n) {
            child1[k1 % n] = parent2[k1 % n];
            k1++;
        }
        if (find(child2, child2 + n, parent1[k2 % n]) == child2 + n) {
            child2[k2 % n] = parent1[k2 % n];
            k2++;
        }
    }
}

// 变异
void mutate(int *individual) {
    int p1 = rand() % n;
    int p2 = rand() % n;
    swap(individual[p1], individual[p2]);
}

// 遗传算法求解TSP问题
void solve_tsp() {
    init_pop();
    calc_fitness();
    for (int i = 0; i < MAX_GEN; i++) {
        int new_pop[POP_SIZE][MAXN];
        for (int j = 0; j < POP_SIZE; j += 2) {
            int parent1 = select();
            int parent2 = select();
            int child1[MAXN], child2[MAXN];
            for (int k = 0; k < n; k++) {
                child1[k] = child2[k] = -1;
            }
            if ((double)rand() / RAND_MAX < CROSSOVER_RATE) {
                crossover(pop[parent1], pop[parent2], child1, child2);
            } else {
                for (int k = 0; k < n; k++) {
                    child1[k] = pop[parent1][k];
                    child2[k] = pop[parent2][k];
                }
            }
            if ((double)rand() / RAND_MAX < MUTATION_RATE) {
                mutate(child1);
            }
            if ((double)rand() / RAND_MAX < MUTATION_RATE) {
                mutate(child2);
            }
            for (int k = 0; k < n; k++) {
                new_pop[j][k] = child1[k];
                new_pop[j + 1][k] = child2[k];
            }
        }
        for (int j = 0; j < POP_SIZE; j++) {
            for (int k = 0; k < n; k++) {
                pop[j][k] = new_pop[j][k];
            }
        }
        calc_fitness();
        int max_fitness_idx = max_element(fitness, fitness + POP_SIZE) - fitness;
        int cur_distance = calc_distance(pop[max_fitness_idx]);
        if (cur_distance < best_distance) {
            best_distance = cur_distance;
            for (int j = 0; j < n; j++) {
                best_path[j] = pop[max_fitness_idx][j];
            }
        }
        best[i] = best_distance;
    }
}

// 输出结果
void print_result() {
    cout << "Path: ";
    for (int i = 0; i < n; i++) {
        cout << best_path[i] << " ";
    }
    cout << endl;
    cout << "Distance: " << best_distance << endl;
}

int main() {
    srand((unsigned)time(NULL));
    cin >> n;
    calc_dist();
    solve_tsp();
    print_result();
    return 0;
}

在代码中，种群中的每个个体表示一条路径，每个个体由城市编号组成。计算适应度时，将路径长度的倒数作为适应度，目的是让路径长度短的个体具有更高的适应度。选择时，使用轮盘赌算法选择个体。交叉时，使用部分匹配交叉（PMX）算法进行交叉。变异时，随机交换路径上的两个城市。最终输出最优路径及其长度。