摘要
PCB单层板布线是不同等电位线网的集合,每个线网就是n个等电位点的无向连通图,于是PCB布线可简化为n个等电位点最短路径搜寻。本文根据PCB布线特点对其进行了数学建模,而建模形成的二维空间度约束下的曼哈顿距离Steiner最优树问题精确算法难以实现,鉴于免疫算法在解决组合优化上的优势,引入免疫算法对PCB布线进行研究,首先对抗体进行交叉变异操作,接着注射疫苗,最后通过免疫选择产生近似于steiner最优树的最小生成树,即为所求。并且通过大量数据分析得出算法在PCB板问题中的最佳参数,实验与仿真结果表明这种算法具有一定的有效性。
PCB routing of single layer board is a collection of different potentialline networks, which is a nondirectional connected graph of n potential, so the PCB routing can be simplified as shortest path searching of n potential points. According to the characteristics of the PCB wiring ,the mathematical model is established as a problem of Manhattan distance Steiner minimum spanning tree under two-dimensional degree constraint. The exact method can not solve the problem, because the immune algorithm has some advantages to solve combinatorial optimization,it is introduced to sovle PCB wiring, antibodies are first crossed and mutated ,then immune vaccines are injected to antibodies,at last immune selection is done so that minimum spanning tree is generated, it is similar to the steiner champion tree, that is asking for by us. And best parameters are acquired by a large number of data analysis. The experiment and simulation results show that the new algorithm has its effectiveness.
出处
《自动化技术与应用》
2012年第12期6-10,共5页
Techniques of Automation and Applications
