易云飛，林郭隆，董文永

(1.河池學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，廣西 宜州 546300;2.武漢大學(xué) 計(jì)算機(jī)學(xué)院，武漢 430072)

0 引 言

粒子群算法[1-5](particle swarm optimization，PSO)是一種基于種群研究的智能優(yōu)化算法。由于該算法具有全局尋優(yōu)能力強(qiáng)、收斂速度快、參數(shù)設(shè)置少等特點(diǎn)而被廣大學(xué)者所重視。其中, 在粒子群算法發(fā)展進(jìn)程中具有較大的改變有：Shi等[6]在速度項(xiàng)中引入慣性權(quán)，并動(dòng)態(tài)調(diào)整慣性權(quán)重來(lái)平衡全局性和收斂性。之后，Shi等[7]又將模糊系統(tǒng)的慣性權(quán)重做了動(dòng)態(tài)調(diào)整以便對(duì)慣性權(quán)重實(shí)現(xiàn)非線性控制。Peram等[8]則從粒子網(wǎng)絡(luò)優(yōu)勢(shì)方面更新粒子的學(xué)習(xí)方式，粒子不只向全局最優(yōu)粒子學(xué)習(xí)，而是根據(jù)一定的適應(yīng)值-距離-比例原則，向周?chē)Ｗ右圆煌潭瓤拷?。Bergh等[9]以群體智能為基礎(chǔ)，利用多個(gè)協(xié)同工作的子群對(duì)解向量不同部分進(jìn)行分部?jī)?yōu)化。Tizhoosn[10]將反向?qū)W習(xí)策略引入群智能算法，在差分演化算法中取得了較好的效果。喻飛等[11]在反向?qū)W習(xí)基礎(chǔ)上加上透鏡成像原理，使得算法在一定程度上有所加強(qiáng)。Jing Liang等[12]提出了每個(gè)粒子的速度更新基于所有其他粒子的歷史最優(yōu)位置的綜合學(xué)習(xí)粒子群優(yōu)化算法，使粒子速度更新有了新的方式，達(dá)到了粒子與粒子間綜合學(xué)習(xí)的目的。紀(jì)震等[13]采用反向思維，舍棄了粒子群體優(yōu)勢(shì)，以單粒子更新提出智能單粒子思想，采用降維更新策略，在一定程度上避免了粒子因全局最優(yōu)和當(dāng)前最優(yōu)粒子的影響而陷入局部最優(yōu)，達(dá)到了預(yù)期的效果。

此外，粒子群算法[14]還被用于與其他思想融合而產(chǎn)生的混合算法，有些算法會(huì)產(chǎn)生比較好的性能。比較代表性的思想融合包括：差分演化[15]、混合蛙跳[16]、人工蜂群算法[17]和引力搜索算法[18]等一種或幾種算法思想進(jìn)行融合。

1 標(biāo)準(zhǔn)粒子群算法

在標(biāo)準(zhǔn)PSO算法中，m個(gè)粒子在一個(gè)n維空間中搜索，粒子初始化時(shí)隨機(jī)產(chǎn)生其初始位置，然后按照(1)式和(2)式進(jìn)行更新，直到滿足終止條件。

(1)

(2)

粒子群算法是根據(jù)粒子速度和位置公式來(lái)迭代粒子，從速度和位置公式可以看出，除了隨機(jī)數(shù)和學(xué)習(xí)因子以外，粒子的進(jìn)化方式完全由當(dāng)前粒子的局部最好值和全局最好值來(lái)決定，這導(dǎo)致了粒子進(jìn)化的局部性，指導(dǎo)粒子進(jìn)行更新的信息有限，使得粒子容易陷入局部最優(yōu)，并且很難只借助全局最優(yōu)和當(dāng)前粒子的歷史最優(yōu)值來(lái)跳出局部最優(yōu)。

在標(biāo)準(zhǔn)粒子群算法中有一定數(shù)量的粒子種群，其算法的更新方式單一，只根據(jù)2個(gè)極值來(lái)決定，當(dāng)2個(gè)極值不再更新時(shí)，則當(dāng)前粒子的飛行就受到了嚴(yán)重阻礙，因此，應(yīng)該從根本上通過(guò)改變粒子群算法的單一更新方式來(lái)解決易陷入局部最優(yōu)的問(wèn)題，由于當(dāng)前粒子周?chē)牧Ｗ右部赡芴峁┮欢康男畔ⅲㄟ^(guò)獲取這些信息可以更好地權(quán)衡粒子的進(jìn)化方向，促使粒子擁有更強(qiáng)的逃離局部最優(yōu)的性能。因此，粒子搜索過(guò)程中應(yīng)當(dāng)充分地利用好這些粒子資源從而構(gòu)建一個(gè)粒子網(wǎng)絡(luò)來(lái)協(xié)同更新，或者可以采取在線社會(huì)網(wǎng)絡(luò)中的信息擴(kuò)散模型來(lái)達(dá)到粒子間的信息交流、信息擴(kuò)散和信息影響。

PSO算法在搜索過(guò)程中保持權(quán)值w、學(xué)習(xí)因子c1，c2不變，使得粒子速度并不具有明顯的自適應(yīng)調(diào)整速度的功能，從而無(wú)法適應(yīng)動(dòng)態(tài)變化的環(huán)境，不能真正達(dá)到智能搜索的目的。

通過(guò)分析粒子的適應(yīng)值，利用其在整個(gè)粒子網(wǎng)絡(luò)中的地位來(lái)自適應(yīng)地調(diào)整搜索速度以達(dá)到快速收斂的目標(biāo)。

