遗传算法求解TSP C++

遗传算法（Genetic Algorithm）可以用于求解TSP问题（Traveling Salesman Problem），以下是一个C++实现的示例代码：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 30; //城市数量
const int POP_SIZE = 100; //种群大小
const int MAX_GEN = 500; //最大迭代次数
const double MUTATION_RATE = 0.1; //变异概率
const double CROSSOVER_RATE = 0.9; //交叉概率
const double PI = acos(-1.0);

int city[N][2]; //城市坐标
int pop[POP_SIZE][N]; //种群
double fitness[POP_SIZE]; //适应度
int best_idx; //最优个体的索引
int best_path[N]; //最优路径

//初始化城市坐标
void init_city()
{
    srand(time(NULL));
    for (int i = 0; i < N; i++) {
        city[i][0] = rand() % 100;
        city[i][1] = rand() % 100;
    }
}

//计算两个城市之间的距离
double dist(int i, int j)
{
    return sqrt((city[i][0] - city[j][0]) * (city[i][0] - city[j][0]) + (city[i][1] - city[j][1]) * (city[i][1] - city[j][1]));
}

//初始化种群
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);
    }
}

//计算个体的适应度
double calc_fitness(int *p)
{
    double len = 0;
    for (int i = 0; i < N; i++) {
        len += dist(p[i], p[(i + 1) % N]);
    }
    return 1.0 / len;
}

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

//选择操作（轮盘赌）
int select()
{
    double r = (double)rand() / RAND_MAX;
    double sum = 0;
    for (int i = 0; i < POP_SIZE; i++) {
        sum += fitness[i];
        if (r < sum) {
            return i;
        }
    }
}

//交叉操作（顺序交叉）
void crossover(int *p1, int *p2, int *c1, int *c2)
{
    int pos1 = rand() % N, pos2 = rand() % N;
    if (pos1 > pos2) {
        swap(pos1, pos2);
    }
    bool vis[N] = {false};
    for (int i = pos1; i <= pos2; i++) {
        c1[i] = p1[i];
        vis[c1[i]] = true;
        c2[i] = p2[i];
        vis[c2[i]] = true;
    }
    int p = pos2 + 1;
    for (int i = pos2 + 1; i < N; i++) {
        while (vis[p]) {
            p = (p + 1) % N;
        }
        c1[i] = p2[i];
        c2[i] = p1[i];
        vis[c1[i]] = true;
        vis[c2[i]] = true;
        p = (p + 1) % N;
    }
    for (int i = 0; i < pos1; i++) {
        while (vis[p]) {
            p = (p + 1) % N;
        }
        c1[i] = p2[i];
        c2[i] = p1[i];
        vis[c1[i]] = true;
        vis[c2[i]] = true;
        p = (p + 1) % N;
    }
}

//变异操作（交换变异）
void mutation(int *p)
{
    for (int i = 0; i < N; i++) {
        if ((double)rand() / RAND_MAX < MUTATION_RATE) {
            int j = rand() % N;
            swap(p[i], p[j]);
        }
    }
}

//进化操作
void evolve()
{
    int new_pop[POP_SIZE][N];
    int idx = 0;
    while (idx < POP_SIZE) {
        int p1 = select();
        int p2 = select();
        if ((double)rand() / RAND_MAX < CROSSOVER_RATE) {
            crossover(pop[p1], pop[p2], new_pop[idx], new_pop[idx + 1]);
            idx += 2;
        } else {
            copy(pop[p1], pop[p1] + N, new_pop[idx]);
            copy(pop[p2], pop[p2] + N, new_pop[idx + 1]);
            idx += 2;
        }
    }
    for (int i = 0; i < POP_SIZE; i++) {
        mutation(new_pop[i]);
        copy(new_pop[i], new_pop[i] + N, pop[i]);
    }
}

//选择最优个体
void select_best()
{
    best_idx = 0;
    for (int i = 1; i < POP_SIZE; i++) {
        if (fitness[i] > fitness[best_idx]) {
            best_idx = i;
        }
    }
}

//输出最优路径
void output_best_path()
{
    copy(pop[best_idx], pop[best_idx] + N, best_path);
    cout << "Best path: ";
    for (int i = 0; i < N; i++) {
        cout << best_path[i] << " ";
    }
    cout << best_path[0] << endl;
}

int main()
{
    init_city();
    init_pop();
    calc_pop_fitness();
    for (int i = 0; i < MAX_GEN; i++) {
        evolve();
        calc_pop_fitness();
        select_best();
        cout << "Generation " << i << ": " << 1.0 / fitness[best_idx] << endl;
    }
    output_best_path();
    return 0;
}

这个示例代码中，采用顺序交叉和交换变异作为遗传算法的操作。计算适应度的方法是计算路径长度的倒数，因为TSP问题是求解最短路径问题，所以路径长度越短的个体越优秀。轮盘赌算法用于选择操作，选择最优个体的方法是找出所有个体中适应度最高的个体。