CO-EVOLUTIONARY PLACEMENT ALGORITHM BASED ON INTERACTION SUBPOPULATIONS DIFFERING IN SEARCH STRATEGIES

Abstract

A new methodology and method for placing VLSI elements has been developed, which differ in that the solution of the placement problem is based on the use of a fixed order of position selection, focused on the effective solution of the placement problem, and a heuristic procedure for distributing elements by positions, which reduces the overall complexity and improves the quality of the solution. The process of forming a list of positions on the switching field is carried out using the mechanisms of the wave algorithm. The choice of the final list is based on the principle of constructing a route with a minimum estimate of the total linear length of distances between route positions. To solve the placement problem, a search algorithm based on the modified ant colony method has been developed. To exclude premature convergence and localization of the global extremum of the problem, the development of the algorithm was carried out on the basis of the coevolutionary approach. The architecture of the co-evolutionary placement algorithm is developed on the basis of the ant colony algorithm paradigm. In the search space, sub-populations implement four optimization strategies in parallel. In the work, the coevolution process is implemented on the basis of the interaction of subpopulations that differ in search strategies. A distinctive feature of the co-evolutionary approach used is that subpopulations of solutions are actually virtual. The process of co-evolution is implemented by one population of agents Z by sequential formation and merging of virtual subpopulations of solutions into one population. In this paper, the solution of the placement problem is aimed at improving traceability by minimizing the resources required to implement connections. A significant contribution to minimizing the spatial and temporal complexity of the search procedure was made by: the use by virtual sub-populations of a common evolutionary memory, a common solution search graph, the formation of a single interpretation of the solution in the form of a route on a complete directed graph with binary directed edges. Testing was carried out on benchmarks 19s, PrimGA1, PrimGA2. The results compared to existing algorithms are improved by 7-8%. The probability of obtaining a global optimum was 0.96. On average, solutions differ from the optimal by less than 1.5%. The time complexity of the algorithm for fixed values of the population size and the number of generations is O(n). The total time complexity of the hybrid algorithm is O(n2)−O(n3).