由于標(biāo)準(zhǔn)的粒子群算法并沒(méi)有配備相應(yīng)的擾動(dòng)操作，這也是經(jīng)典粒子群算法輕松掉入局部極值的另一個(gè)根本緣由，在整個(gè)粒子搜索過(guò)程中并不是每一次都要求搜索到更好的解，而是在陷入局部最優(yōu)時(shí)算法應(yīng)該能自動(dòng)甄別出，并采取相應(yīng)的措施跳出局部最優(yōu)進(jìn)入新的領(lǐng)域繼續(xù)進(jìn)行搜索。

2 粒子群算法改進(jìn)策略

在算法初始化階段引入k-means聚類(lèi)思想和貪心[19]思想用于初始化粒子，在算法更新方式中引入智能單粒子優(yōu)化算法思想，為了更加明智地指導(dǎo)家庭之間的更新，算法中引入在線社會(huì)網(wǎng)絡(luò)信息擴(kuò)散模型，最后為了提高改進(jìn)算法的收斂速度，還引入反向策略和禁忌搜索策略的思想。

2.1 智能單粒子優(yōu)化策略

智能單粒子優(yōu)化算法[13]將更新的基本單位從整個(gè)粒子位置矢量轉(zhuǎn)變?yōu)橐跃S度為基本單位組成的子矢量進(jìn)行更新，并在更新子矢量的同時(shí)，算法會(huì)采取一種自適應(yīng)的學(xué)習(xí)策略，更新速度子矢量受到當(dāng)前粒子位置子矢量歷史搜索結(jié)果的影響，當(dāng)獲得更好的結(jié)果時(shí)，會(huì)給予一定的加速策略，當(dāng)獲得更差的結(jié)果時(shí)，會(huì)給予一定的降速策略，使得算法可以更快速尋到最佳解。

在經(jīng)典粒子群算法中，粒子都被當(dāng)作一個(gè)基本單位進(jìn)行更新，從而忽略了粒子維度的價(jià)值和關(guān)系，本文算法通過(guò)將智能單粒子優(yōu)化算法的降維更新思想結(jié)合家庭概念對(duì)粒子進(jìn)行局部更新，這樣粒子搜索就更具完整性。

2.2 禁忌優(yōu)化策略

禁忌搜索算法是基于區(qū)域搜索的算法，將區(qū)域中搜索出的一部分極值的較好解狀態(tài)作為候選解加入禁忌表，當(dāng)達(dá)到禁忌迭代次數(shù)設(shè)定時(shí)，還沒(méi)有搜索到更好的解，則會(huì)將部分禁忌對(duì)象釋放。禁忌搜索算法中對(duì)周?chē)鷧^(qū)域構(gòu)造的確定至關(guān)重要，因?yàn)榻伤阉鞅旧硪彩菍?duì)周?chē)鷧^(qū)域搜尋的有效提升，周?chē)鷧^(qū)域構(gòu)造的設(shè)定不僅影響解的數(shù)量和形式，還有各個(gè)解之間的聯(lián)系。對(duì)于高維組合優(yōu)化問(wèn)題，由于鄰域的規(guī)模過(guò)于龐大，因此，在禁忌搜索中只會(huì)選取一定鄰域狀態(tài)進(jìn)行求解，并選取少量?jī)?yōu)秀狀態(tài)作為候選解。在實(shí)際求解組合優(yōu)化問(wèn)題時(shí)，對(duì)禁忌長(zhǎng)度的設(shè)定也是至關(guān)重要的，設(shè)置得過(guò)大或者過(guò)小都會(huì)嚴(yán)重影響到算法的進(jìn)程，特赦準(zhǔn)則的存在是為了搜索到最優(yōu)解，禁忌表則是為了增強(qiáng)全局搜索能力。

引入禁忌搜索優(yōu)化算法的思想讓粒子在更新進(jìn)程中更容易跳過(guò)局部極值范圍，對(duì)局部極值范圍保留記錄，并設(shè)定禁忌準(zhǔn)則，使得粒子不會(huì)重復(fù)多次搜索同一區(qū)域，增強(qiáng)了粒子的搜索能力和增大搜索到問(wèn)題最優(yōu)解的概率。

2.3 聚類(lèi)初始化策略

本文引入k-means聚類(lèi)算法用于初始化粒子維度，從而將粒子的所有維度劃分到不同的家庭，以家庭為基本單位對(duì)粒子進(jìn)行更新。k-means算法先從集合中無(wú)規(guī)律地找出k個(gè)點(diǎn)看成中心點(diǎn)，其中，各個(gè)中心點(diǎn)都可以表示為各個(gè)的簇，就像家族中的祖先一樣。然后對(duì)剩余的每個(gè)粒子計(jì)算他們到每個(gè)中心點(diǎn)的距離，再根據(jù)每個(gè)粒子和簇的相似度，即每個(gè)粒子到每個(gè)簇的距離，將粒子賦給當(dāng)前相識(shí)程度最高的簇，這有點(diǎn)類(lèi)似于當(dāng)今社會(huì)一些家族尋源，總是會(huì)首先尋找與自己關(guān)系最近的家族。將調(diào)整以后的家族，重新計(jì)算出一個(gè)家族中心，再計(jì)算剩余粒子到這些新家族中心的距離。再次重新賦給當(dāng)前相識(shí)度最高的簇，當(dāng)達(dá)到調(diào)整閾值或者家族中心不再變化時(shí)終止。

k-means算法可以得到比較有效的分類(lèi)，在本文算法中我們以2個(gè)城市之間的歐氏距離作為相似性的判斷準(zhǔn)則，通過(guò)(3)式可以得到J(ck)，即第k個(gè)類(lèi)中所有點(diǎn)到類(lèi)中心的平方和，再通過(guò)(4)式可以得到所有城市到他們類(lèi)中心的距離之和J(C)，聚類(lèi)目標(biāo)可以使得J(C)最小。

(3)

(4)

(3)—(4)式中：xi為聚簇中的點(diǎn)；uk為第k個(gè)聚簇；ck為族的質(zhì)心；K表示聚簇的數(shù)量。

