本文關(guān)鍵詞：動作空間帶平衡約束圓形Packing問題的擬物求解算法

  更多相關(guān)文章： NP難度 圓形Packing 擬物 動作空間 平衡約束

【摘要】：對于一個(gè)以衛(wèi)星艙內(nèi)設(shè)備布局為背景的具有NP難度的全局優(yōu)化問題——帶平衡約束的圓形Packing問題,提出了基于動作空間的擬物求解算法.在擬物下降遇到局部極小點(diǎn)的陷阱時(shí),如何找到當(dāng)前格局下的最空閑空間以使搜索過程跳到更有前景的區(qū)域去是設(shè)計(jì)跳坑策略的一個(gè)關(guān)鍵難點(diǎn).借鑒求解矩形Packing問題中動作空間的概念,通過化"圓"為"方",將不規(guī)則的空閑空間近似為一系列規(guī)則的矩形空間,從而有效地解決了此難點(diǎn).另外,將擬物法與提前中止、粗精調(diào)和自適應(yīng)步長這3個(gè)擬人輔助策略相結(jié)合,以提高勢能下降的效率.對3組共13個(gè)代表性算例的計(jì)算結(jié)果及與國內(nèi)外代表性算法的比較表明,所提格局的外包絡(luò)圓半徑多為最小或次小,且在部分算例上找到了有更小外包絡(luò)圓半徑的格局,總體計(jì)算結(jié)果較好,且靜不平衡量的精度較高.
【作者單位】： 華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院;
【關(guān)鍵詞】： NP難度 圓形Packing 擬物 動作空間 平衡約束
【基金】：國家自然科學(xué)基金(61173180,61272014)~~
【分類號】：TP301.6
【正文快照】： 圓形Packing問題是高復(fù)雜度典型的NP難度問題,在無線通信、航空航天及交通運(yùn)輸?shù)阮I(lǐng)域均有著廣泛的應(yīng)用.隨著問題規(guī)模的增大,問題的解空間呈指數(shù)級膨脹,使得精確算法的求解時(shí)間過長而不適于實(shí)際應(yīng)用.國內(nèi)外研究者多采用啟發(fā)式方法求解此類問題,如擬物算法[1,2]、禁忌算法[3,4]

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前1條

1 黃文奇,趙孝武;求解正交數(shù)組問題的擬物擬人算法[J];計(jì)算機(jī)研究與發(fā)展;2002年02期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 趙孝武;求解正交表問題的擬物擬人方法[D];中國科學(xué)院軟件研究所;2001年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前3條

1 楊辰凱;求解帶平衡約束的圓形Packing問題的擬物擬人算法[D];華中科技大學(xué);2013年

2 蘇梅瑞;基于密度擴(kuò)散策略的純粹擬物算法研究與應(yīng)用[D];華中科技大學(xué);2008年

3 付樟華;求解等圓packing問題的擬物擬人算法[D];華中科技大學(xué);2007年

，

本文編號：1117380