基于能量機(jī)制的多頭絨泡菌動(dòng)力學(xué)優(yōu)化算法

劉 陽(yáng) 馮 翔,2 虞慧群 羅 飛

1(華東理工大學(xué)信息科學(xué)與工程學(xué)院 上海 200237) 2 (上海交通大學(xué)智慧城市協(xié)同創(chuàng)新中心 上海 200240) (18255387158@163.com)

基于能量機(jī)制的多頭絨泡菌動(dòng)力學(xué)優(yōu)化算法

劉 陽(yáng)1馮 翔1,2虞慧群1羅 飛1

1(華東理工大學(xué)信息科學(xué)與工程學(xué)院 上海 200237)2(上海交通大學(xué)智慧城市協(xié)同創(chuàng)新中心 上海 200240) (18255387158@163.com)

隨著人工智能和大數(shù)據(jù)的迅猛發(fā)展，大數(shù)據(jù)的爆炸式增長(zhǎng)和問(wèn)題的復(fù)雜性分布導(dǎo)致對(duì)并行智能處理的要求日趨迫切.傳統(tǒng)的理論模型和技術(shù)方法面臨嚴(yán)峻挑戰(zhàn)，受自然界啟發(fā)的物理學(xué)法則和生物學(xué)方法逐漸成為研究熱點(diǎn).受多頭絨泡菌的生長(zhǎng)覓食等行為啟發(fā)，提出了一種基于能量機(jī)制的多頭絨泡菌動(dòng)力學(xué)算法(physarum-energy dynamic optimization algorithm, PEO).該算法以多頭絨泡菌算法為基礎(chǔ)，根據(jù)其動(dòng)力學(xué)特征，引入能量機(jī)制，以改進(jìn)現(xiàn)有的多頭絨泡菌算法全局信息交互能力差等缺點(diǎn).此外，PEO引入了年齡因子的概念和擾動(dòng)機(jī)制，以控制算法在不同階段的尋優(yōu)能力和收斂速度，并從理論角度對(duì)算法模型的收斂性進(jìn)行證明.最后，通過(guò)在TSP數(shù)據(jù)集上實(shí)驗(yàn)證明算法在不同規(guī)模數(shù)據(jù)集的有效性和收斂性，并進(jìn)行了參數(shù)分析.與其他的優(yōu)化算法的對(duì)比實(shí)驗(yàn)數(shù)據(jù)表明，PEO在面對(duì)復(fù)雜問(wèn)題的求解速度和收斂速度明顯優(yōu)于其他的優(yōu)化算法，具有高精度和快收斂的特性.

多頭絨泡菌動(dòng)力學(xué)優(yōu)化算法；能量機(jī)制；年齡因子；旅行商問(wèn)題

正如微軟的創(chuàng)始人之一Allen在《Science》上發(fā)表的論文“New frontiers in bioscience”中所說(shuō)：“探索生物學(xué)的復(fù)雜性是一場(chǎng)迷人的挑戰(zhàn)，我渴望能探索它的奧義與陣地，建立出可靠的預(yù)測(cè)模型并將其應(yīng)用于實(shí)際中去.這種極富創(chuàng)新性和創(chuàng)造性的工作極大地推動(dòng)了人類社會(huì)的進(jìn)步，也正是這種信念支持著我對(duì)基礎(chǔ)科學(xué)的不懈研究[1].”隨著信息科學(xué)技術(shù)的迅猛發(fā)展，研究者們受自然規(guī)律或生物行為的靈感啟發(fā)，提出了許多有效成熟的理論模型和算法思想，并得到了廣泛的應(yīng)用[2-4].其中自然行為[5]、群體行為[6]、生物行為[7]等，這些算法已經(jīng)廣泛地應(yīng)用于生活的各個(gè)方面，并能成功地解決各種復(fù)雜的問(wèn)題.

著名的旅行商問(wèn)題(traveling salesman problem, TSP)是組合優(yōu)化問(wèn)題領(lǐng)域中最重要和最有代表性的問(wèn)題之一，在過(guò)去的半個(gè)世紀(jì)以來(lái)，吸引了大量的研究人員為此不懈努力.TSP是一個(gè)典型的NP難題，其搜索空間巨大，即在多項(xiàng)式時(shí)間內(nèi)無(wú)法精確求解.當(dāng)前對(duì)于TSP問(wèn)題的應(yīng)用主要包含印刷電路板的制造、車輛路由和調(diào)度問(wèn)題等.針對(duì)該類問(wèn)題，目前主要有2種方法求解，精確的傳統(tǒng)方法和高效的智能算法.由于TSP問(wèn)題的時(shí)間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)，精確的傳統(tǒng)方法例如動(dòng)態(tài)規(guī)劃法，只能解決規(guī)模較小的簡(jiǎn)單問(wèn)題.當(dāng)面臨大規(guī)模的復(fù)雜問(wèn)題時(shí)，該類方法失效.為了可以在合理的時(shí)間空間代價(jià)下有效地解決大規(guī)模TSP問(wèn)題，就有必要提出能夠?qū)ふ掖蝺?yōu)解的智能算法.智能算法雖然不一定能夠精確的求解問(wèn)題，但是對(duì)于規(guī)模較大的問(wèn)題，可以在有限時(shí)間內(nèi)將解的有效性控制在一定的誤差范圍內(nèi).