2.4 基于在線社會(huì)網(wǎng)絡(luò)的優(yōu)化策略

經(jīng)典的粒子群算法的粒子更新手段過(guò)于單一，使得粒子更新的性能受限，只取決于2個(gè)極值，而沒(méi)有考慮周?chē)Ｗ拥淖饔?。為了更好地利用周?chē)Ｗ铀峁┑男畔ⅲ朐诰€社會(huì)網(wǎng)絡(luò)的信息傳播模型，可以更好地指導(dǎo)粒子利用粒子網(wǎng)絡(luò)信息進(jìn)行粒子自身的信息采納方式的決策，指導(dǎo)粒子如何更好利用社會(huì)因素和信息因素使得粒子自身利益最大化，從而提高整個(gè)粒子網(wǎng)絡(luò)的信息質(zhì)量，促使整個(gè)網(wǎng)絡(luò)向最優(yōu)目標(biāo)轉(zhuǎn)移。

用戶(hù)信息可以利用在線社會(huì)網(wǎng)絡(luò)進(jìn)行擴(kuò)散，也可以通過(guò)在線社會(huì)網(wǎng)絡(luò)獲取信息，在粒子群算法中每個(gè)粒子都相當(dāng)在線社會(huì)網(wǎng)絡(luò)中的一個(gè)用戶(hù)，不但需要將自己的家庭信息表擴(kuò)散給周?chē)脩?hù)，也需要獲取周?chē)脩?hù)的家庭交換記錄信息，并將在線社會(huì)網(wǎng)絡(luò)信息擴(kuò)散模型應(yīng)用于指導(dǎo)粒子學(xué)習(xí)由其他粒子擴(kuò)散而來(lái)的家庭關(guān)系表，本文選取博弈論模型來(lái)指導(dǎo)粒子學(xué)習(xí)周?chē)Ｗ蛹彝ソ粨Q記錄信息。

2.5 反向?qū)W習(xí)策略

在2005年，Tizhoosn首次提出反向?qū)W習(xí)策略的概念，通過(guò)對(duì)反向?qū)W習(xí)策略的研究開(kāi)發(fā)，成功將其與差分進(jìn)化算法相融合，也是首次將反向?qū)W習(xí)策略引入群體智能優(yōu)化算法中，并獲得了明顯的改進(jìn)效果[10]。Tizhoosn認(rèn)為智能算法尋找最優(yōu)解本身就具有很高的隨機(jī)性，從算法的初始種群通過(guò)隨機(jī)產(chǎn)生，然后根據(jù)一定的人工策略進(jìn)行不斷的迭代，使得種群向最佳解靠近，最后達(dá)到結(jié)束條件時(shí)獲取最佳解或類(lèi)似最佳解。目前智能算法的起始值都是隨機(jī)產(chǎn)生的，而起始值對(duì)整個(gè)算法的搜索具有非常重要的作用，產(chǎn)生好的隨機(jī)初始種群，能夠促使算法快速搜索到最優(yōu)解或者達(dá)到結(jié)束條件，如果產(chǎn)生的解質(zhì)量太差或者完全與最優(yōu)解相反，則會(huì)導(dǎo)致算法性能下降甚至找不到好解。為了解決這種情況，Tizhoosn提出了反向?qū)W習(xí)策略的概念，當(dāng)算法在解空間進(jìn)行搜索時(shí)， 不僅獲取當(dāng)前解，并將優(yōu)秀的反向解加入搜索種群中，并舍棄當(dāng)前解，智能算法的尋優(yōu)過(guò)程是一種隨機(jī)性的經(jīng)驗(yàn)過(guò)程，種群中的解質(zhì)量越高越有利于搜索到更好的解，從而大大提高算法效率。當(dāng)前解和反向解都有可能作為下一代解，在粒子更新時(shí)，將當(dāng)前解和反向解同等作為候選解，并選出其中具有更好適應(yīng)值的解作為下一代粒子。隨著反向?qū)W習(xí)策略的提出并成功應(yīng)用于差分進(jìn)化算法，其他研究者也將反向?qū)W習(xí)策略與粒子群優(yōu)化算法、蟻群優(yōu)化算法相結(jié)合都產(chǎn)生了很好的效果。

下面將介紹反向?qū)W習(xí)[11]的一些重要概念，如反向數(shù)、反向點(diǎn)、反向優(yōu)化、一般反向?qū)W習(xí)和動(dòng)態(tài)一般反向?qū)W習(xí)。

反向數(shù)的概念：假設(shè)x為實(shí)數(shù)，并且n的取值為[a,b]，則x反向數(shù)值為x′可通過(guò)(5)式獲得。

x′=a+b-x

(5)

反向點(diǎn)的概念：對(duì)應(yīng)每個(gè)點(diǎn)的每個(gè)維度引入反向數(shù)，再將所有維度結(jié)合起來(lái)從而組成反向點(diǎn)。

反向優(yōu)化的概念：假設(shè)適應(yīng)值函數(shù)為f，得到當(dāng)前解的適應(yīng)值為v1，反向點(diǎn)的適應(yīng)值為v2，如果v2優(yōu)于v1，則將反向點(diǎn)加入種群，并刪除當(dāng)前點(diǎn)。

一般反向?qū)W習(xí)的概念：實(shí)數(shù)x∈[a,b],令F=D-x，則有x′=D-x，在此，D是可估量值，則可以得到逆向解x′∈[D-b,D-a]。

D=k(A(t)+B(t))

(6)

3 PSODN算法設(shè)計(jì)

本文提出了一種基于維度近鄰關(guān)系擴(kuò)散的改進(jìn)粒子群優(yōu)化算法(improved particle swarm optimization algorithm based on dimension neighbors diffusion， PSODN)。

3.1 初始化

