遗传算法解决TSP问题

一、求解问题概述

1.1 TSP问题

TSP问题是指旅行商问题（Traveling Salesman Problem）。在TSP问题中，假设有一名旅行商要在给定的一组城市之间进行旅行，每个城市只能被访问一次，并且旅行商必须最终返回出发城市。问题的目标是找到一条路径，使得旅行商的总旅行距离最短。

TSP问题是一个经典的组合优化问题，在计算复杂性理论中被证明是NP-难问题，意味着在一般情况下，找到最优解需要耗费大量的计算时间。TSP问题在实际应用中具有广泛的应用，如物流规划、电路板设计、基因组测序等领域。为了解决TSP问题，许多算法和启发式方法被提出，包括穷举搜索、动态规划、近似算法（如最近邻算法和模拟退火算法）、遗传算法等。这些方法旨在找到一个近似最优解或者在可接受的时间内找到较好的解决方案。

1.2 目标函数

在该问题中，我们需要定义一个目标函数，它是根据决策变量的值来计算问题的目标。目标函数可以是线性的、非线性的、凸的或非凸的，具体取决于问题的性质。例如，在一个生产调度问题中，目标函数可以是最小化总生产时间或最大化利润。

$$\arg \underset{x}{\min }\sum _{i=1}^n\sum _{j=1}^n{c}_{ij}{x}_{ij}$$

其中：

$n$ 是城市的数量。
$c_{ij}$ 是城市i到城市j之间的距离（或时间）。
$x_{ij}$ 是决策变量，表示是否从城市i移动到城市j。当路径经过城市i到城市j时，$x_{ij}$ 取值为1，否则为0。
TSP 的目标函数即为所有路径距离或路径时间的总和，通过最小化这个目标函数，可以找到一条最优路径，使得旅行商经过所有城市后的总距离或总时间最小。

二、优化方法概述

TSP问题属于组合优化问题，往往这种问题如果用枚举法来求解的话，都会遇到 $n!$ 或者 $m^n$ 等复杂度爆炸的情况，都属于 NP 难问题。

解决这种问题的方法一般采用近似法求解，即：在损失少量求解精度的前提下，节约大量的时间3开销。

下面采用一种改进的遗传算法对 TSP 问题进行求解。

三、程序代码

该算法参考自计算机学报论文《一种改进的求解 TSP 问题的演化算法》¹

