何湘竹

(中南民族大學(xué) 電子信息工程學(xué)院，武漢 430074)

一種改進的基于教與學(xué)的優(yōu)化算法求解旅行商問題

何湘竹

(中南民族大學(xué) 電子信息工程學(xué)院，武漢 430074)

提出了一種改進的基于教與學(xué)的優(yōu)化算法(TLBO)求解旅行商(TSP)問題，闡述了TLBO算法的基本思想和求解步驟，給出了算法流程，針對算法在解決大規(guī)模問題時易陷入局部最優(yōu)的缺陷，引入混沌搜索機制對其進行了改進.著重研究了改進后的TLBO算法求解TSP問題的求解結(jié)果和性能分析，通過benchmark實例進行了仿真實驗，結(jié)果表明：與諸如遺傳算法和粒子群優(yōu)化算法等已有啟發(fā)式算法相比，改進后的TLBO算法在求解TSP問題時性能更為優(yōu)越，從而為TSP問題的求解找到了一條新途徑.

旅行商問題；NP完全；傳統(tǒng)優(yōu)化算法；啟發(fā)式算法；TLBO算法；混沌搜索

旅行商問題(TSP)是圖論中一個經(jīng)典問題，同時也是一典型的組合優(yōu)化問題，許多諸如網(wǎng)絡(luò)路由選擇、物流車輛路線規(guī)劃等實際工程問題都是TSP的擴展應(yīng)用， TSP的研究不僅具有重要的理論價值更具有實際工程意義[1].

但由于TSP的NP難屬性，致使諸如線性規(guī)劃、動態(tài)規(guī)劃等傳統(tǒng)的優(yōu)化算法在求解該問題時效率低下，尤其隨著城市規(guī)模的增加，會出現(xiàn)組合爆炸現(xiàn)象[2].因此很多啟發(fā)式算法應(yīng)運而生，較為代表的有遺傳算法(GA)[3-4]、粒子群優(yōu)化算法(PSO)[5]、蟻群算法[6]等，這些算法尋找問題的近似最優(yōu)解來取代最優(yōu)解，既高效靈活又可修改或微調(diào)以適用于求解多種具體問題，被證實比經(jīng)典算法性能更加優(yōu)越并因此獲得廣泛應(yīng)用.

基于教與學(xué)的優(yōu)化(TLBO)算法是一個受課堂知識傳授現(xiàn)象啟發(fā)而來的新智能算法，它于2010年由Rao等人首次提出，其最大的特點是算法運行不需要特殊的控制參數(shù)，從而克服了許多啟發(fā)式算法參數(shù)過多的缺陷.TLBO算法自問世以來，不僅在理論研究上取得了一系列的成果，而且在各應(yīng)用領(lǐng)域也備受關(guān)注[7-9].但試驗結(jié)果表明對于大的benchmark函數(shù)，TLBO算法易陷入局部最優(yōu)[10].對“早熟”現(xiàn)象分析后發(fā)現(xiàn)：問題的原因是解缺少多樣性.針對該缺陷，考慮到混沌搜索機制具有隨機性和各態(tài)遍歷的特點，將其引入對解產(chǎn)生擾動增加其多樣性，從而改善算法在整個解空間的全局搜索能力.

本文在對TSP問題進行數(shù)學(xué)建模的基礎(chǔ)上，在深入分析TLBO算法的基本思想和流程之后，將混沌搜索機制引入TLBO對算法進行改進，并將改進后的算法用于TSP問題的求解，給出了詳細的求解步驟.對TSPLIB中的benchmark實例仿真實驗結(jié)果表明，改進后的TLBO算法在求解TSP問題上表現(xiàn)良好，性能優(yōu)越，從而為TSP求解找到了一條新的途徑.

1 TSP問題建模

