遗传算法最优路径c++

遗传算法是一种全局搜索算法，可以用于求解TSP问题的近似最优解。在C++中，可以通过编写遗传算法的代码来求解TSP问题的最优路径。具体实现步骤如下：
1. 定义城市坐标和距离矩阵。
2. 初始化种群，即生成随机的路径序列。
3. 计算每个路径的适应度值，即路径长度。
4. 选择优秀的个体进行交叉和变异操作，生成新的个体。
5. 计算新个体的适应度值。
6. 重复步骤4和5，直到达到停止条件。
7. 输出最优路径和路径长度。

以下是一个简单的C++遗传算法求解TSP问题的代码示例：

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

const int CITY_NUM = 38; // 城市数量
const int POP_SIZE = 100; // 种群大小
const int MAX_GEN = 500; // 最大迭代次数
const double CROSS_RATE = 0.8; // 交叉概率
const double MUTATE_RATE = 0.1; // 变异概率

// 城市坐标
double city_x[CITY_NUM] = { ... };
double city_y[CITY_NUM] = { ... };

// 距离矩阵
double dist[CITY_NUM][CITY_NUM];

// 个体结构体
struct Individual {
    vector<int> path; // 路径
    double fitness; // 适应度值
};

// 初始化距离矩阵
void initDist() {
    for (int i = 0; i < CITY_NUM; i++) {
        for (int j = 0; j < CITY_NUM; j++) {
            dist[i][j] = sqrt(pow(city_x[i] - city_x[j], 2) + pow(city_y[i] - city_y[j], 2));
        }
    }
}

// 计算路径长度
double calcPathLen(const vector<int>& path) {
    double len = 0;
    for (int i = 0; i < CITY_NUM - 1; i++) {
        len += dist[path[i]][path[i + 1]];
    }
    len += dist[path[CITY_NUM - 1]][path[0]];
    return len;
}

// 初始化种群
void initPop(vector<Individual>& pop) {
    for (int i = 0; i < POP_SIZE; i++) {
        Individual ind;
        for (int j = 0; j < CITY_NUM; j++) {
            ind.path.push_back(j);
        }
        random_shuffle(ind.path.begin(), ind.path.end());
        ind.fitness = calcPathLen(ind.path);
        pop.push_back(ind);
    }
}

// 选择操作
void select(vector<Individual>& pop, vector<Individual>& new_pop) {
    double sum_fitness = 0;
    for (int i = 0; i < POP_SIZE; i++) {
        sum_fitness += pop[i].fitness;
    }
    for (int i = 0; i < POP_SIZE; i++) {
        double r = (double)rand() / RAND_MAX * sum_fitness;
        double s = 0;
        for (int j = 0; j < POP_SIZE; j++) {
            s += pop[j].fitness;
            if (s >= r) {
                new_pop[i] = pop[j];
                break;
            }
        }
    }
}

// 交叉操作
void crossover(vector<Individual>& pop, vector<Individual>& new_pop) {
    for (int i = 0; i < POP_SIZE; i += 2) {
        if ((double)rand() / RAND_MAX < CROSS_RATE) {
            int pos1 = rand() % CITY_NUM;
            int pos2 = rand() % CITY_NUM;
            if (pos1 > pos2) {
                swap(pos1, pos2);
            }
            vector<int> child1(CITY_NUM, -1);
            vector<int> child2(CITY_NUM, -1);
            for (int j = pos1; j <= pos2; j++) {
                child1[j] = pop[i + 1].path[j];
                child2[j] = pop[i].path[j];
            }
            int k1 = pos2 + 1, k2 = pos2 + 1;
            for (int j = 0; j < CITY_NUM; j++) {
                if (find(child1.begin(), child1.end(), pop[i].path[j]) == child1.end()) {
                    child1[k1 % CITY_NUM] = pop[i].path[j];
                    k1++;
                }
                if (find(child2.begin(), child2.end(), pop[i + 1].path[j]) == child2.end()) {
                    child2[k2 % CITY_NUM] = pop[i + 1].path[j];
                    k2++;
                }
            }
            new_pop[i].path = child1;
            new_pop[i].fitness = calcPathLen(child1);
            new_pop[i + 1].path = child2;
            new_pop[i + 1].fitness = calcPathLen(child2);
        }
        else {
            new_pop[i] = pop[i];
            new_pop[i + 1] = pop[i + 1];
        }
    }
}

// 变异操作
void mutate(vector<Individual>& pop, vector<Individual>& new_pop) {
    for (int i = 0; i < POP_SIZE; i++) {
        if ((double)rand() / RAND_MAX < MUTATE_RATE) {
            int pos1 = rand() % CITY_NUM;
            int pos2 = rand() % CITY_NUM;
            swap(new_pop[i].path[pos1], new_pop[i].path[pos2]);
            new_pop[i].fitness = calcPathLen(new_pop[i].path);
        }
    }
}

// 遗传算法求解TSP问题
void solveTSP() {
    srand((unsigned)time(NULL));
    initDist();
    vector<Individual> pop(POP_SIZE);
    vector<Individual> new_pop(POP_SIZE);
    initPop(pop);
    int gen = 0;
    while (gen < MAX_GEN) {
        select(pop, new_pop);
        crossover(new_pop, new_pop);
        mutate(new_pop, new_pop);
        pop = new_pop;
        gen++;
    }
    sort(pop.begin(), pop.end(), [](const Individual& a, const Individual& b) { return a.fitness < b.fitness; });
    cout << "最优路径长度：" << pop[0].fitness << endl;
    cout << "最优路径：";
    for (int i = 0; i < CITY_NUM; i++) {
        cout << pop[0].path[i] << " ";
    }
    cout << endl;
}

int main() {
    solveTSP();
    return 0;
}