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

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

2、年的研究,人們發(fā)現(xiàn),好的啟發(fā)式優(yōu)化算法往往能夠在合理計(jì)算時(shí)間內(nèi)找到高質(zhì)量的解方案,能夠又快又好的解決問(wèn)題。啟發(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)的回顧。然后,以?xún)蓚€(gè)經(jīng)典的有重要實(shí)際價(jià)值的問(wèn)題――圓形Packing問(wèn)題和團(tuán)簇結(jié)構(gòu)優(yōu)化問(wèn)題――為研究介質(zhì),分別為其設(shè)計(jì)了高效的啟發(fā)式優(yōu)化算法,并通過(guò)計(jì)算實(shí)驗(yàn)對(duì)算法進(jìn)行了分析和評(píng)價(jià)。

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

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

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

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