迄今為止，現(xiàn)有的求解TSP問(wèn)題的智能算法主要有彈性網(wǎng)絡(luò)算法[8]、基于螞蟻行為啟發(fā)的蟻群算法[9-10]、鳥群群內(nèi)覓食行為的粒子群算法[11]、基于演化策略的遺傳算法[12]、源于熱力學(xué)中退火原理的模擬退火算法[13]等.對(duì)于現(xiàn)有的智能算法來(lái)說(shuō)，雖然能夠在有限時(shí)間內(nèi)找到問(wèn)題的近似最優(yōu)解，但是依然存在各種不足有待繼續(xù)優(yōu)化改進(jìn).其中，彈性網(wǎng)絡(luò)算法雖然具有較好的并行性，但是依然存在局部最小值和參數(shù)調(diào)整問(wèn)題[14]；蟻群算法雖然求解精度較高，正反饋機(jī)制且參數(shù)較少，但計(jì)算時(shí)間長(zhǎng)，收斂速度慢[15]；粒子群算法具有強(qiáng)大的全局搜索能力，但是極易陷入局部最優(yōu)[16]；遺傳算法簡(jiǎn)單，具有快速搜索能力，但在計(jì)算演化過(guò)程中易早熟收斂，交互信息能力差，計(jì)算代價(jià)大[17]；模擬退火算法具有較強(qiáng)的局部?jī)?yōu)化能力，但缺乏對(duì)搜索空間的了解，搜索過(guò)程不易趨向希望方向，求解效率低下[18]等.

隨著啟發(fā)式算法的深入研究發(fā)展，簡(jiǎn)單單一的經(jīng)典算法模型通常就會(huì)具有很大的局限性.為了能彌補(bǔ)現(xiàn)有算法的不足，近年來(lái)研究人員也提出了許多改進(jìn)算法，例如Arshad等人提出的混合GA算法[19]、Saadatmand-Tarzjan等人提出的構(gòu)建優(yōu)化神經(jīng)網(wǎng)絡(luò)算法[20]、Hu等人提出的可變采樣蟻群優(yōu)化算法[21]、Ye等人提出的改進(jìn)的混合模擬退火遺傳算法[18]等.然而，當(dāng)待求解問(wèn)題越發(fā)復(fù)雜，為了尋找更優(yōu)的解決方案，經(jīng)典算法的改進(jìn)模型就會(huì)對(duì)復(fù)雜問(wèn)題進(jìn)行更為細(xì)致的刻畫，即可能出現(xiàn)算法的可擴(kuò)展性變差或者雖精度提高但求解速度降低等情況.

針對(duì)以上不足，需要提出更為有效的智能優(yōu)化算法模型，該算法模型需要能夠高度并行且收斂，有較好的全局尋優(yōu)能力，在求解大規(guī)模復(fù)雜問(wèn)題時(shí)既能夠保證求解精度，又能提高尋優(yōu)效率，在兩者之間找到很好的制衡點(diǎn)，以滿足待解決問(wèn)題的需要.本文受多頭絨泡菌生長(zhǎng)覓食行為啟發(fā)，根據(jù)其在演化行為過(guò)程中的能量變化及并行行為，提出基于能量機(jī)制的多頭絨泡菌動(dòng)力學(xué)優(yōu)化算法(physarum-energy dynamic optimization algorithm, PEO)，使得其在解決大規(guī)模的復(fù)雜問(wèn)題中具有高度并行性和快速求解能力.此外，引入年齡因子機(jī)制，以控制算法在不同階段的尋優(yōu)能力和尋優(yōu)精度，避免陷入早熟收斂.

本文的主要貢獻(xiàn)有5個(gè)方面:

1) 提出基于能量機(jī)制的多頭絨泡菌動(dòng)力學(xué)優(yōu)化算法PEO，在解決復(fù)雜問(wèn)題中具有高度的并行性和全局尋優(yōu)能力；

2) 基于動(dòng)力學(xué)機(jī)制，設(shè)計(jì)能量函數(shù)，構(gòu)建多頭絨泡菌能量子模型，保證算法收斂；

3) 提出年齡因子模型，控制算法在不同階段的尋優(yōu)能力和尋優(yōu)精度；

4) 引入隨機(jī)擾動(dòng)子模型，避免算法陷入早熟收斂；

5) 建立多頭絨泡菌的生物物理模型和數(shù)學(xué)模型，并給出收斂性證明和理論可行性證明.

1 相關(guān)工作

2000年，Nakafaki等人在《Nature》中提出，多頭絨泡菌可以有效地解決迷宮問(wèn)題[22].多頭絨泡菌能根據(jù)外界環(huán)境情況來(lái)調(diào)整生長(zhǎng)結(jié)構(gòu)，使得機(jī)體向著最有利于生存的方向生長(zhǎng)[23-26].本文受多頭絨泡菌的覓食行為及規(guī)律的啟發(fā)[27-28]，刻畫出多頭絨泡菌覓食的生物模型.多頭絨泡菌由于其趨食性會(huì)導(dǎo)致食物源產(chǎn)生壓力差[29]，即產(chǎn)生勢(shì)能，而維持機(jī)體生長(zhǎng)會(huì)導(dǎo)致能量耗損，所以該系統(tǒng)具有動(dòng)力學(xué)特征.

2013年，Mersch等人通過(guò)研究發(fā)現(xiàn)，螞蟻受年齡因素影響會(huì)導(dǎo)致社會(huì)化分工演變[30]，年輕螞蟻在蟻巢內(nèi)部從事護(hù)理工作，中年螞蟻分布在蟻巢各處進(jìn)行清理工作，老年螞蟻在蟻巢外側(cè)進(jìn)行覓食工作，如圖1所示：

Fig. 1 Affection of ages to ants圖1 螞蟻受年齡因素影響示意圖

2 問(wèn)題描述

旅行商問(wèn)題(TSP問(wèn)題)是一個(gè)組合優(yōu)化問(wèn)題，也被證明了是NP難題，即：存在N個(gè)城市，旅行商由城市i出發(fā)，依次訪問(wèn)完所有的N個(gè)城市，并回到出發(fā)點(diǎn)i的最短路徑長(zhǎng)度.

對(duì)于TSP問(wèn)題來(lái)說(shuō)，需要訪問(wèn)城市的集合為：C={c1,c2,…,cn}，城市ci的坐標(biāo)為(xi,yi).假設(shè)旅行商訪問(wèn)的順序集合為：Order={o1,o2,…,on}，其中,oi表示旅行商訪問(wèn)順序中第i個(gè)被訪問(wèn)城市的標(biāo)號(hào)，1≤i≤n,on+1=o1，那么目標(biāo)函數(shù)可以表示為

