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

### 遗传算法求解旅行商问题(C++)实例教程

#### 定义城市坐标结构体
为了表示各个城市的地理位置，定义一个简单的 `City` 结构体来存储二维平面上的城市位置。

struct City {
    int id;
    double x, y;

    // 计算两个城市之间的距离
    static double distance(const City& a, const City& b) {
        return std::sqrt(std::pow(a.x - b.x, 2) + std::pow(a.y - b.y, 2));
    }
};

#### 初始化种群
创建初始种群时随机打乱访问顺序形成不同的路径组合作为染色体。

std::vector<std::vector<int>> initialize_population(int population_size, int num_cities) {
    std::vector<std::vector<int>> population(population_size);
    
    for (int i = 0; i < population_size; ++i) {
        std::vector<int> individual(num_cities);
        std::iota(individual.begin(), individual.end(), 0); // 城市编号从0到num_cities-1
        
        std::random_shuffle(individual.begin(), individual.end());
        
        population[i] = individual;
    }

    return population;
}

#### 计算适应度函数
对于TSP来说，最短总路程代表最高适应度。因此需要计算每条路线的总长度并取其倒数作为适应度值[^1]。

double calculate_fitness(const std::vector<City>& cities, const std::vector<int>& route) {
    double total_distance = 0.0;
    
    for (size_t i = 0; i < route.size(); ++i) {
        size_t next_city_index = (i + 1) % route.size();
        total_distance += City::distance(cities[route[i]], cities[route[next_city_index]]);
    }

    return 1 / total_distance; // 路程越短越好
}

#### 实现交叉操作
采用部分映射交配(PMX)，确保子代不会含有重复节点的同时继承父辈特征[^2]。

void pmx_crossing(const std::vector<int>& parent1, const std::vector<int>& parent2,
                  std::vector<int>& child1, std::vector<int>& child2) {
    int start_pos = rand() % parent1.size();
    int end_pos = start_pos + 1 + rand() % (parent1.size() - start_pos);

    // 复制片段
    copy(parent1.begin() + start_pos, parent1.begin() + end_pos, child1.begin() + start_pos);
    copy(parent2.begin() + start_pos, parent2.begin() + end_pos, child2.begin() + start_pos);

    // 映射剩余部分...
}

// ...此处省略具体实现细节

#### 变异机制
以一定概率交换两条路径上的任意两点位置，保持群体多样性防止过早收敛于局部最优解[^4]。

void mutate(std::vector<int>& chromosome, double mutation_rate) {
    for (auto &gene : chromosome) {
        if ((rand() / double(RAND_MAX)) < mutation_rate) {
            auto swap_with = rand() % chromosome.size();
            std::swap(gene, chromosome[swap_with]);
        }
    }
}