基于混沌螞蟻的群集協(xié)同求解算法及應(yīng)用.pdf

1、群集智能源于對(duì)社會(huì)性生物群集行為的研究，科學(xué)界的研究動(dòng)機(jī)是分析生物群集通過(guò)個(gè)體之間的相互作用產(chǎn)生的涌現(xiàn)和自組織行為，工程應(yīng)用領(lǐng)域的研究目的是構(gòu)建由大量簡(jiǎn)單嵌入式設(shè)備構(gòu)成的分布式自治系統(tǒng)，如無(wú)線自組織網(wǎng)絡(luò)、機(jī)器人協(xié)作系統(tǒng)等。盡管群集智能在這兩方面已經(jīng)取得了大量的成果，但大部分研究集中在蟻群優(yōu)化算法(AntColonyOptimization，ACO)和粒子群算法(ParticleSwarmOptimization，PSO)等隨機(jī)型算法，且

2、多關(guān)注這類算法的應(yīng)用，而沒(méi)有考慮群集內(nèi)個(gè)體之間的信息協(xié)同交互方式以及研究尺度對(duì)算法求解效果的影響，也很少涉及群集智能的協(xié)同求解方法研究。
　　 近年來(lái)，生物學(xué)家Cole對(duì)群居螞蟻的研究中發(fā)現(xiàn)，螞蟻個(gè)體的活動(dòng)是混沌的，而整個(gè)蟻群則是一種周期性行為，并且學(xué)者Solé給出了螞蟻個(gè)體行為的混沌映射表達(dá)式。螞蟻群集智能體現(xiàn)在自發(fā)地分布式協(xié)調(diào)資源配置來(lái)協(xié)同完成任務(wù)的自組織行為，若從動(dòng)力學(xué)的角度看，蟻群的自組織能力必然與螞蟻個(gè)體的混沌行為存在

3、著內(nèi)在的聯(lián)系，所以我們認(rèn)為蟻群的周期性行為正是一個(gè)由混沌態(tài)到自組織態(tài)的轉(zhuǎn)換過(guò)程。
　　 因此，本論文從微觀層內(nèi)個(gè)體、微觀層個(gè)體與宏觀層群集之間的聯(lián)系兩個(gè)角度分析螞蟻個(gè)體混沌行為與蟻群的自組織行為之間的關(guān)系，圍繞如何構(gòu)建螞蟻群集協(xié)同求解算法進(jìn)行研究，形成組合優(yōu)化問(wèn)題、高維函數(shù)優(yōu)化問(wèn)題、復(fù)雜分布式協(xié)同優(yōu)化問(wèn)題、動(dòng)態(tài)分布式約束優(yōu)化問(wèn)題的協(xié)同求解方法，以深化和拓寬群集智能的研究。
　　 本論文的主要研究工作如下:
　　

4、(1)對(duì)當(dāng)前相關(guān)研究工作進(jìn)行了調(diào)查、分析與總結(jié)，指出需要進(jìn)一步解決的問(wèn)題。從混沌同步的角度，闡釋了混沌螞蟻群算法（ChaoticAntSwarm，CAS）的協(xié)同機(jī)制;
　　 (2)從微觀層內(nèi)個(gè)體之間信息交互方式的角度，構(gòu)建了基于混沌螞蟻群算法的組合優(yōu)化問(wèn)題協(xié)同求解算法。首先，提出了求解經(jīng)典TSP的集中式算法(ChaoticAntSwarmfortheTravelingSalesmanProblem，CAS-TSP)，該算法在CA

5、S的基礎(chǔ)上引入連續(xù)空間到離散空間的映射、反向操作和交叉操作，數(shù)值仿真實(shí)驗(yàn)表明該算法對(duì)標(biāo)準(zhǔn)測(cè)試問(wèn)題庫(kù)TSPLIB中實(shí)例是有效的;然后，提出了求解無(wú)線傳感器網(wǎng)絡(luò)分布式任務(wù)分配算法(ChaoticAntSwarmforDecentralizedTaskAllocation，CAS-DTA)，該算法的目標(biāo)函數(shù)考慮了任務(wù)能耗和任務(wù)執(zhí)行可靠性，任務(wù)分配的過(guò)程通過(guò)任務(wù)映射、通信路由分配和任務(wù)分配方案優(yōu)化三個(gè)步驟獲得，其中任務(wù)映射由螞蟻的混沌行為產(chǎn)生，