3 生物物理模型

3.1生物模型

定義1. 電導(dǎo)率.連接食物A和B管道內(nèi)原生質(zhì)流動(dòng)的傳導(dǎo)性被稱為電導(dǎo)率.

定義2. 流量.連接食物A和B管道內(nèi)單位時(shí)間內(nèi)流動(dòng)的原生質(zhì)的體積被稱為流量.

定義3. 壓力.多頭絨泡菌的趨食性導(dǎo)致食物對(duì)管道內(nèi)原生質(zhì)具有吸引力即壓力.

定義4. 壓力差.連接食物A和B管道內(nèi)原生質(zhì)的壓力差值稱為壓力差.

由多頭絨泡菌的覓食特性[26]可知，管道內(nèi)原生質(zhì)的流量和電導(dǎo)率存在著正反饋機(jī)制，如圖2所示，即當(dāng)管道內(nèi)原生質(zhì)的流量逐漸增多，管道電導(dǎo)率就會(huì)增大，電導(dǎo)率的增大又會(huì)進(jìn)一步導(dǎo)致管道內(nèi)流量增加，反之亦然.

Fig. 2 Positive feedback mechanism of Physarum圖2 多頭絨泡菌機(jī)體的正反饋機(jī)制

3.2能量模型

多頭絨泡菌體內(nèi)的原生質(zhì)在食物吸引力下流動(dòng)，同時(shí)維持機(jī)體生長(zhǎng)將導(dǎo)致能量耗損，即整個(gè)系統(tǒng)具有能量開(kāi)銷，因此多頭絨泡菌具有著動(dòng)力學(xué)特性[31].本文根據(jù)多頭絨泡菌的動(dòng)力學(xué)特性來(lái)構(gòu)建能量模型.

連接食物源之間的原生質(zhì)管道內(nèi)存在著由壓力差產(chǎn)生的勢(shì)能，即原生質(zhì)流動(dòng)的動(dòng)力.經(jīng)過(guò)管道內(nèi)流量和電導(dǎo)率間的正反饋機(jī)制不斷演化，隨時(shí)間的增長(zhǎng)，流量和電導(dǎo)率逐漸趨于穩(wěn)定.系統(tǒng)的能量變化也將逐漸趨于穩(wěn)定.本文考慮整個(gè)系統(tǒng)中能量的變化受以下幾種因素的影響.

定義5. 個(gè)體效用.連接食物A和B間管道的狀態(tài)距穩(wěn)定狀態(tài)的差距，即該管道的成功值．該管道的成功值越大，其個(gè)體效用就越強(qiáng).

定義6. 整體效用.所有的管道個(gè)體效用值的累加即整體效用.當(dāng)系統(tǒng)達(dá)到最優(yōu)解時(shí)，其整體效用將不再發(fā)生變化.

定義7. 目標(biāo)吸引力.系統(tǒng)在演化過(guò)程中，以期望達(dá)到的最優(yōu)狀態(tài)對(duì)當(dāng)前狀態(tài)的吸引力.目標(biāo)吸引力將會(huì)使個(gè)體效用最小的管道的效用值增加，以提高整體效用.

定義8. 交互信息行為.系統(tǒng)在演化過(guò)程中，各管道之間的變化相互影響的方式即交互信息行為.

能量模型在4種因素的影響下，向目標(biāo)狀態(tài)演化，這4種因素為：1)個(gè)體效用的優(yōu)化行為；2)整體效用的優(yōu)化行為；3)目標(biāo)對(duì)整體的吸引力；4)個(gè)體管道結(jié)構(gòu)之間的交互信息行為.

3.3年齡因子模型

PEO的整個(gè)演變過(guò)程按照其持續(xù)的時(shí)間長(zhǎng)短可以劃分為3個(gè)階段，分別是初期的不穩(wěn)定狀態(tài)階段、中期的亞穩(wěn)定狀態(tài)階段以及后期的穩(wěn)定狀態(tài)階段.

定義9. 不穩(wěn)定狀態(tài).算法初期，系統(tǒng)的能量值、個(gè)體效用和整體效用變化幅度較大，算法趨向于全局尋優(yōu)，收斂速度較快.

定義10. 亞穩(wěn)定狀態(tài).算法中期，系統(tǒng)的能量值、個(gè)體效用及整體效用值變化幅度小于不穩(wěn)定狀態(tài).該階段算法的尋優(yōu)能力更趨向于局部尋優(yōu)，收斂速度較慢.

定義11. 穩(wěn)定狀態(tài).算法后期至結(jié)束.系統(tǒng)能量值、個(gè)體效用值及整體效用穩(wěn)定，算法已經(jīng)求解到最優(yōu)解.

年齡因子模型使得PEO在不同階段選擇不同的尋優(yōu)機(jī)制，即不穩(wěn)定狀態(tài)時(shí)，提高全局尋優(yōu)能力，加快收斂速度；亞穩(wěn)定狀態(tài)時(shí)，提高局部尋優(yōu)能力，減緩收斂速度，以期在穩(wěn)定狀態(tài)時(shí)能夠得到更理想的最優(yōu)值.

3.4隨機(jī)擾動(dòng)模型

根據(jù)多頭絨泡菌的避光性特點(diǎn)，隨機(jī)光照擾動(dòng)會(huì)對(duì)其生長(zhǎng)結(jié)構(gòu)產(chǎn)生一定影響.本文在PEO尋優(yōu)過(guò)程中引入隨機(jī)擾動(dòng)機(jī)制.PEO算法的每次隨機(jī)擾動(dòng)將獲得一個(gè)新解，如果新解的解質(zhì)量?jī)?yōu)于當(dāng)前解，則接受新解，否則將以一定概率接受新解，通過(guò)此機(jī)制使得算法跳出局部最優(yōu).

4 數(shù)學(xué)模型

4.1生物數(shù)學(xué)模型

首先對(duì)TSP問(wèn)題中的主要變量進(jìn)行描述,如表1所示：

Table 1 The Main Variables of TSP表1 TSP中的主要變量

