c++旅行商问题遗传算法

旅行商问题是一个经典的组合优化问题，它的目标是在不重复经过每个城市的前提下，完成所有城市的旅行并回到起点，使得总路程最短。遗传算法是一种基于生物进化原理的优化算法，通过模拟自然选择、交叉和变异等过程来搜索最优解。

在使用遗传算法解决旅行商问题时，一般需要进行以下步骤：

1. 确定问题的编码方式，即将每个城市表示成一个基因，将整个旅行序列表示成一个染色体。

2. 初始化种群，即随机生成多个个体作为初始解。

3. 评估每个个体的适应度，即计算每个个体的总路程。

4. 选择优秀的个体作为父代，可以采用轮盘赌选择等方法。

5. 进行交叉和变异操作，产生新的个体。

6. 评估新个体的适应度，并选择出最优解。

7. 不断重复步骤4-6，直到达到预设的停止条件。

需要注意的是，在实际操作中，还需要考虑一些优化策略，如精英保留、多次交叉和变异等措施，以提高算法的效率和精度。

相关问题

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

遗传 算法 旅行商问题 c++

旅行商问题是一个经典的组合优化问题，遗传算法是解决这个问题的一种常用方法。下面是一份使用C++实现遗传算法解决旅行商问题的示例代码：

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

const int CITY_NUM = 10;  // 城市数量
const int POPULATION_SIZE = 100;  // 种群数量
const int GENERATION_NUM = 500;  // 迭代次数
const double CROSSOVER_PROBABILITY = 0.8;  // 交叉概率
const double MUTATION_PROBABILITY = 0.2;  // 变异概率

// 城市坐标结构体
struct City
{
    double x;
    double y;
};

// 生成随机种群
vector<vector<int> > generate_population(int population_size, int city_num)
{
    vector<vector<int> > population(population_size);
    for (int i = 0; i < population_size; i++)
    {
        vector<int> chromosome(city_num);
        for (int j = 0; j < city_num; j++)
        {
            chromosome[j] = j;
        }
        random_shuffle(chromosome.begin(), chromosome.end());
        population[i] = chromosome;
    }
    return population;
}

// 计算染色体的适应度
double fitness(vector<int> chromosome, vector<City> cities)
{
    double distance = 0.0;
    for (int i = 0; i < chromosome.size() - 1; i++)
    {
        int city1 = chromosome[i];
        int city2 = chromosome[i + 1];
        distance += sqrt((cities[city1].x - cities[city2].x) * (cities[city1].x - cities[city2].x) + 
                         (cities[city1].y - cities[city2].y) * (cities[city1].y - cities[city2].y));
    }
    distance += sqrt((cities[chromosome[chromosome.size() - 1]].x - cities[chromosome[0]].x) * 
                     (cities[chromosome[chromosome.size() - 1]].x - cities[chromosome[0]].x) + 
                     (cities[chromosome[chromosome.size() - 1]].y - cities[chromosome[0]].y) * 
                     (cities[chromosome[chromosome.size() - 1]].y - cities[chromosome[0]].y));
    return 1.0 / distance;
}

// 选择操作
vector<vector<int> > selection(vector<vector<int> > population, vector<City> cities)
{
    vector<vector<int> > new_population;
    double fitness_sum = 0.0;
    for (int i = 0; i < population.size(); i++)
    {
        fitness_sum += fitness(population[i], cities);
    }
    for (int i = 0; i < population.size(); i++)
    {
        double p = rand() / (double)RAND_MAX;
        double cumulative_probability = 0.0;
        for (int j = 0; j < population.size(); j++)
        {
            cumulative_probability += fitness(population[j], cities) / fitness_sum;
            if (p <= cumulative_probability)
            {
                new_population.push_back(population[j]);
                break;
            }
        }
    }
    return new_population;
}

// 交叉操作
vector<vector<int> > crossover(vector<vector<int> > population)
{
    vector<vector<int> > new_population;
    for (int i = 0; i < population.size(); i += 2)
    {
        double p = rand() / (double)RAND_MAX;
        if (p <= CROSSOVER_PROBABILITY)
        {
            int pos1 = rand() % (population[i].size() - 1) + 1;
            int pos2 = rand() % (population[i].size() - pos1) + pos1 + 1;
            vector<int> child1, child2;
            child1.resize(population[i].size());
            child2.resize(population[i].size());
            for (int j = 0; j < pos1; j++)
            {
                child1[j] = population[i][j];
                child2[j] = population[i + 1][j];
            }
            for (int j = pos1; j < pos2; j++)
            {
                child1[j] = population[i + 1][j];
                child2[j] = population[i][j];
            }
            for (int j = pos2; j < population[i].size(); j++)
            {
                child1[j] = population[i][j];
                child2[j] = population[i + 1][j];
            }
            new_population.push_back(child1);
            new_population.push_back(child2);
        }
        else
        {
            new_population.push_back(population[i]);
            new_population.push_back(population[i + 1]);
        }
    }
    return new_population;
}

// 变异操作
vector<vector<int> > mutation(vector<vector<int> > population)
{
    for (int i = 0; i < population.size(); i++)
    {
        double p = rand() / (double)RAND_MAX;
        if (p <= MUTATION_PROBABILITY)
        {
            int pos1 = rand() % (population[i].size() - 1) + 1;
            int pos2 = rand() % (population[i].size() - pos1) + pos1 + 1;
            reverse(population[i].begin() + pos1, population[i].begin() + pos2);
        }
    }
    return population;
}

// 主函数
int main()
{
    srand((unsigned)time(NULL));
    vector<City> cities(CITY_NUM);
    for (int i = 0; i < CITY_NUM; i++)
    {
        cities[i].x = rand() / (double)RAND_MAX;
        cities[i].y = rand() / (double)RAND_MAX;
    }
    vector<vector<int> > population = generate_population(POPULATION_SIZE, CITY_NUM);
    for (int i = 0; i < GENERATION_NUM; i++)
    {
        population = selection(population, cities);
        population = crossover(population);
        population = mutation(population);
    }
    double max_fitness = 0.0;
    int max_index = 0;
    for (int i = 0; i < population.size(); i++)
    {
        double f = fitness(population[i], cities);
        if (f > max_fitness)
        {
            max_fitness = f;
            max_index = i;
        }
    }
    cout << "The optimal solution is: ";
    for (int i = 0; i < population[max_index].size(); i++)
    {
        cout << population[max_index][i] << " ";
    }
    cout << endl;
    return 0;
}

这份代码使用遗传算法求解旅行商问题，其中包括随机种群生成、适应度计算、选择操作、交叉操作、变异操作等遗传算法的基本步骤。在主函数中，先随机生成一组城市坐标，然后生成随机种群，接着进行多轮迭代，最后输出最优解。