改進(jìn)群體智能算法及其在背包問題中的應(yīng)用.pdf

1、隨著人類社會、經(jīng)濟(jì)和科學(xué)技術(shù)的飛速發(fā)展，許多復(fù)雜性、非線性、龐大巨系統(tǒng)和快速反應(yīng)性系統(tǒng)等方面的問題大量呈現(xiàn)在人們的面前，傳統(tǒng)的優(yōu)化方法逐漸陷入困境。這時，自然界中那些群居的簡單生物表現(xiàn)出來的復(fù)雜的群體智慧給人們很好的啟迪。這些生物群體中每一個個體的行為都很簡單，也沒有受到集中統(tǒng)一的指揮，但它們之間的有機(jī)協(xié)調(diào)和自組織能力，卻使得整個群體表現(xiàn)出高度的智慧，能夠完成非常復(fù)雜的任務(wù)。這種現(xiàn)象吸引了眾多學(xué)者的關(guān)注，去深入研究在現(xiàn)象背后存在的機(jī)理，

2、并通過計(jì)算機(jī)模擬其中可循的規(guī)律，用來指導(dǎo)和解決傳統(tǒng)方法難以解決的實(shí)際問題。 目前通過模擬生物群體的行為來解決優(yōu)化問題已經(jīng)成為優(yōu)化領(lǐng)域新的研究熱點(diǎn)，并已經(jīng)在一些實(shí)際應(yīng)用領(lǐng)域取得突破性的進(jìn)展。其中有代表性的有意大利學(xué)者M(jìn)arco Dorigo于1991年提出的蟻群優(yōu)化方法和1995年James Kennedy和Russell Eberhart基于對鳥群、魚群捕食行為的模擬，提出了粒子群優(yōu)化方法。由于這些方法概念簡明、實(shí)現(xiàn)方便，特別用

3、以解決復(fù)雜的組合優(yōu)化問題具有優(yōu)越性，迅速得到國際優(yōu)化計(jì)算領(lǐng)域的認(rèn)可，并在工程設(shè)計(jì)、生產(chǎn)優(yōu)化等應(yīng)用領(lǐng)域取得成功的應(yīng)用。 本論文重點(diǎn)研究了當(dāng)前應(yīng)用最廣泛、最典型的群體智能優(yōu)化方法——蟻群優(yōu)化方法和粒子群優(yōu)化方法。系統(tǒng)深入地分析了蟻群優(yōu)化算法基本原理和對已有的NP-hard問題的求解過程，然后給出了改進(jìn)的對背包問題的蟻群算法。此外，本文對基本粒子群算法原理作了系統(tǒng)深入的研究，對NP-難問題求解的已有工作進(jìn)行了深入分析，在此基礎(chǔ)上，設(shè)計(jì)

4、了一種新型的混合粒子群算法和實(shí)現(xiàn)步驟。上述理論研究成果都通過實(shí)際算例給出驗(yàn)證。體現(xiàn)了改進(jìn)算法的有效性和優(yōu)越性。 本文的主要創(chuàng)新點(diǎn)體現(xiàn)在三個方面： 一是在對基本蟻群算法原理、實(shí)現(xiàn)過程深入研究的基礎(chǔ)上，為了減小或避免基本蟻群算法容易早熟從而只是求得局部最優(yōu)解的可能性，給出了對局部最優(yōu)個體進(jìn)行變異的方法。同時考慮到信息素在蟻群算法中的重要性，對蟻群算法加以改進(jìn)，引入了基于信息素的變異算子——種群入侵算子，這兩種算子分別稱為內(nèi)變

5、異和外變異，根據(jù)這種混合變異提出了一種新的改進(jìn)方案，設(shè)計(jì)了這種新算法的實(shí)現(xiàn)步驟。 二是在對基本粒子群算法原理和實(shí)現(xiàn)過程深入研究的基礎(chǔ)上，提出了一種新的改進(jìn)方案，該算法引入遺傳算法中交叉和變異的思想，將當(dāng)前的適應(yīng)值與個體的適應(yīng)值及全局適應(yīng)值進(jìn)行交叉，得到新的適應(yīng)值，再進(jìn)行變異操作。在交叉操作過程中，采用了Davis提出的順序交叉方法。變異操作則采用了逆轉(zhuǎn)變異方法。由此設(shè)計(jì)了一種新型的混合粒子群算法和實(shí)現(xiàn)步驟。 三是將上述兩