求解旅行商問(wèn)題的混合粒子群優(yōu)化算法

沈繼紅，王侃

(1.哈爾濱工程大學(xué)理學(xué)院，黑龍江 哈爾濱 150001;2.哈爾濱工程大學(xué)自動(dòng)化學(xué)院，黑龍江 哈爾濱 150001)

優(yōu)化問(wèn)題可以自然分為2類:一類是連續(xù)變量的優(yōu)化問(wèn)題;另一類是離散變量的優(yōu)化問(wèn)題，即所謂的組合優(yōu)化問(wèn)題.旅行商問(wèn)題(travel salesman problem，TSP)是組合優(yōu)化問(wèn)題中的一個(gè)著名NP難題，TSP因其典型性已經(jīng)成為許多啟發(fā)式搜索、優(yōu)化算法的間接比較標(biāo)準(zhǔn).同時(shí)TSP也是一個(gè)具有廣泛的應(yīng)用背景與重要理論價(jià)值的組合優(yōu)化難題，對(duì)求解該問(wèn)題高效的全局優(yōu)化算法的研究，一直被科學(xué)界和工程界所高度重視.

TSP問(wèn)題的求解方法歸納起來(lái)可以分為得到最優(yōu)解的精確算法和找到近似解的近似算法.完全枚舉法、動(dòng)態(tài)規(guī)劃法和全局搜索算法屬于精確算法.TSP問(wèn)題精確算法的運(yùn)行時(shí)間是指數(shù)級(jí)復(fù)雜度，難以適應(yīng)大規(guī)模的實(shí)例，隨著對(duì)TSP問(wèn)題的認(rèn)識(shí)加深，精確算法的研究越來(lái)越少.近年來(lái)受到自然界的啟發(fā)，人們提出了各種各樣的計(jì)算智能方法，如人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群優(yōu)化算法、粒子群優(yōu)化算法和人工免疫系統(tǒng)等.智能優(yōu)化算法為解決TSP問(wèn)題提供了新的思路，它們被廣泛地應(yīng)用于各種NP難題的優(yōu)化問(wèn)題求解，雖然不能保證獲取最優(yōu)解，但在問(wèn)題規(guī)模較大時(shí)也可以在可行時(shí)間內(nèi)找到滿意的解.

粒子群優(yōu)化算法(particle swarm optimization，PSO)是一種群智能優(yōu)化方法，它是由美國(guó)社會(huì)心理學(xué)家Kennedy和電氣工程師R.Eberhart在1995年提出的，它利用了生物群體中信息共享的思想，其概念簡(jiǎn)單、易于實(shí)現(xiàn)，同時(shí)又有深刻的智能背景，既適合科學(xué)研究，又適合工程應(yīng)用.因此，PSO一經(jīng)提出，就引起了眾多學(xué)者的關(guān)注，得到了非常廣泛的應(yīng)用.為解決組合優(yōu)化問(wèn)題，Kennedy等［1］首先提出了PSO算法的離散二進(jìn)制版;Clerc［2］提出了求解TSP問(wèn)題的離散粒子群優(yōu)化算法，對(duì)TSP問(wèn)題的求解重新定義粒子的位置、速度和相關(guān)運(yùn)算，但其性能與其他算法相比仍有不小的差距;高尚等［3］在粒子群算法中加入遺傳算法思想，構(gòu)造了混合算法;Hendlass等［4］通過(guò)對(duì)離散PSO的每個(gè)粒子增加記憶功能，成功解決了一個(gè)小規(guī)模的TSP;王康平等［5］通過(guò)引入“交換子”和“交換序”的概念，給出了另一種解決TSP的PSO方法，為求解TSP問(wèn)題提供了新的思路.但在算法的收斂速度方面以及在城市規(guī)模較大的情況下，現(xiàn)有文獻(xiàn)中的粒子群算法都存在著一定的缺陷，本文試圖通過(guò)與其他智能優(yōu)化算法的結(jié)合來(lái)解決這一問(wèn)題.光學(xué)尋優(yōu)算法［6］是2007年沈繼紅教授提出的模擬光自然屬性的智能優(yōu)化算法，利用在可行域中填充正方形介質(zhì)，模擬光的折射以及反射現(xiàn)象，通過(guò)最基本光學(xué)定律找到最優(yōu)值，算法迭代機(jī)理簡(jiǎn)單、收斂速度快，具有很強(qiáng)的并行計(jì)算能力.2010年，李焱等［7］給出了基于正六邊形網(wǎng)絡(luò)的光學(xué)尋優(yōu)算法，在高維迭代中具有良好的仿真效果，李加蓮等［8］給出了光學(xué)尋優(yōu)算法的基本理論證明，并與其他算法進(jìn)行了比較，完善了算法的理論體系.本文通過(guò)正方形網(wǎng)絡(luò)光學(xué)尋優(yōu)算法的搜索機(jī)制形成初始粒子群，加入混沌優(yōu)化的思想，并引入“交換子”概念，利用離散粒子群算法求解TSP問(wèn)題，提出了一種新的解決TSP問(wèn)題的光學(xué)混沌粒子群算法.

