基于混合离散粒子群优化的轨道分配算法

现有的轨道分配工作大多忽略局部线网问题,并且容易陷入局部极值.为此,文中基于离散粒子群优化、遗传操作和基于协商的精炼策略,综合考虑局部线网、重叠冲突、线长和障碍物,提出轨道分配算法.算法抽象局部线网,构建对应的线段模型.为了扩大种群多样性,混合遗传操作以提高全局搜索效率.同时,设计简单高效的适应度函数.最后,使用基于协商的精炼策略进一步减少线段重叠.实验表明文中算法的有效性,该算法可以获得较佳的重叠代价指标优化值,减少关键布线区域的拥挤情况.

Track Assignment Algorithm Based on Hybrid Discrete Particle Swarm Optimization

Most of the existing track allocation works neglect the local nets problem, and are prone to fall into the local extremums. Based on discrete particle swarm optimization, genetic operation and negotiation-based refining strategy, a track assignment algorithm is proposed by considering local nets, overlapping conflict, wirelength and blockages. The algorithm abstracts local nets and constructs the corresponding model of segments. To expand population diversity, hybrid genetic operation is incorporated to improve the efficiency of global search. At the same time, a simple and efficient fitness function is designed. Finally, the negotiation-based refining strategy is exploited to further reduce the overlap of segments. The experimental results indicate the effectiveness of the proposed algorithm. The algorithm can obtain better overlapping cost index optimization value and reduce the congestion in the key routing area.