多层布线有约束通孔最小化的遗传优化算法

提出了一种基于遗传算法的多层布线有约束通孔优化算法．算法允许通孔打在任意两层之间，并使得通孔不在它所穿过的层上与其它线网相交．通过在适应度函数中附加惩罚项，算法将有约束通孔优化问题转换为无约束通孔优化问题．同时采取面向线段的交配操作和面向线网的交配操作相结合的方式加快了算法的收敛速度．另外，自然编码方式与期望值选择机制也提高了算法的执行效率．实验结果表明本算法不仅优化效果好，而且收敛稳定和快速

A Genetic Optimization Algorithm of Constrained Via Minimization for Multi Layer Routing

A genetic algorithm is presented for constrained via minimization problems in multi layer routing. The algorithm allows vias to occur between any layers, but not to cross with the other nets at any layer. By adding penalty to fitness function, the constrained optimal problems can be transformed to non constrained optimal problems. The modified symmetric crossover speeds the convergence of the algorithm. In addition nature coding and expected value selection also improve the efficiency of GA. The experimental results show that the proposed algorithm not only generates fairly good solutions, but also converges steadily and rapidly.