求解不等球和不等圓Packing問題的高性能算法研究.pdf

1、NP難度問題在現(xiàn)實生產(chǎn)和生活中廣泛存在,其高效求解有著極其重要的經(jīng)濟價值、科研價值、軍事價值,但是,由于NP是否等于P一直是一個理論上懸而未決的難題,因而有效的求解其全局最優(yōu)解的算法隨著問題的規(guī)模變大而變得令人望而卻步,即使對于較小的N,非常簡單的問題,例如N=20的等圓裝填問題,其全局最優(yōu)解至今尚未被尋獲或證實。因此,設(shè)計高效能的啟發(fā)式算法,使得能在可獲得的計算資源、可接受的計算時間內(nèi)找到優(yōu)度盡量高的局部最優(yōu)解解成為當前唯一有效的解決

2、辦法。而在現(xiàn)實中,很多優(yōu)秀的啟發(fā)式算法也確實表現(xiàn)不俗,取得的結(jié)果比常規(guī)的經(jīng)驗性結(jié)果大為改進,產(chǎn)生巨大的效益。
　　論文的研究針對NP難問題中的兩個具有重要實用背景的形式簡單的實例:不等球和不等圓裝填問題,研究、設(shè)計求解它們的高性能算法并對結(jié)果進行了分析和討論。本論文主要綜合應(yīng)用禁忌搜索、迭代局部搜索、擬牛頓法、變鄰域搜索、擬牛頓法的連續(xù)優(yōu)化策略來解決這兩個問題,同時,在迭代局部搜索中,根據(jù)關(guān)鍵元素導向的擾動策略(CEGP),采用了

3、大圓或大球優(yōu)先的擾動策略。本文的主要創(chuàng)新點在于:
　　1、首次應(yīng)用迭代禁忌搜索來解決不等圓和不等球裝填問題;
　　2、在鄰域的構(gòu)造過程的連續(xù)優(yōu)化階段,使用擬牛頓法,大大提高了計算速度;
　　3、首次提出將某一較小的圓盤放置到某一較大的空穴然后進行連續(xù)優(yōu)化以形成鄰域的方法;
　　4、首次使用“打格子”的方法來尋找格局中的空穴;
　　5、不等圓裝填問題中將構(gòu)造鄰域的兩種方法在禁忌搜索中交替使用,應(yīng)用變鄰域搜索技

4、術(shù);
　　6、在迭代禁忌搜索的擾動過程中基于關(guān)鍵元素驅(qū)動的策略思想使用大圓盤優(yōu)先的擾動策略;
　　7、在擬牛頓法的迭代過程中,使用Greedy-Redo的貪心策略,大大節(jié)省了連續(xù)優(yōu)化的計算時間;
　　8、在擬牛頓法的過程的運行過程中設(shè)定時間檢查點,通過與其它鄰域的擬牛頓過程的對應(yīng)時間點時的優(yōu)度進行比較,進行貪心剪枝,以節(jié)省計算時間;
　　9、在不等球的裝填問題中,設(shè)計了一種外半徑容器可以根據(jù)計算情況自適應(yīng)變化的方

5、法,從而不需要在一開始就設(shè)定一個較合理的容器半徑以啟動計算;
　　通過本文設(shè)計的算法進行實驗計算,將結(jié)果與當今世界的最好記錄比較,對于其中的一個經(jīng)典系列,ri=1/i-1/2,改進了其中N=17-19和N=21-30的13項世界紀錄,N小于等于30的其它世界紀錄也都可以平。對于ri=i的另一個經(jīng)典算例系列,可以平其中的N=1-30的世界紀錄。以上結(jié)果顯示出本論文提出的算法具有相當?shù)膬?yōu)勢。
　　本論文進而分析了兩個系列算例的當