定義12. 食物源i的位置坐標(biāo)為(xi,yi).

定義13. 連接食物源i與j的管道長(zhǎng)度是lij，即i點(diǎn)和j點(diǎn)之間的歐式距離：

定義14. 連接食物源i和j的管道lij兩端存在壓力差pij，即點(diǎn)i的壓力pi和點(diǎn)j的壓力pj的差值的絕對(duì)值.

(1)

定義15. 連接食物源i和j的管道lij之間的流量用flowij來(lái)表示.根據(jù)哈根-泊肅葉方程得知：

(2)

其中，lij是i和j之間的距離，rij代表管道的內(nèi)徑，ζ代表流體的粘度.

定義16. 連接食物源i和j的管道電導(dǎo)率用dij表示：

(3)

(4)

定義17. 電導(dǎo)率dij變化和流量flowij的關(guān)系為

(5)

根據(jù)式(5)可得：

(6)

其中，機(jī)體維持管道會(huì)產(chǎn)生能量損耗，而σ和ρ是控制流量和能量耗損的權(quán)重系數(shù).由此可見(jiàn)，管道內(nèi)電導(dǎo)率的變化趨勢(shì)和管道內(nèi)流量的變化趨勢(shì)是一致的，是正反饋?zhàn)饔玫慕Y(jié)果.

4.2能量數(shù)學(xué)模型

根據(jù)PEO的能量模型可知，其能量變化受4個(gè)方面的因素影響，以下對(duì)這4個(gè)因素進(jìn)行數(shù)學(xué)模型構(gòu)建：

定義18.uij(t)為食物源i和j之間管道的個(gè)體效用值，表示管道的連接狀態(tài)距離目標(biāo)值的徑向距離，即距離目標(biāo)的成功度.

(7)

其中，食物源i和j之間管道的距離lij越短，管內(nèi)流量flowij越大，電導(dǎo)率dij也就越高.其向著目標(biāo)的成功度也就越高，個(gè)體效用值就越強(qiáng).

定義19.J(t)代表在時(shí)刻t的整個(gè)系統(tǒng)管道的整體效用，即：

(8)

定義20. 管道之間的交互式行為函數(shù)Q(t)：

(9)

定義21. 在時(shí)刻t，由最終的目標(biāo)產(chǎn)生的吸引力函數(shù)為

(10)

其中,0<ε<1，P(t)越大，即向著目標(biāo)變化的速度越快，那么TSP問(wèn)題的求解速度越快.

定義22. 系統(tǒng)在以上4個(gè)因素的影響下向目標(biāo)結(jié)構(gòu)演化的過(guò)程，通過(guò)混合的吸引力函數(shù)Eij(t)表示：

Eij(t)=-λ1uij(t)-λ2J(t)-λ3P(t)-λ4Q(t)，

(11)

其中，0<λ1,λ2,λ3,λ4<1.

對(duì)于PEO來(lái)說(shuō)，其比較顯著的特點(diǎn)就是具有高度的并行性，對(duì)于管道的2個(gè)參數(shù)，電導(dǎo)率參數(shù)dij和壓力差參數(shù)pij都可以動(dòng)態(tài)并行地進(jìn)行計(jì)算更新，從而可以達(dá)到高效快捷的求出目標(biāo)優(yōu)化解的目的，即：

(12)

(13)

定義23. 個(gè)體效用隨時(shí)間變化的變化率為

(14)

4.3年齡因子數(shù)學(xué)模型

算法的年齡因子將算法的階段劃分為3個(gè)階段，第3個(gè)階段算法已經(jīng)取得了最優(yōu)解，那么對(duì)算法的前2個(gè)階段進(jìn)行數(shù)學(xué)模型構(gòu)建：

1) 初期的不穩(wěn)定階段

在初期的尋優(yōu)搜索階段，適當(dāng)?shù)丶涌焖惴ǖ氖諗克俣?根據(jù)式(10)可知，參數(shù)ε的值控制著吸引力函數(shù)P(t)的大小.由此可以適當(dāng)?shù)卦黾应诺闹担蕴岣咚惴ㄊ諗康乃俣龋藭r(shí)算法側(cè)重全局尋優(yōu).

2) 中期的亞穩(wěn)定階段

在中期尋優(yōu)階段，適當(dāng)?shù)亟档挺诺闹担蕴岣呔植克阉鞯木龋m當(dāng)降低算法的收斂速度.

4.4隨機(jī)擾動(dòng)數(shù)學(xué)模型

在PEO中引入擾動(dòng)機(jī)制，即每次生長(zhǎng)過(guò)程中，隨機(jī)選擇某管道，對(duì)其電導(dǎo)率dij在一定范圍內(nèi)添加擾動(dòng)項(xiàng)，判斷當(dāng)前系統(tǒng)和擾動(dòng)前系統(tǒng)的能量值變化，若能量增加，則以一定的概率接受當(dāng)前的擾動(dòng)修改，以提供一種防止算法陷入局部最優(yōu)的機(jī)制.

定義24. 若能量增加，ΔE>0，接受當(dāng)前修改的概率為

P(ΔE>0)=e-ΔEt，

(15)

其中，t為當(dāng)前算法的迭代次數(shù).

5 PEO算法

基于能量機(jī)制的多頭絨泡菌優(yōu)化算法PEO具體步驟為：1)初始化各個(gè)食物源的位置坐標(biāo)，并且確定機(jī)體管道結(jié)構(gòu)的電導(dǎo)率，壓力差以及相關(guān)參數(shù)等；2)分別求得每個(gè)管道個(gè)體效用、整體效用、目標(biāo)吸引力和交互信息等；3)不斷迭代更新個(gè)體效用，并判斷算法所處階段，引入擾動(dòng)機(jī)制；4)當(dāng)個(gè)體效用不再發(fā)生變化時(shí)，算法結(jié)束，求得最優(yōu)解.算法的主要流程如圖3所示：

Fig. 3 The flow chart of algorithm圖3 算法流程圖