一個具有n個頂點的圖G，常?？梢员硎緸镚=，其中V=為頂點集，E=[eij]n×n為邊集，其中vi(1 ≤ i ≤ n)為頂點，eij(1 ≤ i, j≤ n)為連接頂點vi和vj的邊.若邊有方向，則為有向圖，否則為無向圖.圖G中頂點和頂點之間的關(guān)系用鄰接矩陣A(G)=[aij]n×n(1≤ i, j≤ n)表示，若(vi,vj)∈E(G)則aij=1，否則aij=0.當邊上帶權(quán)W=[wij]n×n，圖G稱為帶權(quán)圖(WG)，若wij=wji，則WG為對稱圖，否則為非對稱圖.對于不同的TSP問題，權(quán)值代表的意義不同，如可表示距離、成本等，本文僅討論無向圖且邊上權(quán)值為距離的情況.

經(jīng)過每一個城市一次的回路稱為哈密頓圈(HC)，距離最短的HC稱為最優(yōu)哈密爾頓圈(OHC)，在圖論中，TSP問題指在帶權(quán)圖G中找到OHC，G中的頂點和邊分別代表城市和路線.具體描述如下：對于一個具有n個頂點的無向帶權(quán)圖G=(V, E, D)，V={v1,…,vn}為代表城市的頂點集，E=[eij]n×n為表示城市之間連接公路的邊集，D={dij|(vi,vj)∈E且vi≠vj, dij>0}代表城市vi和vj之間的距離的集合.設(shè)：

(1)

則TSP問題的數(shù)學(xué)模型如下：

(2)

(3)

其中式(2)為目標函數(shù)，式(3)表示目標函數(shù)必須滿足的約束條件：任一城市vi被遍歷到且僅被遍歷1次，任一可能的遍歷序列中必須包含所有的頂點.

2 TLBO算法

2.1 算法思想

TLBO算法是Rao于2010年提出的一種新自然啟發(fā)式算法，該算法基于老師對于一個班級學(xué)生成績的影響來實現(xiàn)，TLBO算法不需要具體控制參數(shù)，和其它如GA和PSO之類的算法相比，實現(xiàn)更為簡單且性能更好.

TLBO算法模擬課堂教學(xué)過程，認為一個好老師可以使整個班級學(xué)生的平均成績提高.班級中成績最好的學(xué)生被選擇模擬老師，從而使整個班級的成績往自身方向提高，此時再產(chǎn)生新老師，循環(huán)執(zhí)行上述過程直到發(fā)現(xiàn)最優(yōu)解.算法中種群被看作一組學(xué)生，不同的設(shè)計變量被類比為提供給學(xué)生的不同學(xué)科，學(xué)生的成績類比為適應(yīng)值，老師被認為是目前所獲得的最優(yōu)解.

2.2 算法步驟

TLBO算法由兩部分組成：老師階段和學(xué)生階段.

2.1.1 老師階段

此階段模擬學(xué)生向老師學(xué)習(xí)的過程，在這個階段中老師試圖將整個班級學(xué)生的平均成績Mi提高到自身水平Mnew，現(xiàn)有平均值和新的平均值之間的差值為：

Difference_Meani=ri(Mnew-TFMi).

(4)

其中TF是教學(xué)因子，它決定了平均值被改變的程度，一般取1或2，是啟發(fā)式中重要的一步，由公式(5)以相同的概率隨機確定，ri是一個在[0,1]范圍內(nèi)取值的隨機數(shù).

TF=round[1+rand(0,1){2-1}].

(5)

由平均值差Difference_Meani，根據(jù)公式(6)更新已知解：

Xnew,i=Xold,i+Difference_Meani.

(6)

2.1.2 學(xué)生階段

在此階段所有學(xué)生通過互相影響來獲取知識.一個學(xué)生隨機地與另一學(xué)生交流來提高其知識水平.學(xué)生總是能從更有知識的另一方那里學(xué)到新東西.這一階段的學(xué)習(xí)現(xiàn)象可以用數(shù)學(xué)公式(7)和(8)表示.

