基于人工免疫算法的PCB板布线研究.pdfVIP

自动化技术与应用》2012年第31卷第12期 控 制 理 论 与应 用 ControlTheoryandApplications 基于人工免疫算法的PCB板布线研究 蒋小兵 ，周永华 ．闪静洁 (广西大学 电气工程学院，广西 南宁 530004) 摘 ~：PCB单层板布线是不同等 电位线网的集合，每个线网就是n个等 电位点的无向连通图，于是PCB_布线可简化为n个等 电位点 最短路径搜寻。本文根据PCB布线特点对其进行了数学建模，而建模形成的二维空间度约束下的曼哈顿距离Steiner@9~树 问题精确算法难以实现，鉴于免疫算法在解决组合优化上的优势，引入免疫算法对PcB布线进行研究， 先对抗体进行文叉变 异操作 ，接着注射疫苗，最后通过免疫选择产生近似于steiner最优树的最小生成树，即为所求。并且通过人量数据分析得…算 法在 PCB板问题中的最佳参数，实验与仿真结果表明这种算法具有一定的有效性。 关键词：人工免疫算法 ；最优路径；最小生成树；Steiner最优树．PCB布线 中罔分类号：TP3l1．1 文献标识码 ：A 文章编号2012)12—0006 05 TheResearchAboutPCBRoutingBasedon ArtificiallmmUneAlgorithm JIANG Xiao-bing，ZHOUYong—hua，SHANJing-jie (CollegeofElectricalEngineering，GuangxiUniversity，Nanning530004China) Abstract：PCB routingofsinglelayerboardisacollectionofdifferentpotentiallinenetworks，whichisanondirectionalconnected graphofnpotentia1．SOthePCB routingcanbesimplifiedasshortestpathsearchingofnpotentialpoints．Accordingto thecharacteristicsofthePCBwiring，themathematicalmodelisestablishedas aproblem ofManhattandistanceSteiner rainimum spanningtreeundertWO—dimensionaldegreeconstraint．Theexactmethodcannotsolvetheproblem，because theimmunealgorithm hassomeadvantagestosolvecombinatorialoptimization，itisintroducedtosovlePCBwiring， antibodiesarefirstcrossedandmutated，thenimmunevaccinesareinjectedtoantibodies，atlastimmuneselectionis doneSOthatminimum spanningtreeisgenerated，itissimilartothesteinerchampiontree，thatisaskingforbyUS．And bestparametersareacquiredbyalargenumberofdataanalysis．Theexperimentandsimulationresultsshow thatthe new algorithm hasitseffectiveness． Keywords：immunealgorithm ；thebe