（控制理论与控制工程专业论文）基于蚁群优化的pcb布线系统研究.pdf

成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：俪刍殳 2 0 o 年7 月芝妇 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 。| 口即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：f 西白父 导师签名：i 虱矛弋 妒年月矽日 基于蚁群优化的p c b 布线系统研究 摘要 本文针对基本蚁群算法原理在p c b 布线上的应用问题，提出几步修改 方法，首先搜寻出蚁群算法闭合环路中最长的支路路径，然后用环路路径 总长度减去这条路径得到非闭合环路最优路径的总长度，再对寻优路径重 新存储，使得以闭合环路中路径最长的那条支路为起始端和终端，最后再 用探索线段的方式完成对开叉型非闭合环路布线最优路径的衍化。 最后对蚁群算法基本原理在p c b 布线上应用的参数进行讨论，分别从 寻优最大值、寻优最小值、寻优平均值和寻优花费总时间进行比对，最终 确定一组比较适合在p c b 布线上应用的参数，并给出一个实例的仿真界面 图。 关键词：蚁群优化( a c o ) 最优路径非闭合路径算法p c b 布线 a b s t r a c t t h ep a p e rp r o p o s e st h em e t h o df o ri m p r o v i n gt h ea p p l i c a t i o no fa n t c o l o n yo p t i m i z a t i o no np c br o u t i n g f i r s t l y , f i n d i n go u tt h el o n g e s tr o u t ei na c l o s e dl o o po fa n tc o l o n yo p t i m i z a t i o na n dt h el e n g t ho ft h eo p t i m u mr o u t ei n t h en o n - c l o s e dr o u t i n gi sr e c e i v e db yu s i n gt h et o t a ll e n g t ho ft h ec l o s e dl o o p m i n u st h el e n g t ho ft h el o n g e s tr o u t e s e c o n d l y , t h er o u t eo ft h eo p t i m u mr o u t e i su p d a t e da n dm a k et w ot e r m i n a l so ft h el o n g e s tr o u t eb e c o m et h eb e g i n n i n g a n de n d i n gc o d eo ft h eo p t i m u mr o u t e t h i r d l y , t h ee v o l v e m e n to ft h eo p t i m u m r o u t ei nt h en o n c l o s e dr o u t i n gb a s e dt r e em o d e li sf m i s h e db yt h em e t h o do f e x p l o r i n g l i n e l a s t l y , w eh a v ead i s c u s s i o no nt h ep a r a m e t e r so f a n tc o l o n yo p t i m i z a t i o n a p p l i e do np c br o u t i n g ，f i n do u tas e r i e so fp a r a m e t e r sw h i c ha r ef i tf o rt h e a p p l i c a t i o no np c br o u t i n gb yc o m p a r i n g o nt h em a x i n u mo ft h eo p t i m u mr o u t e ， t h em i n i n u mo ft h eo p t i m u mr o u t e ，t h ea v e r a g eo ft h eo p t i m u mr o u t ea n dt h e t i m e s p a no ff i n d i n go u tt h eo p t i m u mr o u t e ，a n dg i v et h es i m u l a t i o ni n t e r f a c e d i a g r a m o fa ne x a m p l e k e yw o r d s ：a n t c o l o n yo p t i m i z a t i o n ( a c o ) ；t h eb e s tr o u t e ；t h en o n - c l o s e d r o u t e ；a l g o r i t h m ；p c br o u t i n g 摘要 j d l 】! i s t r a c t i i 目录i i i 第一章绪论1 1 1 引言1 1 2 电路板布线主要发展阶段1 1 2 1 手工布线初期阶段1 1 2 2 计算机辅助自动布线阶段2 1 2 3 超大规模集成电路布线系统的设计3 1 3 自动布线设计的分类5 1 3 1 有网格布线设计5 1 3 2 无网格布线设计6 1 4 国内对自动布线算法的探索7 1 5 工业上p c b 布线的主要使用软件介绍8 1 6 研究背景和本文基本架构8 第二章几种仿生智能优化算法及其在p c b 布线上的应用9 2 1 引言一9 2 2 遗传算法及其在p c b 布线上的应用一9 2 2 1 遗传算法简介9 2 2 2 遗传算法的特点及其不足9 2 2 3 遗传算法在p c b 布线问题上的应用1 0 2 3 模拟退火算法及其在p c b 布线上的应用1 2 2 3 1 模拟退火算法简介1 2 2 3 2 模拟退火算法的特点1 3 2 3 3 模拟退火算法在p c b 布线问题上的应用1 3 2 4 粒子群优化算法及其在p c b 布线上的应用1 4 2 4 1 粒子群算法简介及其模型1 4 2 4 2 粒子群算法在p c b 布线问题上的应用1 5 2 5 基于非曼哈顿的通道布线算法1 6 2 5 1p c b 布线的分区1 6 2 5 2 非曼哈顿通道布线算法的具体实现1 7 2 6 本章小结。1 9 第三章蚁群算法原理及其改进2 0 3 1 引言2 0 3 2 蚁群算法基本原理生物模型2 0 3 3 蚁群算法基本原理数学模型2 l 3 4 基本蚁群算法原理具体实现流程2 3 3 5 基本蚁群算法原理伪代码描述2 5 3 6 基本蚁群算法原理的特点2 7 3 7 基本蚁群算法原理的不足及其改进2 7 3 8 本章小结2 8 第四章蚁群算法在p c b 布线上的应用及其改进2 9 4 1p c b 布线系统应用的预备知识2 9 4 1 1 点与点之间的距离2 9 4 1 2 力一g e o m e t r y 布线理论2 9 4 2 蚁群算法在p c b 布线系统上的应用3 0 4 2 1 能见度的预处理3 0 4 2 2 最佳寻优路径的存储3 1 4 3 伪代码描述3 1 4 4 关于p c b 布线方法的改进3 3 4 4 1 路径长度计算方面的改进3 3 4 4 2 寻优路径起始端和终端的重新存储3 4 4 4 3 向开叉型非闭合环路布线路径的改进3 6 4 5 需要注意的问题不唯一性3 8 4 5 1 非闭合环路布线路径的不唯一性3 8 4 5 2 开叉型非闭合环路布线路径的不唯一性3 9 4 6 本章小结3 9 第五章实例仿真及其对参数的讨论一4 0 5 1 布线系统的坐标初始化4 0 5 2 参数的选择对蚁群算法布线的影响4 l i v 5 2 1 信息素影响因子口对蚁群算法布线的影响4 l 5 2 2 能见度系数对蚁群算法布线的影响4 2 5 2 3 挥发系数p 对蚁群算法布线的影响4 3 5 2 4 蚂蚁总数m 对蚁群算法布线的影响4 5 5 3 布线系统的仿真界面图4 6 5 3 1 非闭合环路布线路径仿真界面图4 6 5 3 2 开叉型非闭合环路布线路径仿真界面图4 7 5 4 本章小结4 7 第六章总结与展望4 8 6 1 总结4 8 6 2 展望4 8 参考文献4 9 致谢5 2 攻读学位期间发表论文情况5 3 v 广西大目臼i e b 掌位美譬墓于蚁曩筝1 蓖化的p c b 布线习0 晓研究 1 1 引言 第一章绪论 近年来随着经济的发展，人们日益增长的物质文化需求不断地促进着生产力的发 展。电子技术的出现是对人类生活的革命，千姿百态的电子设备更是使得人们的生活多 姿多彩。科技在创新，生活在进步，人们的需求也多种多样，这也促使电子技术也取得 了突飞猛进的进步。微型电子元器件为此应运而生，适时的适应了人们对电子设备小巧 便捷的要求，这样电子设备随身可带，随时随地都可以享受现代时尚生活给人们带来的 乐趣。 电子产品的灵巧性、可携带性和美观性，这都要求印制电路板( p 血t c d c 硫血b o a r d ， 简称p c b ) 既小巧又稳定，这就促进了电路板布线技术的发展。 1 2 电路板布线主要发展阶段 1 2 1 手工布线初期阶段 在早期电子技术不发达时期，各种电子元器件的连接基本都是靠导线来完成连接。 这样就使得电子设备体积太过庞大，并且由于线路接触不良造成不能正常工作的现象时 有发生。后来人们想到了在一个不能导电的板子上敷铜处理的办法，这样既减轻减小了 电子设备的重量和体积，另外焊接的方法也使得线路的连接更加稳固。手工简单敷铜的 方法在计算机技术未普及阶段，以及当今电子实验中对不是很复杂的单面电路板、双面 电路板时，或者对电路板布线轻巧灵便性要求不高且无需规模化生产时，我们都有采用， 一般对电路板采用手工布线。当今手工布线设计一般使用的是贴图法，其步骤是首先根 据原理图凭借设计者的经验而直接设计出p c b 图，然后打印在专用油纸上，在印制在 材料板上，再经过腐蚀、打磨、测试等工序再投入使用，如图l 一1 所示： | k 于蚁群优化的p c b 布线系统研究 选材并清洁版面 j 打印p c b 图纸 j 贴图并去除透明胶带 j i 用凡c 毛或环保蚀刻剂蚀刻 j 清水清洗并砂纸打磨光滑 j 测试校对 图1 - 1 手工布线流程图 f i g 1 - it h ef l o w c h a r to f m a n u a lr o u t i n g 手工电路板布线具有投资少，方便快捷、电路性能稳定等优点，但是也存在着不可 避免的缺点，大量的布线设计工作繁重且乏味很容易造成工作人员疲倦、烦躁而误操作 致使破坏电路板或电路板线路导致的经济损失。 1 2 2 计算机辅助自动布线阶段 一般少量或者精度型要求不高的电路板可以手工制作，但是大量的电路板要全都靠 手工制作完成恐怕难以接受且精度恐怕也难以达到要求。另外手工布线需要丰富的实践 经验，这限制了手工布线方法的全面普及。 随着电子计算机的产生和微型计算机的普及，计算机芯片等硬件设施各方面连年不 断完善，处理能力和速度不断提高，以及各种计算机辅助软件不断涌现为自动布线设计 工作提供了必要条件。自动布线设计的概念是由c m y 和k i s c h 在1 9 5 6 年首次提出的【l 】。 自动布线设计理念一经推出，便引起了工程人员和研究爱好者等的广泛兴趣，自动布线 概念在工程应用中广泛推广和实践应用，提高了生产效率和经济效益。自动布线设计具 体流程如图1 2 如下： 2 广西大学啊页士掌位论文 | k 亏咱良爿h 笔喇循由p c b 布线j 统习”宅 图1 2 自动布线流程图 f i g 1 - 2t h ef l o w e h mo f a u t om i n i n g 1 2 - 3 超大规模集成电路布线系统的设计 电子设备的不断小型化以及数字电路的出现，使得电路板线路的分布越来越密集， 特别是超大规模集成电路( v e 巧l 吨es o m e 删c 讹u i t ，简称v l s i ) 的出现，更是加 剧了电路布线的高精度性和复杂性。随着上世纪5 0 年代计算机辅助制造( c a d ) 技术的 出现，以及后期计算机辅助工程( c a e ) 、计算机辅助测试( c a t ) 、和计算机辅助制造 ( c a m ) 等计算机辅助软件的蓬勃发展使得电子设计自动化( e l 眦o m cd e s i 口 a u t o m a t i o n ，简称e d a ) 技术日臻完善，也使得用微型计算机实现超大规模集成电路布 线系统的设计成为可能，这种技术主要用来制造微处理器和存储器，其具体操作见图1 3 所示： 3 r - 西大掌硕士学位论文 基于蚁群啊臼眨的p c b 布线系崩巴习f 究 图1 - 3v l s i 电路设计流程图 f i g 1 - 3t h ef l o w c h a r to fv l s ic i r c u i td e s i g n 系统规范说明主要是指系统功能设计、性能指标和物理大小等参数。另外就是结合 以上三个参数决定采用设计的模式和制造流程，然后再根据这些指标确定工作速度、芯 片大小、制造工艺和功率损耗等。 系统功能设计主要是根据垂直约束图或者时序图避免循环约束的问题，减少后续设 计工程量。 通过逻辑设计工作得到v l s i 布线系统的逻辑结构，并对其进行逻辑最小化处理，并 模拟测试其正确性。 电路设计是根据以上步骤设定出的参数如功率损耗和工作速度以及需要采用的元 器件的性能参数来进行详细的电路图设计。 物理设计是v l s i 布线系统设计中耗时最长的步骤。它主要是把每个电子元器件的电 路及其互连的连接线转换成几何表示，这种电路的几何表示称之为版图【2 】，故此设计过 程又称作版图设计。 设计验证过程就是保证物理设计过程中所得到的几何图形符合系统规范说明中的 4 广1 重大粤明页士掌位簧譬| l 于蚁群优化的p c b 布线膏渔研究 各种适用规范。 芯片制造包含芯片的准备、杂质的注入、扩散工艺和光刻技术的应用等流程。 v l s i 布线技术是上世纪七十年代末期研制成功的，是自动布线史上的革命，其具备 以下几点特征： 1 微型性v l s i 顾名思义就是一块小小的p c b 板上集成着很多其他体积是非常 小的电子元器件，这是v l s i 技术最基本的特征。 2 成产成本低对于一个物品而言，只要它的体积小，那么要生产该种产品所要 花费的原料就相对减少，即生产成本随着体积的大小成反比例降低。 3 可靠性体积的减小使得在p c b 板上连接电子元器件的走线也相应减短，这就 减少了电磁耦合而产生串扰的可能性。 4 高度集成性v l s i 电路并不是由几个实现特定功能单元的功能模块拼接而成， 而是从综合性的角度考虑实现整体功能，大大较少连接各个功能模块之间的逻辑设计。 5 技术含量高v l s i 布线技术是建立在物理光学光刻技术、半导体技术、材料学 与工程、自动控制技术、加工工艺学等多种现代技术基础之上发展而来的。任何一项技 术的不足都会阻碍v l s i 技术的发展和应用。 1 3 自动布线设计的分类 1 3 1 有网格布线设计 1 9 6 1 年著名科学家g y l e e 提出了历史上著名的李氏算法，又称为迷路法或波 扩法。它的基本理论是：把p c b 板分成一定大小一定的n x n 网格，然后由起始点起步 向上、下、左、右四个方向搜索，已经走过的网格加入禁忌表( t a b ut a b l e ) ，这样逐步搜 索下去只要存在着通路，那么总能找到一条通往目的点的最短路径，这个过程叫做扩展 过程。当搜索到终点时则马上按照搜索路径逐步回找，这个过程叫做回找过程【3 1 。示意 图如图1 _ 4 所示： 5 ：嚣q j 广西大爿瞻页士掌位论文墓亏嗡疋群啊e 化的p c b 布线勇统研究 网格的路径寻址方式，同样是基于起始点向上、下、左、右四方一步一步步进到终点寻 优，截止后然后回找的过程。但是与有网格布线不同之处在于该处步进的不是有网格布 线设计中的小正方网格而是不能走线处边缘所形成的大网格，这样明显每次步进的网格 值大于有网格中的小网格，大大加快了步进的速度，提高了路径寻优的速度。示意图1 5 如下： 2 l2 4 5 l1 一一a 一 上 4 7 3 2 1 7 2 l v 34 l 0 5 i 山6 i l 舌l 4 一 广西大国昀页士学位论文| k 亏q 良群优化的p c b 布线膏诩巴研究 我国研究员杨瑞元教授在基于d 砒蚴t o w e r 线探索法之上，于1 9 8 0 年提出了朝 向目标的线探索法【9 】。这种算法的改进之处在于：它并不是从两等电位点交替发出逃避 线，而是以其中一点为起点发出带探索针的逃避线，不断向另外一个点行进，只要两点 之间存在着通路，这种逃避线就一定能够在探索针的指引下找到相通路径。但是这种算 法的不足之处就是：所搜索到的布线通路不一定是最短的，所以在路径寻优完成以后， 需要人工的手动进行优化改进。文献 5 】和 1 0 】都对线探索法进行了更深层次的分析和探 讨。 1 5 工业上p c b 布线的主要使用软件介绍 当今社会上有很多自动布线设计软件如美国c a d e n c e 公司的推出的o r c a d 、 s p e c 舰；美国i n n o v e d a 公司推出的的v i e w d r a w 、p o w 日p c b 和澳大利亚a h i 岫公司开 发的p r o w l 设计平台。 其中以舢t i 眦公司的p r o t e l 布线软件最富盛名，它整合了电路原理设计、p c b 自 动元件布局、p c b 自动布线和电路仿真实验结果分析等众多功能，并以良好的可操作性 和友好的界面在自动布线领域受到工程师们普遍青睐，也是我国工程师主要使用布线设 计软件。 尽管自动布线算法在我国已经有很多年深入的研究，但是市面上依然很难寻觅到我 国自身研发的布线软件。经过我们不懈努力相信在不远的将来，我们也将使用我国自主 研发的自动布线软件。 1 6 研究背景和本文基本架构 我们能看到关于p c b 布线的研究主要集中在有障碍物下的两点布线、多层布线板 的布局布线、布线单元之间的通道布线和减少多层布线板的通孔数布线算法研究，而对 单层布线板的多等电位节点布线鲜有研究，本文尝试性地提出一种改进方法。 本文第一章绪论主要介绍p c b 布线的发展历程、自动布线算法的分类、我国对p c b 布线算法的研究探索现状等；第二章主要是介绍近代几种仿生智能优化算法及其在p c b 布线领域应用的状况；第三章主要是关于蚁群算法基本原理和其特点的介绍；第四章是 本文的核心章节，主要是讲蚁群算法原理在p c b 布线系统应用上的改进：第五章是对 改进蚁群算法的实例仿真；第六章是对本文做一个总结并对不足之处提出展望。 8 广西大曹明曩士曹q 也论文 | k j q 良翻哺乞化的p c b 布线角0 皖研究 第二章几种仿生智能优化算法及其在p c b 布线上的应用 2 1 引言 p c b 布线方法日新月异，各种电子线路布线也错综复杂，针对高速信号电路中的电 磁干扰( e l e c t r o m a g n e t i ci n t e r f e r e n c e ) 提出了差分对布线方法( d i f f e r e n t i a l - p a i r s ) 【l i j ；为解 决通道布线问题，提出了长度约束布线法等【1 2 1 ，依然难以解决其他很多复杂的p c b 布 线问题。 随着人家对大自然的大千事物的逐步了解，人们对自然界的各种生物和现象都进行 了更深层次的分析和研究甚至模拟，这就奠定了仿生智能优化算法的研究基础。形形色 色的仿生智能优化算法的提出虽然暂时不能十分完美地解决各种应用问题，但是它们能 趋向于最优结果或次优结果，这就远强于为得到最优结果而去花费大量时间和金钱好得 多。仿生智能优化算法在生产生活、工程实践中不断实践、探索、改进，并且取得了显 著成果和喜人的成绩，节约了生产成本和提高了生产效率。现介绍几个著名的仿生智能 优化算法及其在布线领域的应用研究情况。 2 2 遗传算法及其在p c b 布线上的应用 2 2 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是美国m i c h i g a n 大学h o l l a n d 教授和他的学 生经过多年努力研究和探索后提出来的。这种算法主要是模仿自然界生物的发展与进化 的过程，以达尔文的生物进化论“物竞天择，适者生存”和孟德尔的遗传变异理论 为基础【1 3 】，是一种启发式全局优化搜索算法。它的基本思想理论过程是：首先选择一组 初始解，然后根据“染色体 在遗传算子、杂交算子、变异算子等多种仿生算子不断影 响下一代的方法进行优化迭代，并以适应度评价函数作为判定条件，优于当前结果则取 而代之，直到找到最优结果或者近似最优结果。如今遗传算法在多方面已经广泛应用， 如配电网规划【、流体机械1 卯、入侵检测n 6 1 、频域控制【1 刀、专家系统维护【1 8 l 等。 2 2 2 遗传算法的特点及其不足 遗传算法是一种复杂优化系统中的搜索算法，它的主要特点如下： 9 广西大学硕士掌位论文 基于蚁群优化的p c b 布线勇统研究 1 以可行解为算法中的编码对象 这样模仿生物界中基因和染色体的编码方式使得优化问题的最优解搜索过程很容 易地转化为生物的发展和进化的过程，有利于快速地搜索到最好结果或者次优结果。 2 以可行解为自变量建立了适用度函数 适用度函数的取值越大，说明这个可行解遗传到下一代的可能性就越大。这有效地 避免了除了要比较目标函数之外还需要其导函数为辅助的情况，大大地化简了整个求解 过程的运算难度，同样也使得搜索速度大大提高。 3 并行性 遗传算法搜索最优解的过程是从多个状态并行开始的，而不是像以往搜索最优解时 那样逐一比较得来，提高了搜索效率。 4 概率型搜索 搜索方式的概率性，使得搜索的方向不定。传统搜索方式方向的确定性使得搜索总 是朝着固定的方向前行，如果遇上特殊问题总是会陷入死角或者死点，造成无解或者局 部最优的情况。遗传算法的概率性搜索方式可以使其更有效地搜索到全局最优路径。 遗传算法的不足在于初始信息量过大容易造成运算缓慢的问题：“近亲繁殖 容易 导致过早收敛而陷入局部最优；对遗传算法的收敛性问题缺少广泛应用的有效性研究。 2 2 3 遗传算法在p c b 布线问题上的应用 1 预编码和对种群初始化 假如遗传算法的可行解的空间用染色体x 表示，令x = 【毛，x 2 ，】。这里的编码用 各个等电位节点编号来实现，五，而，毛分别代表各个等电位节点的编号。每一个可行 解的长度可能不同，这些不同长度相异的可行解就构成了初始化染色体的种群。在这里 要保证所选取的种群染色体之间的差异性，其区别越大就越容易跳出局部最优，收敛于 全部最优的概率就越大。整个搜索的过程就是在可行解x 的空间下，搜索到一条使得代 价函数f i x ) 取值最小的x 的取值的过程。 2 建立适应度评价函数 针对布线平面有比较多的等电位节点，选用以下函数作为适用度函数聊。 f = i ( 2 1 ) 州1 + 刀is ( o l ” 1 0 | 0 亏叫良硝哺乞化的p c b 布线曩0 晓研究 其中n 表示布线系统中所含的布线等电位节点总数；s ( i ) 表示的是对于染色体i 说， 布线系统中染色体x 已经用过的各种不同颜色的集合。 3 遗传进化过程 ( 1 ) 继承 遗传算法中的选择过程就是选择在上一代染色体中，利用适用度函数判断它的值比 较大，适应能力比较强的染色体遗传到下一代，相当于生物遗传学中的继承上一代比较 好的基因的过程。这个过程比较好地保留了上一次循环搜索中比较好的运算结果。 在n 个种群当中对于染色体i 来说，它的继承概率可以用公式2 2 表示为 只= 了生一 ( 2 2 ) 。 石+ 正+ + 五 ( 2 ) 杂交 在完成一次循环搜索得到若干个染色体即可行解，容易找出每条染色体中是否有相 同的基因成分，如果有相同的基因组成，那么可以对其进行杂交得到新的可行解。由于 遗传算法中染色体长度的可变性，杂交后的染色体的长度各有不同，那么我们可以选出 最优的结果。 例如在搜索过程中找到两条染色体，具体结构组成如厶= l ，0 ，6 ，4 ，8 ，3 ，2 和 厶= 3 ，5 ，9 ，7 ，8 ，1 0 ，1 3 ，这里存在交叉基因8 ，那么经过杂交变化之后，组成新的染色体 = 1 ，5 ，9 ，7 ，8 ，3 ，2 ) 和厶= 3 ，5 ，6 ，4 ，8 ，1 0 ，1 3 ，再对两条新的染色体和丘计算总长度， 如果_ _ m i n c 厶，厶) 或者丘_ ，每个可行解s 指的是每种循环遍 1 3 基于蚁霸阳已化的p c b 布线系统研究 历完所有等电位节点的一种排列组合，记为 乃，乃， 。其中乃，乃，瓦表示的是每 个可行解中的走线时各个等电位节点的依次顺序，并令+ ，= 乃。 2 适用度函数f ( s ) 的计算 设布线系统中有需要连接的等电位节点若干个，以及由各个节点之间的距离构成的 邻接矩阵d = 【吃】。，其中吃表示的是等电位节点i 到等电位节戊之间的距离。那么在 p c b 布线问题上的应用问题就是找出遍历完整个系统中的所有等电位节点，所走的总路 径长度最短，即厂( s ) = 噍确。适用度函数的差值则为瞄】： i = 1 鲈= ( z 铀+ 噍铂) 一0 0 + z 妒“) ( 2 - 4 ) 最后依据m e t r o p o l i s 准则判断是否接收新的信息状态点，如此循环反复，直到判定 适应度e 1 标函数f ( s ) 符合结束要求，即达到最大迭代次数或者结束迭代输出最优结果、 最接近最优结果。模拟退火算法在布线方面的研究和运用，解决了多层线路板布线分层 问题 2 4 , 2 5 1 ，充分利用已有的布线层资源，减少了p c b 板内通孔数，提高了布线质量 2 6 1 。 另外，模拟退火算法在高速p c b 布线应用中也较好地完成了对时钟二叉树的构建【2 7 1 和 降低了时钟树的整体功耗【2 蚋。 2 4 粒子群优化算法及其在p c b 布线上的应用 2 4 1 粒子群算法简介及其模型 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，简称p s o ) 是美国学者1 9 9 5 年受到飞 鸟群觅食的启发研究探索后提出的。当一个鸟群在一个陌生的环境觅食的时候，在天空 飞行的鸟都能看到食物在何处，它们都知道自己和食物相距的距离和自身该朝哪个方向 飞行。鸟群中的其他鸟也能通过交流也能获知此信息，当自身和食物相距比较远的时候 那么可以及时调节自己的飞行速度和方向，以便更好地朝食物飞行，更快地抢食食物。 那么，与食物相距距离的远近程度就决定了自身所处位置的优劣 2 9 3 2 】。虽然提出的时间 不长，但是一经提出就引起了科学研究人员的广泛兴趣，在工程应用、生产生活和科学 研究中已取得了一定的应用性研究成果，比如在溶解氧的优化问题和水文频率分析问题 都有有效的应用【3 3 ，3 4 】。 粒子群算法是以调整粒子自身位置为调优对象。在d 维空间当中，总数为m 个粒 1 4 广西大驾明炙士学位议咒墓于蚁群联化的p c b 布线系统研究 子群中的第i 个粒子来说，它的相对位置假如用向量乏= ( 而，而：，) 表示；速度用向 量瓦= ( u 。，峰：，) 表示，i = 1 , 2 , - - - m 。那么根据目标函数去得到适应度函数来调整粒子 i 的相对位置i 和相对速度瓦。具体可以根据以下公式来更新粒子自身的位置和速度【2 1 。 o + 1 ) = 国v 玉o ) + q 巧 p 耐( f ) 一x i d ( t ) + c 2 r 2 p g d ( t ) 一x g a ( t ) ( 2 - 5 ) o + 1 ) = ( f ) + o + 1 ) ( 2 6 ) 其中i 的取值为1 ，2 ，i n ；d 的取值为1 ，2 ，d 。缈是加权系数，它的取值越大， 那么搜索到全局最优路径的能力就越强，取值过小的话那么就趋向于局部最优。q 和乞 为常数，叫做学习因子；吒和吃是由r a n d ( ) 函数生成的o 、1 区间内的随机小数。 2 4 2 粒子群算法在p c b 布线问题上的应用 1 目标函数的建立 n - 1 以遍历完所有等电位节点总的距离三= 为目标函数。其中n 为布线系统中等电位 j = l 节点总数。 2 点阵的生成 对于有障碍物的布线系统用线探索的方式来收集布线系统的边缘点集，如图2 1 。 1 23456789 1 0 图2 - 1 点阵图 f i g 2 - 1t h ed i a g r a mo fd o t sa r r a y 3 实现步骤 ( 1 ) 对粒子群中的粒子进行位置和速度的初始化。 1 5 基亏q 良群优化的p c b 布线系统研究 三 进行初始化，其中对于每个粒子都要满足 f ，k 。圪1 速度按照矩阵v o = l ； 。 ；l 来完成初始化，同样对于每个粒子都要满足 l 巧= o ，i = l ，2 ，n o 假如有两个集合x = 五，置，以) 和y = 写，e ，k ) ，可得到它们之间的模糊矩 阵r = c 吩，。= 三： ，乃表示矩阵第；行中的数对于访问等电位节点，的隶属程 速度。我国研究者任斌提出一种多方向搜索粒子群算法【3 5 1 ，加快了搜索速度，提高了搜 2 5 基于非曼哈顿的通道布线算法 2 5 ip c b 布线的分区 其实p c b 布线按照区域可以分为单元布线区域和通道布线区域。单元布线区是每 个完成一个特定电路功能的单元，例如工作在高频率下的高速电路布线区、针对数字信 1 6 晶；晶 嚣 f l o 昂 m 阵 矩 乞 照 t 捌 i 土 置 b 位 驴 。闩 广西大学訇野嘿扛位美譬 | l 亏强良曩事优喇泊p c b 布线系箴研究 号处理的数字电路布线区、以及传统的模拟信号处理的模拟电路布线区或者为其他特定 功能而特别划定的单元布线区。单元布线区如图2 2 中灰色矩形区域，每个p c b 板有若 干个单元布线区组成。现在随着大家对生活水平追求的提高，对电路的要求也提出更高 要求，为了屏蔽各种不同类别信号之间的差异，所以有必要将它们进行分区布线。 r ? ? _ 鼍 少 一黧 ； 纽。345 。2 6 ，7 1 1 ，59 - 。2 ，1 2 7 1 0 1 1 1 3 捌 单元布线区一一通道布线区 形24i l65 。7 3 861 04i 3 9 31 28 耐 ，。w n ， 秀 骜 ， 孕 棼叠 熬i 蕊貔荆二= 觑彩；，j ，瓣嘉蔼刎铴黝黝勘删凇崩z 貔 图2 - 2p c b 布线分区示意图 f i g 2 - 2t h es u b a r e as k e t c hd i a g r a mo fp c br o u t i n g 通道布线区是将每个实现特别功能的单元布线区需要连接起来的信号连接起来的 。 布线区域。单元布线区和通道布线区的划分示意图如图2 - 2 所示，图中相同的阿拉伯数 字表示的是单元布线区所要连接起来的等电位点，o 表示的是无需连接的等电位点，其 他数字所代表的都是单元布线区内不同信号的等电位点，为了把各个单元区布线的信号 连接起来实现p c b 板的整体功能，需要在通道布线区内进行布线将这些数字相同的信 号点连接起来。 2 5 2 非曼哈顿通道布线算法的具体实现 非曼哈顿通道算法主要是应用在通道布线区域内的一种布线方法。这种布线方法把 布线层主要分成两层：第一层主要走水平线和斜4 5 。角；第二层基本上走的是垂直的线 段，最后第一层和第二层的互连则是通过通孔来连接。如图，所画的实线是第一层正面 上布的线，所画的虚线则是第二层背面布的线，黑色的点代表连接第一层正面和第二层 背面的通孔处。这种布线方式的主要目的是减少通孔数目、缩短走线长度、避免各个走 线线路之间的串扰。 1 7 墓于蚁群优化的p c b 布线习0 晓研究 2 霉tl6573861 04t 3931 287 1 0 ：= _ 、2 一：1 ；氛i勰。k 。一z i | 一一? | ? 一。矗一。? o = 南i i 茹。j 诫z t 讯“； 图2 - 3 基于非曼哈顿方法的通道区布线示意图 f i g 2 - 3t h es k e t c hd i a g r a mo f c h a n n e lr o u t i n gb a s e dn o n - m a n h a t t a n 基于非曼哈顿的通道布线算法具体实现步骤如下： 第一步，根据垂直约束图的连接示意图并采用线层转移的方法去掉约束图中的循环 约束的情况。 第二步，根据垂直约束图从左到右、从上到下、先短线后长线的原则得到所要布线 的通道的走线顺序三= q ，a 2 ，a n 。 第三步，从上到下、或者从左到右地逐渐递增的定义布线轨道数。 第四步，根据布线的通道的走线顺序逐项地搜索布线通道走线顺序中占用轨道数量 最大的列数记为c ，如图2 3 中第1 1 列，即2 4 列。 第五步，对于列数编号大于c 的列数，采用自左向右、自上而下的布线顺序，尽可 能少的占用布线轨道，这样一直逐列走线下去，直到走线到布线通道的最右边或者最下 边，如图2 3 中的1 2 一1 7 列。 第六步，对于列数编号小于c 的列数，采用第五步同样的布线顺序，尽可能少的占 用布线轨道，然后一直逐列走线下去，直到走线到布线通道中占用轨道数最多的那列c 左边的c - 1 列，图中如1 1 0 列。 第七步，在通道布线区的背面完成需要布的线，如图2 3 虚线所示。 第八步，在p c b 的通道布线区放置通孔，用以衔接正面所布的水平直线和斜4 5 0 角的走线。 第九步，统计出通道布线过程中所用到的总轨道数，计算出所需占用的总的距离， 然后算出每个轨道所占用的距离，完成整个通道布线的轨道分布的均匀化、美观化。 1 8 墓亏q 良期盹乞化的p c b 布线习漱研究 2 6 本章小结 本章主要介绍了近代几种人工智能优化算法和一种针对通道布线区的非曼哈顿布 线方法及其它们在p c b 布线上的应用情况。 1 9 广西大掌司n b 学位论文 蓉亏钧义群优1 艺的p c b 布线系统研究 3 1 引言 第三章蚁群算法原理及其改进 蚂蚁是一种大家都比较熟悉的节肢动物，属于昆虫纲。当蚂蚁群体外出觅食时，表 现出良好协作能力，总是能彼此通过触角交流信息或者从其他蚂蚁留下的痕迹获取信 息，并不会出现单个蚂蚁各行其是而脱离群体不参与协作的情况。 经过科学家长期努力研究发现，当蚂蚁在一个陌生的环境下觅食时，蚂蚁之间的沟 通协作主要是依靠它们身体内释放出来的生物荷尔蒙信息素( p h e r o m o n e ) 来完成 的。但是这种信息素的浓度会随着时间的往后推移而逐渐变淡。那么，相对长一些路径 上的信息素挥发得多一些，相对短一些的路径上的信息素就挥发得少一些，而后行蚂蚁 群它们总是选择信息素浓度强的路径行走，这就相当于选择了路径短的路径，这样对于 整体蚂蚁群来说就找到了一条通往食物源最短的路径。 3 2 蚁群算法基本原理生物模型 如图3 1 ( a ) 所示，左边为蚂蚁巢穴，右边为远处食物源。蚂蚁群的出发点到达食物 源有长短不同的两条路径，分别为路径1 和路径2 ，假设路径1 长度小于路径2 长度。 在开始寻找食物阶段，蚂蚁群随机地以相同概率地分别选择路径1 和路径2 去爬行( 如 图3 一l ( b ) 所示) 。但是在爬行过程中蚂蚁身体内的一种生物荷尔蒙信息素会沿途挥发， 分别在路径1 和路径2 上彰示它们爬行过此条路径。经过一段时间以后，这种生物信息 素会随着时间的推移会不断地挥发减弱。因为路径1 长度小于路径2 ，所以路径l 上的 信息素挥发的速度比路径2 上的信息素挥发的速度要慢，那么蚂蚁的后行者则沿着信息 素强的一条路径爬行。这样爬行在信息素强的路径上的蚂蚁也就越来越多，到最后蚂蚁 群体中所有成员都将选择路径短的路径1 行进到食物源，如图3 1 ( c ) 所示。蚁群算法原 理( a n tc o l o n yo p t i m i z a t i o n ，简称a c o ) 就是模拟蚂蚁群觅食的方式而提出的。 广西大肖昀炙士掌位谶譬 路径l 食 ， i j 路径2 ( a ) 路径l 食 荽 7 酵 j 薹 路径2 ( b ) 如路径1 秘 食 老。 掣7 ，、， i 棒 路径2 ( c ) 图3 - 1 生物界中的蚁群觅食模拟图 f i g 3 - 1t h es i m u l a t i o nd i a g r a mo f a n t sf o r a g i n gi nt h en a t u r e 3 3 蚁群算法基本原理数学模型 设蚁群系统中需要遍历的节点共有n 个，那么基本蚁群算法在t s p 问题中所要求 解的问题就是在遍历完这n 个所有的节点之后，然后再回到起点处，保证整个行进的距 离，即整个闭合的环路的长度为最小或者接近最小值。 在整个蚁群系统中m 表示在整个系统中蚂蚁的总个数，它等于岛( f ) ，其中包( f ) 是 i = l 指在时间t 时在节点i 处的蚂蚁总个数：t o ( t ) 表示的是在时间为t 的时候在节点i 和节 点j 之间的信息素的强度，意味着在时间t 之前其他前行蚂蚁所遗留下来的信号，它能 影响在节点i 处的蚂蚁对节点j 的选择。当一只蚂蚁在节点i 处，它是否向下一个节点j 行进，这要看向节点j 处行进的概率为多大，见下列公式3 1 。 2 1 l ； 墓