在第i次迭代中，考慮兩個不同的學(xué)生Xi和Xj(i≠j):

Xnew,i=Xold,i+ri(Xi-Xj),if f(Xi)

(7)

Xnew,i=Xold,i+ri(Xj-Xi),if f(Xj)

(8)

如果Xnew的函數(shù)值更為理想，則接受它.

TLBO的具體實現(xiàn)步驟如下：

第1步：初始化優(yōu)化問題的種群、設(shè)計變量以及迭代次數(shù)，并對種群進行評價；

第2步：選出每一個科目成績最好的學(xué)生作為該科目的老師并計算各科目所有學(xué)生的平均成績；

第3步：根據(jù)式(4)利用教學(xué)因子TF計算目前平均值和最好平均值之間的差值；

第4步：根據(jù)式(6)在老師幫助下的更新每位學(xué)生的知識；

第5步：根據(jù)式(7)和(8)利用其它學(xué)員的知識更新每位學(xué)生的知識；

第6步：重復(fù)第2步到第5步直到算法終止條件滿足.

2.3 算法流程圖

算法的流程圖如圖1所示.

3 TLBO算法改進

3.1 混沌搜索

混沌是非線性動態(tài)系統(tǒng)中存在的確定卻類似隨機的一個過程，具有非周期、不收斂和約束的特點，且對初始條件和參數(shù)十分敏感.混沌的天性使其具有明顯的隨機性和不可預(yù)測性，但同時卻擁有規(guī)則的元素.從數(shù)學(xué)角度理解，混沌是一個簡單的確定性動態(tài)系統(tǒng)的隨機性狀態(tài)，且混沌系統(tǒng)可以看作隨機源[11].

混沌映射是一個在混沌狀態(tài)下運行的離散的動態(tài)系統(tǒng)：

xk+1=f(xk),0

(9)

其中，混沌序列{xk:k=0,1,2,…}可以作為隨機序列的擴頻序列，且被證明易于快速產(chǎn)生和保存，即便對非常長的序列，也只需要保存少數(shù)幾個函數(shù)(混沌圖)和極少的參數(shù)(初始條件)，而無需存儲整個序列[12].

在本文中，r個混沌變量由如下Logistic映射獲得：

(10)

3.2 改進的TLBO算法

將混沌搜索引入TLBO算法，改進后的TLBO算法其偽碼如圖2所示.

4 實驗結(jié)果

以下仿真實驗開發(fā)環(huán)境為ADMPhenom(tm)ⅡX2B59 處理器3.40GHz，開發(fā)軟件為Matlab2013.為了測試改進的TLBO算法求解TSP問題的性能，我們選擇了http://www.crpc.rice.edu/softlib/tsplib/上的具有14個城市的TSP標準問題，該benchmark問題常被用來驗證比較算法的性能，14個城市的坐標信息見表1.

我們將GA、PSO、改進后的TLBO算法分別用于求解該benchmark問題，為了保證實驗結(jié)果的有效性，三種算法的種群數(shù)均設(shè)置為100個，最大迭代次數(shù)設(shè)置為600次，每種算法獨立運行20次.改進后TLBO算法的性能分析見表2.

從實驗結(jié)果可以看出，TLBO算法在規(guī)定的迭代次數(shù)內(nèi)得到了最優(yōu)解，這證明了算法求解TSP問題的有效性.為了更好分析TLBO算法的求解效率和收斂特性，給出了三種算法的收斂曲線比較圖(圖3所示)，從圖中可以看出，與GA和PSO算法相比，改進TLBO算法只經(jīng)過很小的迭代次數(shù)(128次)便得到了最優(yōu)解，收斂速度更快，這主要得益于TLBO算法的教師和學(xué)生階段以及引入的混沌搜索機制，在保證算法的全局搜索能力的同時加強了算法的局部搜索速度.

5 結(jié)語

