TA的每日心情![](source/plugin/dsu_paulsign/img/emot/kx.gif) | 开心 2024-8-31 15:58 |
---|
签到天数: 89 天 [LV.6]常住居民II
管理员
- 积分
- 3366
|
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问题,可能需要更复杂和高效的算法和数据结构。 |
|