一種基于Geatpy庫求解TSP問題的方法

張亦寧

（河南大學(xué)國(guó)際教育學(xué)院 河南省開封市 475001）

遺傳算法（GA）是由美國(guó)密歇根大學(xué) Holland 教授提出的一種進(jìn)化算法，屬于智能算法中的一種，它的基本原理是根據(jù)生物進(jìn)化法則“物競(jìng)天擇、適者生存”，遺傳算法使用染色體代表問題的參數(shù)編碼，在每一代的進(jìn)化過程中進(jìn)行選擇、交叉以及變異等運(yùn)算來改良種群中染色體，最終生成最優(yōu)解或次優(yōu)解的染色體[1]。

對(duì)于遺傳算法求解TSP 問題，研究者們進(jìn)行了大量的嘗試工作。文獻(xiàn)[2]使用貪心算法對(duì)種群進(jìn)行初始化，在選擇操作中融入了最優(yōu)保存策略和摻雜算子的方法，以保證多樣性的群體。針對(duì)基本遺傳算法在解決TSP 問題時(shí)所存在的收斂速度慢、容易“早熟”的問題，文獻(xiàn)[3]把選擇因子融入了選擇算子中，同時(shí)提出一種改進(jìn)的交叉算子和基于種群相似度的更新策略，獲得了較好的效果。

上述遺傳算法或者改進(jìn)遺傳算法對(duì)于求解TSP 問題的效果雖然不錯(cuò)，但是都需要自己進(jìn)行算法設(shè)計(jì)和編碼，通用性不是太強(qiáng)。本文提出一種基于遺傳算法庫Geatpy 來求解TSP 問題，通過編寫簡(jiǎn)單的代碼即可完成遺傳算法的求解，具有很強(qiáng)的通用性。

1 TSP問題的數(shù)學(xué)描述

已知條件：知道n 個(gè)城市的坐標(biāo)，有一旅行商要從其中一個(gè)城市出發(fā)依次訪問每個(gè)城市有且只有一次，最后再返回到出發(fā)城市。問題是：求這個(gè)旅行商怎么走才能走最短的距離。

數(shù)學(xué)模型描述：假設(shè)n 個(gè)城市的坐標(biāo)分別是(xi,yi)，其中，則兩個(gè)城市間的距離使用歐氏距離表示為：那么目標(biāo)函數(shù)可以表示為需要求解的變量為w，w 是使得目標(biāo)函數(shù)達(dá)到最小值的一個(gè)排列且w 的最后一項(xiàng)滿足回到出發(fā)城市，即i0=in。

2 基于Geatpy庫的遺傳算法求解TSP問題

2.1 Geatpy庫介紹

Geatpy 是一個(gè)高性能實(shí)用型的Python 遺傳算法工具箱，提供一個(gè)面向?qū)ο蟮倪M(jìn)化算法框架，提供了許多已實(shí)現(xiàn)的遺傳和進(jìn)化算法相關(guān)算子的庫函數(shù)，如初始化種群、選擇、交叉、變異、重插入、多目標(biāo)優(yōu)化非支配排序等，并且提供諸多已實(shí)現(xiàn)的進(jìn)化算法模板來實(shí)現(xiàn)多樣化的進(jìn)化算法。其執(zhí)行效率高于Matlab、Java 和Python編寫的一些知名工具箱、平臺(tái)或框架等，學(xué)習(xí)成本低、模塊高度脫耦、擴(kuò)展性高。Geatpy 支持二進(jìn)制/格雷碼編碼種群、實(shí)數(shù)值種群、整數(shù)值種群、排列編碼種群。支持輪盤賭選擇、隨機(jī)抽樣選擇、錦標(biāo)賽選擇。提供單點(diǎn)交叉、兩點(diǎn)交叉、洗牌交叉、部分匹配交叉(PMX)、順序交叉(OX)、線性重組、離散重組、中間重組等重組算子。提供簡(jiǎn)單離散變異、實(shí)數(shù)值變異、整數(shù)值變異、互換變異等變異算子。支持隨機(jī)重插入、精英重插入。支持awGA、rwGA、nsga2、快速非支配排序等多目標(biāo)優(yōu)化的庫函數(shù)、提供進(jìn)化算法框架下的常用進(jìn)化算法模板等。

2.2 基于Geatpy庫遺傳算法求解TSP問題的核心代碼編寫

基于Geatpy 庫使用遺傳算法求解TSP 問題的主要思路是：

（1）實(shí)現(xiàn)MyProblem 類，在該類中完成TSP 問題的定義和求解過程；

（2）在main 文件中寫主程序進(jìn)行參數(shù)設(shè)置和求解方法的調(diào)用，輸出求解結(jié)果。下邊使用偽代碼描述這兩個(gè)文件的實(shí)現(xiàn)。

下邊對(duì)MyProblem.py 文件中的編寫的MyProblem 類的核心代碼主要包括的三個(gè)函數(shù)和main 文件中的主程序的功能進(jìn)行描述。

2.2.1 構(gòu)造函數(shù) __init__(self)的描述

構(gòu)造函數(shù)的主要功能是對(duì)遺傳算法的參數(shù)進(jìn)行初始化，初始化的主要內(nèi)容描述如下：

（1）初始化name。name 是函數(shù)名稱，可以隨意設(shè)置，此處設(shè)置為GAForTSP；

（2）初始化M。M 是目標(biāo)維數(shù)，此處設(shè)置為1；

（3）初始化maxormins。maxormins 目標(biāo)最小最大化標(biāo)記列表，1 表示最小化該目標(biāo)；-1 表示最大化該目標(biāo)，本文解決問題求解的是最小值，故設(shè)置為1；