算法1. 基于能量機(jī)制的多頭絨泡菌動(dòng)力學(xué)算法

① 初始化所有點(diǎn)的坐標(biāo)，獲得各城市間的距離；

② 初始化所有邊的電導(dǎo)率dij，壓力差pij；

③ While(t

④ Ift=X/*X為修改年齡因子的閾值*/

⑤ε=αε; /*α為修改年齡因子的參數(shù)*/

⑥ 根據(jù)式(7)～(11)分別計(jì)算uij，J(t)，P(t)，Q(t)，E(t)；

⑦ 生成隨機(jī)值，隨機(jī)修改某一電導(dǎo)率dij的值；

⑨ If Δu>0

6 算法理論分析

6.1算法收斂性分析

本文在PEO中引入了動(dòng)力學(xué)機(jī)制，即伴隨著演化過(guò)程的推進(jìn)，由于系統(tǒng)存在能量開(kāi)銷，系統(tǒng)的總能量將逐漸減小至0.目標(biāo)狀態(tài)產(chǎn)生的吸引力將不斷推動(dòng)著系統(tǒng)的演化，同時(shí)吸引力函數(shù)也會(huì)隨之變化.當(dāng)吸引力逐漸變化至消失時(shí)，整個(gè)系統(tǒng)的能量演化過(guò)程將趨于穩(wěn)定收斂狀態(tài).由于算法數(shù)學(xué)模型的構(gòu)建基于微分方程，則該算法的收斂性穩(wěn)定性可以使用Lyapunov穩(wěn)定性理論來(lái)證明.

Lyapunov穩(wěn)定性理論，函數(shù)L(x)具有2個(gè)特點(diǎn)：

1)L(x)>0；

那么L(X(t))稱為L(zhǎng)yapunov的備選方程，X滿足Lyapunov漸進(jìn)穩(wěn)定性.

證明. 根據(jù)Lyapunov穩(wěn)定性理論，定義一個(gè)Lyapunov方程L(D(t))：

L(D(t))D(t)，

那么D(t)的更新公式為

那么，根據(jù)dij∈[0,1]，可以得知D(t)>0恒成立，所以L(D(t))>0也恒成立.

其中，

那么，

即：

證畢.

6.2年齡因子控制參數(shù)分析

定理2. 當(dāng)ε比較小的情況下，目標(biāo)吸引力函數(shù)P(t)將會(huì)使得距離目標(biāo)成功度最小的管道向著最優(yōu)結(jié)構(gòu)的目標(biāo)演化，即個(gè)體效用最小的管道增加.

證明. 設(shè)定S(t)為個(gè)體效用最小的管道，即：

那么，就存在不等式成立：

由此，對(duì)上述不等式的符號(hào)兩邊分別取對(duì)數(shù)，可以得到：

n.

由于nn是常數(shù)，而且ε很小，那么我們可以通過(guò)移項(xiàng)得到：

由此可得，目標(biāo)吸引力函數(shù)P(t)作用于個(gè)體效用最小的個(gè)體，所以當(dāng)增加目標(biāo)吸引力函數(shù)的值時(shí)，就可以使得個(gè)體效用值最小的個(gè)體向最優(yōu)解目標(biāo)移動(dòng).于是可以通過(guò)修改ε的值來(lái)調(diào)整目標(biāo)吸引力函數(shù)的大小，以此來(lái)優(yōu)化個(gè)體效用值最小的個(gè)體從而達(dá)到優(yōu)化系統(tǒng)的整體效用的效果，即ε可控制算法的收斂速度.

證畢.

7 實(shí)驗(yàn)分析

本實(shí)驗(yàn)使用TSP問(wèn)題作為測(cè)試問(wèn)題，采用TSPLIB數(shù)據(jù)集，將PEO算法的實(shí)驗(yàn)結(jié)果和其他算法進(jìn)行對(duì)比，以此證明算法PEO的收斂性和有效性，并對(duì)算法的參數(shù)進(jìn)行實(shí)驗(yàn)分析.實(shí)驗(yàn)環(huán)境為聯(lián)想深騰6800高性能計(jì)算集群，該計(jì)算集群共擁有8個(gè)計(jì)算節(jié)點(diǎn)和1個(gè)總控節(jié)點(diǎn).每個(gè)計(jì)算節(jié)點(diǎn)都是一臺(tái)高性能服務(wù)器，內(nèi)存24 GB，四核2.4 GHz中央處理器.每個(gè)節(jié)點(diǎn)服務(wù)器的操作系統(tǒng)都是Red Hat Enterprise Linux 7.

7.1實(shí)驗(yàn)證明算法的有效性

為了驗(yàn)證算法的有效性，本實(shí)驗(yàn)采用不同規(guī)模的TSPLIB實(shí)例進(jìn)行實(shí)驗(yàn)，對(duì)于算法PEO，GA，PSO，ACO的參數(shù)設(shè)置見(jiàn)表2所示.其中，PEO的參數(shù)分別為個(gè)體效用權(quán)重λ1、整體效用權(quán)重λ2、目標(biāo)對(duì)整體的吸引力權(quán)重λ3、個(gè)體間交互行為權(quán)重λ4、吸引力影響因子ε、吸引力更正參數(shù)α、年齡因子閾值參數(shù)r.GA的參數(shù)分別為種群的個(gè)數(shù)pnum、交叉概率pc、變異概率pm、選擇概率ps[32].PSO的參數(shù)為種群規(guī)模pnum、慣性因子w(Mt是最大迭代次數(shù)，t代表當(dāng)前迭代次數(shù))、個(gè)體權(quán)重影響c1和全局權(quán)重影響c2[33].ACO的參數(shù)依次分別為信息素的重要程度α、啟發(fā)式因子的重要程度β、信息素的揮發(fā)程度ρ、信息素增強(qiáng)系數(shù)Q和種群規(guī)模pnum[32].本實(shí)驗(yàn)通過(guò)比較在相同實(shí)例下，PEO與GA，SA，PSO和ACO的實(shí)驗(yàn)結(jié)果和性能來(lái)驗(yàn)證PEO的有效性.