1 混合粒子群優(yōu)化算法的構(gòu)建

1.1 旅行商問(wèn)題以及標(biāo)準(zhǔn)粒子群算法

TSP的描述十分簡(jiǎn)單，即尋找一條最短的遍歷N個(gè)城市的路徑，其數(shù)學(xué)描述如下:

設(shè)有N個(gè)城市的集合C={c1，c2，…，cN}，每2個(gè)城市之間的距離為d(ci，cj)∈R+，其中 ci，cj∈C(1≤i，j≤N)，求使目標(biāo)函數(shù)

達(dá)到最小的城市序列(c∏(1)，c∏(2)，…，c∏(N))，其中，∏(1)，∏(2)，…，∏(N)是1，2，…，N的全排列.

1998年，Shi等［9］給出了標(biāo)準(zhǔn)的 PSO 算法的數(shù)學(xué)描述:設(shè)搜索空間為D維空間，粒子數(shù)為n，第i個(gè)粒子的位置用 xi=(xi1，xi2，…，xiD)表示;第i個(gè)粒子的速度變化率用vi=(vi1，vi2，…，viD)表示;第i個(gè)粒子迄今為止搜索的得最好位置為pi=(pi1，pi2，…，piD)，記為pbest，整個(gè)粒子群迄今為止搜索到的最好位置為 pg=(pg1，pg2，…，pgD)，記為 gbest，對(duì)于每一次迭代，第i個(gè)粒子在第D維運(yùn)動(dòng)的表達(dá)式如下:

式中:c1、c2為正常數(shù)，稱為加速因子;rand()為［0，1］之間的隨機(jī)數(shù);w稱為慣性因子.第d維的位置和速度的變化范圍為［－xdmax，xdmax］和［－vdmax，vdmax］，如果在某一維中迭代的xid、viid超過(guò)了取值邊界則按照邊界取值.

1.2 光學(xué)尋優(yōu)算法

光學(xué)尋優(yōu)算法借鑒了費(fèi)馬定理，利用光在傳播過(guò)程中自動(dòng)尋優(yōu)的機(jī)制，將光的折射與反射原理與最優(yōu)化的尋優(yōu)過(guò)程聯(lián)系起來(lái)，給出一種新的最優(yōu)化搜索算法.這種算法將坐標(biāo)空間設(shè)想為填充了具有不同折射率的介質(zhì)的空間，如圖1所示，將搜索路徑設(shè)想為光的傳播路徑，通過(guò)光的折射原理，使搜索方向趨向于目標(biāo)函數(shù)值減小的方向，通過(guò)光的反射原理，改變搜索方向，使得搜索在折射無(wú)法進(jìn)行時(shí)繼續(xù)下去.

圖1 在可行域中填充介質(zhì)Fig.1 Filling medium in feasible region

針對(duì)以下問(wèn)題進(jìn)行研究:

