A Multi-Objective Ant Colony Optimization for Routing in Printed Circuit Boards

Resumo

Automatic routing for Very Large-Scale Integration (VLSI) and Printed Circuit Board (PCB) design is an important tool to facilitate and optimize the work of engineers. Such a tool is typically provided by popular Computer-Aided Design (CAD) software and is a long-running research field. As electronics technology evolves and both discrete and integrated components get smaller and faster, the constraints to design circuits become more complex and new challenges arise. To deal with these difficulties, strategies using computational intelligence algorithms are employed to provide viable routing solutions in a timely manner. Within these strategies, multi-agent and swarm algorithms are highly relevant, being frequently applied alongside other approaches or by themselves. In this paper, we introduce a variation of the typical Ant Colony Optimization (ACO) algorithm modified to perform PCB routing, focusing on length matching between traces. The PCB area is divided into a grid that represents the search space for the algorithm. For each trace, the initial and final positions are known and contained within a cell of the grid. The routing of each trace is performed by an individual ant colony. The ants of a colony must travel from the initial to the final position of a trace to find the route that better fits the constraints of a multi-objective function. An ant in a cell can only move to neighboring cells. The number of movements it makes represents the length of the route. The algorithm consists of three steps. First, colonies and data structures are initialized. In the second step, one iteration is performed; the ants of each colony find a route to a trace. In the third step, the results found by the ants are evaluated, and the pheromone trails for the colonies are updated. The pheromone trails are updated based on a function that simultaneously minimizes three objectives: trace length, the number of times that traces cross with each other, and the length difference between traces. In other words, the ants try to find the shortest possible trace that has the same length as the other traces without crossing with them. Steps two and three are repeated until the maximum number of iterations is reached. We tested our algorithm in five fundamental scenarios and performed a statistical analysis on multiple executions of each scenario. The results obtained show that our algorithm is a viable approach to perform PCB trace routing with length matching.