蟻群算法中基于分布估計(jì)的量子信息素控制研究

翟亞紅，徐龍艷

（湖北汽車(chē)工業(yè)學(xué)院電氣與信息工程學(xué)院，湖北十堰442002）

0 引 言

蟻群算法已發(fā)展成為求解復(fù)雜優(yōu)化問(wèn)題的有效工具，但由于其信息素控制方法主要是面向離散問(wèn)題設(shè)計(jì)的，故難以對(duì)連續(xù)優(yōu)化問(wèn)題進(jìn)行高效求解。因此，研究人員提出了一些新的信息素表示方法，其中基于可行解的信息素表示是常見(jiàn)的一種方法［1］。該方法特點(diǎn)是結(jié)構(gòu)及控制過(guò)程相對(duì)簡(jiǎn)單，曾作為蟻群算法求解連續(xù)優(yōu)化問(wèn)題的主要解決方案。但這種依靠若干個(gè)可行解的信息素駐留方式，限制了螞蟻搜索的視野，容易使蟻群算法陷入局部最優(yōu)解。Krzysztof Socha與Dorigo共同提出了一種面向連續(xù)問(wèn)題的基于分布估計(jì)的信息素模型［2］，是對(duì)連續(xù)問(wèn)題求解比較流行的另一種方法，它所采用的分布估計(jì)方法能夠從宏觀角度把握進(jìn)化方向，有助于提高對(duì)螞蟻搜索的全局搜索能力。然而，由于其概率模型比較單一，缺乏對(duì)螞蟻搜索的多樣性指導(dǎo)，亦容易使蟻群算法陷入局部最優(yōu)解。

在蟻群算法中，信息素是實(shí)現(xiàn)群集智能的關(guān)鍵，是人工螞蟻實(shí)現(xiàn)間接通信、完成群體協(xié)作的重要媒介。已有的研究表明，信息素的留存、初始化、播撒及揮發(fā)等控制策略，在很大程度上影響著蟻群算法的優(yōu)化性能。因此，進(jìn)一步優(yōu)化信息素控制策略，對(duì)于改善蟻群算法的優(yōu)化性能、擴(kuò)展其應(yīng)用領(lǐng)域，具有重要的研究?jī)r(jià)值和現(xiàn)實(shí)意義?；谡n題組的前期工作，本文以信息素控制策略為研究重點(diǎn)，通過(guò)引入分布估計(jì)方法以及量子態(tài)疊加機(jī)制等，對(duì)蟻群算法在連續(xù)問(wèn)題求解中的信息素控制方法進(jìn)行新的探索。

1 量子態(tài)疊加原理與分布估計(jì)算法

1.1 量子態(tài)疊加原理

微觀粒子所處的狀態(tài)即量子態(tài)具有疊加特性，一個(gè)量子態(tài)可以由態(tài)空間中的多個(gè)基態(tài)線性疊加而成。量子態(tài)疊加示意圖如圖1所示。

Kuk－Hyun Han等人提出的量子進(jìn)化算法是目前為止求解組合優(yōu)化問(wèn)題中最有效的量子進(jìn)化算法之一。與普通的進(jìn)化算法相比，該算法可以在提高搜索多樣性的同時(shí)降低群體規(guī)模，避免了算法陷入局部最優(yōu)解。

文獻(xiàn)［3，4］通過(guò)引入量子比特、量子旋轉(zhuǎn)門(mén)及量子非門(mén)等技術(shù)，提出了一種用于求解連續(xù)優(yōu)化問(wèn)題的連續(xù)量子蟻群算法（continuous quantum ant colony algorithm，CQACA）。該算法使用一組量子比特的概率幅表示螞蟻當(dāng)前位置，螞蟻采用量子旋轉(zhuǎn)門(mén)、非門(mén)等方法對(duì)量子比特進(jìn)行操作，實(shí)現(xiàn)位置移動(dòng)。實(shí)驗(yàn)顯示該算法體現(xiàn)了量子計(jì)算的高效性，但限制了螞蟻的全局尋優(yōu)能力，導(dǎo)致該算法的求解精度較差。量子比特示意圖如圖2所示。

圖2 量子比特

1.2 分布估計(jì)算法

近年來(lái)新興起了一種隨機(jī)優(yōu)化算法即分布估計(jì)算法（estimation of distribution algorithm，EDA）［5］，它將統(tǒng)計(jì)學(xué)與傳統(tǒng)的遺傳算法相結(jié)合，成為當(dāng)前計(jì)算領(lǐng)域的研究熱點(diǎn)。分布估計(jì)算法與傳統(tǒng)的遺傳算法的基本流程如圖3所示。

圖3 分布估計(jì)算法與遺傳算法的基本流程

