遗传 算法 旅行商问题 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;
}

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