式中:f(X)是正函數(shù)，即?(x，y)∈M，f(x，y)＞0.X是可行解，M是f(X)的可行域，R×R是二維實(shí)數(shù)空間.P(i)為第i次的搜索方向，h、τ為網(wǎng)格步長(zhǎng).對(duì)于第i次迭代，令搜索以P(i)方向在矩形分塊Di中搜索到點(diǎn)X(i)=(xi，yi)，并在X(i)點(diǎn)改變搜索方向，到達(dá)X(i+1)點(diǎn)，方向的迭代關(guān)系滿足:

式中:αi為Di中的入射角，αi+1為Di+1中的折射角，vi為光在Di中的傳播速度，可設(shè)定為Di中X(i+1)=(xi+1，yi+1)點(diǎn)的函數(shù)值.vi+1為光在Di+1中的傳播速度，可設(shè)定為Di+1中X(i+1)=(xi+1，yi+1)點(diǎn)的函數(shù)值.

式中:αi為Di中的入射角，αi+1為Di+1中的反射角.圖3～4是加入了多個(gè)臨界面的水平以及豎直方向的搜索路徑.光學(xué)尋優(yōu)算法能快速找到最優(yōu)搜索路徑.

圖2 基于反射和折射搜索方向的更新Fig.2 Updating searching direction based on reflection and refraction

圖3 增加多個(gè)臨界面光路的更新Fig.3 Updating light line after adding

圖4 增加水平豎直臨界面Fig.4 Adding horizontal and many critical surfaces vertical critical surfaces

1.3 TSP問(wèn)題中的光學(xué)尋優(yōu)思想

光學(xué)尋優(yōu)算法遵循費(fèi)馬原理，費(fèi)馬原理表明，光在介質(zhì)中從一點(diǎn)向另一點(diǎn)傳播時(shí)，總是沿著時(shí)間最少的路徑，光的傳播在不同介質(zhì)中速度不同，運(yùn)用光學(xué)尋優(yōu)的思想可以很容易地得到粒子群的一組性能良好的初始粒子，大大減少算法的迭代次數(shù).

定義1 當(dāng)前城市密度.從當(dāng)前城市到其他未被遍歷過(guò)的城市的最短路徑.

定義2 前沿城市密度.去除已經(jīng)遍歷的城市，剩余城市路徑的平均值.

定義3 TSP問(wèn)題中的反射.從當(dāng)前城市開始，隨機(jī)選擇一條與未被遍歷城市的路徑.

定義4 TSP問(wèn)題中的折射.從當(dāng)前城市開始，選擇與未被遍歷城市之間最短的路徑.

光學(xué)尋優(yōu)初始化初始值的過(guò)程如下:

1)隨機(jī)選擇一個(gè)城市作為出發(fā)點(diǎn)，選擇與當(dāng)前城市之間的最短路徑城市作為下一個(gè)遍歷點(diǎn).

2)計(jì)算當(dāng)前城市密度與前沿城市密度.

3)如果當(dāng)前城市密度小于前沿城市密度，則發(fā)生折射，選擇與未被遍歷城市之間最短路徑城市作為下一個(gè)遍歷點(diǎn);如果當(dāng)前城市密度大于前沿城市密度，隨機(jī)選擇一個(gè)未被遍歷的城市作為下一個(gè)遍歷城市.

4)重復(fù)3)的過(guò)程直到所有的城市都被遍歷.

5)將每一個(gè)城市都作為起點(diǎn)，依據(jù)光學(xué)尋優(yōu)的思想形成N個(gè)城市序列，作為混沌粒子群算法的初值.

2 光學(xué)混沌粒子群算法

2.1 TSP問(wèn)題中的混沌粒子群算法

2.1.1 TSP問(wèn)題中混沌粒子群算法的相關(guān)定義

定義5 交換子.2個(gè)城市序列［10］Xi=［xi1xi2… xim］與Xj=［xj1xj2… xjm］，如果2個(gè)序列在相同的位置，數(shù)值不相同，即 xia≠xja，稱(xia，xja)為城市序列的交換子，即為Vij(xia，xja).

