何湘竹

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

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

何湘竹

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

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

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

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

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

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

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

1 TSP問題建模

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

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

(1)

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

(2)

(3)

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

2 TLBO算法

2.1 算法思想

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

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

2.2 算法步驟

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

2.1.1 老師階段

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

Difference_Meani=ri(Mnew-TFMi).

(4)

其中TF是教學(xué)因子，它決定了平均值被改變的程度，一般取1或2，是啟發(fā)式中重要的一步，由公式(5)以相同的概率隨機(jī)確定，ri是一個(gè)在[0,1]范圍內(nèi)取值的隨機(jī)數(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é)生通過互相影響來獲取知識(shí).一個(gè)學(xué)生隨機(jī)地與另一學(xué)生交流來提高其知識(shí)水平.學(xué)生總是能從更有知識(shí)的另一方那里學(xué)到新東西.這一階段的學(xué)習(xí)現(xiàn)象可以用數(shù)學(xué)公式(7)和(8)表示.

在第i次迭代中，考慮兩個(gè)不同的學(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的具體實(shí)現(xiàn)步驟如下：

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

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

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

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

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

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

2.3 算法流程圖

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

3 TLBO算法改進(jìn)

3.1 混沌搜索

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

混沌映射是一個(gè)在混沌狀態(tài)下運(yùn)行的離散的動(dòng)態(tài)系統(tǒng)：

xk+1=f(xk),0

(9)

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

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

(10)

3.2 改進(jìn)的TLBO算法

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

5 結(jié)語

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

[1] 趙秋實(shí)． 混合遺傳算法解決旅行商問題的研究[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] 杜明，王江晴． 一個(gè)基于遺傳算法的TSP 問題解決方案[J]． 中南民族大學(xué)學(xué)報(bào): 自然科學(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é)報(bào): 自然科學(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

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

TP391

A

1672-4321(2015)04-0089-05