浙江大学学报（工学版）
浙江大學學報（工學版）
절강대학학보（공학판）
JOURNAL OF ZHEJIANG UNIVERSITY(ENGINEERING SCIENCE)
2007年
10期
1679-1683
,共5页
电路划分%贪心随机自适应搜索过程%启发式策略%Path-Relinking
電路劃分%貪心隨機自適應搜索過程%啟髮式策略%Path-Relinking
전로화분%탐심수궤자괄응수색과정%계발식책략%Path-Relinking
为提高基于迭代改进的传统电路划分算法的划分质量,提出了一种基于贪心随机自适应搜索过程(greedy randomized adaptive search procedure,GRASP)的电路划分改进算法.GRASP由构造阶段和局部搜索阶段组成,能够快速构造较好的初始划分.在其构造阶段引入启发式子集选择策略,并与高效搜索技术Path-Relinking相结合,在各个局部最优解之间建立路径,从而有效搜索了局部最优解空间.实验结果表明,该算法与基本GRASP相比,能在合理的时间范围内改进解的质量,获得更好的划分结果.在获得的最小划分上,改进程度最大达到33.3%;而在平均划分上,最大达到27.4%.
為提高基于迭代改進的傳統電路劃分算法的劃分質量,提齣瞭一種基于貪心隨機自適應搜索過程(greedy randomized adaptive search procedure,GRASP)的電路劃分改進算法.GRASP由構造階段和跼部搜索階段組成,能夠快速構造較好的初始劃分.在其構造階段引入啟髮式子集選擇策略,併與高效搜索技術Path-Relinking相結閤,在各箇跼部最優解之間建立路徑,從而有效搜索瞭跼部最優解空間.實驗結果錶明,該算法與基本GRASP相比,能在閤理的時間範圍內改進解的質量,穫得更好的劃分結果.在穫得的最小劃分上,改進程度最大達到33.3%;而在平均劃分上,最大達到27.4%.
위제고기우질대개진적전통전로화분산법적화분질량,제출료일충기우탐심수궤자괄응수색과정(greedy randomized adaptive search procedure,GRASP)적전로화분개진산법.GRASP유구조계단화국부수색계단조성,능구쾌속구조교호적초시화분.재기구조계단인입계발식자집선택책략,병여고효수색기술Path-Relinking상결합,재각개국부최우해지간건립로경,종이유효수색료국부최우해공간.실험결과표명,해산법여기본GRASP상비,능재합리적시간범위내개진해적질량,획득경호적화분결과.재획득적최소화분상,개진정도최대체도33.3%;이재평균화분상,최대체도27.4%.