粒子編碼方式：在解決不同類(lèi)型的問(wèn)題時(shí)，粒子的編碼方式也不相同，本文算法在求解TSP(traveling salesman problem)問(wèn)題時(shí)，對(duì)二維空間中的城市進(jìn)行編號(hào)，每個(gè)編號(hào)唯一映射一個(gè)城市，如數(shù)據(jù)集att48，數(shù)據(jù)集中共有48個(gè)城市，則算法中對(duì)48個(gè)城市分別編碼為1-48。其中，一個(gè)可行解可表示為(1,2,…,48)，即從1開(kāi)始訪問(wèn)到第48個(gè)城市，并回到編號(hào)為1的城市形成一條回路。

粒子的速度：不同于函數(shù)優(yōu)化問(wèn)題，定義域是一個(gè)連續(xù)區(qū)間，組合優(yōu)化問(wèn)題是一類(lèi)非連續(xù)問(wèn)題，因此對(duì)于算法的更新速度需要重新定義，算法中選取遺傳算法的一次交換表示速度為1的移動(dòng)，如擁有5個(gè)城市的一個(gè)數(shù)據(jù)集當(dāng)前得到一個(gè)可行解為(3,5,2,1,4)，并且粒子當(dāng)前的更新速度為1，則粒子可以通過(guò)更新得到10種不同的狀態(tài)，包括(5,3,2,1,4)，(3,5,1,2,4)，(3,5,4,1,2)等狀態(tài)。

粒子的鄰域：鄰域的實(shí)際表現(xiàn)形式也與問(wèn)題類(lèi)型相關(guān)，在組合優(yōu)化問(wèn)題中，我們定義鄰域即為當(dāng)前解通過(guò)交換操作后產(chǎn)生的所有狀態(tài)，即組成當(dāng)前粒子的鄰域。

在解決TSP問(wèn)題時(shí)，假設(shè)擁有n個(gè)城市坐標(biāo)數(shù)據(jù)，C={x1,x2,…,xn}，其中，xi為平面坐標(biāo)數(shù)據(jù)(x,y)。首先，通過(guò) (7) 式得到城市劃分類(lèi)的個(gè)數(shù)K，為了使得劃分出的類(lèi)的個(gè)數(shù)不會(huì)過(guò)多或者過(guò)少影響算法尋優(yōu)效果，因此,需要保證類(lèi)的個(gè)數(shù)。

(7)

通過(guò)隨機(jī)得到K個(gè)城市作為初始類(lèi)中心U，然后將未被選做類(lèi)中心的粒子根據(jù) (8)式得到當(dāng)前測(cè)試的粒子應(yīng)該被歸入哪個(gè)類(lèi)k中，并根據(jù)(9)式對(duì)修改過(guò)的類(lèi)進(jìn)行類(lèi)中心的調(diào)整(即計(jì)算出新的質(zhì)心)。

k=min(dis(z,ui))

(8)

(9)

(8) 式中：z為當(dāng)前ui類(lèi)的質(zhì)心；dis為距離函數(shù)。(9)式中：ui為計(jì)算得到的新質(zhì)心；numk為第k個(gè)類(lèi)的成員個(gè)數(shù)；(xi,yi)為對(duì)應(yīng)類(lèi)成員的坐標(biāo)。

通過(guò)遍歷所有城市，將城市劃分入不同的類(lèi)中，從而得到算法的初始聚類(lèi)，最后通過(guò)從不同的城市出發(fā)并應(yīng)用貪心思想(選取離當(dāng)前城市最近的城市作為下一城市)，先在聚類(lèi)得到的類(lèi)內(nèi)部構(gòu)造路線，然后在類(lèi)間構(gòu)造路線，從而得到最終的初始化粒子。

3.2 更新方式

本文算法粒子的更新方式分為2種形式，分為聚類(lèi)內(nèi)部的更新和聚類(lèi)間的更新。

1)聚類(lèi)內(nèi)部的更新。通過(guò)借鑒智能單粒子優(yōu)化算法的思想進(jìn)行更新，通過(guò)初始化產(chǎn)生的類(lèi)，類(lèi)總數(shù)為k個(gè)，首先通過(guò)(10)式產(chǎn)生每個(gè)類(lèi)的更新速度。

(10)

(10)式中：k為第幾個(gè)類(lèi)；d為迭代次數(shù)；r為[-0.5,0.5]的隨機(jī)數(shù)；p為下降因子；a為多樣性因子；b為加速因子；L由(11)式可以得到，L的取值與更新類(lèi)后取得的適應(yīng)值好壞相關(guān)，如果當(dāng)前得到的適應(yīng)值較上代要差，則會(huì)縮小L，如果當(dāng)前得到的適應(yīng)值更好，則L的取值會(huì)增大。根據(jù)(10)式可以看出v的取值在增大。

(11)

(11)式中：s為收縮因子；x為粒子的位置；xk為粒子的每k個(gè)類(lèi)。

最后通過(guò)(12)式得到粒子的新位置。

(12)

2)聚類(lèi)外部更新。當(dāng)分析類(lèi)的外部更新時(shí)，將每個(gè)類(lèi)作為一個(gè)整體，在初始時(shí)每個(gè)粒子通過(guò)隨機(jī)選擇2個(gè)類(lèi)交換位置，如果產(chǎn)生更好的適應(yīng)值則將此次交換的類(lèi)和優(yōu)化的適應(yīng)值差進(jìn)行記錄。由于粒子存在于整個(gè)粒子網(wǎng)絡(luò)中，每個(gè)粒子自身都攜帶著自身類(lèi)的交換記錄，通過(guò)借鑒在線社會(huì)網(wǎng)絡(luò)信息擴(kuò)散模型的思想，每個(gè)粒子都會(huì)對(duì)周?chē)Ｗ訑y帶的交換記錄進(jìn)行評(píng)估。選擇的標(biāo)準(zhǔn)為首先選擇出自身適應(yīng)值最高的粒子和交換記錄后適應(yīng)值差最大的粒子，然后進(jìn)行概率選擇，兩者都以40%的概率被選中，剩余的20%概率選擇其他交換記錄。如果自身適應(yīng)值最高的粒子沒(méi)有攜帶的交換記錄信息，則將其40%的概率賦予給后者，如果沒(méi)有滿足條件的記錄，則粒子進(jìn)行隨機(jī)交換類(lèi)。