（4）初始化Dim。Dim 是決策變量維數(shù)，此處求解的是51 個(gè)城市的TSP 問題，旅游者只需從其中一個(gè)城市出發(fā)再經(jīng)過50 個(gè)城市就可以走遍所有的城市有且僅有一次，所以決策變量的維數(shù)設(shè)置為50；

（5）初始化varTypes。varTypes 是決策變量的類型，元素為0表示對(duì)應(yīng)的變量是連續(xù)的，1 表示是離散的，本文中的城市編號(hào)屬于離散型的，故設(shè)置為1；

（6）決策變量上界和下界。由于決策變量的位數(shù)為50，所以下界是1，上界是50；

（7）決策變量下邊界。決策變量下邊界決定了決策變量是否包含下邊界在內(nèi)，0 表示不包含該變量的下邊界，1 表示包含該變量的下邊界，此處應(yīng)該包含，股設(shè)置為1；

（8）決策變量上邊界。決策變量上邊界決定了決策變量是否包含上邊界在內(nèi)，0 表示不包含該變量的上邊界，1 表示包含該變量的上邊界，此處應(yīng)該包含，股設(shè)置為1；

（9）調(diào)用父類構(gòu)造方法完成實(shí)例化。通過調(diào)用父類構(gòu)造函數(shù)來完成父類需要初始化的對(duì)象和屬性；

（10）新增一個(gè)屬性（self.places）存儲(chǔ)旅行地坐標(biāo)，從文件eil51.tsp 中獲取各個(gè)城市的坐標(biāo)，從而為求解TSP 問題提供數(shù)據(jù)來源；

（11）把一行多列轉(zhuǎn)換成多行一列，以滿足self.places 的數(shù)據(jù)類型的需求。

2.2.2 目標(biāo)函數(shù)aimFunc(self,pop)的功能描述

（1）得到?jīng)Q策變量矩陣x。從aimFunc 的形參pop 中獲取，即x=pop.Phen；

（2）調(diào)整決策變量矩陣x 的形式X，方便求最短距離，即X=np.Hstack ([np.zeros((x.shape[0],1)),x,np.zeros((x.shape[0],1))]).astype(int)；

（3）計(jì)算X 中每一條染色體對(duì)應(yīng)的路徑長(zhǎng)度并存入ObjV 列表中，方便后續(xù)統(tǒng)計(jì)最優(yōu)解，此值由aimFunc 函數(shù)的參數(shù)pop 帶回，即pop.ObjV=np.array([ObjV]).T；

2.2.3 getDataFromFile(self,filename)從文件中獲取原始數(shù)據(jù)的功能描述

（1）打開txt 文件，以‘utf-8’編碼讀取文件中的數(shù)據(jù)；

（2）跳過前6 行數(shù)據(jù)，引文TSPLIB 庫提供的數(shù)據(jù)前6 行不是城市坐標(biāo)信息，因此跳過從第7 行開始讀?。?/p>

（3）遍歷每一行有效數(shù)據(jù)，使用split函數(shù)把縱橫坐標(biāo)的值分開，然后進(jìn)行類型轉(zhuǎn)換，把字符串類型轉(zhuǎn)換為數(shù)值類型，把得到的城市的坐標(biāo)（x,y）存入原始數(shù)組列表srcData；

（4）把得到的結(jié)果進(jìn)行返回，供構(gòu)造函數(shù)調(diào)用獲取原始數(shù)據(jù)并賦值給self.places 使用。

2.2.4 main 文件中主程序的功能描述

（1）實(shí)例化問題對(duì)象problem，即problem=MyProblem()；

（2）設(shè)置遺傳算法的編碼方式為’P’，即采用排列編碼方式；

（3）設(shè)置種群規(guī)模，即NIND=100；

（4）創(chuàng)建區(qū)域描述器Field；

（5）實(shí)例化種群對(duì)象population；

（6）實(shí)例化算法模板對(duì)象myAlgorithm，并設(shè)置最大進(jìn)化代數(shù)為1000，變異概率為0.5，每一代進(jìn)化都進(jìn)行日志記錄，打印日志記錄信息，繪制結(jié)果圖等；

（7）調(diào)用算法模板進(jìn)行種群進(jìn)化，即[BestIndi,population]=myAlgorithm.run()；

（8）把得到的最優(yōu)化結(jié)果保存到文件中，即BestIndi.save()。

3 實(shí)驗(yàn)仿真

使用TSPLIB 庫中的數(shù)據(jù)eil51 進(jìn)行實(shí)驗(yàn)，把種群規(guī)模設(shè)為100，最大進(jìn)化代數(shù)設(shè)置為1000，變異概率設(shè)置為0.5，采用排列編碼方式進(jìn)行編碼，通過20 次實(shí)驗(yàn)，基于Geatpy 庫的遺傳算法求解該TSP 問題的最優(yōu)是437.73，對(duì)應(yīng)的旅游路線圖如圖1（左圖）所示；TSPLIB 官網(wǎng)給出的最優(yōu)解路線圖如圖1（右圖）所示，根據(jù)此路線圖計(jì)算出的最短路徑長(zhǎng)度是429.98。

4 結(jié)束語

使用本文給出的方法求得的最優(yōu)解雖然沒有TSPLIB 給出的最優(yōu)解好，但是本文方法使用簡(jiǎn)單，尤其是新手容易上手，為我們求解組合優(yōu)化問題提供了一個(gè)很好的方法思路。另外Geatpy 庫的源代碼是開源的，還可以通過靈活的修改遺傳算法的算子來改良該算法，實(shí)用性很強(qiáng)，這也是后續(xù)需要開展的工作，希望通過算法改良將來可以給出更好的結(jié)果。

圖1：本文方法和TSPLIB 公布的最優(yōu)路徑圖