Table 2 Parameter for Each Algorithm表2 各算法參數(shù)表

算法PEO,GA,PSO和ACO在不同規(guī)模數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)的運(yùn)行時(shí)間和尋優(yōu)結(jié)果如表3所示.

Fig. 4 The experimental results on ulysses16圖4 算法PEO,GA,PSO,ACO在數(shù)據(jù)集ulysses16上的實(shí)驗(yàn)

Table 3 Experimental Results Comparsion AmongPEO,GA,PSO,ACO

表3中的每列分別表示30次重復(fù)試驗(yàn)的TSPLIB實(shí)例、對(duì)比算法、平均尋優(yōu)時(shí)間、平均尋優(yōu)結(jié)果.由表3分析可得：

1) 算法PEO，GA，PSO和ACO在不同規(guī)模數(shù)據(jù)集上均能求解，但尋優(yōu)能力不盡相同.其中，PEO的全局能力相對(duì)優(yōu)于其他3種算法.

2) 當(dāng)要處理的數(shù)據(jù)集規(guī)模不大的時(shí)候，各算法尋優(yōu)能力相當(dāng)，但PEO的尋優(yōu)時(shí)間相對(duì)較短，收斂速度很快.

3) 對(duì)于復(fù)雜的大規(guī)模數(shù)據(jù)集來(lái)說(shuō)，PEO，PSO和ACO算法的尋優(yōu)能力相對(duì)較好，但PEO算法在并行計(jì)算求解過(guò)程中，耗費(fèi)的時(shí)間代價(jià)較小，算法解決問(wèn)題的時(shí)間優(yōu)勢(shì)明顯，能夠在很快時(shí)間內(nèi)對(duì)TSP問(wèn)題求解.

4種算法的尋優(yōu)時(shí)間和尋優(yōu)結(jié)果對(duì)比如圖4、圖5所示.由于TSP問(wèn)題的最優(yōu)解通常具有相鄰城市相連且盡量路徑間避免交叉的特點(diǎn)，通過(guò)圖4、圖5分析可得，PEO的尋優(yōu)能力優(yōu)于GA,PSO以及ACO算法，能夠有效的避免算法陷入局部最優(yōu).此外，由于PEO算法在尋優(yōu)過(guò)程中，根據(jù)系統(tǒng)的動(dòng)力學(xué)特性會(huì)不斷地進(jìn)行優(yōu)化調(diào)整，尋優(yōu)能力不受制于算法的初始化過(guò)程中的設(shè)定，最終系統(tǒng)會(huì)趨于穩(wěn)定而得到最優(yōu)解，所以PEO算法具有魯棒性的特點(diǎn).

Fig. 5 The experimental results on att48圖5 算法PEO,GA,PSO,ACO在數(shù)據(jù)集att48上的實(shí)驗(yàn)

Fig. 6 Solution results of PEO algorithm on different scale data sets圖6 算法在不同規(guī)模數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

圖6分別是算法PEO在數(shù)據(jù)集eil76，ch130，att532和pcb3038上的實(shí)驗(yàn)結(jié)果.根據(jù)圖6分析可得，PEO算法在小規(guī)模或一般規(guī)模的數(shù)據(jù)集上都能取得較好的尋優(yōu)結(jié)果，在較大規(guī)模和大規(guī)模的數(shù)據(jù)集上依然能夠?qū)?wèn)題求解，表現(xiàn)出了較好的尋優(yōu)能力.

通過(guò)圖7分析可得算法PEO針對(duì)不同規(guī)模的數(shù)據(jù)集，尋優(yōu)時(shí)間都相對(duì)其他算法處于較低水平，收斂速度較快.根據(jù)圖8可知，PEO相對(duì)于其他算法在不同規(guī)模的問(wèn)題上都能得到相對(duì)較好的結(jié)果.

Fig. 7 Algorithm’s optimal time comparison chart圖7 算法的尋優(yōu)時(shí)間對(duì)比圖

Fig. 8 Algorithm’s optimal value comparison chart圖8 算法的尋優(yōu)結(jié)果對(duì)比圖

7.2實(shí)驗(yàn)證明算法收斂性

為了證明算法的收斂性，算法PEO對(duì)于數(shù)據(jù)集ulysses16進(jìn)行了實(shí)驗(yàn)，分析了其各管道電導(dǎo)率和壓力差的變化趨勢(shì).由圖9分析可得，各邊電導(dǎo)率伴隨迭代次數(shù)的增加在區(qū)間[0,1]內(nèi)不斷變化，各管道的壓力差也在逐漸變化.在迭代次數(shù)100次到150次之間，電導(dǎo)率的值逐漸處于收斂狀態(tài)，構(gòu)成目標(biāo)路徑解的管道電導(dǎo)率逐漸收斂至1趨于穩(wěn)定.相反，其他的管道的電導(dǎo)率將在演化迭代中逐漸收斂到0而不再發(fā)生變化.

Fig. 9 The change tendency of each pipe’s conductivity and pressure difference in ulysses16圖9 電導(dǎo)率和壓力收斂變化圖

7.3引入年齡因子和擾動(dòng)機(jī)制的實(shí)驗(yàn)效果

通過(guò)對(duì)比PEO未引入年齡因子機(jī)制及擾動(dòng)機(jī)制和引入年齡因子機(jī)制及擾動(dòng)機(jī)制的實(shí)驗(yàn)結(jié)果，由圖10分析可得：未引入年齡因子機(jī)制及擾動(dòng)機(jī)制的算法會(huì)過(guò)早的陷入早熟收斂，導(dǎo)致收斂的速度很快；引入年齡因子機(jī)制及擾動(dòng)機(jī)制求解的精度有所提升，但是收斂的速度變慢.

7.4算法參數(shù)分析

Fig. 10 The validity analysis of age factor and disturbance mechanism圖10 年齡因子和隨機(jī)擾動(dòng)機(jī)制的有效性分析