分布估計(jì)算法能夠從宏觀角度把握進(jìn)化的趨勢(shì)，因此能夠在求解連續(xù)優(yōu)化問(wèn)題時(shí)很好的從全局角度搜索最優(yōu)路徑。受其啟發(fā)，Socha和Dorigo合作提出了一種基于分布估計(jì)的信息素模型［2］，使用描述最優(yōu)解在空間分布的概率估計(jì)模型表示信息素，以改善蟻群算法在求解連續(xù)優(yōu)化問(wèn)題時(shí)信息素表示能力的不足。通過(guò)人工螞蟻對(duì)信息素進(jìn)行隨機(jī)采樣創(chuàng)建可行解，并以所創(chuàng)建解的信息作為依據(jù)更新信息素。經(jīng)過(guò)實(shí)驗(yàn)證明，這種基于分布估計(jì)的信息素模型，在很大程度上能夠改善螞蟻在連續(xù)空間上的全局搜索能力，能夠有效提高蟻群算法在求解連續(xù)問(wèn)題時(shí)的整體優(yōu)化性能。不過(guò)，該模型還存在著一些不足，主要表現(xiàn)在信息素更新過(guò)程中的大量排序工作耗費(fèi)了較大的計(jì)算代價(jià)，并且表示信息素的概率模型較單一而限制了螞蟻搜索的多樣性等方面。

2 分布估計(jì)的量子信息素模型及其蟻群算法

本文將分布估計(jì)算法和量子態(tài)疊加機(jī)制思想相結(jié)合，設(shè)計(jì)了一種面向連續(xù)優(yōu)化問(wèn)題的基于分布估計(jì)的量子信息素模型（quantum pheromone and its control strategy based on estimation of distribution，QPED）及其蟻群算法。

2.1 分布估計(jì)的量子信息素模型基本框架

基于分布估計(jì)的量子信息素模型的基本框架如圖4所示。其中，量子信息素Ψ被看作一個(gè)量子態(tài)疊加，由k個(gè)量子基態(tài)Ψi（i＝1，2，…，k）按照量子態(tài)疊加原理線性疊加而成。

圖4 基于分布估計(jì)的量子信息素模型

每個(gè)量子基態(tài)Ψi采用簡(jiǎn)單的正態(tài)分布表示，ci為Ψi的疊加系數(shù)，分別是其期望值和方差，表示基態(tài)Ψi第j維的正態(tài)分布。

每個(gè)量子基態(tài)Ψi由一個(gè)描述最優(yōu)解在空間中分布的概率模型表示，如下所示

2.2 量子信息素的數(shù)據(jù)結(jié)構(gòu)

量子信息素的數(shù)據(jù)結(jié)構(gòu)采用數(shù)組表示，如圖5所示。采用一個(gè)大小為k×（n＋1）的數(shù)組（k為量子信息素的基態(tài)個(gè)數(shù)，n為解空間維數(shù)），存儲(chǔ)量子信息素Ψ的主要信息。其中，第i行用來(lái)表示基態(tài)Ψi的有關(guān)信息，包括其疊加系數(shù)ci，各維的分布期望值μij。

量子信息素中各正態(tài)分布的方差取值十分重要，如果取值過(guò)大，則螞蟻搜索范圍過(guò)與廣泛，缺乏針對(duì)性，便會(huì)降低蟻群算法的收斂速度；反之，如果取值過(guò)小，則螞蟻搜索范圍會(huì)過(guò)窄，容易使算法陷入局部最優(yōu)狀態(tài)。基于以上考慮，引入了一種自適應(yīng)方差計(jì)算方法，如下所示

為了提高螞蟻之間通信的時(shí)效性，增強(qiáng)群體的協(xié)作能力，采用了在線計(jì)算的原則進(jìn)行方差值計(jì)算，即只有在螞蟻創(chuàng)建解的過(guò)程中需要用到某正態(tài)分布時(shí)，才對(duì)其進(jìn)行方差計(jì)算。

圖5 量子信息素模型的數(shù)據(jù)結(jié)構(gòu)

2.3 分布估計(jì)的量子蟻群算法

基于量子信息素模型和分布估計(jì)算法，提出了一種基于分布估計(jì)的量子蟻群算法（quantum－inspired ant colony optimization for continuous domain，QACOC），QACOC算法包括螞蟻創(chuàng)建解和信息素更新兩個(gè)方面，其算法流程描述如下:

根據(jù)各基態(tài)的疊加系數(shù)從量子信息素中選取一個(gè)量子基態(tài)Ψi；

根據(jù)基態(tài)和所計(jì)算的方差序列，隨機(jī)采L個(gè)樣本；

從L個(gè)樣本中選取最優(yōu)的一個(gè)作為該只螞蟻創(chuàng)建的解Xant保留；｝

2.3.1 螞蟻創(chuàng)建解