定義6 交換序列.由交換子組成的序列V=［V1V2… Vn］，其中n為2個(gè)城市對(duì)應(yīng)序列相同，但數(shù)值不同的位置個(gè)數(shù).

定義7 粒子的位置.粒子的位置是由城市序列X=［X1X2… Xm］表示，m為城市的個(gè)數(shù);

粒子的速度.粒子的速度V=［V1aV2b… Vmn］，其中Vmn表示交換子，速度為交換序列.

2.1.2 交換子與交換序列的運(yùn)算法則

1)位置與交換子的加法.

位置與速度的加法形成新的城市序列:設(shè)X=［X1X2… Xm］為城市序列，Vij(Xi，Xj)為交換，則

X=［X1X2… XjXiXm］為新形成的城市序列.

例1:

2)位置與位置的減法.

位置與位置的減法形成交換序列即生成新速度:Vij=Xi－ Xj，其中 Xi、Xj為城市序號(hào).先找到與第1個(gè)城市序列中第1個(gè)元素相同的第2個(gè)城市序列位置，形成交換子v(1，i)，然后將此交換子作用在第1個(gè)序列上得到新的第1個(gè)序列，再找到新的第1個(gè)城市序列與第2個(gè)城市序列數(shù)值相同的第1個(gè)位置，形成交換子v(2，i)，依次進(jìn)行下去，得到2個(gè)城市序列的交換序列.

例2:

3)交換子的數(shù)乘.

速度的數(shù)乘具有概率意義，例如Via=c·Vjb，其中c∈［0，1］是一個(gè)常數(shù)，在計(jì)算Via時(shí)，對(duì)Vjb中的每一維速度Vjn生成一個(gè)(0，1)的隨機(jī)數(shù).

4)混沌思想.

通常一類非常簡(jiǎn)單卻又廣泛應(yīng)用的混沌系統(tǒng)是Logistic 映，其定義如下［11］:

式中:zk為實(shí)值序列，u為參數(shù)，研究表明當(dāng)3.571 448≤u≤4時(shí)，該混沌映射處于混沌狀態(tài)，把3.571 448≤u≤4稱為混沌區(qū)域.Logistic混沌映射所生成的序列具有如下混沌特性:①非周期的序列;②該混沌序列不收斂;③zk可以遍歷整個(gè)(0，1)區(qū)域.

本文取u=4，設(shè)城市數(shù)量為n，按照順序隨機(jī)地生成(0，1)的n個(gè)隨機(jī)數(shù)，構(gòu)成向量序列Z(k)=［z1(k)z2(k)… zn(k)］，將 z1，z2，…，zn按照從小到大排列1，2，…，n的下標(biāo)號(hào)構(gòu)成城市序列Xi=［Xi1Xi2… Xin］，按照式(1)生成向量，然后對(duì)Z(k+1)中元素從小到大進(jìn)行排列下標(biāo)號(hào)1，2，…，n構(gòu)成新的城市序列 X(i+1)=［X(i+1)1X(i+1)2… X(i+1)n］.混沌遍歷的引入，有效地增加了城市序列的多樣性.

例3:

生成的城市序列為Xi=［4 1 2 3 4 6］，運(yùn)用式(3)，

生成新的城市序列為Xi+1=［6 4 3 5 1 2］.

針對(duì)TSP問(wèn)題，結(jié)合混沌思想的粒子群的更新公式變?yōu)?

式中:?1、?2為(0，1)的數(shù)，f(x)為 xi(k)向量從小到大排列下標(biāo)形成的向量函數(shù)，Xi(k)為當(dāng)前城市序列，Xi(k+1)為新生成的城市序列，Pbesti為當(dāng)前個(gè)體最好序列，Gbesti為全局最好序列.Pbesti－ Xi(k)=Vp(k)，Gbesti－Xi(k)=VG(k)表示為交換序列，?1(Pbesti－Xi(k))表示當(dāng)概率小于?1時(shí)發(fā)生交換操作，當(dāng)概率大于?1不進(jìn)行操作，城市序列保持不變.

