模擬退火和遺傳算法求解TSP問題

源代碼傳送門：GITHUB
數(shù)據(jù)傳送門：TSPLIB

文章目錄

• 模擬退火和遺傳算法求解TSP問題
• • 摘要
  • 1 導(dǎo)言
  • • 1.1 問題重述
    • 1.2 TSP問題選擇
    • 1.3 思路設(shè)計
    • 1.4 結(jié)果簡覽
  • 2 實驗過程
  • • • 2.1 TSPbase
      • 2.2 LocalSearch
      • • 2.2.1 流程圖
        • 2.2.2 滿意度、活躍度機制
        • 2.2.3 鄰域操作
        • 2.2.4 代碼分析
      • 2.3 SimulatedAnnealing
      • • 2.3.1 流程圖
        • 2.3.2 代碼分析
      • 2.4 GeneticAlgorithm
      • • 2.4.1 流程圖
        • 2.4.2 交叉與變異算子
        • 2.4.3 評分機制及精英保留策略
        • 2.4.4 代碼分析
  • 3 結(jié)果分析
  • • • 3.1 實驗環(huán)境
      • • 3.1.1 系統(tǒng)信息
        • 3.1.2 開發(fā)工具
      • 3.2 編譯運行
      • • 3.2.1 初始狀態(tài)
        • 3.2.2 編譯
        • 3.2.3 運行及自定參數(shù)
        • 3.3.4 結(jié)果可視化
      • 3.3 搜索結(jié)果及比較
      • • 3.3.1 實驗數(shù)據(jù)對比
        • 3.3.2 實驗數(shù)據(jù)可視化
        • 3.3.3 路線對比
      • 3.4 性能分析
      • 3.5 探索與展望
  • 4 結(jié)論
  • 5 主要參考文獻

摘要

本實驗使用局部搜索、模擬退火、遺傳算法（C/C++實現(xiàn)），對TSP問題進行搜索求解。

在實現(xiàn)算法、適當調(diào)參后，在選用的5個TSP問題中皆搜索得到誤差小于10%的路線。

---

1 導(dǎo)言

1.1 問題重述

選一個大于100個城市數(shù)的TSP問題：

局部搜索與模擬退火：

采用多種鄰域操作的局部搜索local search策略求解；

在局部搜索策略的基礎(chǔ)上，加入模擬退火simulated annealing策略，并比較兩者的效果；

要求求得的解不要超過最優(yōu)值的10％，并能夠提供可視化圖形界面，觀察路徑的變化和交叉程度。

用遺傳算法求解TSP問題（問題規(guī)模等和模擬退火求解TSP實驗同），要求：

設(shè)計較好的交叉操作，并且引入多種局部搜索操作（可替換通常遺傳算法的變異操作）

和之前的模擬退火算法（采用相同的局部搜索操作）進行比較

得出設(shè)計高效遺傳算法的一些經(jīng)驗，并比較單點搜索和多點搜索的優(yōu)缺點。

1.2 TSP問題選擇

本實驗從TSPLIB中選擇了5個不同的TSP問題，分別為：

TSP NameCommentDIMENSIONOptimal Solution

kroC100	100-city problem C (Krolak/Felts/Nelson)	100	20749
ch150	150 city Problem (churritz)	150	6528
tsp225	A TSP problem (Reinelt)	225	3919
a280	drilling problem (Ludwig)	280	2579
pcb442	Drilling problem (Groetschel/Juenger/Reinelt)	442	50778

1.3 思路設(shè)計

主要思想即上圖所示，詳細算法內(nèi)容將在之后的部分說明。

---

1.4 結(jié)果簡覽

以下實驗結(jié)果以5次實驗取平均值，詳細結(jié)果分析將在之后的部分說明。

Summary

TSP NameLocalSearchSimulated AnnealingGenetic Algorithm

kroC100	22792.88 (Loss 9.85%)	20851.4 (Loss 0.49%)	21903.34(Loss 5.56%)
ch150	7260.656 (Loss 11.22%)	6560.936 (Loss 0.50%)	7124.162 (Loss 9.13%)
tsp225	4308.558 (Loss 9.94%)	3968.232 (Loss 1.26%)	4236.946 (Loss 8.11%)
a280	2906.766 (Loss 12.7%)	2612.91 (Loss 1.31%)	2922.06 (Loss 13.3%)
pcb442	57557.38(Loss 13.35%)	51877.96 (Loss 2.17%)	57649.48 (Loss 13.5%)

在本次實驗實現(xiàn)的三種算法中，可以看到模擬退火算法的表現(xiàn)極佳，遺傳算法稍遜，局部搜索算法較次。

