c++旅行商问题遗传算法具体代码

下面是一个简单的C++代码示例，用遗传算法求解旅行商问题：

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

using namespace std;

// 定义城市结构体
struct City {
    double x, y;
};

// 定义遗传算法参数
const int POPULATION_SIZE = 100;     // 种群大小
const int MAX_GENERATION = 1000;     // 最大迭代次数
const double CROSSOVER_RATE = 0.8;   // 交叉概率
const double MUTATION_RATE = 0.1;    // 变异概率
const int TOURNAMENT_SIZE = 5;       // 锦标赛选择的比例

// 定义全局变量
int num_cities;                     // 城市数量
vector<City> cities;                // 城市数组
vector<vector<int>> population;     // 种群数组

// 计算两个城市间的距离
double distance(int a, int b) {
    double dx = cities[a].x - cities[b].x;
    double dy = cities[a].y - cities[b].y;
    return sqrt(dx * dx + dy * dy);
}

// 计算一条路径的总距离
double path_distance(const vector<int>& path) {
    double dist = 0.0;
    for (int i = 0; i < num_cities - 1; i++) {
        dist += distance(path[i], path[i+1]);
    }
    dist += distance(path[num_cities-1], path[0]);
    return dist;
}

// 初始化种群
void init_population() {
    for (int i = 0; i < POPULATION_SIZE; i++) {
        vector<int> path(num_cities);
        for (int j = 0; j < num_cities; j++) {
            path[j] = j;
        }
        random_shuffle(path.begin(), path.end());
        population.push_back(path);
    }
}

// 锦标赛选择
vector<int> tournament_selection() {
    vector<int> result;
    mt19937 rng(random_device{}());
    uniform_int_distribution<int> dist(0, POPULATION_SIZE-1);
    for (int i = 0; i < TOURNAMENT_SIZE; i++) {
        int index = dist(rng);
        result.push_back(index);
    }
    sort(result.begin(), result.end());
    return {population[result[0]], population[result[1]]};
}

// 交叉操作
void crossover(vector<int>& parent1, vector<int>& parent2) {
    mt19937 rng(random_device{}());
    uniform_int_distribution<int> dist(0, num_cities-1);
    int pos1 = dist(rng);
    int pos2 = dist(rng);
    if (pos1 > pos2) {
        swap(pos1, pos2);
    }
    vector<int> child1(num_cities, -1), child2(num_cities, -1);
    for (int i = pos1; i <= pos2; i++) {
        child1[i] = parent1[i];
        child2[i] = parent2[i];
    }
    int index1 = pos2 + 1, index2 = pos2 + 1;
    while (index1 < num_cities && index2 < num_cities) {
        int city1 = parent1[index1];
        int city2 = parent2[index2];
        if (find(child1.begin(), child1.end(), city2) == child1.end()) {
            child1[index1] = city2;
            index1++;
        }
        if (find(child2.begin(), child2.end(), city1) == child2.end()) {
            child2[index2] = city1;
            index2++;
        }
        if (index1 == index2) {
            index2++;
        }
    }
    for (int i = 0; i < num_cities; i++) {
        if (child1[i] == -1) {
            child1[i] = parent2[i];
        }
        if (child2[i] == -1) {
            child2[i] = parent1[i];
        }
    }
    parent1 = child1;
    parent2 = child2;
}

// 变异操作
void mutation(vector<int>& path) {
    mt19937 rng(random_device{}());
    uniform_int_distribution<int> dist(0, num_cities-1);
    int pos1 = dist(rng);
    int pos2 = dist(rng);
    swap(path[pos1], path[pos2]);
}

int main() {
    // 读入城市数据
    cin >> num_cities;
    for (int i = 0; i < num_cities; i++) {
        City city;
        cin >> city.x >> city.y;
        cities.push_back(city);
    }

    // 初始化种群
    init_population();

    // 迭代遗传算法
    for (int generation = 0; generation < MAX_GENERATION; generation++) {
        // 计算适应度
        vector<pair<double, int>> fitness;
        for (int i = 0; i < POPULATION_SIZE; i++) {
            double dist = path_distance(population[i]);
            fitness.push_back({1.0 / dist, i});
        }
        sort(fitness.begin(), fitness.end(), greater<>());

        // 输出当前最优解
        cout << "Generation " << generation << ": " << 1.0 / fitness[0].first << endl;

        // 选择、交叉、变异
        vector<vector<int>> new_population;
        while (new_population.size() < POPULATION_SIZE) {
            auto parents = tournament_selection();
            vector<int> child1 = parents[0], child2 = parents[1];
            if ((double)rand() / RAND_MAX < CROSSOVER_RATE) {
                crossover(child1, child2);
            }
            if ((double)rand() / RAND_MAX < MUTATION_RATE) {
                mutation(child1);
            }
            if ((double)rand() / RAND_MAX < MUTATION_RATE) {
                mutation(child2);
            }
            new_population.push_back(child1);
            new_population.push_back(child2);
        }

        // 更新种群
        population = new_population;
    }

    // 输出最终结果
    vector<pair<double, int>> fitness;
    for (int i = 0; i < POPULATION_SIZE; i++) {
        double dist = path_distance(population[i]);
        fitness.push_back({1.0 / dist, i});
    }
    sort(fitness.begin(), fitness.end(), greater<>());
    cout << "Best solution: " << 1.0 / fitness[0].first << endl;

    return 0;
}

这个代码示例中，我们使用了C++的STL库来实现一些常用的操作，如随机数生成、排序等。在代码实现中，我们选择了锦标赛选择的方式来进行个体选择，采用轮盘赌的方式来进行交叉和变异操作。代码中还包括一些优化措施，如使用局部变量来避免不必要的拷贝等。