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

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

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