2.2 光學(xué)混沌粒子群算法步驟

1)利用1.3中光學(xué)尋優(yōu)的思想初始化粒子群，從每一個(gè)城市出發(fā)，得到N個(gè)初始值良好的城市序列;隨機(jī)生成混沌序列Z(1)并運(yùn)用函數(shù)f(x)得到城市序列Xf(1).

圖5 混合粒子群算法的流程Fig.5 A flow sheet of mixed particle swarm algorithm

2)如果滿足最優(yōu)條件，最短城市距離不再變——或者達(dá)到最大迭代次數(shù)轉(zhuǎn)到5)，如不滿足條件對(duì)初始種群進(jìn)行更新，找到個(gè)體最好位置Pbesti以及全局最好位置Gbesti.

3)根據(jù)式(4)更新城市序列;

①根據(jù)式(1)和(3)計(jì)算混沌生成序列Z(k)并運(yùn)用函數(shù)f(x)得到新的城市序列Xf(k);

②運(yùn)用例2的思想計(jì)算交換序列，Pbesti－ Xi(k)=Vp(k)，Gbesti－ Xi(k)=VG(k);

③根據(jù)式(2)計(jì)算 φ1(Pbesti－Xi(k))+φ2(Gbesti－Xi(k));φ1、φ2為執(zhí)行操作的控制概率.

④根據(jù)以上3個(gè)結(jié)果結(jié)合式(4)得到新的城市序列Xi(k+1).

4)迭代次數(shù)增加，更新粒子的位置轉(zhuǎn)到2).

5)輸出最優(yōu)城市序列，并輸出最短距離.

2.3 混合算法時(shí)間復(fù)雜度分析

算法的時(shí)間復(fù)雜度是對(duì)算法運(yùn)行時(shí)間的度量，用來(lái)表示算法的計(jì)算效率的高低.算法的時(shí)間復(fù)雜度的大小在一定程度上反映了算法性能的優(yōu)劣.忽略硬件及環(huán)境因素，假設(shè)每次執(zhí)行時(shí)硬件條件和環(huán)境條件是完全一致的.設(shè)城市數(shù)量為n，運(yùn)行迭代次數(shù)為m，則光學(xué)混沌粒子群算法的時(shí)間復(fù)雜度量級(jí)為O(m(2n2+1)).

以下來(lái)說(shuō)明該算法的時(shí)間復(fù)雜度數(shù)量級(jí)為O(m(2n2+1)).根據(jù)混合算法的特點(diǎn)首先應(yīng)用光學(xué)尋優(yōu)算法初始化城市序列，并應(yīng)用混沌方法生成新的城市序列，然后應(yīng)用粒子群算法的核心思想不斷地更新城市序列直到滿足條件.

1)以一次迭代為例，城市數(shù)量為n，隨機(jī)選取城市作為城市序列初始點(diǎn)，并應(yīng)用光學(xué)尋優(yōu)算法進(jìn)行初始化，需要n(n－1)次運(yùn)算，所以時(shí)間復(fù)雜度為O(n2－n).

2)應(yīng)用混沌思想更新城市序列，對(duì)N個(gè)序列都進(jìn)行更新，時(shí)間復(fù)雜度為O(n).

3)n個(gè)序列用來(lái)計(jì)算適應(yīng)度函數(shù)的時(shí)間復(fù)雜度為O(n)，在此基礎(chǔ)上進(jìn)一步確定個(gè)體極值以及群體極值，計(jì)算交換子序列從而對(duì)每一個(gè)城市序列進(jìn)行更新，此步驟一共運(yùn)行的時(shí)間復(fù)雜度為O(n2).

4)在一次迭代完成之后判斷是否達(dá)到終止條件，操作的時(shí)間復(fù)雜度為O(1).