實驗中的數(shù)據(jù)比較也進行了可視化處理，將在之后的實驗結(jié)果中詳細分析。

---

2 實驗過程

2.1 TSPbase

TSPbase 是一個用于預(yù)處理TSP問題數(shù)據(jù)、為高級搜索方法提供API的基類。

這里給出頭部文件的實例，詳細實現(xiàn)可參見src/TSPbase.cpp。

/***************************************************************** FileName : TSPbase.h ** Author : Karl ** Created Date : June 5, 2020 ** Updated : June 8, 2020 - Add Function ** June 9, 2020 - Fix Bug ** June 9, 2020 - Modify Perfomance ** June 22, 2020 - Last Check **==============================================================** @Functions: ** TSPbase::TSPbase(MAP_TYPE& origin) - Consructor. ** TSPbase::distance(COORD city1, COORD city2) ** - calculate EUC2D distance between city1 and city2. ** TSPbase::currentCost() - calculate cost of `private` path. ** TSPbase::currentCost(vector<int> path) ** - calculate cost of path. ** TSPbase::roulette() - generate a random decimal in (0, 1). ** TSPbase::generateRandomPath() - generate a random path. ** TSPbase::getOptCost() - return the best(least) cost so far.** TSPbase::updateOptCost(double new_dist) ** - update current best cost with new_dist. ** TSPbase::backUp() - back up current path. ** TSPbase::recover() - recover current path with backup. **==============================================================*/ class TSPbase { public:... protected:int N; // DimensionMAP_TYPE citys; // Citys mapdouble* dist_map; // Dists mapdouble opt_cost; // Optimal cost(least distance)int* path; // Current pathint* city2path; // Map a city to its position in pathint* path_bak; // Path backupint* city2path_bak; // Map backup };

首先，對于一個TSP問題，分析需要考慮的內(nèi)容：

城市總數(shù)，即問題的維度：N

每個城市編號以及對應(yīng)坐標：citys

路徑：path

在讀入問題文件后，分析需要記錄、預(yù)計算的內(nèi)容：

城市間距離：dist_map

在搜索過程中，會非常頻繁地計算整條路徑的長度（歐氏距離），如果每次都要進行運算，將大大影響我們程序的效率，因此，預(yù)計算城市之間距離，靜態(tài)存到數(shù)組中，在計算路徑長度時以查表代替計算，能有效提高效率。

最優(yōu)解：opt_cost

城市編號到路徑的映射：city2path

在搜索過程中，可能涉及城市權(quán)重等需要按城市順序存儲的數(shù)據(jù)，因此，在選中一個城市后，想在O(1)時間內(nèi)定位到它在路徑中的位置，就需要建立一個從城市編號到路徑位置的對應(yīng)關(guān)系。

對每一次搜索進行備份：

類似于常見的搜索算法，當當前搜索結(jié)果并不如意，我們需要回溯到上一狀態(tài)，這就要求TSPbase能夠提供備份、恢復(fù)的功能。

路徑的備份：path_bak

城市編號到路徑的映射的備份：city2path_bak

注：

TSPbase提供的方法API在文件頭部注釋中有詳細介紹，且命名是具有可讀性的，在此不展開篇幅進行介紹。

---

2.2 LocalSearch

LocalSearch是基于TSPbase實現(xiàn)的局部搜索算法，為優(yōu)化效果，加入了以下特性：

加入了滿意度、活躍度機制

提前終止

以下對局部搜索算法進行詳細介紹：

2.2.1 流程圖

2.2.2 滿意度、活躍度機制

該機制參考于論文《求解TSP問題的自適應(yīng)領(lǐng)域搜索法及其擴展》

滿意度

直觀地，對每個城市而言，最佳位置是該城市和與之相距最近的兩個城市相連。

在選擇城市的時候，我們自然希望所有城市盡可能在自己的最佳位置。為了判斷一個城市所在位置是否足夠令人滿意，加入了滿意度（$f_i$, 第i個城市的滿意度）的定義：

對城市i以及與之相連的城市j、k，以及距離城市i最近的兩個城市s和城市t：
$$\begin{gathered} f_i=exp[?\frac{(d_{ij}+d_{ik}?d_{is}?d_{it}{)}^2}{2{\delta }^2}] \\ {f}_i：第i個城市的滿意度 \\ {d}_{XY}:城市X與城市Y之間的距離 \\ \delta ：參數(shù) \end{gathered}$$
由此可見，滿意度是一個在區(qū)間(0, 1]內(nèi)變化的數(shù)，當滿意度為1時，說明該城市已達到最佳狀態(tài)。

活躍度

為了避免某些滿意度低的城市經(jīng)過多次操作仍然難以提高滿意度，從而導(dǎo)致算法始終只操作某些低滿意度城市、忽略滿意度相對高的城市，陷入局部最優(yōu)解的情況，引入活躍度進行限制：

對城市i：
$$\begin{gathered} V_i(t+1)=\eta V_i(t)+\Delta V \\ {h}_i(t+1)=1?exp[?\frac{(V_i(t+1){)}^2}{2{\sigma }^2}] \\ {V}_i(t)：t時刻的信息素 \\ \eta ：松弛系數(shù)，取值(0,1)，未進行操作的城市將緩慢降低活躍度 \\ {h}_i(t)：t時刻的活躍度 \\ \Delta V：若城市i進行了反轉(zhuǎn)操作，則\Delta V=\frac{N\sigma (1?\eta )}{K},K為反轉(zhuǎn)操作的城市數(shù)量 \\ 否則，\Delta V=0 \end{gathered}$$
城市權(quán)重

當某些低滿意度的城市被頻繁操作后，它們的滿意度會大幅上升，此時按照權(quán)重函數(shù)：
$$P_i(t)=[1?f_i(t)][1?h_i(t)]$$
能避免對同一個城市過于頻繁操作或根本不對某些城市進行操作的情況。

2.2.3 鄰域操作

鄰域定義

對每個城市，其鄰域定義為：
$$\begin{gathered} d_{ij}\le d_{it}+\Delta d \\ \Delta d=\frac{3}{N}\sum _{i=1}^N{d}_i \\ {d}_i：城市i與相距最近的城市距離 \end{gathered}$$
對城市i，找到距離它次近的城市t，對于其他城市j，若滿足上述條件，則判定城市j在其鄰域中。

操作 - 交換兩個城市

樸素操作，當變換能夠優(yōu)化路徑，則保留。

因此容易陷入局部最優(yōu)解。

操作 - 逆轉(zhuǎn)一段序列

通過逆轉(zhuǎn)序列操作，能夠優(yōu)化上述情況。

操作 - 3-opt

3-opt操作能產(chǎn)生以上7種新情況，從中選擇效果最好的一種。

2.2.4 代碼分析

這里給出頭部文件的實例，詳細實現(xiàn)可參見src/LocalSearch.cpp。

/***************************************************************** FileName : LocalSearch.h ** Author : Karl ** Created Date : June 5, 2020 ** Updated : June 8, 2020 - Add Function ** June 9, 2020 - Fix Bug ** June 9, 2020 - Modify Perfomance ** June 12, 2020 - Add satification ** and activity **==============================================================** @Functions: ** LocalSearch::LocalSearch(MAP_TYPE& origin, int LOOP_LIMITS,** int LOOSE_COEF, int EARLY_STOP, ** int VERBOSE) - Consructor. ** LocalSearch::chooseNode() ** - choose a Node according to its weight. ** LocalSearch::chooseNode(int base, int range) ** - choose a Node within (base - range, base + range) ** LocalSearch::propagateWeightChange(int node_num, int value)** - propagate weight change of node`node_num`. ** LocalSearch::search() ** - do neighbour operation to search for a new solution. ** LocalSearch::checkPath() - check `private` path's validity.** LocalSearch::checkPath(vector<int> path) ** - check path's validity. ** LocalSearch::earlyStop() - check whether to early stop. ** LocalSearch::run() - start LocalSearch process. ** LocalSearch::report() - save result to files. ** LocalSearch::exchangeTwoNode(int pos, vector<int>& p) ** - Neighbour operation: exchange two node(city). ** LocalSearch::reverseSequence(int pos, vector<int>& p) ** - Neighbour operation: reverse a sub-sequence. ** LocalSearch::popToFront(int pos, vector<int>& p) ** - Neighbour operation: pop a node to front. **==============================================================*/class LocalSearch: public TSPbase { public:... protected:int LOOP_LIMITS; // Maximum Loop Timesint EARLY_STOP; // Early Stop Epochint VERBOSE; // Verbose Messageint early_stop_counter; // Early Stop Counterdouble LOOSE_COEF; // Coefficient to contorl loose op.double delta_d; // parameterdouble delta_v; // parameterdouble* node_weights; // Weight for selectiondouble* node_satisfication; // Satisfication for citiesdouble* node_active_value; // Activy for citiesvector<Individual> opt_hist; // History of optimal costvector<nop> n_ops; // Vector of neighbour operationsADJ_MAP_TYPE closest_city; // 2 Closest citysADJ_MAP_TYPE adj_city; // Adjacent citys };

---

2.3 SimulatedAnnealing

SimulatedAnnealing是基于LocalSearch實現(xiàn)的模擬退火算法。

與局部搜索不同的是：

算法的結(jié)束由溫度控制

對于比當前解差的解也有機會選用，選用概率與兩個解差值以及溫度有關(guān)，溫度越低，接受概率越低

在高溫狀態(tài)下將會劇烈震蕩，只有溫度降低后才呈現(xiàn)收斂趨勢并逐漸收斂。

2.3.1 流程圖

2.3.2 代碼分析

這里給出頭部文件的實例，詳細實現(xiàn)可參見src/LocalSearch.cpp。

/***************************************************************** FileName : SimulatedAnnealing.h ** Author : Karl ** Created Date : June 6, 2020 ** Updated : June 11, 2020 - Add Function ** June 11, 2020 - Fix Bug ** June 12, 2020 - Modify Perfomance** June 22, 2020 - Last Check **==============================================================** @Functions: ** SimulatedAnnealing::SimulatedAnnealing(MAP_TYPE& origin, ** double LOOSE_COEF, double TEMP_INIT, ** double TEMP_END, int LOOPS_PER_TEMP, ** double ANNEALING_COEF, int VERBOSE) ** - Consructor. ** SimulatedAnnealing::runSA() - start Simulated Annealing. ** SimulatedAnnealing::run() - override run() in LocalSearch. ** SimulatedAnnealing::report() - save result to files. ** ** SimulatedAnnealing::Metropolis(int pos, vector<int>& p) ** - criterion for acceptance of worse solution. **==============================================================*/class SimulatedAnnealing: public LocalSearch { public:... private:double TEMP_INIT; // Initial temperaturedouble TEMP_END; // Terminal temperatureint LOOPS_PER_TEMP; // Loop times per temperature dodouble ANNEALING_COEF; // Coefficient to control annealing speed };

模擬退火的溫度控制機制由以下屬性控制：

初始溫度：TEMP_INIT

終止溫度：TEMP_END

退火系數(shù)：ANNEALING_COEF

每次循環(huán)結(jié)束后，新溫度 = 當前溫度 * 退火系數(shù)，實現(xiàn)降溫。

---

2.4 GeneticAlgorithm

2.4.1 流程圖

2.4.2 交叉與變異算子

遺傳算法是模擬生物種群繁衍的一種搜索策略，其中最關(guān)鍵的即為基因的交叉與變異操作。

交叉算子

基因的交叉即，兩個個體基因的片段進行交換，在TSP問題中，基因即是一種可能的路徑排列，基因交叉的過程，即將兩條路徑的一部分進行交換。

按以下流程進行交叉：

遍歷整個群體，每個個體隨機選擇一個其他個體進行交叉（不與相鄰的個體進行交叉以避免近親交配）

每個個體按輪盤賭策略，隨機產(chǎn)生一個概率，只有該概率超過預(yù)定的交叉概率時才允許交叉

交叉后處理沖突

更新新個體的路徑代價

沖突處理：

由于一條路徑中，城市是唯一的，所以基因的交叉可能導(dǎo)致非法路徑的出現(xiàn)：

Path1 - 1 2 3 4 5 6 7 8 9

Path2 - 1 2 9 6 3 4 7 8 5

在位置2到4進行交叉：

Path1 - 1 2 9 6 5 6 7 8 9 - 城市9，6沖突

Path2 - 1 2 3 4 3 4 7 8 5 - 城市3，4沖突

分別遍歷交叉后的兩條路徑，每條路徑在訪問到重復(fù)城市時，暫停等候另一條路徑也訪問到重復(fù)城市（原路徑內(nèi)城市編號唯一，因此當一條路徑出現(xiàn)重復(fù)時，另一路徑一定也會出現(xiàn)重復(fù)）；兩條路徑都暫停后，交換這兩個城市即可。

Function crossOver:elite_size:= POPULATION_SIZE * 0.2;i:= elite_size;while i < POPULATION_SIZE - 2get random `prob` by roulette()if prob <= CROSSOVER_PROB:j:= get another unit j randomlycross_point: = choose cross_point randomlycross(population[i], population[j], cross_point);end ifsolveCrossOverConflict(population[i], population[j]);update cost of i and jend while endFunction cross(UNIT i1, UNIT i2, pos):copy i2[pos:] to i1[pos:]copy i1[pos:] to i2[pos:] endFunction solveCrossOverConflict(UNIT i1, UNIT i2):i:= 0, j:= 0, N:= Numbers of City;while i < N and j < N: if i1[i] is visited and i2[j] is visited:swap i1[i] and i2[j]i++, j++;end ifif i < N and i1[i] is not visited:note i1[i] as visited, i++;end ifif j < N and i2[j] is not visited:note i2[j] as visited, j++;end ifend while end

---

變異算子

基因的變異即，路徑內(nèi)部發(fā)生非正常的變化，本實驗中采用局部搜索中鄰域操作作為變異的操作。

為提高收斂速度，只有優(yōu)秀的變異會被采納。

按以下流程進行變異：

遍歷整個群體

每個個體按輪盤賭策略，隨機產(chǎn)生一個概率，只有該概率超過預(yù)定的變異概率時才允許變異

全部個體完成變異后，只有使個體變優(yōu)秀的變異被采用

Function mutation(last_population):elite_size:= POPULATION_SIZE * 0.2;for i from elite_size to POPULATION_SIZE-1:get random `prob` by roulette();if prob <= MUTATION_PROB:mutate(population[i]);end ifend forfor i from elite_size to POPULATION_SIZE-1:if newcost[i] is not better than oldcost[i]:Unit i is recoverd by old unit;end ifend for endFunction mutate(UNIT ind):get random `prob` by roulette();buildCity2Path(city2path, ind.second);get random `pos` by roulette();if prob < 0.25:neighbour operation 0 at `pos`;else if prob < 0.5:neighbour operation 1 at `pos`;else if prob < 1:neighbour operation 2 at `pos`;end ifupdate cost of unit ind; end

---

2.4.3 評分機制及精英保留策略

評分是基于TSP問題的最優(yōu)解以及當前路徑長度設(shè)定的：
$$Score(Unit)=\frac{1}{cur\_len?optimal\_len}$$
精英保留策略：

在每一代中，將表現(xiàn)最好（路徑代價最小、評分最高）的個體優(yōu)先保留20%，在后續(xù)隨機選取個體時就不再進行選擇。這些精英個體不會主動進行交叉、變異操作，但可以接受其他個體的交叉請求。

2.4.4 代碼分析

/***************************************************************** FileName : GeneticAlgorithm.h ** Author : Karl ** Created Date : June 12, 2020 ** Updated : June 13, 2020 - Modify Perfomance** June 23, 2020 - Last Check **==============================================================** @Functions: ** GeneticAlgorithm::GeneticAlgorithm(MAP_TYPE& origin, ** int LOOP_LIMITS, int POPULATION_SIZE, ** int GENERATIONS, int MUTATION_TIMES = 3, ** double CROSSOVER_PROB = 0.7, ** double MUTATION_PROB = 0.2, ** double OPT_COST = 0.0, int VERBOSE = 0) ** - Consructor. ** GeneticAlgorithm::runGA() - start Genetic Algorithm. ** GeneticAlgorithm::run() - override run() in LocalSearch. ** GeneticAlgorithm::init() - Initialization. ** GeneticAlgorithm::keepBest() - Keep the elite, the elite ** never crossover or mutate. ** GeneticAlgorithm::selectUnit() - select from population. ** GeneticAlgorithm::crossOver() - crossoveer genetically. ** GeneticAlgorithm::cross(UNIT& i1, UNIT& i2, int pos) ** - crossover between i1 and i2. ** GeneticAlgorithm::solveCrossOverConflict() ** - solve conflicts(same city in 1 path)** GeneticAlgorithm::mutation(vector<UNIT> last_population) ** - mutate genetically. ** GeneticAlgorithm::mutate(UNIT& ind) - unit ind mutates. ** GeneticAlgorithm::score(vector<int>& p) ** - calculate score of path `p`. ** GeneticAlgorithm::evaluate() - evaluate current population.** GeneticAlgorithm::checkPath() - check path's validity. ** GeneticAlgorithm::getElite() - return elite solution. ** GeneticAlgorithm::report() - save result to files. **==============================================================*/class GeneticAlgorithm: public LocalSearch { public:... private:int POPULATION_SIZE; // The size of the populationint GENERATIONS; // Iterations the population will doint MUTATION_TIMES; // Times to try to mutate per loopint GA_VERBOSE; // GA Verbose Messagedouble CROSSOVER_PROB; // The probability to crossoverdouble MUTATION_PROB; // The probability to mutatedouble OPT_COST; // The optimal cost of the tspUNIT ELITE; // The best unit in the populationvector<UNIT> elite_hist; // History of elitesvector<UNIT> population; // Population of unitsvector<double> scores; // Scores to evaluate unitvector<double> chance_by_score; // Accumulation of scores };

---

3 結(jié)果分析

3.1 實驗環(huán)境

3.1.1 系統(tǒng)信息

OSUbuntu 18.04.4 LTS

CPU	Intel? Core? i7-7700HQ CPU @ 2.80GHz

3.1.2 開發(fā)工具

• Vscode + make
• gcc/g++ 7
• python 3.7

---

3.2 編譯運行

3.2.1 初始狀態(tài)

$ tree ./LocalSearch . ├── bin ├── src │ ├── LocalSearch.cpp │ ├── LocalSearch.h │ ├── localsearch_main.cpp │ ├── Makefile │ ├── TSPbase.cpp │ └── TSPbase.h └── testcases└── ...9 directories, 21 files--- $ tree ./SimulatedAnnealing . ├── bin ├── src │ ├── LocalSearch.cpp │ ├── LocalSearch.h │ ├── Makefile │ ├── SimulatedAnnealing.cpp │ ├── SimulatedAnnealing.h │ ├── simulatedannealing_main.cpp │ ├── TSPbase.cpp │ └── TSPbase.h └── testcases└── ...7 directories, 26 files--- $ tree ./GeneticAlgorithm . ├── bin ├── src │ ├── GeneticAlgorithm.cpp │ ├── GeneticAlgorithm.h │ ├── geneticalgorithm_main.cpp │ ├── LocalSearch.cpp │ ├── LocalSearch.h │ ├── Makefile │ ├── TSPbase.cpp │ └── TSPbase.h └── testcases└── ...5 directories, 32 files

3.2.2 編譯

在三種算法各自文件夾內(nèi)：

$ cd src/ && make

示例：LocalSearch的Makefile

CXX = g++-7 CXXFLAGS = -Wall -Werror -Wextra -pedantic -std=c++17 -g -fsanitize=address LDFLAGS = -fsanitize=addressSRC = localsearch_main.cpp TSPbase.cpp LocalSearch.cpp OBJ = $(SRC:.cpp=.o) EXEC = ../bin/local_searchall: $(EXEC)$(EXEC): $(OBJ)$(CXX) $(LDFLAGS) -o $@ $(OBJ) $(LBLIBS)clean:rm -rf $(OBJ) $(EXEC) g++-7 -Wall -Werror -Wextra -pedantic -std=c++17 -g -fsanitize=address -c -o localsearch_main.o localsearch_main.cpp g++-7 -Wall -Werror -Wextra -pedantic -std=c++17 -g -fsanitize=address -c -o TSPbase.o TSPbase.cpp g++-7 -Wall -Werror -Wextra -pedantic -std=c++17 -g -fsanitize=address -c -o LocalSearch.o LocalSearch.cpp g++-7 -fsanitize=address -o ../bin/local_search localsearch_main.o TSPbase.o LocalSearch.o

3.2.3 運行及自定參數(shù)

切換到bin/文件夾

$ ./local_search Invalid Usage. >> ./local_search [TSP_FILE_NAME] e.g.: >> ./local_search a280

按照使用格式調(diào)用，此處以a280問題為例

需要進行搜索的問題需要提前將文件[tsp_name].tsp以及[tsp_name].opt.tour復(fù)制到testcases/中。

$ ./local_search a280

<img src="https://img-blog.csdnimg.cn/2020062509291792.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAwNTMyOQ==,size_16,color_FFFFFF,t_70" alt="在這里插入圖片描述" style="zoom:50%;" /> <img src="https://img-blog.csdnimg.cn/20200625092916899.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDAwNTMyOQ==,size_16,color_FFFFFF,t_70" alt="在這里插入圖片描述" style="zoom: 67%;" />在程序運行后，接受參數(shù)或回車使用參數(shù)缺省值，再次回車確認將開始搜索。相關(guān)參數(shù)已在命令行中說明。```bash $ ./simulated_annealing a280 $ ./genetic_algorithm a280

3.3.4 結(jié)果可視化

每次運行完程序，結(jié)果將保存在 testcases/result.[method].tour（搜索得到的最佳路徑）以及testcases/result.[method].hist（搜索記錄）中。

本實驗采用Python + matplotlib進行數(shù)據(jù)可視化：

$ cd testcases/ $ python Benchmarker.py [Method(ls/sa/ga)] [TSP_FILE_NAME] # e.g. python Benchmarker.py ls a280

Python腳本會創(chuàng)建文件夾：[TSP_FILE_NAME].[method].benchmarker.out/，其中包括歷史記錄圖示、路線變化GIF，以及最優(yōu)解對比圖等。

---

3.3 搜索結(jié)果及比較

3.3.1 實驗數(shù)據(jù)對比

Local Search

TSP1st2nd3rd4rd5rdAVE

kroC100	22523.3	22667.5	24123.4	22938.9	21711.3	22792.88 (Loss 9.85%)
ch150	6929.42	7696.9	7076.38	6996.5	7604.08	7260.656 (Loss 11.22%)
tsp225	4276.71	4404.6	4344.26	4229.38	4287.84	4308.558 (Loss 9.94%)
a280	2951.92	2888.39	2902.9	2918.46	2872.16	2906.766 (Loss 12.7%)
pcb442	58725.1	57542.1	57856.8	56568.1	57094.8	57557.38(Loss 13.35%)

Simulated Annealing

TSP1st2nd3rd4rd5rdAVE

kroC100	20871.4	20871.4	20750.8	20993.5	20769.9	20851.4 (Loss 0.49%)
ch150	6553.66	6563.02	6563.02	6559.6	6565.38	6560.936 (Loss 0.50%)
tsp225	3973.63	3948.07	3964.74	3972.09	3973.63	3968.232 (Loss 1.26%)
a280	2590.18	2634.79	2590.18	2597.54	2651.87	2612.91 (Loss 1.31%)
pcb442	51468.7	52130.3	51981.3	52061.9	51747.6	51877.96 (Loss 2.17%)

Genetic Algorithm

TSP1st2nd3rd4rd5rdAVE

kroC100	21817.3	22212.8	22108.4	21560.9	21817.3	21903.34(Loss 5.56%)
ch150	7162.96	7205.97	7033.58	7109.15	7109.15	7124.162 (Loss 9.13%)
tsp225	4222.78	4205.8	4258.63	4256.1	4241.42	4236.946 (Loss 8.11%)
a280	3005.36	2907.37	2865.11	2931.69	2900.76	2922.06 (Loss 13.3%)
pcb442	58931	56844.7	57073.4	58810	56588.3	57649.48 (Loss 13.5%)

summary

TSP NameLocalSearchSimulated AnnealingGenetic Algorithm

kroC100	22792.88 (Loss 9.85%)	20851.4 (Loss 0.49%)	21903.34(Loss 5.56%)
ch150	7260.656 (Loss 11.22%)	6560.936 (Loss 0.50%)	7124.162 (Loss 9.13%)
tsp225	4308.558 (Loss 9.94%)	3968.232 (Loss 1.26%)	4236.946 (Loss 8.11%)
a280	2906.766 (Loss 12.7%)	2612.91 (Loss 1.31%)	2922.06 (Loss 13.3%)
pcb442	57557.38(Loss 13.35%)	51877.96 (Loss 2.17%)	57649.48 (Loss 13.5%)

3.3.2 實驗數(shù)據(jù)可視化

3.3.3 路線對比

Local Search

Simulated Annealing

Genetic Algorithm

---

3.4 性能分析

TSP NameLocalSearchSimulated AnnealingGenetic Algorithm

kroC100	22792.88 (Loss 9.85%)	20851.4 (Loss 0.49%)	21903.34(Loss 5.56%)
ch150	7260.656 (Loss 11.22%)	6560.936 (Loss 0.50%)	7124.162 (Loss 9.13%)
tsp225	4308.558 (Loss 9.94%)	3968.232 (Loss 1.26%)	4236.946 (Loss 8.11%)
a280	2906.766 (Loss 12.7%)	2612.91 (Loss 1.31%)	2922.06 (Loss 13.3%)
pcb442	57557.38(Loss 13.35%)	51877.96 (Loss 2.17%)	57649.48 (Loss 13.5%)
Time	around 10s	150 ~ 300s	300s

[回顧實驗數(shù)據(jù)](####3.3 搜索結(jié)果及比較)

算法精度

再次參考實驗結(jié)果表，可以看到，模擬退火算法的效果最為突出，誤差都在**3%**以內(nèi)，另外兩個算法表現(xiàn)一般，誤差子10%上下波動。

算法效率

同時，除去精度，三個算法的速度也各有區(qū)別，模擬退火以及遺傳算法的耗時較高，局部搜索耗時較低；

這是由于算法性質(zhì)導(dǎo)致的，存在優(yōu)化空間。

路徑的變化與交叉

首先，隨機初始化的路徑往往是充滿大量交叉路徑，使得路徑代價大大提高，各種領(lǐng)域操作搜索的原理實質(zhì)上是在盡量消除路徑代價。

為了充分觀察在搜索過程中路徑的變化，我將實驗過程中的路徑變化取樣并且壓在GIF圖中，并建立了網(wǎng)頁示例，可訪問DEMO中查看(GIF文件較大，需要時間加載)。

3.5 探索與展望

嘗試更多鄰域操作。

嘗試不同的參數(shù)而不是設(shè)定的默認參數(shù)（默認參數(shù)已經(jīng)過調(diào)試、修訂)。

嘗試將搜索并行化，遺傳算法顯然是可并行的。

探究遺傳算法效果不佳的原因（概率的設(shè)定？種群的大小？迭代次數(shù)？交叉變異操作？精英策略以外的策略？如何避免陷入局部最優(yōu)？）

提高模擬退火算法的效率（如何選擇一個更合適的退火系數(shù)？）

對于默認初始溫度50000度，默認終止溫度1e-5，以0.99的退火系數(shù)需要約2200次降溫，如何設(shè)定退火系數(shù)值得推敲。

4 結(jié)論

模擬退火算法、遺傳算法，對于計算機專業(yè)的學(xué)生來說并不陌生，只是在實驗前都是紙上談兵。

在本次實驗中，從邏輯設(shè)計開始，完成了三個搜索算法的C/C++實現(xiàn)，雖然細節(jié)手法仍然稚嫩，性能、效率上都沒有做到最優(yōu)，但對了解算法、了解TSP問題幫助極大。

實驗要求中相關(guān)問題

（模擬退火）求得的解不要超過最優(yōu)值的10％，并能夠提供可視化圖形界面，觀察路徑的變化和交叉程度。

求得的解精度在3%以內(nèi)，效果很好。

可視化圖形界面由python實現(xiàn)，路徑的變化和交叉程度在上文已經(jīng)進行了介紹。

（遺傳算法）和之前的模擬退火算法（采用相同的局部搜索操作）進行比較

效果不如模擬退火算法好，可能出現(xiàn)的問題已在上文進行了介紹。

（遺傳算法）得出設(shè)計高效遺傳算法的一些經(jīng)驗，并比較單點搜索和多點搜索的優(yōu)缺點。

在概率的設(shè)定、種群的大小、迭代次數(shù)、交叉變異操作、精英策略以外的策略、避免陷入局部最優(yōu)上需要多下功夫。

單點搜索優(yōu)點：速度快、易收斂、實現(xiàn)簡單。

單點搜索缺點：容易陷入局部最優(yōu)解。

多點搜索優(yōu)點：模擬自然規(guī)律，直觀上更可信，能更好避免局部最優(yōu)解。

多點搜索缺點：速度慢、實現(xiàn)復(fù)雜、魯棒性不足（不同TSP問題應(yīng)該對應(yīng)的自然模型可能不同）。

關(guān)于實驗評分

所有實驗成果必須原創(chuàng)。允許提交半成品、失敗品但絕不允許提交復(fù)制品。

本實驗代碼原創(chuàng)，基本完成功能，仍有改進空間（并行化、算法改進等）。

實驗程序?qū)φ_的輸入有正確的輸出。

程序要求tsp問題文件置于testcases/中，并在調(diào)用程序是使用正確的tsp問題名，如：

$ ls testcases/ a280.tsp a280.opt.tour $ ./local_search a280

提交實驗結(jié)果，完整齊全。

實驗結(jié)果已在前文展示。

源代碼編寫符合編碼規(guī)范，可讀性高。

源代碼符合C/C++ google style，函數(shù)方法在文件頭有說明，且部分函數(shù)是self-explainable的。

源代碼邏輯清晰。

邏輯已在前文說明。

程序具有魯棒性。

對于任意挑出的五個tsp問題，程序都能很好處理，具有足夠的魯棒性。

同時，對于一些可能的錯誤輸入、文件格式問題，都在程序內(nèi)進行了提示性報錯。

界面友好。

未單獨繪制GUI界面，而是以CMD形式提供交互界面；對于輸出的結(jié)果可視化提供了python腳本，無需另外處理實驗結(jié)果。

5 主要參考文獻

趙雪梅. 遺傳算法及其在TSP問題求解中的應(yīng)用[J]. 四川兵工學(xué)報(11):22-27.

王銀年. 遺傳算法的研究與應(yīng)用[D]. 江南大學(xué).

范展, 梁國龍, 林旺生,等. 求解TSP問題的自適應(yīng)鄰域搜索法及其擴展[J]. 計算機工程與應(yīng)用, 2008(12):75-78.

Song, Chi-Hwa, Kyunghee Lee, and Won Don Lee. “Extended simulated annealing for augmented TSP and multi-salesmen TSP.” Proceedings of the International Joint Conference on Neural Networks, 2003.. Vol. 3. IEEE, 2003.

Chi-Hwa Song, Kyunghee Lee and Won Don Lee, “Extended simulated annealing for augmented TSP and multi-salesmen TSP,” Proceedings of the International Joint Conference on Neural Networks, 2003., Portland, OR, 2003, pp. 2340-2343 vol.3, doi: 10.1109/IJCNN.2003.1223777.

---

源代碼傳送門：GITHUB
數(shù)據(jù)傳送門：TSPLIB

---

Karl 2020/6

Back To Top

總結(jié)

以上是生活随笔為你收集整理的局部搜索、模拟退火和遗传算法求解TSP问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。