在更新方式上，不僅考慮了局部更新，也兼顧了全局更新，使得粒子的搜索結(jié)果更加優(yōu)秀。

3.3 禁忌策略應(yīng)用

運(yùn)用禁忌搜索的思想對(duì)已經(jīng)搜索過(guò)的局部最優(yōu)值加入禁忌表，不但可以節(jié)省大量的搜索資源，也可以降低群落中的粒子陷入局部最優(yōu)區(qū)域的概率。為了降低種群中的粒子陷入局部最優(yōu)的概率，本文引入禁忌搜索優(yōu)化算法的思想。

在應(yīng)用禁忌策略時(shí)，主要涉及關(guān)鍵參數(shù)和操作的定義，以下為本文算法的定義。

3.3.1 初始解和適應(yīng)值函數(shù)

在禁忌搜索算法中，該算法對(duì)于初始解的敏感度很高。因此，本文通過(guò)上述聚類(lèi)和貪心思想產(chǎn)生的初始解比較優(yōu)秀，可以加快收斂速度。對(duì)適應(yīng)值函數(shù)的確定，即可以得到當(dāng)前解所對(duì)應(yīng)的路徑值，由 (13) 式和(14) 式得到。

(13)

(14)

(13)式中：N為城市的個(gè)數(shù)；xi為城市向量。

3.3.2 鄰域結(jié)構(gòu)和禁忌對(duì)象的確定

本文中，將每個(gè)粒子通過(guò) (11)—(13)式以及粒子的更新操作(每次交換都可以得到一個(gè)鄰域解，故根據(jù)速度大小就可以得到不同數(shù)量的鄰域解)得到一定數(shù)量的可行解，將所有粒子得到的可行解組成禁忌策略中的鄰域結(jié)構(gòu)。

禁忌對(duì)象的記錄通常可以使用明晰記憶和屬性記憶，明晰記憶是記錄完整的當(dāng)前解，而屬性記憶則是記錄當(dāng)前的狀態(tài)變化，雖記錄完整的當(dāng)前解消耗的內(nèi)存資源相對(duì)較多，但是相比屬性記憶可以降低解析狀態(tài)變化的時(shí)間花費(fèi)，因此，算法中選擇明晰記憶方式作為禁忌對(duì)象。

3.3.3 禁忌表和禁忌長(zhǎng)度的確定

選擇隊(duì)列作為存儲(chǔ)禁忌對(duì)象的數(shù)據(jù)結(jié)構(gòu)。為了使得禁忌表的長(zhǎng)度不會(huì)過(guò)大，需要設(shè)置禁忌長(zhǎng)度來(lái)動(dòng)態(tài)釋放禁忌對(duì)象，在算法中禁忌長(zhǎng)度的選擇對(duì)算法的收斂和避免進(jìn)入局部最優(yōu)的循環(huán)起到關(guān)鍵作用。禁忌長(zhǎng)度通?？梢允褂渺o態(tài)設(shè)置和動(dòng)態(tài)設(shè)置2種方案，大量研究表明動(dòng)態(tài)設(shè)置禁忌長(zhǎng)度能提高算法性能，本文根據(jù) (15)—(17) 式來(lái)動(dòng)態(tài)確定當(dāng)前禁忌長(zhǎng)度L。

(15)

L=baseL+f(a)

(16)

(17)

(15)—(17)式中：N為城市規(guī)模,基本的禁忌長(zhǎng)度baseL與城市規(guī)模有關(guān)，隨著城市規(guī)模的增長(zhǎng)禁忌長(zhǎng)度也隨著增長(zhǎng)，而當(dāng)前實(shí)際禁忌長(zhǎng)度L還與函數(shù)f(a)相關(guān)。(17)式中：xd為當(dāng)前解；xd-1為上代解即為禁忌隊(duì)列中最后一個(gè)入隊(duì)的禁忌對(duì)象；m為算法得到的解持續(xù)變好或變差的次數(shù)，當(dāng)解狀態(tài)進(jìn)行跳躍(即解在變好與變差之間切換時(shí))則會(huì)被重置為0。當(dāng)前解優(yōu)化上代解時(shí)，說(shuō)明算法搜索能力強(qiáng)或者可能陷入局部最優(yōu)區(qū)域，因此需要?jiǎng)討B(tài)增大禁忌長(zhǎng)度，從而達(dá)到避免循環(huán)搜索局部區(qū)域的能力，當(dāng)前解劣于上一代時(shí)，通過(guò)適當(dāng)降低禁忌長(zhǎng)度，隨著解的效果越來(lái)越差時(shí)，禁忌長(zhǎng)度下降幅度也會(huì)不斷變大，從而釋放禁忌對(duì)象，重新納入搜索范圍。

3.3.4 特赦準(zhǔn)則和終止準(zhǔn)則

首先是對(duì)特赦準(zhǔn)則的選取，特赦準(zhǔn)則最常用的確定方式是基于適應(yīng)值的原則，當(dāng)從鄰域結(jié)構(gòu)中產(chǎn)生的禁忌候選解優(yōu)于“best so far”狀態(tài)時(shí)，則滿足特赦準(zhǔn)則，將禁忌表中的對(duì)象釋放，并將當(dāng)前禁忌候選解加入禁忌表，并標(biāo)記為新的“best so far”。終止準(zhǔn)則主要涉及2個(gè)條件：①通過(guò)設(shè)定最大迭代次數(shù)；②設(shè)定禁忌對(duì)象被禁忌頻率閾值。當(dāng)?shù)_(dá)到設(shè)定的最大迭代次數(shù)時(shí)算法近似收斂結(jié)束，或者當(dāng)某個(gè)禁忌對(duì)象被禁忌的頻率達(dá)到設(shè)定的最大值時(shí)，算法也會(huì)結(jié)束，說(shuō)明算法已經(jīng)收斂到最優(yōu)區(qū)域。