通過(guò)以上的分析可以得出1)～4)的時(shí)間復(fù)雜度為O(2n2+1)，假設(shè)整體算法的迭代次數(shù)為m，則混合算法的整體運(yùn)行時(shí)間為O(m(2n2+1)).因此整體算法的時(shí)間復(fù)雜度與城市的序列以及算法的運(yùn)行代數(shù)有關(guān)，如何在保證精確度的前提下減少迭代次數(shù)也就成了控制算法運(yùn)行時(shí)間的關(guān)鍵因素.

2.4 光學(xué)混沌粒子群算法收斂性分析

根據(jù)混沌序列的更新以及例3可得f(xi(k))是線性映射，可以寫成城市序列與交換子的線性組合的形式:f(xi(k))=X(k)+βv(k).β∈［0，1］，線性系統(tǒng)變成如下形式:

為了方便計(jì)算與分析，首先將空間簡(jiǎn)化為一維空間，將模型轉(zhuǎn)化為式(5):

令 ?=?1+?2，記 Pbesti=pi(t)，Gbesti=pg(t)，并對(duì)模型進(jìn)行簡(jiǎn)化可得表達(dá)式:

整理記為式(6):

通過(guò)標(biāo)準(zhǔn)粒子群算法的數(shù)學(xué)描述可以將系統(tǒng)變?yōu)殡x散線性系統(tǒng)，這里假定在t次迭代之后粒子找到最優(yōu)位置時(shí)，pbest、gbest將保持不變，式(6)中pi(t)、pg(t)不隨著時(shí)間變化.

定理1當(dāng)w＜1+β，β＜?1+?2＜2w+2+β時(shí)，線性定常離散系統(tǒng)(6)漸近穩(wěn)定，并且系統(tǒng)收斂.

證明通過(guò)系統(tǒng)(6)以及模型(5)的表達(dá)式可將xi(t)消去得到如下的差分表達(dá)式:

對(duì)式(7)求特征方程可得

為了對(duì)式(7)進(jìn)行穩(wěn)定性分析，用雙曲線性變換將離散系統(tǒng)轉(zhuǎn)化為線性系統(tǒng)，令帶入式(7)得:

根據(jù)勞斯－赫爾維茨判據(jù)［12］，很容易得到表達(dá)式:

可得，當(dāng)w＜1+β，β＜?1+?2＜2w+2+β時(shí)，線性定常離散系統(tǒng)(6)漸進(jìn)穩(wěn)定.

當(dāng)系統(tǒng)(6)穩(wěn)定，

當(dāng)參數(shù)滿足條件(8)，|A|＜1，所以，

3 數(shù)值仿真

首先運(yùn)用30個(gè)城市的標(biāo)準(zhǔn)TSP測(cè)試數(shù)據(jù)Oliver30對(duì)算法性能進(jìn)行評(píng)估，運(yùn)用蟻群算法、遺傳算法、模擬退火方法、禁忌搜索方法［13］、混沌粒子群算法以及光學(xué)混沌粒子群算法，在最大迭代次數(shù)Mt=300的限定下分別對(duì)測(cè)試城市進(jìn)行計(jì)算，根據(jù)定理1設(shè)定 ?1=0.5，?2=0.5，w采用線性遞減原則，t為當(dāng)前的迭代次數(shù)，w=0.6 － (t/Mt)*0.5，混沌系數(shù)u=4.每種算法運(yùn)行20次，對(duì)比如圖6所示(X、Y的散點(diǎn)坐標(biāo)圖，取計(jì)算最好效果).各種算法計(jì)算的最好結(jié)果、最差結(jié)果以及平均迭代次數(shù)如表1所示.

表1 對(duì)于Oliver30的算法效果對(duì)比Table 1 Algorithm contrast effects of Oliver30

