自适应大邻域 | 用ALNS框架求解一个TSP问题 - 代码详解
自适应大邻域 | 用ALNS框架求解一个TSP问题 - 代码详解
用户1621951
发布于 2019-06-06 11:04:53
发布于 2019-06-06 11:04:53
写在前面
这是ALNS系列的最后一篇文章辣！！！自此，该系列就完结了，撒花！
我们总算是把整个ALNS的代码框架给大家说明白了。不知道大家对整个框架了解了没有。
不过打铁要趁热，心急了要吃热豆腐。今天就来实战一下，教大家怎么用ALNS的代码框架，求解一个老生常谈的TSP问题。
So, get ready？
01 文件说明
整个项目由多个文件组成，为了大家更好了解各个文件的内容以及他们之间的关系，小编特地做了一份表格说明。
类名或文件名 | 说明 |
|---|---|
main | 主文件 |
TSPSolution | Solution的定义和各种相关操作 |
TSP_LS | LocalSearch |
TSP_Best_Insert | repair方法 |
TSP_Random_Insert | repair方法 |
TSP_History_Removal | destroy方法 |
TSP_Random_Removal | destroy方法 |
TSP_Worst_Removal | 主destroy方法 |
02 主逻辑过程分析
这一篇文章主要分析该程序的主逻辑过程，代码中的相关模块看不懂没关系，后面会详细讲解到的。
大家先知道这么一个东西就行了。代码和具体解释贴在下面了，该过程主要是生成相应的模块，并且组装进去然后run起来而已，还算蛮简单的了。
1int main(int argc, char* argv[])
2{
3 //构造TSP数据，100个点，坐标随机生成，这里你们可以按照自己的方式输入数据
4 double* x = new double[100];
5 double* y = new double[100];
6 for(int i = 0; i < 100; i++)
7 {
8 x[i] = 100*(static_cast<double>(rand()) / RAND_MAX);
9 y[i] = 100*(static_cast<double>(rand()) / RAND_MAX);
10 }
11 double** distances = new double*[100];
12 for(int i = 0; i < 100; i++)
13 {
14 distances[i] = new double[100];
15 for(int j = 0; j < 100; j++)
16 {
17 distances[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
18 }
19 }
20
21 //生成初始空解。参数是距离矩阵和城市数目
22 TSPSolution initialSol(distances,100);
23 //生成repair和destroy方法
24 TSP_Best_Insert bestI("Best Insertion");
25 TSP_Random_Insert randomI("Random Insertion");
26 TSP_Random_Removal randomR("Random Removal");
27 TSP_Worst_Removal worstR("Worst Removal");
28 TSP_History_Removal historyR("History Removal",100);
29
30 //对初始空解进行填充，形成初始解
31 randomI.repairSolution(dynamic_cast<ISolution&>(initialSol));
32
33 //加载相关参数
34 ALNS_Parameters alnsParam;
35 alnsParam.loadXMLParameters("./param.xml");
36
37 CoolingSchedule_Parameters csParam(alnsParam);
38 csParam.loadXMLParameters("./param.xml");
39 ICoolingSchedule* cs = CoolingScheduleFactory::makeCoolingSchedule(dynamic_cast<ISolution&>(initialSol),csParam);
40 SimulatedAnnealing sa(*cs);
41
42
43 //添加repair和destroy方法到OperatorManager
44 OperatorManager opMan(alnsParam);
45 opMan.addDestroyOperator(dynamic_cast<ADestroyOperator&>(randomR));
46 opMan.addDestroyOperator(dynamic_cast<ADestroyOperator&>(worstR));
47 opMan.addDestroyOperator(dynamic_cast<ADestroyOperator&>(historyR));
48 opMan.addRepairOperator(dynamic_cast<ARepairOperator&>(bestI));
49 opMan.addRepairOperator(dynamic_cast<ARepairOperator&>(randomI));
50 //生成SolutionManager和LocalSearchManager对Solution和LocalSearch进行管理
51 SimpleBestSolutionManager bestSM(alnsParam);
52 SimpleLocalSearchManager simpleLsManager(alnsParam);
53 //生成LocalSearch
54 TSP_LS ls("My LS");
55 TSP_LS lsB("LS FD");
56 //将LocalSearch添加到 LocalSearchManager
57 simpleLsManager.addLocalSearchOperator(dynamic_cast<ILocalSearch&>(ls));
58 simpleLsManager.addLocalSearchOperator(dynamic_cast<ILocalSearch&>(lsB));
59 //生成ALNS算法框架
60 ALNS alns("tspExample",dynamic_cast<ISolution&>(initialSol),dynamic_cast<IAcceptanceModule&>(sa),alnsParam,dynamic_cast<AOperatorManager&>(opMan),dynamic_cast<IBestSolutionManager&>(bestSM),dynamic_cast<ILocalSearchManager&>(simpleLsManager));
61 //destroy方法TSP_History_Removal需要进行部分内容更新
62 alns.addUpdatable(dynamic_cast<IUpdatable&>(historyR));
63 //求解
64 alns.solve();
65 //清理
66 for(int i = 0; i < 100; i++)
67 {
68 delete[] distances[i];
69 }
70 delete[] distances;
71 delete[] x;
72 delete[] y;
73 delete cs;
74
75 return 0;
76}03 LocalSearch
前面我们提到，可以用LocalSearch也可以不用LocalSearch。一般用了LocalSearch情况会更好一点，来看看此处的LocalSearch是怎么定义的吧。
其实LocalSearch是继承于ALNS框架里面的ILocalSearch 类的，其中最主要的一个函数就是performLocalSearch执行LocalSearch操作，具体代码如下：
1bool TSP_LS::performLocalSearch(ISolution& sol)
2{
3 TSPSolution& tspsol = dynamic_cast<TSPSolution&>(sol);
4 bool ok = false;
5 bool toReturn = false;
6 do
7 {
8 ok = false;
9 //找出下标和该位置存储的城市序列值相同的点，移除
10 for(int cust = 0; cust < tspsol.getCustomerSequence().size(); cust++)
11 {
12 double prevCost = tspsol.getObjectiveValue();
13 int prevPos = 0;
14 for(int pos = 0; pos < tspsol.getCustomerSequence().size(); pos++)
15 {
16 if(tspsol.getCustomerSequence()[pos] == cust)
17 {
18 tspsol.remove(pos);
19 prevPos = pos;
20 break;
21 }
22 }
23 //寻找一个更优的位置插入
24 for(int pos = 0; pos < tspsol.getCustomerSequence().size(); pos++)
25 {
26 if(tspsol.evaluateInsert(cust,pos)+tspsol.getObjectiveValue()<prevCost-0.01)
27 {
28 tspsol.insert(cust,pos);
29 prevPos = -1;
30 ok = true;
31 toReturn = true;
32 break;
33 }
34 }
35 if(prevPos != -1)
36 {
37 tspsol.insert(cust,prevPos);
38 }
39 }
40 }while(ok);
41 return toReturn;
42}看不太懂？没关系，小编可是图文并茂的好手。这就是LocalSearch执行的操作。
04 TSPSolution
这里的TSPSolution继承于之前介绍过的ISolution，其相关接口和说明已经注释在代码里面了。
然后再唠叨两句，nonInserted存储的是未插入解的城市，customerSequence存储的是解里面的城市，好了大家看代码把吧：
1class TSPSolution: public ISolution {
2public:
3 //! Constructor
4 TSPSolution(double** distances, int nbNodes);
5 //! Destructor.
6 virtual ~TSPSolution();
7 //! A getter for the value of the objective function.
8 //! \return the value of the objective function of this solution.
9 virtual double getObjectiveValue();
10 //! \return a penalized version of the objective value if the solution
11 //! is infeasible.
12 virtual double getPenalizedObjectiveValue();
13 //! A getter for the feasibility of the current solution.
14 //! \return true if the solution is feasible, false otherwise.
15 virtual bool isFeasible();
16 //! A comparator.
17 //! \return true if this solution is "better" than the solution it is compared to.
18 virtual bool operator<(ISolution&);
19 //! Compute the "distance" between solution.
20 //! This feature can be used as part of the ALNS to favor the
21 //! diversification process. If you do not plan to use this feature
22 //! just implement a method returning 0.
23 virtual int distance(ISolution&);
24 //! This method create a copy of the solution.
25 virtual ISolution* getCopy();
26 //! Compute a hash key of the solution.
27 virtual long long getHash();
28 //! Simple getter.
29 std::vector<int>& getCustomerSequence(){return customerSequence;};
30 std::vector<int>& getNonInserted(){return nonInserted;};
31 void recomputeCost();
32 void insert(int node, size_t pos);
33 void remove(size_t pos);
34 double evaluateInsert(int node, size_t pos);
35 double evaluateRemove(size_t pos);
36private:
37 int nbNodes;
38 double** distanceMatrix;
39 double cost;
40 std::vector<int> customerSequence;
41 std::vector<int> nonInserted;
42};关于其CPP文件，挑几个值得将的方法来讲讲吧。
…… …… …… …… ……
呃，然后发现好像也没什么可讲的。讲讲一个难点吧，大家在看CPP文件的时候，插入城市和评估插入城市情况的时候会看到大量这样的代码：
1 cost -= distanceMatrix[customerSequence[pos-1]][customerSequence[pos]];
2 cost += distanceMatrix[customerSequence[pos-1]][node];
3 cost += distanceMatrix[node][customerSequence[pos]];
4 ............
5 delta -= distanceMatrix[customerSequence[pos-1]][customerSequence[pos]];
6 delta += distanceMatrix[customerSequence[pos-1]][node];
7 delta += distanceMatrix[node][customerSequence[pos]];讲讲具体原理。假如有以下城市序列：
现在我们把城市5给移除掉了。那么移除以后需要再计算一下该序列的cost怎么办呢？
难道又要重头加到尾吗？？？ NO！NO！NO！
看下面：
new_cost = cost - distance(7, 5) - distance(5, 1) + distance(7, 1)。
懂了吧？这种东西，意会一下就行了，不用我说得太明白。
05 repair和destroy方法
其实，repair和destroy方法组合起来，本质上还是一个LocalSearch的算子，这一点大家还是要理解的。
所以，这里挑两个来给大家讲讲就好了，毕竟关于具体的TSP求解算子，在之前的文章中介绍了很多，像什么2opt、2hopt、3opt等等。也不是本文的重点辣。
5.1 TSP_Best_Insert
TSP_Best_Insert继承于ARepairOperator ，它具体执行的操作如下。
其实很简单，找到合适的位置插入，直到把整个解都给修复了为止，那么如何判断该位置是否合适？由evaluateInsert方法评估得出：
1void TSP_Best_Insert::repairSolution(ISolution& sol)
2{
3 TSPSolution& tspsol = dynamic_cast<TSPSolution&>(sol);
4 while(!tspsol.getNonInserted().empty())
5 {
6 int pos = 0;
7 int node = 0;
8 double best = 100000;
9 for(vector<int>::iterator it = tspsol.getNonInserted().begin(); it != tspsol.getNonInserted().end(); it++)
10 {
11 for(size_t i = 0; i <= tspsol.getCustomerSequence().size(); i++)
12 {
13 double cost = tspsol.evaluateInsert(*it,i);
14 if(cost < best)
15 {
16 best = cost;
17 pos = i;
18 node = *it;
19 }
20 }
21 }
22 tspsol.insert(node, pos);
23 }
24}5.2 TSP_Random_Removal
这个destroy方法也很简单，它也继承于ADestroyOperator。
和TSP_Best_Insert不同的是，它实现的是从解的城市序列里面随机移除多个城市，具体代码如下：
1void TSP_Random_Removal::destroySolution(ISolution& sol)
2{
3 TSPSolution& tspsol = dynamic_cast<TSPSolution&>(sol);
4 int randomDest = (rand() % static_cast<int>(0.1 * static_cast<double>(tspsol.getCustomerSequence().size()))) + static_cast<int>(0.1 * static_cast<double>(tspsol.getCustomerSequence().size()));
5 for(int i = 0; i < randomDest; i++)
6 {
7 int pos = rand() % tspsol.getCustomerSequence().size();
8 tspsol.remove(pos);
9 }
10}05 小结
这次介绍了具体怎么在ALNS的基础上定制自己的代码求解一个TSP问题，有了前面的理解，相信这里对大家来说简直小菜一碟。
至此，整个ALNS系列就完结了，谢谢大家的一路跟随。希望这些代码能给你萌带来意想不到的收获。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读