螞蟻根據(jù)各量子基態(tài)疊加系數(shù)ci從量子信息素Ψ中選取一個(gè)量子基態(tài)Ψi作為采樣對(duì)象，計(jì)算該基態(tài)的各維分布的方差。然后，對(duì)該基態(tài)各維上的正態(tài)分布進(jìn)行隨機(jī)采樣，計(jì)算出問(wèn)題的可行解。在采樣過(guò)程中，個(gè)別采樣值可能會(huì)超出定義域范圍，使其計(jì)算得到的解成為非可行解。為避免此種情況發(fā)生，保證螞蟻在每次采樣后都能獲得可行解，算法中對(duì)超越定義域范圍的采樣值采用反彈法［6－8］進(jìn)行處理，保證采樣值不超出定義域范圍。反彈法算法描述如下:

2.3.2 信息素更新

量子信息素的更新操作主要包括期望值和疊加系數(shù)更新兩個(gè)方面。首先，螞蟻將自己創(chuàng)建的可行解Xant與采樣對(duì)象基態(tài)Ψi的期望值序列Ui＝（μi1，…，μin）進(jìn)行對(duì)比，如果F（Xant）優(yōu)于F（Ui），則另Ui＝Xant，否則，不做任何操作。其次，為了避免螞蟻過(guò)度集中地選擇某一基態(tài)，在螞蟻完成更新期望值序列后，根據(jù)ci＝ci×ρ（ρ為疊加系數(shù)的更新參數(shù)，0≤ρ≤1），更新其采樣對(duì)象Ψi的疊加系數(shù)。另外在每次迭代開(kāi)始時(shí)可將基態(tài)的疊加系數(shù)都設(shè)為1.0，從而增強(qiáng)信息素對(duì)螞蟻搜索的多樣性和全局性。

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

本文從收斂性能和求解精度兩個(gè)方面對(duì)QACOC和ACOR［2］算法進(jìn)行了實(shí)驗(yàn)分析，算法性能測(cè)試采用3種常用的連續(xù)函數(shù)實(shí)現(xiàn)［9，10］。表1給出了3種函數(shù)的表達(dá)式及其定義域。

表1 評(píng)價(jià)函數(shù)

3.1 收斂性能分析

QACOC和ACOR算法在f1，、f2和f3這3個(gè)評(píng)價(jià)函數(shù)上的收斂趨勢(shì)如圖6所示。其中，縱坐標(biāo)表示函數(shù)值，橫坐標(biāo)表示函數(shù)對(duì)比次數(shù)，即在算法運(yùn)行中對(duì)解的目標(biāo)函數(shù)值進(jìn)行對(duì)比的次數(shù)。采樣這項(xiàng)指標(biāo)，可以避免因?qū)嶒?yàn)人員的主觀因素（如編程習(xí)慣等）對(duì)算法評(píng)價(jià)時(shí)造成客觀性的影響。

圖6中的曲線，表示了QACOC和ACOR兩種算法隨函數(shù)對(duì)比次數(shù)增加的收斂趨勢(shì)。其中，由“◆”標(biāo)記的深色曲線是QACOC算法的收斂曲線走勢(shì)；由“■”標(biāo)記的淺色曲線是ACOR算法的收斂曲線走勢(shì)。顯而易見(jiàn)，在3個(gè)函數(shù)實(shí)例上，QACOC算法的收斂速度均明顯優(yōu)于ACOR算法。例如，在f1函數(shù)上，QACOC算法獲得小于0.1的解需要160次函數(shù)對(duì)比，而ACOR算法需要340次；在f2上，QACOC算法只耗費(fèi)240次函數(shù)對(duì)比就能得到小于0.1的解，ACOR算法需要740次；同樣，在f3上，QACOC算法只需要120次函數(shù)對(duì)比就能得到小于0.05的解，而ACOR算法需要280次。

實(shí)驗(yàn)結(jié)果表明，QACOC算法的收斂速度明顯優(yōu)于ACOR算法。其原因是QACOC算法量子信息素在更新過(guò)程中不需要排序，節(jié)省了大量的排序時(shí)間，而ACOR算法將大量時(shí)間花費(fèi)在了信息素更新的排序上，降低了算法的執(zhí)行效率。

圖6 兩種算法的收斂情況

3.2 求解精度分析

對(duì)算法的求解精度進(jìn)行比較，目的是為了研究算法的全局搜索性能，從而驗(yàn)證算法是否具有避免陷入局部最優(yōu)解的控制能力。讓QACOC和ACOR兩種算法每次都運(yùn)行足夠長(zhǎng)時(shí)間，然后對(duì)它們每次運(yùn)行所獲得的解進(jìn)行統(tǒng)計(jì)分析，得出的結(jié)果見(jiàn)表2。其中α表示獲得最優(yōu)解0.0的次數(shù)，ω為20次解的平均值，Good為最佳解，Bad為最壞解。

