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

admin1

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

模拟退火算法(Simulated Annealing, SA)是一种全局优化技术，灵感来源于固体冷却过程中的原子结构变化。在解决旅行商问题(TSP)中，SA通过接受一定概率的劣解来避免局部最优，最终达到全局最优解或接近最优解。下面是一个使用C++实现的SA算法来解决TSP问题的示例代码：

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

const int NUM_CITIES = 10;         // 城市数量
const int MAX_ITERATIONS = 10000;  // 最大迭代次数
const double INITIAL_TEMP = 1000;  // 初始温度
const double COOLING_RATE = 0.99;  // 冷却率

// 城市坐标
std::vector<std::pair<double, double>> cities;

// 距离矩阵
std::vector<std::vector<double>> distances;

// 计算两城市之间的距离
double calculateDistance(int city1, int city2)
{
    double dx = cities[city1].first - cities[city2].first;
    double dy = cities[city1].second - cities[city2].second;
    return sqrt(dx * dx + dy * dy);
}

// 初始化距离矩阵
void initializeDistances()
{
    distances.resize(NUM_CITIES, std::vector<double>(NUM_CITIES));
    for (int i = 0; i < NUM_CITIES; ++i)
    {
        for (int j = i + 1; j < NUM_CITIES; ++j)
        {
            distances[i][j] = calculateDistance(i, j);
            distances[j][i] = distances[i][j];
        }
    }
}

// 计算路径总距离
double calculatePathDistance(const std::vector<int>& path)
{
    double distance = 0.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;
}

// 生成初始路径
std::vector<int> generateInitialPath()
{
    std::vector<int> path(NUM_CITIES);
    std::iota(path.begin(), path.end(), 0);
    std::random_shuffle(path.begin(), path.end());
    return path;
}

// 接受新解的概率
double acceptanceProbability(double currentEnergy, double newEnergy, double temperature)
{
    if (newEnergy < currentEnergy)
        return 1.0;
    return exp((currentEnergy - newEnergy) / temperature);
}

// 模拟退火主函数
std::vector<int> simulatedAnnealing()
{
    std::vector<int> currentPath = generateInitialPath();
    double currentEnergy = calculatePathDistance(currentPath);
    double temperature = INITIAL_TEMP;

    for (int i = 0; i < MAX_ITERATIONS; ++i)
    {
        // 生成邻居解
        std::vector<int> neighborPath = currentPath;
        std::swap(neighborPath[rand() % NUM_CITIES], neighborPath[rand() % NUM_CITIES]);

        double neighborEnergy = calculatePathDistance(neighborPath);
        double ap = acceptanceProbability(currentEnergy, neighborEnergy, temperature);

        if (ap > static_cast<double>(rand()) / RAND_MAX)
        {
            currentPath = neighborPath;
            currentEnergy = neighborEnergy;
        }

        temperature *= COOLING_RATE; // 冷却
    }

    return currentPath;
}

int main()
{
    // 初始化城市坐标
    std::srand(std::time(nullptr)); // 使用当前时间作为随机种子
    for (int i = 0; i < NUM_CITIES; ++i)
    {
        cities.push_back(std::make_pair(std::rand() / (double)RAND_MAX, std::rand() / (double)RAND_MAX));
    }

    initializeDistances();

    // 执行模拟退火算法
    std::vector<int> bestPath = simulatedAnnealing();
    double bestDistance = calculatePathDistance(bestPath);

    // 输出结果
    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;
}
```

这段代码首先生成了一系列随机的城市坐标，并基于这些坐标计算了城市之间的距离。然后，使用模拟退火算法来寻找最优路径。算法开始时，温度设定得较高，这样算法倾向于接受大部分新解，包括那些比当前解更差的解。随着迭代次数的增加，温度逐渐降低，算法接受更差解的概率也随之降低，最终趋向于收敛到一个局部最优解或全局最优解。

需要注意的是，模拟退火算法的参数（如初始温度、冷却率、最大迭代次数等）对算法的性能有显著影响。在实际应用中，可能需要通过实验来调整这些参数，以获得最佳的结果。此外，算法的效率和结果也可能受到城市数量的影响，对于大规模的TSP问题，可能需要更复杂和高效的算法和数据结构。