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

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

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

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