從表1結(jié)果中可以看出，這4種經(jīng)典智能算法精度有所差異，在有限次迭代的情況下得到的最優(yōu)解效果一般，如果設(shè)置較高的迭代次數(shù)，精度能達(dá)到滿意的要求，不過(guò)迭代次數(shù)較高，往往容易收斂到局部最優(yōu)點(diǎn).本文構(gòu)建的混沌粒子群算法以及加入光學(xué)原理的混沌粒子群算法具有良好的精度，對(duì)比于基本的粒子群優(yōu)化算法改進(jìn)效果顯著，在最大迭代次數(shù)上限為300的情況下，可以找到精確的結(jié)果，其中光學(xué)混合粒子群算法性能更為突出，每次運(yùn)行都能找到最優(yōu)值423.740 6.在迭代次數(shù)上，蟻群算法具有較快的收斂速度，但容易陷入局部最優(yōu)點(diǎn)，影響算法的精度.同比與其他的5種算法，光學(xué)混沌粒子群算法在收斂速度上有很大的優(yōu)勢(shì).從圖7中可以看出光學(xué)混沌粒子群算法具有很強(qiáng)的收斂速度.

圖6 7種算法Oliver30效果對(duì)比Fig.6 Seven contrast figures of Oliver30

圖7 Oliver30 4種算法進(jìn)化曲線Fig.7 Four evolutionary curves of Oliver30

本文提出的光學(xué)混沌粒子群算法的GUI界面如圖8所示，得到的最優(yōu)城市序列為(28，27，26，25，24，15，14，8，7，11，10，21，20，19，18，9，3，2，1，6，5，4，13，12，30，23，22，17，16，29)，平均迭代 113 次迭代找到最優(yōu)解，混沌粒子群算法得到的最好結(jié)果為424.691 8，平均迭代次數(shù)為272，遠(yuǎn)遠(yuǎn)大于光學(xué)混沌算法，無(wú)論是迭代時(shí)間、算法精度都要劣于加入光學(xué)尋優(yōu)思想的粒子群算法.光學(xué)尋優(yōu)算法初始化的本質(zhì)就是要減少迭代次數(shù)，提高算法精度，原因就在于用光學(xué)尋優(yōu)思想形成的初始解與最優(yōu)序列之間部分區(qū)域序列是相似的，甚至是完全相同的，這樣在運(yùn)用粒子群算法迭代時(shí)就減少了迭代次數(shù).混沌方法具備的全局遍歷性在保證算法的精度前提下，加強(qiáng)了算法跳出局部最優(yōu)點(diǎn)的能力，增強(qiáng)了算法的適用性.

圖8 光學(xué)混合算法GUI效果圖Fig.8 GUI interface

表2是對(duì)測(cè)試問(wèn)題eil51，參數(shù)設(shè)置與Oliver30實(shí)驗(yàn)相同，最大迭代次數(shù)300，每種算法計(jì)算20次所得的數(shù)據(jù).

表2 對(duì)于51個(gè)城市問(wèn)題eil51的算法效果對(duì)比Table 2 Algorithm contrast effects of eil51

在TSP城市規(guī)模增大的情況下，光學(xué)混沌粒子群算法的優(yōu)勢(shì)得到明顯體現(xiàn)，無(wú)論是算法精度還是算法的收斂速度都要好于其他算法.從以上結(jié)果可以看出本文提出的基于光學(xué)原理的混合粒子群算法相比于其他優(yōu)化算法具有良好的效果，能成功解決中大型TSP路徑優(yōu)化問(wèn)題并保持較高的精度，加入的光學(xué)尋優(yōu)思想能大大節(jié)約迭代次數(shù)，保證算法在規(guī)定的迭代次數(shù)內(nèi)找到最優(yōu)解.

表3是對(duì)測(cè)試問(wèn)題CH130的對(duì)比數(shù)據(jù)，CH130是相對(duì)復(fù)雜的130個(gè)城市的TSP問(wèn)題，最大迭代次數(shù)設(shè)定為500，每種算法運(yùn)行20次，誤差計(jì)算是對(duì)比于CH130給出的精確解6 110，應(yīng)用最優(yōu)路徑計(jì)算得出，所有數(shù)據(jù)如表3所示.

表3 對(duì)于130個(gè)城市問(wèn)題CH130的算法效果對(duì)比Table 3 Algorithm contrast effects of CH130