// 解决TSP问题的重构算法（主要是tsp0的代码风格太丑陋了，修改成C++风格）
#include<iostream>
#include<fstream>
#include<vector>
#include<time.h>
#include<string>
using namespace std;class TSP_M {
private:int numCity;					 // 城市数量vector<vector<double>> cityXY;	 // 城市坐标vector<vector<double>> cityDis;  // 城市间距离的邻接矩阵int numColony = 100;			 // 种群数量vector<vector<int>> colony;		 // 种群vector<double> individualAdaptability; // 个体适应度int maxGen = 200000;			 // 最大演化代数double probabilityMutation = 0.02;	// 变异概率vector<int> bestIndividual;			// 当前最优个体double bestAdaptability;			// 当前最优个体的适应度public:// 计算种群中每个个体的适应度void calculateAdaptability() {// 计算每个个体的适应度for (int i = 0; i < numColony; i++) {double sum = 0;for (int j = 0; j < numCity; j++) {sum += cityDis[colony[i][j]][colony[i][(j + 1) % numCity]];}individualAdaptability[i] = sum;}}// 初始化void init(string filePath) {readTspFile(filePath);// 根据tsp数据，初始化相关数据calculateData();}// 进行迭代计算void evolution() {for (int curGen = 0; curGen < maxGen; curGen++) { // 迭代maxGen次for (int i = 0; i < numColony; i++) { // 遍历种群中所有个体vector<int> path = colony[i]; // 用于存放变异后的路径int posC1 = rand() % numCity; // 随机生成变异点1（在path中的位置）int posC2 = rand() % numCity; // 随机生成变异点2（在path中的位置）int C1, C2; // 变异点1和变异点2对应的城市编号C1 = path[posC1]; // 获取变异点1对应的城市int j = rand() % numColony;   // 用于外变异的另一个 与 i个体 不同的个体int pos_flag = 0; // 用于标记变异过的点的数量double distanceChange = 0; // 用于记录距离变化while (true){// 以 probabilityMutation (default = 0.02)的概率进行内变异if (rand() / 32768.0 < probabilityMutation) {posC2 = rand() % numCity;while (posC1 == posC2) { // 如果两个变异点相同，则重新生成posC2 = rand() % numCity;}C2 = colony[i][posC2]; // 获取变异点1对应的城市}else { // 进行外变异（交叉）j = rand() % numColony;while (i == j) { // 如果两个个体相同，则重新生成j = rand() % numColony;}// 获取个体 j 中 变异点1 对应城市的位置int pos = position(colony[j], path[posC1]);C2 = colony[j][(pos + 1) % numCity]; // 获取变异点2对应的城市posC2 = position(path, C2); // 获取变异点2在个体 i 中的位置(即变异点2对应的城市在个体 i 中的位置}// 如果两个变异点相邻，continueif ((posC1 + 1) % numCity == posC2 || (posC1 - 1 + numCity) % numCity == posC2)break;//if (abs(posC1 - posC2) == 1 || abs(posC1 - posC2) == numCity - 1) {//	continue;//}// 否则进行倒位操作int C1_left = path[posC1]; // 变异点1左边的城市int C1_right = path[(posC1 + 1) % numCity]; // 变异点1右边的城市int C2_left = path[posC2]; // 变异点2左边的城市int C2_right = path[(posC2 + 1) % numCity]; // 变异点2右边的城市// 计算倒位后的路径长度distanceChange += cityDis[C1_left][C2_left] + cityDis[C1_right][C2_right]- cityDis[C1_left][C1_right] - cityDis[C2_left][C2_right];invert(path, posC1, posC2); // 倒位操作pos_flag++; // 变异点数量加一if (pos_flag >= numCity)break;posC1++; // 变异点1的位置加一if (posC1 >= numCity) posC1 = 0; // 如果变异点1的位置超过了numCity，则变异点1的位置为0}// 更新子个体的适应度individualAdaptability[numColony + i] = individualAdaptability[i] + distanceChange;distanceChange = 0;// 记录 产生的 子个体for (int j = 0; j < numCity; j++) {colony[numColony + i][j] = path[j];}}// 一轮迭代之后进行选择selection();bestIndividual = colony[0]; // 更新最优个体bestAdaptability = individualAdaptability[0]; // 更新最优个体的适应度for (int i = 1; i < numColony; i++) {if (individualAdaptability[i] < bestAdaptability) {bestIndividual = colony[i];bestAdaptability = individualAdaptability[i];}}// cout << "第" << curGen << "代的最优个体适应度为：" << bestAdaptability << endl;cout << curGen << ":" << bestAdaptability << endl;// 创建 outfile.txt 文件ofstream outfile("outfile.txt", ios::app);// 每 2000 代将最优个体的适应度写入文件if ((curGen + 1) % 2000 == 0) {outfile << curGen << ":" << bestAdaptability << endl;}// 关闭文件outfile.close();}}// 获取城市在路径中的位置int position(vector<int>& path, int city) {for (int i = 0; i < numCity; i++) {if (path[i] == city) {return i;}}return -1;}void invert(vector<int>& path, int pos1, int pos2) {// 如果pos1在pos2的左边，为一段if (pos1 < pos2) {for (int i = pos1 + 1, j = pos2; i < j; i++, j--) {swap(path[i], path[j]);}}// 如果pos1在pos2的右边，为两段else {// 右边的段 <= 左边的段if (numCity - 1 - pos1 <= pos2 + 1) {int i, j;for (i = pos2 + 1, j = pos1; i <= numCity - 1; i++, j--) {swap(path[i], path[j]);}for (i = 0; i < j; i++, j--) {swap(path[i], path[j]);}}// 右边的段 > 左边的段else {int i, j;for (i = pos2 + 1, j = pos1; j >= 0; i++, j--) {swap(path[i], path[j]);}for (j = numCity - 1; i < j; i++, j--) {swap(path[i], path[j]);}}}}// 在父代和子代中进行一个锦标赛选择void selection() {for (int i = 0; i < numColony; i++) {if (individualAdaptability[i] > individualAdaptability[numColony + i]) {individualAdaptability[i] = individualAdaptability[numColony + i];for (int j = 0; j < numCity; j++) {colony[i][j] = colony[numColony + i][j];}}}}// 读取tsp文件bool readTspFile(string filePath) {fstream input(filePath, ios::in);if (!input) {cout << "文件打开失败" << endl;return false;}input >> numCity; // 城市数量cout << numCity << endl;// 初始化cityXYcityXY = vector<vector<double>>(numCity, vector<double>(2));// 读取城市坐标double x, y;for (int i = 0; i < numCity; i++) {int tmp;input >> tmp >> x >> y;cout << tmp << " " << x << " " << y << endl;cityXY[i][0] = x;cityXY[i][1] = y;}// 关闭文件input.close();return true;}// 根据tsp数据计算城市之间的距离、并随机初始化种群、同时计算适应度void calculateData() {// 初始化cityDiscityDis = vector<vector<double>>(numCity, vector<double>(numCity));// 计算城市间距离for (int i = 0; i < numCity; i++) {for (int j = 0; j < numCity; j++) {cityDis[i][j] = sqrt(pow(cityXY[i][0] - cityXY[j][0], 2) + pow(cityXY[i][1] - cityXY[j][1], 2));}}// 初始化colony （包括父代和子代）colony = vector<vector<int>>(2 * numColony, vector<int>(numCity));// 以时间为种子，随机生成种群srand((unsigned)time(NULL));// 建立一个用于随机生成种群的数组vector<int> tmp(numCity);for (int i = 0; i < numCity; i++) {tmp[i] = i;}// 随机初始化种群for (int i = 0; i < numColony; i++) {int numNeedToRand = numCity;	// 当前需要随机的次数for (int j = 0; j < numCity; j++) {int randIndex = rand() % numNeedToRand; // 随机生成下标colony[i][j] = tmp[randIndex]; // 将随机生成的下标对应的值赋给种群swap(tmp[randIndex], tmp[numNeedToRand - 1]); // 将已经随机过的下标与最后一个下标交换numNeedToRand--; // 需要随机的次数减一}}// 初始化individualAdaptabilityindividualAdaptability = vector<double>(2 * numColony); // 后面的numColony个是用于存放子个体的适应度的// 计算种群中每个个体的适应度calculateAdaptability();}// 获取最优个体vector<int> getBestIndividual() {int bestIndex = 0;for (int i = 1; i < numColony; i++) {if (individualAdaptability[i] < individualAdaptability[bestIndex]) {bestIndex = i;}}return colony[bestIndex];}
};int main() {TSP_M tsp;// tsp.readTspFile("./pcb442.tsp");tsp.init("./pcb442.tsp");tsp.evolution();vector<int> bestIndividual = tsp.getBestIndividual();// 输出最优个体到文件fstream output("./bestIndividual_Serial.txt", ios::out);for (int i = 0; i < bestIndividual.size(); i++) {output << bestIndividual[i] << " ";}return 0;
}

四、运行结果

从图中可以看出算法的所有的路线基本都没有交叉，性能较为鲁棒。

---

1. [1]蔡之华,彭锦国,高伟,魏巍,康立山.一种改进的求解TSP问题的演化算法[J].计算机学报,2005(05):823-828. ↩︎