c++遗传算法求旅行商问题，要求经过所有的点最后回到起点，每个城市可拜访多次具体代码实现

好的，以下是一个 C++ 的遗传算法求解旅行商问题的示例代码，其中使用了交叉、变异等遗传算法的基本操作：

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

using namespace std;

//定义城市结构体，记录城市坐标和是否已访问
struct City {
    int x, y;
    bool visited;
    City(int x, int y) : x(x), y(y), visited(false) {}
};

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

//定义一个旅行路线，即城市的访问顺序
struct Route {
    vector<int> cities;
    double length;
    Route(vector<int> cities) : cities(cities), length(0) {
        for (int i = 0; i < cities.size(); i++) {
            int j = (i + 1) % cities.size();
            length += distance(cities[i], cities[j]);
        }
    }
};

//定义一个遗传算法的类
class GeneticAlgorithm {
private:
    int population_size; //种群大小
    double mutation_rate; //变异率
    int max_generation; //最大迭代次数
    vector<City> cities; //城市列表
    vector<Route> population; //种群
    random_device rd;
    mt19937 gen;
    uniform_real_distribution<> dis;
    uniform_int_distribution<> dis_int;

    //初始化种群
    void init_population() {
        population.clear();
        for (int i = 0; i < population_size; i++) {
            vector<int> cities_index(cities.size());
            for (int j = 0; j < cities.size(); j++) {
                cities_index[j] = j;
            }
            shuffle(cities_index.begin(), cities_index.end(), gen);
            population.push_back(Route(cities_index));
        }
    }

    //选择操作，轮盘赌选择
    Route select() {
        double sum = 0;
        for (Route &r : population) {
            sum += 1.0 / r.length;
        }
        double p = dis(gen) * sum;
        sum = 0;
        for (Route &r : population) {
            sum += 1.0 / r.length;
            if (sum >= p) {
                return r;
            }
        }
        return population.back();
    }

    //交叉操作，选择两个个体，随机选择一个交叉点，交叉得到新个体
    Route crossover(Route &a, Route &b) {
        int n = cities.size();
        int c = dis_int(gen) % n;
        vector<int> cities_index(n, -1);
        for (int i = 0; i <= c; i++) {
            cities_index[a.cities[i]] = a.cities[i];
        }
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (cities_index[b.cities[i]] == -1) {
                while (cities_index[a.cities[j]] != -1) j++;
                cities_index[b.cities[i]] = a.cities[j++];
            }
        }
        return Route(cities_index);
    }

    //变异操作，随机选择一个个体，随机交换两个城市的位置
    void mutate() {
        int i = dis_int(gen) % population_size;
        Route &r = population[i];
        if (dis(gen) < mutation_rate) {
            int a = dis_int(gen) % cities.size();
            int b = dis_int(gen) % cities.size();
            swap(r.cities[a], r.cities[b]);
        }
    }

public:
    GeneticAlgorithm(int population_size, double mutation_rate, int max_generation, vector<City> cities)
    : population_size(population_size), mutation_rate(mutation_rate), max_generation(max_generation),
      cities(cities), gen(rd()), dis(0, 1), dis_int(0, INT_MAX)
    {
        init_population();
    }

    //运行遗传算法，返回最优路线
    Route run() {
        int generation = 0;
        while (generation < max_generation) {
            vector<Route> new_population(population_size);
            new_population[0] = *min_element(population.begin(), population.end(), [](const Route &a, const Route &b) {
                return a.length < b.length;
            });
            for (int i = 1; i < population_size; i++) {
                Route a = select(), b = select();
                new_population[i] = crossover(a, b);
            }
            population = new_population;
            mutate();
            generation++;
        }
        return *min_element(population.begin(), population.end(), [](const Route &a, const Route &b) {
            return a.length < b.length;
        });
    }
};

int main() {
    vector<City> cities = {
        {0, 0},
        {1, 2},
        {3, 1},
        {2, 3},
        {4, 4}
    };
    GeneticAlgorithm ga(100, 0.01, 1000, cities);
    Route r = ga.run();
    for (int i : r.cities) {
        cout << i << " ";
    }
    cout << endl;
    cout << "Length: " << r.length << endl;
    return 0;
}

在实现中，我们首先定义了城市和路线的结构体，分别表示城市的坐标和访问顺序。然后定义了一个遗传算法的类，其中包含了种群初始化、选择、交叉、变异等基本操作，以及运行算法的函数。在主函数中，我们定义了一个城市列表并调用遗传算法求解最优路线。