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

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

2、并通過(guò)計(jì)算機(jī)模擬其中可循的規(guī)律，用來(lái)指導(dǎo)和解決傳統(tǒng)方法難以解決的實(shí)際問(wèn)題。 目前通過(guò)模擬生物群體的行為來(lái)解決優(yōu)化問(wèn)題已經(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基于對(duì)鳥(niǎo)群、魚(yú)群捕食行為的模擬，提出了粒子群優(yōu)化方法。由于這些方法概念簡(jiǎn)明、實(shí)現(xiàn)方便，特別用

3、以解決復(fù)雜的組合優(yōu)化問(wèn)題具有優(yōu)越性，迅速得到國(guó)際優(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)化算法基本原理和對(duì)已有的NP-hard問(wèn)題的求解過(guò)程，然后給出了改進(jìn)的對(duì)背包問(wèn)題的蟻群算法。此外，本文對(duì)基本粒子群算法原理作了系統(tǒng)深入的研究，對(duì)NP-難問(wèn)題求解的已有工作進(jìn)行了深入分析，在此基礎(chǔ)上，設(shè)計(jì)

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

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