基于并行優化與訪存優化遺傳算法的TSP問題求解方法

陸 游,何 嘉(成都信息工程大學計算機學院，成都610025)

基于并行優化與訪存優化遺傳算法的TSP問題求解方法

陸 游,何 嘉
(成都信息工程大學計算機學院，成都610025)

TSP(旅行商問題)問題是數圖論領域中著名問題之一，常采用基于種群的智能算法來解決，其中最具代表性的就是遺傳算法.但由于用遺傳算法在解決TSP問題時往往比較耗時，并且隨著TSP問題規模的增大，時間的消耗也大大增加，因此采用了并行優化與訪存優化方法對遺傳算法進行了從代碼層面的優化，從而提高TSP問題的求解效率.最后，通過實驗驗證了該加速方法的可行性.

遺傳算法;TSP問題;并行;訪存

TSP問題(Traveling Salesman Problem)，簡稱旅行商問題)是一個典型的NP難題，隨著智能方法的流行，使其能夠在相對較短時間內求得近似解，雖然這些算法不能得到精確解，但其誤差能夠控制在可以接收的范圍內.大量的科學實驗證明以基于種群的一些智能算法(遺傳算法，蟻群算法等)在求解TSP問題上具有較高的尋優能力，[1]但隨著問題規模和迭代次數的增加，程序的運行時間依然會大大增加，甚至短時間內無法得到結果.因此，為了能更快地得到結果，本文采用了并行優化和訪存優化兩種方法對程序進行了代碼層面的加速，以期望最大限度地縮短程序的運行時間.由于在這類基于種群的算法中，遺傳算法是其最經典，最具有代表性的算法，因此選用標準遺傳算法作為研究對象，提出了基于并行優化與訪存優化的遺傳算法的TSP問題求解方法.

1 遺傳算法

1.1 遺傳算法簡介

遺傳算法(Genetic Algorithm，簡稱GA)是模擬達爾文論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法.它于1975年由美國的Holland教授在他的專著《自然界和人工系統的適應性》中首先提出.[2]遺傳算法，其描述如下：

(1) 初始化.確定種群規模N、最大進化迭代次數T、交叉概率P_CROSS、變異概率P_MUTATION、產生N個隨機數將其編碼后作為算法的初代種群.

(2) 適應度評價.對種群每一個個體好壞的評判標準，一般來說，個體越好，其適應度值越大，越容易被遺傳.

(3) 選擇運算.將選擇算子作用于群體.目的是選擇優秀個體即適應度值較大的個體進行遺傳操作.

(4) 交叉運算.將交叉算子作用于群體.將選出來的個體依照交叉概率PC進行兩兩交叉.

(5) 變異運算.將變異算子作用于群體.對群體中的個體串中的某些位依照變異概率PM進行改變.

(6) 種群經過以上一系列操作后得到下一代群體.

(7) 終止條件判斷.若達到最大迭代次數，則輸出結果；未達到最大迭代次數，返回步驟(2).

1.2 遺傳算法的并行優化

由于遺傳算法的天然并行性，因此本文采用了基于共享內存的OpenMP(Open Multi-Processing) 并行技術對其進行了并行優化.[3]

在遺傳算法中，計算每個個體適應度值、選擇操作、交叉操作、變異操作中內部的數據相互獨立，所以這幾部分非常適合用共享內存的多核CPU做細粒度的并行.如圖1所示，本文將適應度評價、選擇、交叉、變異這四部分操作都分成了n個線程來并行地執行.

1.3 遺傳算法的訪存優化

在過去二十幾年中，雖然處理器速度與存儲器的速度都有大幅的提高，但兩者之間的增長速度仍有不小差距.[4]到目前為止，處理器的速度仍然遠遠高于存儲器的速度，所以在當前的計算機體系結構中往往都會在CPU與內存之間引入高速緩存(Cache)，由圖2可知，CPU首先會從Cache中取數據，如果沒有找到則才再從內存中取數據.由于Cache的存取速度遠高于內存(Cache的存取速度接近于CPU)，因此如果能讓CPU每次訪問數據的時候盡可能的都能在Cache中找到，那么程序的運行效率將會大大提升.

圖1 Cache系統工作原理圖