3.4 反向策略應(yīng)用

根據(jù) (18)—(20) 式可以計(jì)算出反向點(diǎn)x*為

(18)

(19)

(20)

通過(guò)反向策略得到的反向粒子與當(dāng)前粒子進(jìn)行比較，如果反向粒子優(yōu)于當(dāng)前粒子則用反向粒子替換當(dāng)前粒子。

3.5 算法流程

先對(duì)粒子進(jìn)行初始化，由于禁忌搜索算法對(duì)初始解的敏感度很高，因此，算法初始化階段，通過(guò)聚類(lèi)思想和貪心思想產(chǎn)生了比較優(yōu)秀的初始粒子。

算法更新階段。主要分為2個(gè)方向進(jìn)行：粒子內(nèi)部更新和粒子類(lèi)外部更新。在粒子內(nèi)部更新時(shí)，通過(guò) (10) 式可以得到對(duì)應(yīng)的速度子矢量，將速度子矢量用于類(lèi)的更新，更新過(guò)程中應(yīng)用反向策略得到反向粒子，并比較當(dāng)前粒子與反向粒子的優(yōu)劣，進(jìn)行相應(yīng)替換；在粒子類(lèi)外部更新時(shí)，粒子會(huì)通過(guò)周?chē)Ｗ討?yīng)用類(lèi)外部更新策略對(duì)粒子進(jìn)行更新，并應(yīng)用反向策略得到反向粒子，并比較當(dāng)前粒子與反向粒子的優(yōu)劣，進(jìn)行相應(yīng)的替換。

當(dāng)算法完成更新后，通過(guò)在更新階段得到的所有鄰域解中選出一個(gè)不在禁忌表中并且適應(yīng)值最優(yōu)秀的粒子作為禁忌候選對(duì)象，當(dāng)禁忌候選對(duì)象滿足特赦準(zhǔn)則，即當(dāng)前得到的禁忌候選對(duì)象優(yōu)于“best so far”狀態(tài)，則將禁忌表清空，將禁忌候選對(duì)象加入禁忌表，并設(shè)置其為新的“best so far”狀態(tài)。如果禁忌候選對(duì)象不滿足禁忌準(zhǔn)則，則根據(jù)更改禁忌表中對(duì)象的禁忌長(zhǎng)度屬性，并通過(guò)分析當(dāng)代解與其歷史解的更新情況，通過(guò) (15)—(17) 式更新禁忌長(zhǎng)度。

最后判斷當(dāng)前狀態(tài)是否滿足終止準(zhǔn)則，即是否達(dá)到最大迭代次數(shù)，或者某個(gè)禁忌對(duì)象被禁忌的頻率達(dá)到閾值。

具體流程如下。

Step1通過(guò)(7)式確定聚類(lèi)的參數(shù)K，通過(guò)聚類(lèi)思想和貪心思想初始化粒子，并記錄分類(lèi)情況；

Step2計(jì)算粒子適應(yīng)值，作為初始解，并初始化禁忌表；

Step3通過(guò) (11)—(13) 式對(duì)類(lèi)內(nèi)部進(jìn)行更新，并應(yīng)用 (18)—(20) 式產(chǎn)生反向粒子，并確定當(dāng)前粒子是否被替換；

Step4通過(guò)類(lèi)外部更新策略對(duì)類(lèi)外部進(jìn)行更新，并應(yīng)用 (18)—(20) 式產(chǎn)生反向粒子，并確定當(dāng)前粒子是否被替換；

Step5從產(chǎn)生的鄰域解中，找出不在禁忌表中最優(yōu)秀的禁忌候選解，判定是否滿足特赦準(zhǔn)則，如果滿足特赦準(zhǔn)則，清空禁忌表，設(shè)置新的“best so far”狀態(tài)，并將對(duì)象加入禁忌表，否則，先修改禁忌對(duì)象的禁忌長(zhǎng)度屬性，然后通過(guò) (13)— (15) 式更新禁忌表長(zhǎng)度；

Step6滿足終止準(zhǔn)則，算法結(jié)束；否則返回Step 3。

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

為驗(yàn)證所提出的改進(jìn)算法性能，本文選取了旅行商問(wèn)題和帶容量約束的車(chē)輛路徑問(wèn)題作為實(shí)驗(yàn)數(shù)據(jù)。實(shí)驗(yàn)仿真環(huán)境：1.66 GHz主頻的Intel處理器，1.49 GB內(nèi)存，Microsoft Windows XP，仿真軟件 Eclipse 3.6.2SDK。

實(shí)驗(yàn)中對(duì)att48，eil51，eil76設(shè)置種群粒子數(shù)為30，最大迭代次數(shù)為100；對(duì)rat99，korA100，eil101，pr107設(shè)置種群粒子數(shù)為50，最大迭代次數(shù)為200；對(duì)bier127，ch130，ch150設(shè)置種群粒子數(shù)70，最大迭代次數(shù)為500；對(duì)kroA200設(shè)置種群粒子數(shù)為100，最大迭代次數(shù)為1 000。

由于在標(biāo)準(zhǔn)TSPLIB(TSP library)數(shù)據(jù)集中，以平面坐標(biāo)來(lái)標(biāo)示一個(gè)城市，在實(shí)驗(yàn)結(jié)果圖中的橫縱坐標(biāo)即為坐標(biāo)軸的XY，而2個(gè)城市之間的花費(fèi)即為2個(gè)城市之間的歐氏距離。

