计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2013年
6期
1224-1234
,共11页
何琨%莫旦增%许如初%黄文奇
何琨%莫旦增%許如初%黃文奇
하곤%막단증%허여초%황문기
Packing问题%布局优化%拟物%平衡约束%粗精调技术
Packing問題%佈跼優化%擬物%平衡約束%粗精調技術
Packing문제%포국우화%의물%평형약속%조정조기술
packing problem%layout optimization%quasi-physical%equilibrium constraints%coarse and fine adjustment
带平衡约束的圆形Packing问题是以卫星舱布局为背景的具有NP难度的布局优化问题.文中建立了此问题相应的数学模型,同时提出了两个新的物理模型,并受工艺加工过程中“粗精加工”现象的启发,提出了基于粗精调技术的拟物算法QPCFA.该算法既兼顾了搜索空间的多样性以利于全局搜索,又能对有前途的局部区域进行精细搜索以找到相应的局部最优解.同时,在计算过程中引入禁忌技术和跳坑策略,以提高算法的求解质量.对国际上11个代表性的算例进行了计算,QPCFA更新了其中7个算例的最好记录,其余4个与目前的最好记录基本持平,且与目前的最好结果相比在计算精度上均有较大的提高.
帶平衡約束的圓形Packing問題是以衛星艙佈跼為揹景的具有NP難度的佈跼優化問題.文中建立瞭此問題相應的數學模型,同時提齣瞭兩箇新的物理模型,併受工藝加工過程中“粗精加工”現象的啟髮,提齣瞭基于粗精調技術的擬物算法QPCFA.該算法既兼顧瞭搜索空間的多樣性以利于全跼搜索,又能對有前途的跼部區域進行精細搜索以找到相應的跼部最優解.同時,在計算過程中引入禁忌技術和跳坑策略,以提高算法的求解質量.對國際上11箇代錶性的算例進行瞭計算,QPCFA更新瞭其中7箇算例的最好記錄,其餘4箇與目前的最好記錄基本持平,且與目前的最好結果相比在計算精度上均有較大的提高.
대평형약속적원형Packing문제시이위성창포국위배경적구유NP난도적포국우화문제.문중건립료차문제상응적수학모형,동시제출료량개신적물리모형,병수공예가공과정중“조정가공”현상적계발,제출료기우조정조기술적의물산법QPCFA.해산법기겸고료수색공간적다양성이리우전국수색,우능대유전도적국부구역진행정세수색이조도상응적국부최우해.동시,재계산과정중인입금기기술화도갱책략,이제고산법적구해질량.대국제상11개대표성적산례진행료계산,QPCFA경신료기중7개산례적최호기록,기여4개여목전적최호기록기본지평,차여목전적최호결과상비재계산정도상균유교대적제고.
