TA的每日心情![](source/plugin/dsu_paulsign/img/emot/kx.gif) | 开心 2024-8-31 15:58 |
---|
签到天数: 89 天 [LV.6]常住居民II
管理员
- 积分
- 3366
|
遗传算法解决旅行商问题(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;
}
```
这段代码实现了基本的遗传算法流程,包括选择、交叉和变异操作,以及计算路径总距离的适应度函数。为了使示例简单,我们使用了一个固定的距离矩阵。在实际应用中,距离矩阵可能需要从文件读取或者通过某种方式动态生成。
请注意,遗传算法的性能和结果高度依赖于参数的选择,如种群大小、迭代次数、交叉和变异率等。在实际应用中,可能需要通过实验来找到最适合问题规模和特性的参数组合。 |
|