在圓形Packing及團(tuán)簇結(jié)構(gòu)優(yōu)化問題上的啟發(fā)式優(yōu)化算法研究.pdf

1、NP難度的優(yōu)化問題廣泛的出現(xiàn)在科學(xué)研究和生產(chǎn)實(shí)踐的各個(gè)領(lǐng)域,是各自領(lǐng)域里的核心問題和瓶頸性問題。但是,關(guān)于計(jì)算復(fù)雜性理論的研究經(jīng)驗(yàn)表明,對(duì)于NP難度問題,可能根本不存在那種精確完備而又快速高效的求解算法。迄今為止,人們所能找到的關(guān)于NP難度問題的精確型求解算法都是指數(shù)型的,只能適用于問題規(guī)模較小的情形,或者問題本身有特殊結(jié)構(gòu)的情形。為了現(xiàn)實(shí)求解日常生活中出現(xiàn)的那些大規(guī)模的復(fù)雜的優(yōu)化問題,人們把目光轉(zhuǎn)向非完備的啟發(fā)式優(yōu)化算法。經(jīng)過最近幾十

2、年的研究,人們發(fā)現(xiàn),好的啟發(fā)式優(yōu)化算法往往能夠在合理計(jì)算時(shí)間內(nèi)找到高質(zhì)量的解方案,能夠又快又好的解決問題。啟發(fā)式優(yōu)化算法已成為計(jì)算機(jī)科學(xué)、人工智能和運(yùn)籌學(xué)領(lǐng)域的研究熱點(diǎn)。
　　論文首先對(duì)啟發(fā)式優(yōu)化算法的理論背景、經(jīng)典算法設(shè)計(jì)思路以及算法評(píng)價(jià)準(zhǔn)則進(jìn)行了系統(tǒng)的回顧。然后,以兩個(gè)經(jīng)典的有重要實(shí)際價(jià)值的問題――圓形Packing問題和團(tuán)簇結(jié)構(gòu)優(yōu)化問題――為研究介質(zhì),分別為其設(shè)計(jì)了高效的啟發(fā)式優(yōu)化算法,并通過計(jì)算實(shí)驗(yàn)對(duì)算法進(jìn)行了分析和評(píng)價(jià)。

3、論文的主要貢獻(xiàn)包括:
　　(1)為圓內(nèi)等圓Packing問題提出了一個(gè)高效的擬物型全局優(yōu)化算法。算法包含三個(gè)主要部分:擬物下降過程、擬物跳坑過程以及容器調(diào)整過程。擬物下降過程通過模擬n個(gè)光滑彈性圓餅在一個(gè)剛性容器內(nèi)的相互擠壓運(yùn)動(dòng)來引導(dǎo)所有圓餅到達(dá)一個(gè)局部最優(yōu)格局。擬物跳坑過程通過引入兩種非接觸的強(qiáng)烈的電磁排斥力和中心吸引力來刺激n個(gè)圓餅從局部最優(yōu)的陷阱中跳出來,到達(dá)解空間中某個(gè)更有前景的位置。容器調(diào)整過程將容器的半徑調(diào)整到一個(gè)合適

4、的值,使得圓餅之間沒有嵌入而且容器的半徑盡量小。使用了圓內(nèi)等圓Packing問題n=1,2,...,200的算例對(duì)算法進(jìn)行了測(cè)試,擬物型全局優(yōu)化算法在63個(gè)算例上找到比此前已知最優(yōu)記錄更優(yōu)的布局。
　　(2)為方內(nèi)等圓Packing問題提出了一個(gè)高效的貪心空穴搜索算法。首先為問題提出了一個(gè)貼切的物理模型,并以此為基礎(chǔ)為方內(nèi)等圓Packing問題提出了一個(gè)局部?jī)?yōu)化算法。然后,為方內(nèi)等圓Packing問題提出了一個(gè)貪心空穴搜索算法,它

5、通過不斷地將某個(gè)圓餅移動(dòng)到格局中最空的區(qū)域來產(chǎn)生優(yōu)度越來越好的解。使用了方內(nèi)等圓Packing問題n=1,2,...,200的算例對(duì)算法進(jìn)行了測(cè)試,貪心空穴搜索算法在41個(gè)算例上找到比此前已知最優(yōu)記錄更優(yōu)的布局。
　　(3)為雙原子團(tuán)簇結(jié)構(gòu)優(yōu)化問題提出了一個(gè)高效的啟發(fā)式優(yōu)化算法――3OP算法。雙原子團(tuán)簇結(jié)構(gòu)優(yōu)化問題是計(jì)算化學(xué)中的著名的挑戰(zhàn)性問題。問題的難度一方面是因?yàn)樵诮饪臻g中存在著天文數(shù)字的局部最優(yōu)構(gòu)型;另一方面,我們需要同時(shí)為

6、每個(gè)原子挑選坐標(biāo)位置和原子類型,因此問題中同時(shí)包含有連續(xù)優(yōu)化和離散優(yōu)化。論文提出的3OP算法系統(tǒng)地使用了三個(gè)有針對(duì)性的擾動(dòng)算子來不斷的改進(jìn)團(tuán)簇的構(gòu)型。依靠這三個(gè)擾動(dòng)算子,算法實(shí)際上在問題解空間的局部最小值集合上建立了一個(gè)復(fù)雜的鄰域結(jié)構(gòu)。以該鄰域結(jié)構(gòu)為基礎(chǔ),算法能夠從一個(gè)初始的局部最優(yōu)解出發(fā),不斷的找到優(yōu)度越來越好的局部最優(yōu)解。使用了雙原子團(tuán)簇結(jié)構(gòu)優(yōu)化問題上的標(biāo)準(zhǔn)算例對(duì)算法進(jìn)行了測(cè)試,算法在絕大部分算例上都找到了當(dāng)前的已知最好構(gòu)型,并在1