6、通信路由分配由螞蟻的鄰居選擇方法確定，用A*算法實(shí)現(xiàn)，任務(wù)分配方案優(yōu)化由蟻群的自組織能力實(shí)現(xiàn);大量的仿真實(shí)驗(yàn)表明了CAS-DTA算法能有效地延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)生命期、節(jié)省能量消耗和均衡網(wǎng)絡(luò)負(fù)載;
　　 (3)從微觀層內(nèi)螞蟻個(gè)體行為及其之間交互方式的角度，為減少協(xié)同個(gè)體之間交互的計(jì)算量和通信量，提出了擾動(dòng)混沌螞蟻群算法（DisturbanceChaoticAntSwarm，DCAS）。由于混沌蟻群優(yōu)化算法CAS求解高維優(yōu)化問(wèn)題存在

7、計(jì)算復(fù)雜和搜索精度低的問(wèn)題，DCAS算法通過(guò)建立新的螞蟻?zhàn)顑?yōu)位置更新方法、鄰居選擇形式和自適應(yīng)擾動(dòng)三個(gè)策略改進(jìn)CAS算法，實(shí)現(xiàn)了對(duì)CAS算法的性能改善，并證明了DCAS算法的全局收斂性。通過(guò)兩組測(cè)試函數(shù)，對(duì)DCAS算法的性能進(jìn)行了高達(dá)1000維的大量仿真實(shí)驗(yàn)，測(cè)試結(jié)果表明DCAS算法對(duì)復(fù)雜的高維優(yōu)化問(wèn)題可行有效;
　　 (4)從微觀層個(gè)體相互作用與宏觀層群集行為的聯(lián)系角度，基于動(dòng)態(tài)信息熵，提出了基于混沌螞蟻的復(fù)雜分布式系統(tǒng)協(xié)同優(yōu)

8、化方法。在復(fù)雜系統(tǒng)理論指導(dǎo)下，分析復(fù)雜分布式系統(tǒng)中自主Agent的基本動(dòng)力學(xué)特征，進(jìn)而提出復(fù)雜分布式系統(tǒng)協(xié)同優(yōu)化模型;在此基礎(chǔ)上，借助混沌螞蟻群算法的思想，建立基于混沌螞蟻的復(fù)雜分布式系統(tǒng)協(xié)同優(yōu)化算法(CASbasedCollaborativeOptimization，CAS-CO)。通過(guò)對(duì)復(fù)雜多Agent網(wǎng)絡(luò)中基于位置的任務(wù)分配問(wèn)題進(jìn)行仿真實(shí)驗(yàn)，同時(shí)與已有算法的仿真結(jié)果比較，表明CAS-CO算法的可行性和有效性，說(shuō)明了所提出模型的正確

9、性和Agent的自主性在復(fù)雜分布式系統(tǒng)設(shè)計(jì)與構(gòu)建中的重要性;
　　 (5)從微觀層個(gè)體行為與宏觀層群集行為的決策關(guān)系角度，提出了一種群集自治的分布式協(xié)調(diào)算法(DecentralizedCoordinationAlgorithm，DCA)，能夠有效協(xié)調(diào)群集個(gè)體并使它們的狀態(tài)達(dá)到整體最優(yōu)組態(tài)。DCA算法受單個(gè)螞蟻的混沌行為和整個(gè)蟻群的自組織行為啟發(fā)而設(shè)計(jì)，首先，將每個(gè)Agent看作一個(gè)非線性振子，表現(xiàn)單個(gè)螞蟻的混沌行為;然后，借鑒蟻

10、群的自組織行為建立自組織機(jī)制，并分析了DCA算法的收斂性;最后，采用群集節(jié)點(diǎn)的聚集、分散問(wèn)題評(píng)估DCA算法的有效性，并與分布式梯度算法相比，仿真結(jié)果表明了DCA算法能使群集節(jié)點(diǎn)自治地達(dá)到最優(yōu)組態(tài)。此外，采用DCA算法分布式協(xié)調(diào)機(jī)制，結(jié)合動(dòng)態(tài)分布式約束優(yōu)化問(wèn)題，進(jìn)一步提出了基于混沌螞蟻的動(dòng)態(tài)分布式約束優(yōu)化問(wèn)題協(xié)同求解算法(ChaoticAntbasedDynamicDistributedConstraintOptimizationProb

11、lem，CA-DDCOP)。該算法首先根據(jù)單只螞蟻的混沌行為，建立Agent的受控變量混沌選值策略，實(shí)現(xiàn)Exploration操作;然后模擬蟻群的自組織行為，構(gòu)建Agent個(gè)體受其鄰居和自組織能力的作用機(jī)制，實(shí)現(xiàn)Exploitation操作;最后基于玻爾茲曼分布建立群集宏觀層對(duì)個(gè)體微觀層的決策關(guān)系，實(shí)現(xiàn)Exploration與Exploitation操作協(xié)同求解。為評(píng)估CA-DDCOP算法性能，還將CA-DDCOP算法應(yīng)用于多射頻多信道