本節(jié)主要對(duì)PEO的主要參數(shù)進(jìn)行實(shí)驗(yàn)分析，采用了ulysses16數(shù)據(jù)集，將各參數(shù)的變化區(qū)間分別設(shè)定為：λ1∈[0.01,0.9]，λ2∈[0.01,0.9]，λ3∈[0.1,0.9]，λ4∈[0.1,0.9]進(jìn)行實(shí)驗(yàn).

通過(guò)圖11分析可得：參數(shù)λ1和λ2的取值范圍在[0.1,0.2]時(shí)，算法的尋優(yōu)效果相對(duì)較好；參數(shù)λ3和λ4的取值范圍在[0.6,0.9]和[0.4,0.9]時(shí)，算法能夠得到較好的尋優(yōu)效果.其中，參數(shù)α的大小是用來(lái)控制年齡因子的閾值范圍的，本實(shí)驗(yàn)α=0.8.由于算法的狀態(tài)和年齡階段會(huì)伴隨要解決問(wèn)題的規(guī)模大小的變化而發(fā)生變化，所以算法的年齡因子參數(shù)α需要根據(jù)實(shí)驗(yàn)的效果和問(wèn)題求解的需求進(jìn)行一定范圍的調(diào)整.

Fig. 11 PEO’s parameter analysis diagram圖11 各參數(shù)的設(shè)定對(duì)尋優(yōu)效果的影響

8 總結(jié)與展望

本文提出了基于能量機(jī)制的多頭絨泡菌優(yōu)化算法PEO，根據(jù)系統(tǒng)的動(dòng)力學(xué)特點(diǎn)，其演化過(guò)程伴隨著能量的耗損趨于穩(wěn)定，為算法收斂提供了嚴(yán)密的理論依據(jù).此外，提出年齡因子模型和引入擾動(dòng)機(jī)制，以提高算法的尋優(yōu)能力，避免算法早熟，防止尋優(yōu)過(guò)程陷入局部收斂.通過(guò)實(shí)驗(yàn)證明PEO在針對(duì)不同規(guī)模復(fù)雜程度的問(wèn)題能夠快速收斂，具有很好的求解能力，可以有效避免智能算法常見(jiàn)的早熟收斂情況.對(duì)于設(shè)定年齡因子的閾值方面還需進(jìn)一步改進(jìn)，在一定的迭代次數(shù)下，當(dāng)前最優(yōu)解和目標(biāo)解之間還是存在一定的提升空間，本文的工作還只處于初步階段，將會(huì)進(jìn)行進(jìn)一步的研究.

[1] Allen P G. New frontiers in bioscience[J]. Science, 2016, 352(6281): 11

[2] Kulkarni R V, Venayagamoorthy G K. Particle swarm optimization in wireless-sensor networks: A brief survey[J]. IEEE Trans on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2011, 41(2): 262-267

[3] Luo Chaomin, Yang S X. A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments[J]. IEEE Trans on Neural Networks, 2008, 19(7): 1279-1298

