多重同心圓TSP問題的研究

廖遷，彭剛

（惠州學院計算機科學系，廣東 惠州 506007）

多重同心圓TSP問題的研究

廖遷，彭剛

（惠州學院計算機科學系，廣東 惠州 506007）

旅行商問題（TSP）是一個典型的組合優(yōu)化問題，具有相當廣泛的應用價值，對于實際的生產(chǎn)生活具有重要意義。多重同心圓TSP問題為TSP問題中的一個特殊的例子，運用遺傳算法，求解多重同心圓TSP問題，可以對其他優(yōu)化問題的求解提供參考方案，同時也可以用于對不同算法進行比較。本研究重點著眼于同心圓的個數(shù)、城市數(shù)目、迭代次數(shù)等對算法的影響。

TSP；遺傳算法；多重同心圓

1 引言

TSP問題是數(shù)學上一個典型的組合優(yōu)化問題，可

以描述為[3-4]：指定N個城市(C=c1, c2,...,cn)，商家從任意一個城市開始出發(fā)，不重復地經(jīng)過每一個城市，最終回到出發(fā)城市，按照要求找出商家能夠盡可能地降低成本（時間成本、經(jīng)濟成本等）在所有城市之間巡回的最短路徑。在現(xiàn)實的生產(chǎn)生活中，電路板路線印刷、管道鋪設以及物流配送等問題，均能轉(zhuǎn)變成TSP問題的模型，如果TSP問題能夠被有效地解決，人們的生產(chǎn)生活效率能夠大大地提高，節(jié)省大量的資源。

本研究主要通過控制變量法，利用遺傳算法具有并行性，隨機性等特點，來研究不同因素對算法的影響。本研究對現(xiàn)實的TSP問題進行參數(shù)編碼、通過迭代方式對編碼后的染色體進行遺傳操作來交換群體中染色體的信息，形成新的個體，最后把符合優(yōu)化目標的個體保留下來，即為所求算法的最優(yōu)解。

2 求解多重同心圓TSP問題的遺傳算法

2.1 多重同心圓遺傳算法基本實現(xiàn)方法

研究多重同心圓TSP的問題時，在二重同心圓的基礎上，增加適應多重同心圓的優(yōu)化選擇的方法。由于在多重同心圓上，內(nèi)外圓之間的距離與圓上相鄰兩個點之間的距離比較接近，因此選擇在這種情況下更加合適的優(yōu)化算法：路徑比較法。

所謂路徑比較法[1-2]，就是在隨機選擇的四個點中，兩兩相連，計算并判斷連線的長度，獲取不重復地連接四個點的兩條連線，即為經(jīng)過四個城市的最短路徑。如圖所示：

圖2 優(yōu)化后路徑圖

其步驟如下：

Step1：選擇一條路徑C={C0, C1,...,Ci, Ci+1,...,Cj, Cj+1,...,Cn-1}，隨機找出不規(guī)則的四邊形CiCi+1CjCj+1。

2.2 算法流程

相比于基本遺傳算法，上述算法加入了適應多重同心圓TSP問題的路徑比較法，其算法流程如下：

Step1：隨機地產(chǎn)生個體數(shù)為N的初始群體。

Step2：計算群體中個體的適應度

Step3：判斷種群中個體是否滿足終止條件，若滿足，則終止算法，輸出最優(yōu)解；若不滿足，則執(zhí)行擇優(yōu)保留的選擇操作。

Step4：進行交叉操作。

Step5：進行變異操作。

Step6：執(zhí)行局部優(yōu)化的路徑比較法。

2.3 實驗設計

實驗一：假定城市個數(shù)NG=240、迭代次數(shù)Generation=50不變，只改變圓的個數(shù)Circle。探究圓的個數(shù)不同時，算法的執(zhí)行效率。

實驗二：假定圓的個數(shù)Circle=8、圓的半徑及城市個數(shù)NG=200不變，只改變迭代次數(shù)Generation，觀察算法的收斂過程。

實驗三：假定圓的個數(shù)Circle=8，城市個數(shù)NG= 160，迭代次數(shù)Generation=200不變，通過改變圓的半徑，觀察算法最優(yōu)化時可能出現(xiàn)的圖形。

實驗四：假定圓的個數(shù)Circle=8，迭代次數(shù)Generation=200和圓的半徑不變，改變城市個數(shù)NG（160-320），觀察城市個數(shù)對算法效率的影響。

3 結(jié)果分析

3.1 實驗一

表1 實驗一結(jié)果統(tǒng)計

圖9是實驗四的結(jié)果分析：算法的執(zhí)行時間與城市個數(shù)成正比，最優(yōu)解個數(shù)與城市個數(shù)成反比。當群體規(guī)模增加時，算法計算所消耗時間相應增加，同時獲得最優(yōu)個體的數(shù)量相應減少。

4 結(jié)束語

實驗結(jié)果表明：加入路徑比較法的基本遺傳算法，能夠更加有效地求解多重同心圓的TSP問題，具有較強的全局搜索能力和局部搜索能力；實驗所得圖形也能夠讓我們更加直觀地判斷是否是最優(yōu)解；同時也驗證了遺傳算法在求解TSP問題時，有較強的獲取最優(yōu)個體的能力。

[1]PENG Gang.Ichiro Iimura and Shigeru Nakayama.Application of Genetic Recombination to Genetic Local Search in TSP.[J].International Journal of Information Technology，2007，13（1）：63-64

[2]PENG Gang.Ichiro Iimura and Shigeru Nakayama.An Evolutionary Multiple Heuristic with Genetic Local Search for Solving TSP.[J].International Journal of Information Technology，2008，14（2）：4-5

[3]周敏.遺傳算法求解TSP的研究.[J].無線互聯(lián)科技，2015（3）129

[4]程林輝，李航高.遺傳算法及其在TSP問題中的應用[J].現(xiàn)代計算機，2013，14（5）：20

[5]郭峰，陳勇.改進的遺傳算法求解TSP問題[J].現(xiàn)代計算機，2014，17（11）：48

[6]方建斌.一種基于TSP的改進遺傳算法設計與實現(xiàn)[J].現(xiàn)代經(jīng)濟信息，2015，23（2）：322

[7]王松泉.遺傳算法在組合優(yōu)化中的應用研究.[D].合肥：安徽大學，2010

[8]曹道友.基于改進遺傳算法的應用研究.[D].合肥：安徽大學，2010

Study on Multiple Concentric TSP Problem

LIAO Qian，PENG Gang
（Computer Science Dept.，Huizhou University Huizhou 516007 Guangdong China）

The TSP is a typical combinatorial optimization problem which is widely applied in our life.A Multiple Concentric Circle Problem which shows a regular shape is a special case in TSP.It is valuable for other TSP and comparison of different algorithms solving a Multiple Concentric Circle Problem by using the genetic algorithm combined with heuristic search method.This study emphasis on the efficiency of the parameters in the promising algorithm proposed in the experiment.

Traveling Salesman Problem（TSP）；Genetic Algorithm（GA）；Multiple concentric circle

TP39

A

1671-5934（2016）03-0062-03

2016-05-03

廖遷（1995-），男，廣東梅州人，本科，研究方向為計算機應用。