基于群智能算法求解0-1背包問題的研究及應(yīng)用.pdf

1、作為導(dǎo)向人類復(fù)雜系統(tǒng)研究的一個(gè)過渡，科學(xué)家們通過對(duì)群體生物的觀察與研究產(chǎn)生了以模仿自然界群體生物行為特征的群智能研究領(lǐng)域。群智能是指任何受群體生物集體行為啟發(fā)而設(shè)計(jì)的算法與分布式問題解決裝置。
　　 本文從一維細(xì)胞自動(dòng)機(jī)入手，設(shè)計(jì)了適于求解二元離散優(yōu)化問題的二元蟻群算法（BACO）和二元粒子群算法（BPSO-CA）。Agent（包括ant 和particle）從起始細(xì)胞出發(fā)，根據(jù)相應(yīng)的函數(shù)轉(zhuǎn)換規(guī)則隨機(jī)從細(xì)胞狀態(tài)集合中進(jìn)行選擇，實(shí)

2、現(xiàn)復(fù)雜智能的“涌現(xiàn)”。隨后將BACO及BPSO-CA應(yīng)用于二元離散優(yōu)化問題——單0/1背包問題的求解，對(duì)其時(shí)間復(fù)雜度、空間復(fù)雜度、算法收斂性進(jìn)行分析，并通過拉長(zhǎng)細(xì)胞自動(dòng)機(jī)或增加細(xì)胞狀態(tài)集合中元素?cái)?shù)目的方式來(lái)對(duì)BACO及BPSO-CA進(jìn)行擴(kuò)展，適用于多維0/1背包問題的求解。但在問題求解的過程中，不可避免的會(huì)產(chǎn)生一些非法的個(gè)體，當(dāng)agent（包括ant 和particle）完成了它們的路徑構(gòu)建步驟之后，將具有局部搜索性能的貪心算法引入到具