###
Journal of Software:2011.22(5):833-842

求解VLSI 电路划分问题的混合粒子群优化算法
郭文忠,陈国龙,XIONGNaixue,彭少君
(福州大学 数学与计算机科学学院,福建 福州 350108;福州大学 数学与计算机科学学院,福建 福州 350108;离散数学及其应用教育部重点实验室,福建 福州 350003;Department of Computer Science, Georgia State University, Georgia 30303, USA)
Hybrid Particle Swarm Optimization Algorithm for VLSI Circuit Partitioning
GUO Wen-Zhong,CHEN Guo-Long,XIONG Naixue,PENG Shao-Jun
(College of Mathematics and Computer Sciences, Fuzhou University, Fuzhou 350108, China;College of Mathematics and Computer Sciences, Fuzhou University, Fuzhou 350108, China; Key Laboratory of Discrete Mathematics with Applications of the Ministry of Education, Fuzhou 350003, China;Department of Computer Science, Georgia State University, Georgia 30303, USA)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 4935   Download 3928
Received:June 30, 2010    Revised:January 06, 2011
> 中文摘要: 电路划分是VLSI 物理设计过程中的一个关键阶段.该问题本质上是一个NP 困难的组合优化问题.针对该问题,提出了一种带FM 策略的混合粒子群优化算法.引入遗传算法的两点交叉算子和随机两点交换变异算子,保证了粒子在位置更新后依然可行;为了提高算法的局部搜索能力,将具有较强局部搜索能力的FM 策略融入算法的位置更新;设计了种群多样性变异策略,提高了种群多样性,避免了易陷入局部最优的缺陷.对ISCAS89 标准测试电路的仿真实验结果表明,所构造的算法是有效的.
Abstract:Circuit partitioning is an important part of any very large scale integration (VLSI) physical design automation, but it is a NP-hard combinatorial optimization problem. In this paper, a hybrid particle swarm optimization algorithm with FM strategy is proposed to approch this problem. Inspired by the mechinism of genetic algorithm (GA), two-point crossover and random two-point exchange mutation operators have been designed to avoid generating infeasible solutions. To improve the ability of local exploration, FM strategy is applied to the proposed algorithm to update its position. A mutation strategy is also built into the proposed algorithm to achieve better diversity and break away from local optima. Experiments on ISCAS89 benchmark circuits show that the proposed algorithm is efficient.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(10871221, 61070020); 国家重点基础研究发展计划(973)(2006CB805904, 2011CB808000); 福建省自然科学基金(A0820002, 2009J01284); 福建省科技创新平台计划(2009J1007) 国家自然科学基金(10871221, 61070020); 国家重点基础研究发展计划(973)(2006CB805904, 2011CB808000); 福建省自然科学基金(A0820002, 2009J01284); 福建省科技创新平台计划(2009J1007)
Foundation items:
Reference text:

郭文忠,陈国龙,XIONG Naixue,彭少君.求解VLSI 电路划分问题的混合粒子群优化算法.软件学报,2011,22(5):833-842

GUO Wen-Zhong,CHEN Guo-Long,XIONG Naixue,PENG Shao-Jun.Hybrid Particle Swarm Optimization Algorithm for VLSI Circuit Partitioning.Journal of Software,2011,22(5):833-842