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

admin1

下面是一个使用C++实现的蚁群算法(ACA)来解决旅行商问题(TSP)的基本框架。蚁群算法是一种启发式搜索算法，模拟了蚂蚁寻找食物的行为。在这个算法中，每只“蚂蚁”都会构建一条路径，并基于之前蚂蚁留下的信息素强度和路径的启发式信息来决定下一步的移动方向。

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

const int NUM_ANTS = 50;       // 蚂蚁数量
const int NUM_CITIES = 10;     // 城市数量
const int MAX_ITERATIONS = 100;// 最大迭代次数
const double ALPHA = 1.0;      // 信息素重要程度因子
const double BETA = 5.0;       // 启发式信息重要程度因子
const double RHO = 0.5;        // 信息素挥发速度
const double Q = 100;          // 信息素更新量

std::vector<std::vector<double>> distances(NUM_CITIES, std::vector<double>(NUM_CITIES));
std::vector<std::vector<double>> pheromones(NUM_CITIES, std::vector<double>(NUM_CITIES, 1.0));
std::vector<std::vector<double>> heuristicInfo(NUM_CITIES, std::vector<double>(NUM_CITIES));

void initDistancesAndHeuristics()
{
    // 初始化距离矩阵和启发式信息矩阵
    std::default_random_engine generator;
    std::uniform_real_distribution<double> distribution(1, 100);
   
    for(int i = 0; i < NUM_CITIES; i++)
    {
        for(int j = i+1; j < NUM_CITIES; j++)
        {
            distances[i][j] = distribution(generator);
            distances[j][i] = distances[i][j];
            heuristicInfo[i][j] = 1.0 / distances[i][j];
            heuristicInfo[j][i] = heuristicInfo[i][j];
        }
    }
}

double calculateTotalDistance(const std::vector<int>& path)
{
    double distance = 0;
    for(size_t i = 0; i < path.size() - 1; ++i)
    {
        distance += distances[path[i]][path[i+1]];
    }
    distance += distances[path.back()][path.front()];
    return distance;
}

void updatePheromones(const std::vector<std::vector<int>>& antPaths, const std::vector<double>& antDistances)
{
    // 更新信息素
    for(int i = 0; i < NUM_CITIES; i++)
    {
        for(int j = 0; j < NUM_CITIES; j++)
        {
            pheromones[i][j] *= (1.0 - RHO);
        }
    }
    for(size_t i = 0; i < antPaths.size(); i++)
    {
        double deltaPheromone = Q / antDistances[i];
        for(size_t j = 0; j < antPaths[i].size() - 1; j++)
        {
            pheromones[antPaths[i][j]][antPaths[i][j+1]] += deltaPheromone;
            pheromones[antPaths[i][j+1]][antPaths[i][j]] = pheromones[antPaths[i][j]][antPaths[i][j+1]];
        }
        pheromones[antPaths[i].back()][antPaths[i].front()] += deltaPheromone;
        pheromones[antPaths[i].front()][antPaths[i].back()] = pheromones[antPaths[i].back()][antPaths[i].front()];
    }
}

std::vector<int> constructPath(int startCity)
{
    std::vector<int> path;
    std::vector<bool> visited(NUM_CITIES, false);
    std::default_random_engine generator;
   
    path.push_back(startCity);
    visited[startCity] = true;
   
    while(path.size() < NUM_CITIES)
    {
        double totalProb = 0;
        std::vector<double> probabilities;
        for(int i = 0; i < NUM_CITIES; i++)
        {
            if(!visited[i])
            {
                double prob = pow(pheromones[path.back()][i], ALPHA) * pow(heuristicInfo[path.back()][i], BETA);
                totalProb += prob;
                probabilities.push_back(totalProb);
            }
        }
        
        double r = static_cast<double>(rand()) / RAND_MAX * totalProb;
        auto it = std::upper_bound(probabilities.begin(), probabilities.end(), r);
        int nextCity = std::distance(probabilities.begin(), it);
        
        path.push_back(nextCity);
        visited[nextCity] = true;
    }
    return path;
}

int main()
{
    initDistancesAndHeuristics();
    double bestDistance = DBL_MAX;
    std::vector<int> bestPath;
   
    for(int iter = 0; iter < MAX_ITERATIONS; iter++)
    {
        std::vector<std::vector<int>> antPaths;
        std::vector<double> antDistances;
        
        for(int ant = 0; ant < NUM_ANTS; ant++)
        {
            int startCity = rand() % NUM_CITIES;
            std::vector<int> path = constructPath(startCity);
            double distance = calculateTotalDistance(path);
            antPaths.push_back(path);
            antDistances.push_back(distance);
            
            if(distance < bestDistance)
            {
                bestDistance = distance;
                bestPath = path;
            }
        }
        
        updatePheromones(antPaths, antDistances);
    }
   
    std::cout << "Best Path: ";
    for(int city : bestPath)
    {
        std::cout << city << " -> ";
    }
    std::cout << bestPath.front() << std::endl;
    std::cout << "Minimum Distance: " << bestDistance << std::endl;
   
    return 0;
}
```

这个代码实现了蚁群算法的主要步骤：初始化距离矩阵和启发式信息矩阵，构建路径，以及更新信息素。值得注意的是，在构建路径的过程中，每只蚂蚁都基于当前的信息素浓度和启发式信息来选择下一个城市。此外，信息素的更新是基于所有蚂蚁完成路径后的结果，其中较短路径上的信息素会被加强，而较长路径上的信息素则会减少。

蚁群算法的参数（如`ALPHA`, `BETA`, `RHO`, `Q`等）对算法的性能有显著影响。通常需要通过试验来确定最佳的参数设置。此外，算法的效率也取决于问题的规模，即城市数量。对于较大的问题，可能需要更复杂的策略来提高算法的效率，例如并行计算或使用更高级的路径构建规则。
```