對(duì)表2中數(shù)據(jù)進(jìn)行分析可知，在簡(jiǎn)單的單極值函數(shù)f1上，QACOC和ACOR算法在20次運(yùn)行過(guò)程中均能夠獲得最優(yōu)解0.0。但在復(fù)雜的多極值函數(shù)上，兩種算法的求解精度卻相差較大。例如在f2函數(shù)上，QACOC算法20次都能獲得最優(yōu)解0.0，而ACOR算法只獲得了18次最優(yōu)解；而在f3函數(shù)上，QACOC算法能獲得19次最優(yōu)解，而ACOR算法僅獲得最優(yōu)解4次。

由表2可知，QACOC算法的求解精度相對(duì)于ACOR算法具良好的總體性能，耗費(fèi)較小的計(jì)算成本便能獲得更精確的解，表明其具有更好的全局搜索能力。實(shí)驗(yàn)結(jié)果表明，基于分布估計(jì)的量子信息素模型是一種高效合理的信息素控制方法。

表2 求解精度對(duì)比

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

融合分布估計(jì)和量子態(tài)的疊加機(jī)制，本文提出了一種基于分布估計(jì)的量子信息素控制策略。新的信息素控制策略既具有分布估計(jì)算法的宏觀優(yōu)化特點(diǎn)，又具有量子態(tài)疊加機(jī)制的多樣性。實(shí)驗(yàn)結(jié)果表明，量子態(tài)疊加特性和分布估計(jì)方法相結(jié)合的信息素控制策略可以有效避免蟻群算在法求解連續(xù)問(wèn)題時(shí)使其陷入局部最優(yōu)，提高了螞蟻搜索的多樣性和全局引導(dǎo)能力。新信息素模型的引入能夠幫助蟻群算法對(duì)連續(xù)問(wèn)題具有較好的優(yōu)化能力，耗費(fèi)較小的計(jì)算代價(jià)便可獲得更精確的解。

［1］Toksari M Duran.Ant colony optimization for finding the global minimum［J］.Applied Mathematics and Computation，2006，126（1）:308－316.

［2］Socha K，Dorigo M.Ant colony optimization for continuous domains［J］.European Journal of Operational Research，2008，185（3）:1155－1173.

［3］LI Panchi，LI Shiyong.Quantum ant colony algorithm for continuous space optimization［J］.Control Theory ＆Applica－tions，2008，25（2）:237－241（in Chinese）.［李盼池，李士勇.求解連續(xù)空間優(yōu)化問(wèn)題的量子蟻群算法［J］.控制理論與應(yīng)用，2008，25（2）:237－241.］

［4］CEN Yusen，XIONG Fangmin，ZENG Biqing.Ant colony algorithm based on new pheromone updated strategy［J］.Application Research of Computers，2010，27（6）:2080－2083（in Chinese）.［岑宇森，熊芳敏，曾碧卿.基于新型信息素更新策略的蟻群算法［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（6）:2080－2083.］

［5］ZHOU Shude，SUN Zengqi.A survey on estimation of distribution algorithms［J］.Acta Automatica Sinica，2007，33（2）:113－124（in Chinese）.［周樹(shù)德，孫增圻.分布估計(jì)算法綜述［J］.自動(dòng)化學(xué)報(bào)，2007，33（2）:113－124.］

［6］Andre V Abs da Cruz，Marley M B R Vellasco，Marco Aurelio C Pacheco.Quantum－inspired evolutionary algorithm for numerical optimization［C］//IEEE Congress on Evolutionary Computation，Vancouver，2007:2630－2637.

［7］Yan W，Xiaoyue F，Yanxin H，et al.A novel quantum swarm evolutionary algorithm and its application［J］.Neurocomputing，2007，70（4－6）:633－640.

［8］LI Shiyong，LI Panchi.Quantum computing and quantum optimization algorithm［M］.Harbin:Harbin Industrial University Press，2009:108－116（in Chinese）.［李士勇，李盼池.量子計(jì)算與量子優(yōu)化算法［M］.哈爾濱:哈爾濱工業(yè)大學(xué)大學(xué)出版社，2009:108－116.］

［9］Dorigo M，Birattari M，Stutzle T.Ant colony optimization:Artificial ants as a computational intelligence technique［J］.IEEE Computational Intelligence Magazine，2006（11）:28－39.

［10］Dorigo M，Stutzle T.Ant colony optimization［M］.ZHANG Jun，HU Xiaomin，LUO Xuyao，et al transl.Tsinghua University Press，2007:63－115（in Chinese）.［Dorigo M，Stutzle T.蟻群優(yōu)化［M］.張軍，胡曉敏，羅旭耀，等譯.清華大學(xué)出版社，2007:63－115.］