因此，本文將采用此原理來適當調整訪問數據的順序來盡可能多地讓每一次需要數據能在Cache中被訪問到.經多次實驗發現，本文的遺傳算法所采用的輪盤賭選擇算子在每一次迭代的時候，適應度大的個體更容易被選擇到，但這些適應度大的個體數據又很有可能不在Cache中.因此本文的思路就是在每一次迭代的適應度評價后，將個體按照適應度從大到小排序，又因為Cache訪問內存是按照內存的地址順序訪問，因此在個體排序后，適應度大的個體將會優先存放在Cache中.

圖2 訪存優化遺傳算法原理

如圖3所示，假如按照此思路調整了個體存放順序后，適應度大的個體優先被Cache所緩存，假如就是個體1，2，3，4.當進行輪盤賭選擇算子時候，概率越大的個體則有更大的幾率被CPU選中，也即CPU會有更大的幾率在Cache中找到數據，這樣依次類推，Cache每次都會緩存CPU最有可能訪問到的數據.因此，經過訪存優化后的遺傳算法則會有更高的運行效率.

根據遺傳算法的原理，隨著代數的增加，種群的多樣性會逐漸變小，也即到了遺傳算法后期，每個個體與上次迭代的時候變化不大，而又由于每次迭代時候的排序會消耗一定的時間，因此本文設置了一個K值，當迭代次數小于K就執行排序，大于K時就不執行排序.這樣能使其優化效率最大化.

圖3 優化后的遺傳算法框架圖

2 優化后的遺傳算法求解TSP問題

2.1 TSP問題

TSP問題是數圖論領域中著名問題之一.該問題的經典提法是：假設有一個旅行商人要拜訪n個城市，從城市1出發，經其余各城市至少一次，然后回到城市1，求其最小的路徑成本.[5]

TSP問題屬于組合優化問題，而遺傳算法是一種求解問題的高效全局搜索方法，能夠解決復雜的全局優化問題，所以非常適合用來解決TSP問題.[6]該問題已經被證明具有NP計算復雜性，所以很難得到精確解，而遺傳算法就是解決這類問題比較有效的近似算法.[7]圖4顯示了以兩條路徑A=(1 2 3 4 5 6 7 8)，B=(2 4 6 8 7 5 3 1)為例的標準遺傳算法操作式例.[3]

圖4 標準遺傳算法解決TSP問題操作示例

根據大量實驗結果表明，采用遺傳算法解決的TSP問題隨著城市規模的增大，其程序運行時間大量增加，因此本文就采用優化后的遺傳算法來縮短其運行的時間.

2.2 算法描述

2.2.1 編碼

在遺傳算法求解TSP問題中，目前的編碼方式主要有：近鄰表示(adjacency representation)、[8]次序表示(ordinal representation)、[9]路徑表示(path representation)、[10]布爾矩陣表示.本文采用的是路徑表示方式，這是針對TSP問題最自然、最直觀的表示方式.

例如：有一條路徑為2-3-1-9-4-6-7-8-5可將其表示成(2 3 1 9 4 6 7 8 5).

2.2.2 適應度評價

由于TSP問題解的要求是路徑長度越短越好，因此本文的適應度函數取路徑長度的倒數：

由于種群內的每個個體計算適應度值是相互獨立的，所以本文用OpenMP將這部分并行化，其偽代碼如表1所示：

表1 適應度值部分并行偽代碼

其中SIZE表示種群大小，CITY_NUM表示城市規模，在OpenMP中用parallel for進行編譯指導來優化for循環.為了便于統一和對比，本文采用的都是靜態調度的策略(在代碼中由schedule(static)體現)，即假如任務量為N，有t個線程，則每個線程分配的任務量為N/t.

2.2.3 排序

在計算完適應度值之后，為了進行如圖4中的訪存優化，對個體按照其適應度值的大小進行了升序排序，其偽代碼如表2所示：

在表2中，T_NOW表示當前迭代次數，K值為多次反復實驗得出的值.

表2 訪存優化部分偽代碼

2.2.3 選擇

本文選用遺傳算法中最常用的輪盤賭選擇，即各個個體的選擇概率與其適應度值成比例，適應度值越大的個體被選擇的幾率也就越大.同樣選擇操作部分可以并行地選擇，因此再用OpenMP將其并行化，偽代碼如表2所示：

表3 選擇部分并行偽代碼

在上述偽代碼中，用OpenMP并行化后，編譯器默認的是將循環體里的i這個循環變量共享化，即可以讓多個線程同時訪問i這一變量，若這樣將會造成進程間數據的相互影響，從而導致結果的錯誤.因此，需要語句里加上private這一修飾，將i變為私有變量，即每個線程都有i這一變量的副本，保證每個進程間的數據互不影響.

