Ant colony system application to macrocell overlap removal
We present a novel macrocell overlap removal algorithm, based on the ant colony optimization metaheuristic. The procedure generates a feasible placement from a relative placement with overlaps produced by some placement algorithms such as quadratic programming and force-directed. It uses the concept of ant colonies, a set of agents that work together to improve an existing solution. Each ant in the colony will generate a placement based on the relative positions of the cells and feedback information about the best placements generated by previous colonies. The solution of each ant is improved by using a local optimization procedure which reduces the unused space. The worst runtime is O(n(3)), but the average runtime can be reduced to O(n(2)).
overlap removal ant colony optimization floorplanning macrocell placement wirelength minimization