表1是將本文算法用于求解標(biāo)準(zhǔn)TSPLIB數(shù)據(jù)集中部分問(wèn)題的求解結(jié)果，并將得到的結(jié)果與貪心算法(greedy algorithm,GRA)、改進(jìn)貪心算法(improved greedy algorithm,IMGRA)和蟻群算法(ant colony system,ACS)進(jìn)行比較。表1中給出了該問(wèn)題的實(shí)際最優(yōu)解(optimum solution,opt)進(jìn)行對(duì)比，從表1中可以看出，本文算法得到的最優(yōu)解與實(shí)際最優(yōu)解的誤差都比較小，其他3種算法求解結(jié)果的精確度都低。從表1中還可以看出，GRA求解TSP問(wèn)題時(shí)所得到的結(jié)果相比其他幾種算法的誤差是最大的，主要是因?yàn)镚RA在求解TSP問(wèn)題時(shí)易陷入局部最優(yōu)，從而搜索不到最優(yōu)解，IMGRA相對(duì)GRA的求解結(jié)果有一定的改進(jìn)，而ACS的求解結(jié)果對(duì)比IMGRA有比較大的優(yōu)勢(shì)，ACS用于求解最短路徑問(wèn)題有一定的優(yōu)勢(shì)。

表1 不同算法求解部分TSPLIB結(jié)果比較Tab.1 Comparison of partial TSPLIB results by different algorithms

表2和表3是將本文算法求解結(jié)果與GRA，IMGRA，ACS以及文獻(xiàn)[20]提出的DPSO(discrete particle swarm optimization)和HDPSO(hybrid discrete particle swarm optimization)算法進(jìn)行比較，本文所提策略效果較好。

表2 eil51數(shù)據(jù)多種算法求解結(jié)果比較Tab.2 Comparison of eil51 results by different algorithms

表3 korA100數(shù)據(jù)多種算法求解結(jié)果比較Tab.3 Comparison of korA100 results by different algorithms

圖1是標(biāo)準(zhǔn)PSO算法與本文算法求解數(shù)據(jù)集收斂時(shí)間的對(duì)比。從圖1中可以明顯地看出,本文算法的求解速度優(yōu)于標(biāo)準(zhǔn)PSO算法，可見(jiàn)，本文算法引入的禁忌搜索機(jī)制和反向策略能夠幫助算法跳出局部最優(yōu)區(qū)域，使得粒子更少地在已經(jīng)搜索過(guò)的區(qū)域進(jìn)行重復(fù)搜索，從而提高搜索資源的利用率和加快算法收斂。

圖1 收斂速度比較圖Fig.1 Convergence speed of comparison diagram

此外，我們還將本文提出的算法用于求解標(biāo)準(zhǔn)測(cè)試集Augerat et al.Set A中的A-n32-k5等9個(gè)測(cè)試數(shù)據(jù)，并將實(shí)驗(yàn)結(jié)果與其他經(jīng)典算法進(jìn)行比較分析。圖2為本文算法與標(biāo)準(zhǔn)PSO算法、蟻群算法的求解CVRP(capacitated vehicle routing problem)問(wèn)題數(shù)據(jù)集結(jié)果的折線圖。從圖2中可以看出，本文算法有明顯的改進(jìn)效果。

圖2 求解CVRP結(jié)果對(duì)比圖Fig.2 Results comparison of solving CVRP diagram

5 結(jié) 論

大多智能優(yōu)化算法的改進(jìn)算法在更新粒子位置時(shí)，都是將粒子的所有維度作為一個(gè)整體進(jìn)行更新，從而得到一個(gè)更好的適應(yīng)值。但是，這種傳統(tǒng)的更新方式無(wú)法考慮到粒子每個(gè)維度所具有的價(jià)值，粒子不僅應(yīng)該具有對(duì)外的適應(yīng)價(jià)值，也應(yīng)該具有自身的內(nèi)在價(jià)值。本文引入智能單粒子優(yōu)化算法降維更新的思想對(duì)粒子分析的基本單位從粒子到粒子維度的轉(zhuǎn)變。智能單粒子優(yōu)化算法采用與傳統(tǒng)粒子群優(yōu)化算法不同的勘探思路，放棄對(duì)種群的依賴(lài)，而使用一個(gè)個(gè)體在空間中勘探，傳統(tǒng)粒子群優(yōu)化算法的更新思路是將粒子的所有維數(shù)作為一個(gè)整體進(jìn)行更新，這樣會(huì)導(dǎo)致當(dāng)前解中的一部分維度與最優(yōu)解已經(jīng)相當(dāng)接近或者已經(jīng)是最優(yōu)，但是更新策略將整體進(jìn)行更新，導(dǎo)致本來(lái)已經(jīng)接近最優(yōu)解的維度又遠(yuǎn)離了。本文將粒子的所有維度進(jìn)行劃分形成子矢量(即本文中的家庭)。通過(guò)算法初始化時(shí)運(yùn)用k-means算法對(duì)粒子分量應(yīng)用聚類(lèi)，對(duì)于TSP問(wèn)題經(jīng)觀察發(fā)現(xiàn)家庭初始大小取為3的效果比較好，由于2點(diǎn)之間的調(diào)整至少需要另外一個(gè)點(diǎn)。當(dāng)家庭之間的好感度達(dá)到一定程度時(shí)，將會(huì)被重組成大家庭。當(dāng)算法對(duì)粒子進(jìn)行更新時(shí)，除了會(huì)按照訪問(wèn)概率對(duì)家庭間進(jìn)行交流還會(huì)對(duì)家庭內(nèi)部進(jìn)行調(diào)整，家庭內(nèi)部進(jìn)行調(diào)整是對(duì)局部進(jìn)行改變，家庭之間進(jìn)行交流是對(duì)粒子所有維度之間的調(diào)整，不僅利用了家庭內(nèi)維度關(guān)系更加密切進(jìn)行更新，同時(shí)也兼顧了家庭之間的交流從而組成更大的家庭。按照算法的迭代是趨于將粒子的所有維度合并為一個(gè)大家庭，算法迭代前期粒子維度的家庭數(shù)量會(huì)相對(duì)可以提供更多的信息，后期家庭數(shù)量的減少增強(qiáng)了粒子家庭內(nèi)部調(diào)整的力度，提供了更準(zhǔn)確的搜索。