從結(jié)果可以看出，對(duì)于較大規(guī)模的TSP問(wèn)題光學(xué)混合算法效果顯著，誤差在所有同類算法中最低，無(wú)論是從迭代時(shí)間搜索精度，還是誤差大小同比于其他算法都有很大的優(yōu)勢(shì).與標(biāo)準(zhǔn)粒子群算法以及混沌粒子群算法相比，改進(jìn)效果顯著.圖9為最優(yōu)搜索形成的TSP效果圖.

圖9 應(yīng)用光學(xué)混合算法求解CH130最短路徑6 210.422 0Fig.9 The shortest path 6 210.422 0 of CH130 using the algorithm in this paper

4 結(jié)束語(yǔ)

本文提出了一種結(jié)合光學(xué)尋優(yōu)算法、混沌思想的混合粒子群算法，通過(guò)光學(xué)尋優(yōu)思想形成最優(yōu)初值，利用加入混沌的粒子群算法成功解決了TSP問(wèn)題，該算法迭代次數(shù)少、收斂速度快，對(duì)比于其他智能優(yōu)化算法具有明顯的優(yōu)勢(shì)，并用實(shí)驗(yàn)表明加入光學(xué)尋優(yōu)思想的搜索方式大大減少了算法的迭代次數(shù)，并在一定程度上提高了算法的精度，為高效率解決大規(guī)模TSP問(wèn)題提供了新的思路.

［1］KENNEDY J，EBERHART R.A discrete binary version of the particle swarm algorithm［C］//Proceedings of the World Multiconference on Systemic，Cybernetics and Informatics.Piscataway，USA:IEEE Service Center，1997:4104-4109.

［2］CLERC M.Discrete particle swarm optimization［C］//New Optimization Techniques in Engineering.Berlin:Spinger-Verlag，2004:204-219.

［3］高尚，韓斌，吳小俊，等.求解旅行商問(wèn)題的混合粒子群優(yōu)化算法［J］.控制與決策，2004，19(11):1286-1289.GAO Shang，HAN Bin，WU Xiaojun，et al.Solving traveling salesman problem by hybrid particle swarm optimization algorithm［J］.Control and Decision，2004，19(11):1286-1289.

［4］HENDLASS T.Preserving diversity in particle swarm optimization［J］.Lecture Notes in Artificial Intelligence，2003(2718):155-199.

［5］XIE Shenli，TANG Min，DONG Jinxiang.An improved genetic algorithm for TSP problem［J］.Computer Engineering and Application，2002，38(8):58-60.

［6］SHEN Jihong，LI Yan.Light ray optimization and its parameter analysis［C］//Proceedings of the 2009 International Joint Conference on Computational Science and Optimization.Kunming，China，2007:918-922.

［7］沈繼紅，李焱.基于正六邊形網(wǎng)格的光線尋優(yōu)算法［C］//中國(guó)運(yùn)籌學(xué)會(huì)第十屆學(xué)術(shù)交流會(huì)論文集.南京，中國(guó)，2010:89-94.SHEN Jihong，LI Yan.Light ray optimization on hexagonal grid［C］//Proceedings of the 10th ORSC.Nanjing，China，2010:89-94.

［8］SHEN Jihong，LI Jialian.The principle analysis of light ray optimization［C］//2010 Second International Conference on Computational Intelligence and Natural Computing.Wuhan，China，2010:154-157.

［9］SHI Y，EBERHART R C.A modified particle swarm optimizer［C］//Proceedings of the Congress on Evolutionary Computation.Anchorage，USA，1998:69-73.

［10］ZHANG Guoping，WANG Zhengou，YUAN Guolin.A chaotic search method for a class of combinatorial optimization problems［J］.Systems Engineering Theory ＆ Practice，2001，21(5):102-105.

［11］梁艷春，吳春國(guó).群智能優(yōu)化算法理論與應(yīng)用［M］.北京:科學(xué)出版社，2009:17-21.

［12］鄭大中.線性系統(tǒng)理論［M］.北京:清華大學(xué)出版社，2009:213-251.

［13］ANDRIES P E.計(jì)算智能導(dǎo)論［M］.北京:清華大學(xué)出版社，2010:111-123.