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).