2.2.4 交叉

針對TSP問題的遺傳算法的交叉算子最常用的是基于路徑表示的部分匹配交叉(PMX)、順序交叉(OX)、循環交叉(CX)、邊重組交叉、貪心交叉(GSX)等.[6-8]本文選擇的是循環交叉的方法.其一般性描述為：

(1) 設有兩個父代：

A=(a1,a2,a3,a4 … an)

B=(b1,b2,b3,b4 … bn)

(2)從父代A的左起第一個元素開始作為第一個城市a1，加入到子代A1中：

A1=(a1 … )

(3) 查看父代B中選定的元素a1對應元素，為b1，假如b1=a2，所以得到：

A1=(a1,a2 … )

(4) 查看父代B中選定的元素a2對應元素，為b2，假如b2=a4，，所以得到：

A1=(a1,a2 … ,a4 … )

以此類推，直到檢查父代B中所選元素對應的元素已經存在于A中，則循環結束.再將剩余的元素從父代B中填入，得到最終的子代A1.

同樣，在這部分兩兩個體進行交叉相互之間互不影響，故本文再將其用OpenMP進行并行化，偽代碼如表3所示：

在表4的偽代碼中，P_CORSS表示預先設定的交叉概率，同樣在用OpenMP并行化的時候采用的靜態調度.

表4 交叉部分并行偽代碼

2.2.5 變異

基于TSP的變異算子主要有：點位變異、逆轉變異、對換變異、插入變異、貪心對換變異、倒位變異[3,9,10].我們采用的是對換變異，即隨機選擇串的兩點，交換其值.同樣，兩兩個體變異之間互不影響，于是將這一部分再用OpenMP將其并行化，偽代碼如表4所示.在表4的偽代碼中P_MUTATION表示預先設定的變異概率.

表5 變異部分并行偽代碼

3 實驗結果與分析

3.1 實驗環境

我們所采用的實驗環境為：四核Intel(R) Core(TM) i5-4590s CPU 3.00GHz、8GB內存、Windows7操作系統、Visual Studio 2010編譯器.為了達到實驗效果，本文分別選用了三個數據集來測試，分別是st70、lin318、pr1002，分別代表小規模的TSP問題，中等規模的TSP問題和大規模的TSP問題.為了便于對比，本文的算法參數統一設置如表5所示：

表6 算法參數設置

3.2 并行優化運行時間對比與分析

為方便比較，本文先單獨做了并行優化.在實驗中我們每隔200代記錄了一次當前的運行時間，并分別畫出了其變化曲線，如圖4、圖5、圖6所示，其數據為測試20次的平均值.

圖5 st70串并行時間對比

從圖5、圖6、圖7中可以看出，當迭代次數一定的時候，采用OpenMP并行化后的時間消耗明顯少于串行，并且4線程的時間也明顯優于2線程.表6為具體的統計數據.

圖6 lin318串并行時間對比

圖7 pr1002串并行時間對比

表7為只采用并行優化運行時間統計表，從中可以看出，采用OpenMP后都有明顯的加速效果，但不管是2線程還是4線程其加速比都達不到理想的2或者是4，這是因為在OpenMP中線程的開啟和關閉會帶來一定的時間開銷，又因為4線程中的線程開銷比2線程的更大，所以在上表中4線程的加速比沒有2線程的加速比理想.同時，隨著問題規模的增大，4線的加速比又逐漸變好，這是因為線程的開銷所占用的時間比例會隨著問題規模的增大而逐漸減小，從而在較大規模的問題上會有比較好的加速比.

表7 并行優化運行時間統計表

3.3 訪存優化運行時間對比與分析

在并行優化的基礎上，利用如圖4的優化框架對遺傳算法進行二次優化.經多次實驗得出，在本實驗中K值大約為12000的時候，效率能達到最好.

表8為最終的經過兩次優化時間對比，在并行優化的基礎上的訪存優化后時間最多可以提高25.7%.而與最原始的串行時間對比，時間有了大幅的提高，例如在pr1002這個數據集上最終優化后的時間甚至能達到原始串行的1/5.

表8 二次優化時間對比

3.4 二次優化最優值對比與分析

為了達到對比效果，實驗參數的設置同樣為表6所示，同時依然也是每隔200代記錄了一次當前中最優序列的路徑長度并分別畫出了其變化曲線，如圖8、圖9、圖10所示，其數據為測試20次的平均值.

