求解帶平衡約束的圓形Packing問題的擬物擬人算法.pdf

1、圓形Packing問題是高復(fù)雜度的典型的NP難度問題,在無線通信、航空航天以及交通運輸?shù)阮I(lǐng)域均有著廣泛的應(yīng)用背景。由于問題的客觀難度,精確算法的求解時間過長而不適用于相關(guān)的實際應(yīng)用,因此研究者多采用啟發(fā)式方法求解此問題,其中,擬物法通過在自然世界中尋找與原始問題等價的物理現(xiàn)象,從中受到啟發(fā)而設(shè)計出高效率求解算法。研究了圓形Packing問題的一個重要擴展問題——帶平衡約束的圓形Packing問題。該問題是一個以衛(wèi)星艙設(shè)備布局為背景的全局

2、優(yōu)化問題,它在圓形Packing問題的基礎(chǔ)上引入了靜平衡約束。
　　通過對問題的深入分析,以擬物法為基礎(chǔ)建立了問題的擬物模型,將問題的3個約束轉(zhuǎn)化成單目標(biāo)優(yōu)化函數(shù)。在局部搜索過程中,將擬物法與擬人法相結(jié)合,提出了若干擬物下降的新策略,有效地提高算法的全局搜索能力和局部搜索速度。當(dāng)計算陷入局部極小值陷阱時,借鑒求解矩形Packing問題的“動作空間”的概念,化“圓”為“方”,提出了一種基于“動作空間”的跳坑方法,從而使搜索快速有效地

3、離開局部極小點并跳到有前景的區(qū)域中去。為了盡量避免重復(fù)計算以前搜索過的區(qū)域,在跳坑策略中結(jié)合了禁忌技術(shù)。綜合改進的擬物下降算法和擬人跳坑策略,形成了基于動作空間的擬物算法QPAS。
　　對目前國際上公開的11個有代表性的算例進行了計算,實驗表明,算法QPAS在外包絡(luò)圓半徑、計算精度以及計算耗時三方面均有較好的表現(xiàn)。同時,將兩組共34個公開的典型圓形Packing問題的算例改造成帶平衡約束圓形Packing問題的新算例,并用其對算法