帶平衡約束的圓形Packing問題的算法研究.pdf

1、NP難問題在計(jì)算機(jī)科學(xué)中以難以求解而著稱,同時(shí)其在日常生活中被廣泛應(yīng)用,從而吸引了諸多學(xué)者的研究,并形成了許多相關(guān)的高效求解算法。研究了帶平衡約束的圓形Packing這一以衛(wèi)星艙布局為背景的具有NP難度的布局優(yōu)化問題。它是在典型NP難問題即圓形Packing問題的基礎(chǔ)上引入了靜不平衡約束,從而形成一個(gè)復(fù)雜的具有連續(xù)解空間的全局優(yōu)化問題。
　　根據(jù)問題特性建立了相應(yīng)的數(shù)學(xué)模型,同時(shí)提出了兩個(gè)新的物理模型,即彈力模型和拉力模型,將兩者

2、結(jié)合形成單目標(biāo)函數(shù)的擬物模型。在局部搜索過程中,受工業(yè)加工領(lǐng)域中“粗精加工”現(xiàn)象的啟發(fā),提出了粗調(diào)算法和精調(diào)算法,從而避免在無(wú)前景的局部區(qū)域花費(fèi)過多的計(jì)算時(shí)間,同時(shí)又能對(duì)有前景的區(qū)域進(jìn)行精細(xì)搜索以找到相應(yīng)的局部最優(yōu)解。當(dāng)計(jì)算陷入局部最小值陷阱時(shí),通過引入禁忌技術(shù)的跳坑策略,使計(jì)算不僅可以跳出當(dāng)前局部最小值點(diǎn)陷阱,而且可以盡量避免重復(fù)搜索相同的區(qū)域,從而提高算法的搜索效率。為了提高全局搜索能力,將遺傳算法的思想引入,并綜合粗精調(diào)技術(shù)的擬物

3、下降算法和禁忌技術(shù)的跳坑策略,形成基于粗精調(diào)技術(shù)的擬物算法QPCFA。該算法既兼顧了搜索空間的多樣性以利于全局搜索,又具有較快的局部搜索速度。
　　對(duì)國(guó)際上11個(gè)有代表性的算例進(jìn)行了計(jì)算,QPCFA更新了其中6個(gè)算例的最好記錄,其余5個(gè)與目前的最好記錄基本持平,且與目前的最好結(jié)果相比在計(jì)算精度上均有較大的提高。同時(shí),提出了如何基于典型的圓形Packing問題算例自然、公平地生成此問題新算例的方法,計(jì)算了兩組共34個(gè)生成的新算例并給