圖8 st70二次優化前后最優值變化曲線對比

圖9 lin318 二次優化前后最優值變化曲線對比

從圖8、圖9、圖10可以看到，每種問題的三條曲線都是幾乎重疊，說明本文的優化加速方法后并不影響其精度.同時，隨著問題規模的增大，曲線的下降幅度也逐漸減少，說明對于標準遺傳算法本身找到最優值的難度也越來越大，表9為其具體的數據統計.

圖10 pr1002二次優化前后最優值變化曲線對比

問題理想最優值串行最優值2線程二次優化最優值4線程二次優化最優值st706751002.5671001.1211002.453lin31842029173102.468172142.334172964.330pr10022590452582651.1462576532.1212582348.436

從表9可以看到，由于采用的標準遺傳算法固有的缺點，實際得出來的結果與理想值有一定差距，特別是在318個城市和1002個城市即TSP問題規模較大時，差距尤為明顯.

4 結束語

通過標準遺傳算法的加速優化框架來解決TSP問題，最后通過實驗證明該方法使得程序運行時間得到了大大減少，并且在優化前后，其得到的解都與原始串程序行相差無幾，說明本文的優化方法是有效的.但由于標準遺傳算法固有的一些缺陷，雖然時間上得到了很大程度的減少，但在得到的最優值上與理想值差距較大，但本文的框架適合應用于任何基于種群的優化算法.因此以后的研究方向將會是在算法層面上的改進或者選用更加理想的算法(比如蟻群算法)，再加上本文加速優化的方法使程序在時間上和最優值上都能達到更好的效果.

[1] 馬永杰,云文霞.遺傳算法研究進展[J].計算機應用研究,2012(4):11-15.

[2] HOLLAND JH.Adaptationinnaturalandartificialsystems:anintroductoryanalysiswithapplicationstobiology,control,andartificialintelligence[M] ．Cambridge: MIT Press,1992：23-25．

[3] 龔向堅,皺臘梅,胡義香.基于OpenMP的多核系統并行程序設計方法研究[J].南華大學學報:自然科學版,2013(1):64-69.

[4] J.Hennessy,D.Patterson.ComputerArchitecture:AQuantitativeApproach,2ndEdition[M].San Mateo,Calif:Morgan Kaufmann,1995:11-13.

[5]王 娜.求解TSP的改進遺傳算法[D].西安:西安電子科技大學,2010:2-4.

[6] J.Grefenstete,et al.GeneticAlgorithmsfortheTravelingSalesmanProblem[C]//Int.Conf. On Genetic Algorithms and Applicantions,1985：154-168.

[7] Simianx M, Pataki L M.GeneticAlgorithms：ASurvey[J].Computer,1994：27.

[8] L . Davis.ApplyingAdaptiveAlgorithmstoEpistaticDomains[C]//Int. Joint Conf. on Artificial Intelligence.1985:162-164.

[9] Homaifar,S.Guan, and G.Liepins.ANewApproachontheTravelingSalesmanProblembyGeneticAlgorithms[C]//Int. Conf.On Gentic Algorithms,1993:460-466.

[10]Oliver L M,smith D J,Holland J R C.AstudyofPermutationCrossoverOperatorsontheTravelingSalsmanProblem[C]//In:Proceedings of the Second International Conference on Genetic Algorithms,1987:224-230.

[責任編輯 范 藻]

TSP Problems Solving Based on the Optimization and Memory Access Optimization Genetic Algorithm

LU You, HE Jia

(Chengdu University of Information Technology, Chengdu Sichuan 610025, China)

TSP (Traveling Salesman Problem) is one of several well-known problems in the field of graph theory, we solve this problem by using the standard genetic algorithm. However, due to the TSP problem solving using genetic algorithms is often more time-consuming, and with the increasing size of the TSP, time consumption also increased significantly. Therefore, this article uses the parallel optimization and optimization fetch two acceleration methods for genetic algorithm optimization from the code level to achieve the purpose of reducing the running time of the program, thereby increasing the efficiency of solving the TSP problem.Finally, the experimental method to verify the feasibility of accelerating from curves and tables herein terms of time.

Genetic Algorithm; TSP; parallel

2016-12-25

陸 游(1992—)，男，重慶梁平人.碩士研究生，主要從事計算機智能研究.

TP18

A

1674-5248(2017)02-0011-07