Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

Co-evolution VLSI partitioning algorithm
Authors
	Lebedev B.K.
	Lebedev O.B.
Date of publication
	2020
DOI
	10.31114/2078-7707-2020-3-79-86
Abstract
	To increase the efficiency, enhance the convergence of the algorithm and the ability to exit local optima, the author proposes a co-evolution approach to the construction of the partition algorithm. At the same time, two subpopulations evolve in the search space of the optimization problem, each of which solves the same initial optimization problem, but having different search areas and optimization strategies. The co-evolutionary approach provides a wider overview of the solution space and a higher probability of localizing the global extremum of the problem. To solve the partition problem, the authors developed a modified metaheuristics by analogy with the models of adaptive behavior of ant algorithm (AA). In the work, in contrast to the canonical paradigm of AA. The interpretation of the solution is the subgraph Dk=(Xk∪Wk, Ek), which defines the distribution of the set of vertices Xk over the nodes of the set Wk. The operation of the algorithm actually consists in the formation of a subset of edges Ek. The partition problem is solved by two subpopulations of A1, A2 agents on the D=(X∪W,Y), DkD. Agents of subpopulation A1 construct a solution using the first constructive algorithm on the set of vertices Xk. Agents of subpopulation A1 use the second constructive algorithm on the set of vertices Xk. Strategies C1 and C2 are distinguished by constructive algorithms for splitting the circuit with agents. Both subpopulations form the same subset of Ek edges. For the experiments, we used the synthesis procedure for control examples with the well-known Fopt Optimum by analogy with the well-known BEKU method (Partitioning Examples with Tight Upper Bound of Optimal Solution). The study was subjected to examples containing up to 1000 vertices. The weight of the vertices was taken equal to zero, and the weight of all the edges was taken to be unity. In this case, the graphs were “divided” into two subgraphs with an equal number of vertices in each subgraph. Based on the processing of experimental studies, an average dependence of the quality of solutions on the number of iterations and population size was constructed. The quality estimate is Fopt/F, where F is the estimate of the resulting solution. It was found that the initial amount of pheromone Q should be 14 times greater than the average amount of pheromone τk(l) deposited by agents at each iteration. Update rate ρ=0.95. As a result of experiments, it was found that, with a population volume of M=100, the algorithm converges on average at 120 iterations. Comparative analysis with other partitioning algorithms was performed on standard test examples and diagrams (benchmarks), available on the websites: www.cad.polito.it/tools/9.html, www.cbl.ncsu.edu. The developed algorithms find solutions that are not inferior in quality, and sometimes even superior to their analogues by an average of 3-4%. On average, launching a program provides solutions that differ from the optimal solution by less than 0.5%.
Keywords
	VLSI, partitioning, swarm intelligence, ant algorithm, adaptive behavior, subpopulation, co-evolution, optimization.
Library reference
	Lebedev B.K., Lebedev O.B. Co-evolution VLSI partitioning algorithm // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2020. Issue 3. P. 79-86. doi:10.31114/2078-7707-2020-3-79-86
URL of paper
	http://www.mes-conference.ru/data/year2020/pdf/D029.pdf