嗯哼，时隔半年，再次有时间整理关于组合优化问题——旅行商问题（Traveling Salesman Problem, TSP），这次采用的是经典遗传算法（Genetic Algorithm， GA）进行求解，利用C++语言进行编程实现。关于TSP问题以及GA的简单介绍，可参见我的另一篇文章：https://www.cnblogs.com/Alex-Xu-OR/p/9458239.html
各种启发式算法的整体框架大致都由以下几个操作组成：（1）初始解的产生；（2）解的评价（评价函数）；（3）扰动算子；此外，还可以加上程序原始数据的导入等操作。这些操作是多数启发式算法所通用的算子，基为此，此次在采用C++进行实现的时候，采用一个通用的 HeuristicOperator.h 头文件以及对应的 HeuristicOperator.cpp 类文件对这些操作进行集中放置，造好轮子，方便以后取用。
表1 HeuristicOperator中函数功能清单
编号
功能
记号
函数1
获取客户点坐标
getCoord()
函数2
获取距离矩阵
getDM()
函数3
获取初始解
getInitS()
函数4
解的评价
Eval()
函数5
搜索范围内最优评价值及其相对应的位置
bestS()
函数6
产生Sharking操作位置
RandPosition()
函数7
交换算子（swap）
Swap()
函数8
翻转算子（flip）
Flip()
函数9
插入算子（insert）
Insert()
注：函数5可以直接用 STL 中vector的操作函数max_element、min_element实现类似的功能，写的时候一时没有想起来，就自己造了个轮子。
之前在采用Matlab以及Java实现GA to solve TSP 时，考虑到程序的运行效率，通常会选用 array 来放置各种数据，众所周知，array的特点就是固定分配的连续物理地址进行数据的存储，然而对于不定长度的数据进行存储时，一般的方式是采用“多次少量”，即预先分配一定内存空间，等不够用了再分配一定的内存空间（多说一句，Matlab 中还可以采用以下两种方式：用 array=[]; 以及用cell实现存储不定长度数组，但效率不高）。而在C++ STL 中有一种神奇的数据类型vector容器，它既有着 array 的连续内存分配方式，又能不用指定数据存储长度，对于一组不同规模的数据集进行测试时，再也不用担心使用array时提醒必须预分配确定的存储空间了~~
以下为HeuristicOperator.h头文件：
1 #pragma once 2 #include<iostream> 3 #include<vector> 4 #include <algorithm> // std::shuffle 5 #include <random> // std::default_random_engine 6 #include<chrono> 7 using namespace std; 8 9 class HeuristicOperator { 10 public: 11 vector<vector<double>> getCoord(void); //函数1：获取坐标函数 12 vector<vector<double>> getDM(vector<vector<double>> Coord); //函数2：获取距离矩阵函数 13 vector<int> getInitS(int n); //函数3：获取初始解函数 14 double Eval(vector<int> S, vector<vector<double>> DM, int n); //函数4：评价函数 15 16 vector<double> bestS(vector<double> Eval, int Length); //函数5：搜索范围内最优评价值及其相应的位置函数 17 18 vector<int> RandPosition(int n); //函数6：产生Sharking操作位置函数 19 vector<int> Swap(vector<int> S, vector<int> RP); //函数7：交换算子 20 vector<int> Flip(vector<int> S, vector<int> RP); //函数8：翻转算子 21 vector<int> Insert(vector<int> S, vector<int> RP); //函数9：插入算子 22 };