由于集成电路的规模越来越小,通孔的失误率也就越来越高。双通孔的插入能够提高芯片的成品率和可靠度,减少由于通孔的故障而造成的电路板的成品率下降,所以这种方法是一个有效的和值得推荐的方法。论文中提出了一种用遗传算法来进行优化的双通孔插入方法,这种方法也可以应用于无网格布局的结构。首先建立一个用于表示通孔和冗余通孔之间的候选关系的无向图,这个无向图也能用于表示违反了设计规则的冗余孔之间的冲突关系。在这个无向图中,如果任何冗余孔之间都不存在着冲突关系,那么这个无向图就是一个二分图,如果是这种情况,冗余孔的插入问题就能通过最大二分匹配算法得以优化解决。否则,为了减小问题的规模,我么要对无向图进行预处理,如果冲突图中的连同分量是一个最大团并且这个连同分量的顶点代表冗余孔,它的边代表了两个冗余孔之间由于违反了设计规则而造成了冲突,我们就把这种连同分量合并成一个顶点(一个冗余孔)。最后,提出一种通过遗传算法来优化冗余孔的移除的方法,从而得到一个没有冲突的二分图,通过最大二分匹配算法来实现双通孔的插入。实验结果表明了这种方法对于实现双通孔的插入是很有效的。