[4] Arena P, Fortuna L, Frasca M, et al. An adaptive, self-organizing dynamical system for hierarchical control of bio-inspired locomotion[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B (Cybernetics), 2004, 34(4): 1823-1837

[5] Bandyopadhyay S, Saha S, Maulik U, et al. A simulated annealing-based multiobjective optimization algorithm: AMOSA[J]. IEEE Trans on Evolutionary Computation, 2008, 12(3): 269-283

[6] Herrera-Viedma E, Chiclana F, Herrera F, et al. Group decision-making model with incomplete fuzzy preference relations based on additive consistency[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007, 37(1): 176-189

[7] Zhang Shiwen, Li Zhiyong, Chen Shaomiao, et al. Dynamic multi-objective optimization algorithm based on ecological strategy[J]. Journal of Computer Research and Development, 2014, 51(6): 1313-1330 (in Chinese)(張世文, 李智勇, 陳少淼, 等. 基于生態(tài)策略的動(dòng)態(tài)多目標(biāo)優(yōu)化算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(6): 1313-1330)

[8] Durbin R, Willshaw D. An analogue approach to the travelling salesman[J]. Nature, 1987, 326(16): 689-691

[9] Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem[J]. IEEE Trans on Evolutionary Computation, 1997, 1(1): 53-66

[10] Dorigo M, Birattari M, Stutzle T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine, 2006, 1(4): 28-39

[11] Poli R, Kennedy J, Blackwell T. Particle swarm optimization[J]. Swarm Intelligence, 2007, 1(1): 33-57

[12] Booker L B, Goldberg D E, Holland J H. Classifier systems and genetic algorithms[J]. Artificial Intelligence, 1989, 40(1/2/3): 235-282

[13] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simmulated annealing[J]. Science, 1983, 220(4598): 671-680

[14] Yang Gang, Yi Junyan, Yang Nan. Elastic net with stochastic noise strategy and time-dependent parameters for TSP[C] //Proc the 7th Int Conf on Natural Computation. Piscataway, NJ: IEEE, 2011: 426-430

[15] Yan Jianfeng, Li Na, Li Weihua, et al. Hybrid ant colony algorithm based on scale compression[C] //Proc of 2007 Int Conf on Machine Learning and Cybernetics. Piscataway, NJ: IEEE, 2007: 885-889

[16] Su Jinrong. Improved particle swarm optimization for multi-object traveling salesman problems[C] //Proc of the 7th Int Conf on Natural Computation. Piscataway, NJ: IEEE, 2011: 1175-1179

[17] Lu Jingui, Fang Ning, Shao Dinghong, et al. An improved immune-genetic algorithm for the traveling salesman problem[C] //Proc of the 3rd Int Conf on Natural Computation (ICNC 2007). Piscataway, NJ: IEEE, 2007: 297-301

[18] Ye Gao, Rui Xue. An improved simulated annealing and genetic algorithm for TSP[C] //Proc of the 5th IEEE Int Conf on Broadband Network & Multimedia Technology. Piscataway, NJ: IEEE, 2013: 6-9

[19] Arshad S, Yang Shengxiang. A hybrid genetic algorithm and inver over approach for the travelling salesman problem[C] //Proc of IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2010: 1-8

[20] Saadatmand-Tarzjan M, Khademi M, Akbarzadeh-T M R, et al. A novel constructive-optimizer neural network for the traveling salesman problem[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B (Cybernetics), 2007, 37(4): 754-770

[21] Hu Xiaomin, Zhang Jun, Chung H S H, et al. SamACO: variable sampling ant colony optimization algorithm for continuous optimization[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B (Cybernetics), 2010, 40(6): 1555-1566

[22] Nakagaki T, Yamada H, Tóth á. Maze-solving by an amoeboid organism[J]. Nature, 2000, 407(6803): 470-470

[23] Nakagaki T, Yamada H, Toth A. Path finding by tube morphogenesis in an amoeboid organism[J]. Biophysical chemistry, 2001, 92(1): 47-52

[24] Nakagaki T, Iima M, Ueda T, et al. Minimum-risk path finding by an adaptive amoebal network[J]. Physical review letters, 2007, 99(6): 068104

[25] Tero A, Takagi S, Saigusa T, et al. Rules for biologically inspired adaptive network design[J]. Science, 2010, 327(5964): 439-442

[26] Song Yuning, Liu Liang, Ma Huadong, et al. Physarum optimization: a new heuristic algorithm to minimal exposure problem[C] //Proc of 2012 IEEE Wireless Communications and Networking Conf (WCNC). New York: ACM, 2012: 419-422

[27] Tero A, Kobayashi R, Nakagaki T. A mathematical model for adaptive transport network in path finding by true slime mold[J]. Journal of Theoretical Biology, 2007, 244(4): 553-564

[28] Bonifaci V, Mehlhorn K, Varma G. Physarum can compute shortest paths[J]. Journal of Theoretical Biology, 2012, 309: 121-133

[29] Tero A, Yumiki K, Kobayashi R, et al. Flow-network adaptation in Physarum amoebae[J]. Theory in Biosciences, 2008, 127(2): 89-94

[30] Mersch D P, Crespi A, Keller L. Tracking individuals shows spatial fidelity is a key regulator of ant social organization[J]. Science, 2013, 340(6136): 1090-1093

[31] Feng Xiang, Lau F C M. A parallel evolutionary approach to multi-objective optimization[C] //Proc of 2007 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2007: 1199-1206

[32] Shuang Bing, Chen Jiapin, Li Zhenbo. Study on hybrid PS-ACO algorithm[J]. Applied Intelligence, 2011, 34(1): 64-73

[33] Zhang Jiangwei, Xiong Wei. An improved particle swarm optimization algorithm and its application for solving traveling salesman problem[C] //Proc of 2009 WRI World Congress on Computer Science and Information Engineering. Piscataway, NJ: IEEE, 2009: 612-616

PhysarumDynamicOptimizationAlgorithmBasedonEnergyMechanism

Liu Yang1, Feng Xiang1,2, Yu Huiqun1, and Luo Fei1

1(SchoolofInformationScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237)2(SmartCityCollaborativeInnovationCenter,ShanghaiJiaoTongUniversity,Shanghai200240)

With the rapid development of artificial intelligence and big data, the explosive growth of big data and problem has grown in complexity, which leads to parallel intelligent computing demand increasing. Traditional theoretical models and methods are faced with severe challenges. Physics law and biological method inspired from nature has gradually become a hot spot in the present new period. Inspired by the foraging behavior of physarum, an dynamic algorithm based on energy mechanism is presented. Physarum-energy dynamic optimization algorithm (PEO) is being raised for overcome the drawbacks of physarum algorithm. According to physarum’s dynamic characteristics, the energy mechanism is introduced in PEO which aims to overcome the shortcomings of the existing physarum algorithm, such as its poor information interaction ability in whole. In addition, PEO develops age factor concept and disturbance mechanism, in order to adjust PEOs optimization ability and convergence speed in different age stages, and the convergence of algorithm model is proved through theoretical point of view. Finally, the validity and convergence of PEO are proved by experiments in TSP data set, and the main parameters of PEO are analyzed through experiments. When faced with complex problems, the simulation result comparison analysis between PEO and other optimization algorithms show that PEO is significantly better than other algorithm and PEO has the capability of high accuracy and fast convergence.

physarum-energy dynamic optimization algorithm (PEO); energy mechanism; age factor; traveling salesman problem

Liu Yang, born in 1993. Master candidate in the School of Information Science and Engineering, East China University of Science and Technology. Student member of CCF. Her main research interests include parallel and distributed computing, artificial intelligence and pattern recognition.

Feng Xiang, born in 1977. PhD, professor and PhD supervisor in the School of Information Science and Engineering, East China University of Science and Technology. Member of CCF. Her main research interests include mechanics-related nature inspired algorithm, parallel and distributed computing and computer networks.

Yu Huiqun, born in 1967. PhD, professor and PhD supervisor in the School of Information Science and Engineering, East China University of Science and Technology. Member of CCF. His main research interests include software engineering, trustworthy computing and formal methods (yhq@ecust.edu.cn).

Luo Fei, born in 1978. PhD, associate professor in the School of Information Science and Engineering, East China University of Science and Technology. Member of CCF. His main research interests include distributed computing and embedded systems (luof@ecust.edu.cn).

2017-05-23；

：2017-07-03

國(guó)家自然科學(xué)基金項(xiàng)目(61472139，61462073)；上海市經(jīng)濟(jì)和信息委員會(huì)信息化發(fā)展專項(xiàng)資金項(xiàng)目(201602008)；上海市智慧城市協(xié)同創(chuàng)新中心開(kāi)放基金項(xiàng)目 This work was supported by the National Natural Science Foundation of China (61472139,61462073), the Information Development Special Funds of Shanghai Economic and Information Commission (201602008), and the Open Funds of Shanghai Smart City Collaborative Innovation Center.

馮翔(xfeng@ecust.edu.cn)

TP18