參考文獻(xiàn)：

[1] KENNEDY J, EBERHART R C. Particle Swarm Optimization [C]//Proc IEEE International Conference on Neural Networks. Piscataway, NJ: IEEE Service Center, 1995: 1942-1948.

[2] 何莉,王淼,李博.面向單目標(biāo)優(yōu)化的集成粒子群算法 [J].重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版, 2017, 29(4):527-534.

HE Li，WANG Miao，LI Bo. Ensemble particle swarm optimizer for single objective optimization [J].Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2017, 29(4):527-534.

[3] 易云飛,林郭隆,董文永,等.一種基于粒子優(yōu)勢(shì)分析的異步混合粒子群算法[J].小型微型計(jì)算機(jī)系統(tǒng), 2015,36(6):1379-1383.

YI Yunfei, LIN Guolong, DONG Wenyong, et al. A Hybrid Particle Swarm Optimization Algorithm Based on Asynchronous Advantage Analysis of Particle [J]. Journal of Chinese Computer Systems, 2015, 36(6): 1379-1383.

[4] GONG Maoguo, WU Yue. Discrete particle swarm optimization for high-order graph matching[J].Information Sciences, 328, 2016:158-171.

[5] DONG Wenyong, ZHOU Mengchu. A Supervised Learning and Control Method to Improve Particle Swarm Optimization Algorithms[J]. IEEE Transactions on systems and cybernets, 2016, PP(99):1-14.

[6] SHI Yuhui, EBERHART R C. A modified particle swarm optimizer[C]// Proceedings of the IEEE World Congress on Computational Intelligence. Berlin Heidelberg: Springer, 1998: 69-73.

[7] SHI Yuhui, EBERHART R C. Fuzzy adaptive particle swarm optimization [C]// Proceedings of the IEEE Congress on Evolutionary Computation. Seoul, Korea: IEEE, 2001:101-106.

[8] PERAM T, VEERAMACHANENI K, MOHAN C K. Fitness-distance-ratio based particle swarm optimization [C]//Proceedings of the Swarm Intelligence Symposium. Indianapolis, Indiana, USA:[s.n.], 2003:174-181.

[9] van den BERGH F, ANDRIES P. A cooperative approach to particle swarm optimization[J].IEEE Trasactions on Evolutionary Computation, 2004, 8(3):225-239.

[10] TIZHOOSH H R. Opposition based learning: A new scheme for machine intelligence[C]//Proceedings of the International Conference on Computational Intelligence for Modelling, Control and Automation-CIMCA. Vienna, Austria: IEEE, 2005:695- 701.

[11] 喻飛,李元香,魏波,等.透鏡成像反向?qū)W習(xí)策略在粒子群算法中的應(yīng)用[J].電子學(xué)報(bào),2014,2(42):230- 235.

YUFei, LI Yuanxiang, WEI Bo, et al. The Application of a Novel OBL Based on Lens Imaging Principle in PSO[J].Chinese Journal of Electronics, 2014, 42(2): 230-235.

[12] LIANG Jing, SUGANTHAN P N, DEB K. Novel composition test functions for numerical global opti mization[C]//Proceedings of the IEEE International Swarm Intelligence Symposium. Messina, Italy: IEEE, 2005:68-75.

[13] 紀(jì)震,周家銳,廖惠連,等.智能單粒子優(yōu)化算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(3): 556- 561.

JI Zhen, ZHOUJiarui, LIAO Huilian. A Novel Intelligent Single Particle Optimizer[J].Chinese Journal of Computers, 2010,33(3):556- 561.

[14] 易云飛,苗劍,林郭隆,等.基于牛頓力學(xué)和博弈論模型的粒子網(wǎng)絡(luò)優(yōu)化算法[J].山東大學(xué)學(xué)報(bào)：工學(xué)版, 2017, 47(1): 27-36.

YI Yunfei, MIAO Jian, LIN Guolong, et al. Particle network optimization algorithm based on Newtonian mechanics and game theory model[J]. Journal of Shandong University: Engineering Science, 2017, 47(1): 27-36.

[15] DAS S, SUGANTHAN P N. Differential evolution: A survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1):4-31.

[16] EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithm[J]. J of water Resources Planning and Management, 2003,129(3): 210-225.

[17] KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm [J]. Journal of Global Optimization, 2007, 39(3):459-471.

[18] RASHEDI E, NEZAMABADI-POUR H. A Gravitational Search Algorithm[J]. Information Science, 2009,179 (13):2232-2248.

[19] 饒衛(wèi)振,金淳,陸林濤.考慮邊位置信息的求解ETSP問(wèn)題改進(jìn)貪婪算法[J].計(jì)算機(jī)學(xué)報(bào), 2013, 36(4):836-850.

RAO Weizhen, JIN Chun, LU Lintao. An Improved Greedy Algorithm with information of Edges’ Location for Solving the Euclidean Traveling Salesman Problem[J]. Chinese Journal of Computers, 2013, 36(4): 836-850.

[20] 鄭偉,王磊,曹建蜀.改進(jìn)DPSO算法求解仿真任務(wù)調(diào)度問(wèn)題[J].信號(hào)處理, 2015,31(4):474-482.

ZHENG Wei, WANG Lei, CAO Jianshu. Apply Modified Discrete Particle Swarm Optimization Algorithm to Solve Simulation Task Scheduling[J]. Journal of signal processing, 2015, 31(4):474-482.