旅行商问题遗传算法c++

### 遗传算法解决旅行商问题的C++实现

#### 初始化种群
为了初始化种群，在遗传算法中通常会随机生成多个可能路径作为初始个体。这些路径代表城市访问顺序的不同排列。

#include <vector>
#include <random>

struct City {
    int id;
};

std::vector<std::vector<int>> initializePopulation(int populationSize, const std::vector<City>& cities) {
    std::vector<std::vector<int>> population(populationSize);
    
    for (int i = 0; i < populationSize; ++i) {
        population[i] = generateRandomRoute(cities); // 假设此函数可以生成一条随机路线
    }
    
    return population;
}

#### 计算适应度
适应度计算对于评估每条路径的好坏至关重要。这里采用总距离越短则适应度越高原则来定义适应度函数[^1]。

double calculateFitness(const std::vector<int>& route, const DistanceMatrix& distances) { // 假设有DistanceMatrix类存储各城市间距离
    double totalDistance = 0.0;

    for (size_t i = 0; i < route.size() - 1; ++i) {
        totalDistance += distances.getDistance(route[i], route[i + 1]);
    }

    // 添加回程到起点的距离
    totalDistance += distances.getDistance(route.back(), route.front());

    // 返回倒数，使得更优解具有更高分数
    return 1 / totalDistance;
}

#### 选择操作
通过轮盘赌法或其他概率模型挑选优秀个体参与繁殖下一代的过程称为选择操作。这一步骤有助于保留较佳基因组合并促进群体进化方向向最优解靠拢[^2]。

std::pair<std::vector<int>, std::vector<int>> selectParents(const Population& population) {
    // 实现轮盘赌选择逻辑...
}

// 或者使用锦标赛选择方式
std::pair<std::vector<int>, std::vector<int>> tournamentSelection(const Population& population) {
    // 实现锦标赛选择逻辑...
}

#### 交叉操作
两个父代染色体片段交换位置形成新后代的操作叫做交叉重组。这是创造多样化子代的重要手段之一。

std::vector<int> crossover(const std::vector<int>& parentA, const std::vector<int>& parentB) {
    size_t startPos = rand() % parentA.size();
    size_t endPos = rand() % parentA.size();

    if (startPos > endPos) std::swap(startPos, endPos);

    std::set<int> fragment(parentA.begin() + startPos, parentA.begin() + endPos + 1);
    auto child = parentB;

    for (auto it = child.begin(); it != child.end();) {
        if (fragment.find(*it) != fragment.end()) {
            it = child.erase(it);
        } else {
            ++it;
        }
    }

    for (const auto &gene : fragment) {
        child.push_back(gene);
    }

    return child;
}

#### 变异操作
以一定几率改变某些位点上的数值可增加种群内部差异性，防止早熟收敛现象发生。常见的变异策略有互换、移位等。

void mutate(std::vector<int>& individual, float mutationRate) {
    for (unsigned index = 0; index < individual.size(); index++) {
        if ((rand() / static_cast<float>(RAND_MAX)) < mutationRate) {
            unsigned swapWith = rand() % individual.size();
            
            // 进行交换
            std::swap(individual[index], individual[swapWith]);
        }
    }
}

以上展示了如何利用C++编写一个简单的基于遗传算法求解TSP问题程序框架。实际应用时还需要考虑更多细节优化以及参数调整等问题。