C++实现的基本遗传算法框架来解决TSP的示例代码

admin1

遗传算法解决旅行商问题（TSP）是一个经典的优化问题示例。以下是一个使用C++实现的基本遗传算法框架来解决TSP的示例代码。请注意，这是一个简化版的示例，实际应用中可能需要更多的优化和调整。

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

const int POPULATION_SIZE = 50; // 种群大小
const int GENERATIONS = 100; // 迭代次数
const double MUTATION_RATE = 0.02; // 变异率

// 计算路径总距离
double calculateFitness(const std::vector<int>& path, const std::vector<std::vector<double>>& distances)
{
    double fitness = 0;
    for (size_t i = 0; i < path.size() - 1; ++i)
    {
        fitness += distances[path[i]][path[i + 1]];
    }
    fitness += distances[path.back()][path.front()]; // 回到起点
    return fitness;
}

// 选择操作，使用轮盘赌选择法
std::vector<int> selection(const std::vector<std::vector<int>>& population, const std::vector<std::vector<double>>& distances)
{
    std::vector<double> fitnesses;
    double totalFitness = 0;
    for (const auto& path : population)
    {
        double fitness = calculateFitness(path, distances);
        fitnesses.push_back(fitness);
        totalFitness += fitness;
    }

    std::vector<double> probabilities;
    for (const auto& fitness : fitnesses)
    {
        probabilities.push_back(1 / fitness); // 最优解具有更高的概率被选中
    }
    std::partial_sum(probabilities.begin(), probabilities.end(), probabilities.begin());
    for (auto& p : probabilities)
    {
        p /= probabilities.back();
    }

    std::vector<int> selected;
    std::default_random_engine generator;
    std::uniform_real_distribution<double> distribution(0, 1);
    for (int i = 0; i < POPULATION_SIZE; ++i)
    {
        double r = distribution(generator);
        for (size_t j = 0; j < probabilities.size(); ++j)
        {
            if (r <= probabilities[j])
            {
                selected.push_back(j);
                break;
            }
        }
    }
    return selected;
}

// 交叉操作
std::vector<std::vector<int>> crossover(const std::vector<std::vector<int>>& parents, const std::vector<std::vector<double>>& distances)
{
    std::vector<std::vector<int>> children;
    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(0, POPULATION_SIZE - 1);
    for (int i = 0; i < POPULATION_SIZE; i += 2)
    {
        std::vector<int> child1(parents[i].size()), child2(parents[i].size());
        int start = distribution(generator), end = distribution(generator);
        if (start > end) std::swap(start, end);

        std::copy(parents[i].begin() + start, parents[i].begin() + end + 1, child1.begin() + start);
        std::copy(parents[i + 1].begin() + start, parents[i + 1].begin() + end + 1, child2.begin() + start);

        for (int j = 0; j < parents[i].size(); ++j)
        {
            if (std::find(child1.begin() + start, child1.end(), parents[i + 1][j]) == child1.end())
            {
                for (int k = 0; k < parents[i].size(); ++k)
                {
                    if (child1[k] == 0)
                    {
                        child1[k] = parents[i + 1][j];
                        break;
                    }
                }
            }
            if (std::find(child2.begin() + start, child2.end(), parents[i][j]) == child2.end())
            {
                for (int k = 0; k < parents[i].size(); ++k)
                {
                    if (child2[k] == 0)
                    {
                        child2[k] = parents[i][j];
                        break;
                    }
                }
            }
        }
        children.push_back(child1);
        children.push_back(child2);
    }
    return children;
}

// 变异操作
void mutate(std::vector<int>& path)
{
    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution(0, path.size() - 1);
    int index1 = distribution(generator), index2 = distribution(generator);
    std::swap(path[index1], path[index2]);
}

int main()
{
    // 初始化距离矩阵
    std::vector<std::vector<double>> distances = {
        {0, 2, 9, 10},
        {1, 0, 6, 4},
        {15, 7, 0, 8},
        {6, 3, 12, 0}
    };

    // 初始化种群
    std::vector<std::vector<int>> population;
    std::iota(population.begin(), population.end(), 0); // 填充从0到n-1的序列
    std::shuffle(population.begin(), population.end(), std::default_random_engine{});

    for (int gen = 0; gen < GENERATIONS; ++gen)
    {
        // 选择
        std::vector<int> selected = selection(population, distances);
        std::vector<std::vector<int>> newPopulation;
        for (int index : selected)
        {
            newPopulation.push_back(population[index]);
        }

        // 交叉
        std::vector<std::vector<int>> children = crossover(newPopulation, distances);
        population = children;

        // 变异
        for (auto& path : population)
        {
            if (static_cast<double>(rand()) / RAND_MAX < MUTATION_RATE)
            {
                mutate(path);
            }
        }
    }

    // 输出最优解
    double minFitness = std::numeric_limits<double>::max();
    std::vector<int> bestPath;
    for (const auto& path : population)
    {
        double fitness = calculateFitness(path, distances);
        if (fitness < minFitness)
        {
            minFitness = fitness;
            bestPath = path;
        }
    }
    std::cout << "Best Path: ";
    for (int city : bestPath)
    {
        std::cout << city << " -> ";
    }
    std::cout << bestPath.front() << std::endl;
    std::cout << "Minimum Distance: " << minFitness << std::endl;

    return 0;
}
```

这段代码实现了基本的遗传算法流程，包括选择、交叉和变异操作，以及计算路径总距离的适应度函数。为了使示例简单，我们使用了一个固定的距离矩阵。在实际应用中，距离矩阵可能需要从文件读取或者通过某种方式动态生成。

请注意，遗传算法的性能和结果高度依赖于参数的选择，如种群大小、迭代次数、交叉和变异率等。在实际应用中，可能需要通过实验来找到最适合问题规模和特性的参数组合。