文中采用了一種改進的基于教與學(xué)的優(yōu)化算法(TLBO)來求解旅行商問題.該算法是一種基于種群的新智能算法，主要分為兩個階段：教師階段和學(xué)生階段，其最大的優(yōu)點是除了種群大小和迭代代數(shù)等一般控制參數(shù)之外，算法運行不需要其它特殊控制參數(shù)，但在大規(guī)模問題求解時易陷入局部最優(yōu)，本文引入混沌搜索機制對其改進.實驗表明，改進后的TLBO算法在求解TSP問題上與其它已有的啟發(fā)式算法如遺傳算法和粒子群算法相比，性能更加優(yōu)越，從而為旅行商問題的求解提供了一種有效的手段.

[1] 趙秋實． 混合遺傳算法解決旅行商問題的研究[D]．南寧: 廣西大學(xué)，2013．

[2] Wang Y． The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem[J]．Computers & Industrial Engineering， 2014， 70:124-133．

[3] Liu Y H． Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem[J]． Applied Mathematics and Computation，2010，216( 1) : 125-137．

[4] 杜明，王江晴． 一個基于遺傳算法的TSP 問題解決方案[J]． 中南民族大學(xué)學(xué)報: 自然科學(xué)版，2007，26( 1) : 77-79．

[5] Chen S M，Chien C Y． Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques[J]． Expert Systems with Applications，2011，38( 12) :14439-14450．

[6] 程滿中，王江晴． 基于群集智能的蟻群算法研究[J]．中南民族大學(xué)學(xué)報: 自然科學(xué)版，2006，25 ( 4 ) :73-76．

[7] Rao R V，Savsani V J，Vakharia D P． Teaching - learning-based optimization: a novel method for constrained mechanical design optimization problems[J]． Computer-Aided Design，2011，43( 3) : 303-315．

[8] Rao R V，Savsani V J，Vakharia D P． Teaching - learning-based optimization: an optimization method for continuous non-linear large scale problems [J]． Information Sciences，2012，183( 1) : 1-15．

[9] Togˇ an V． Design of planar steel frames using teaching - learning based optimization[J]． Engineering Structures， 2012，34: 225-232．

[10] Huang J，Li X，Gao L． A new hybrid algorithm for unconstrained optimisation problems[J]． International Journal of Computer Ap plications in Technology，2013， 46( 3) : 187-194．

[11] Alatas B． Chaotic bee colony algorithms for global numerical optimization [J]． Expert Systems with Applications，2010，37( 8) : 5682-5687．

[12] Heidari-Bateni G，McGillem C D． A chaotic directsequencespread-spectrum communication system[J]．IEEE Transactions on Communications，1994，42( 234) :1524-1527．

Teaching-Learning Based Optimization Algorithm
for Traveling Salesman Problem

He Xiangzhu

(College of Electronics and Information, South-Central University for Nationalities, Wuhan 430074, China)

This paper introduced an improved teaching-learning based optimization algorithm into traveling salesman problem, it illustrated the main ideas and the procedure of TLBO, to overcome the shortage of being trapped into local optimum when facing large scale problems, the chaos search mechanism was introduced to improve the performance of TLBO. The paper focused on the result and performance analysis of solving the traveling salesman problem with improved teaching-learning based optimization algorithm, experimental results of some typical benchmarks demonstrated that compared with other heuristic algorithms like GA and PSO, the improved TLBO algorithm achieved a good performance while requiring a much less computation, thus can be served as a new method to solve TSP problem.

traveling salesman problem; NP complete; traditional optimization algorithm; heuristic algorithm; teaching-learning based optimization; chaos search

2015-03-20

何湘竹(1974-), 女, 副教授，研究方向：優(yōu)化算法，E-mail：xzhe@mail.scuec.edu.cn

國家重點基礎(chǔ)研究發(fā)展計劃項目(973計劃項目)(2011CB706804)；教育部中央高?；究蒲袠I(yè)務(wù)費專項(CZQ12002)

TP391

A

1672-4321(2015)04-0089-05