计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2010年
10期
197-201
,共5页
刘耿耿%王小溪%陈国龙%郭文忠%王少铃
劉耿耿%王小溪%陳國龍%郭文忠%王少鈴
류경경%왕소계%진국룡%곽문충%왕소령
超大规模集成电路%布线%粒子群优化%最小矩形Steiner树%障碍物
超大規模集成電路%佈線%粒子群優化%最小矩形Steiner樹%障礙物
초대규모집성전로%포선%입자군우화%최소구형Steiner수%장애물
最小矩形Steiner树问题是VLSI布线的一个关键问题,且是一个典型的NP完全问题.为了有效地解决VLSI布线中考虑障碍物的最小矩形Steiner树问题,提出了一种改进的离散粒子群优化算法.考虑到存在障碍物,设计了一个基于惩罚的适应度函数.引入了遗传算法的变异和交叉算子,增加了种群的多样性并适当地扩展了粒子的寻优范围.实验结果表明,算法是有效的,实现简单,且相对遗传算法能更有效迅速地收敛.
最小矩形Steiner樹問題是VLSI佈線的一箇關鍵問題,且是一箇典型的NP完全問題.為瞭有效地解決VLSI佈線中攷慮障礙物的最小矩形Steiner樹問題,提齣瞭一種改進的離散粒子群優化算法.攷慮到存在障礙物,設計瞭一箇基于懲罰的適應度函數.引入瞭遺傳算法的變異和交扠算子,增加瞭種群的多樣性併適噹地擴展瞭粒子的尋優範圍.實驗結果錶明,算法是有效的,實現簡單,且相對遺傳算法能更有效迅速地收斂.
최소구형Steiner수문제시VLSI포선적일개관건문제,차시일개전형적NP완전문제.위료유효지해결VLSI포선중고필장애물적최소구형Steiner수문제,제출료일충개진적리산입자군우화산법.고필도존재장애물,설계료일개기우징벌적괄응도함수.인입료유전산법적변이화교차산자,증가료충군적다양성병괄당지확전료입자적심우범위.실험결과표명,산법시유효적,실현간단,차상대유전산법능경유효신속지수렴.
