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

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

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

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

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

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

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