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

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

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

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