EVOLUTION ALGORITHM FOR PARTITION BY METHOD OF CRYSTALLIZATION OF ALTERNATIVES FIELD
Б.К. Лебедев, Oleg Borisovich Lebedev, Ekaterina O. Lebedeva · Известия Южного федерального университета. Технические науки · 2020
The operation of the partitioning algorithm is based on the use of collective evolutionarymemory, which means information that reflects the history of the search for a solution and isstored independently of individuals. The algorithm associated with evolutionary memory seeks tomemorize and reuse ways to achieve better results. The collective evolutionary memory of thepartitioning algorithm is a set of statistical indicators that reflect, for each implemented alternative,the number θ of its occurrences in the best solutions at previous iterations of the algorithmand the number δ indicating the usefulness of the implemented alternative when constructing solutionsat previous iterations of the algorithm. The team does not have centralized management, andits features are the presence of indirect exchange of information. Indirect exchange consists inperforming certain actions, at different times, during which some parts of evolutionary memorychange by one agent. In the future, this changed information is used by other agents in these parts.First, at each iteration, a constructive algorithm generates nk solutions Qk. Each solution Qk is amapping Fk=V→X, is represented as a bipartite subgraph Dk and is formed by sequentially assigningelements to nodes. The formation of each solution Qk is performed by the set of agents A,by means of the probabilistic choice by each agent ai of the node vj. The process of assigning anelement to a node involves two stages. In the first stage, agent ai is selected, and in the secondstage, the node. In this case, the restriction must be fulfilled: each agent of the set A correspondsto one unique node of the set V. The estimate ξk of the solution Qk and the utility estimate δk of theset of alternatives implemented by the agents in the solution Qk are calculated. At the second stage,the agents increase the integral utility of the set of alternatives in the integral placer of alternativesR* by the value δk. At the third stage, the utility estimates δk of the integral placer of alternatives arereduced by μ. The paper uses the cyclic method of forming decisions. In this case, the building up ofestimates of the integral utility δk of the set of positions P is performed after the complete formationof the set of solutions Q at iteration l. Experimental studies were carried out on the basis of formedtest cases with the optimal solution obtained earlier. The results obtained were compared with theresults obtained by other well-known algorithms for dividing circuits into parts. For comparison, aset of standard benchmarks was formed. After analyzing the results, we can conclude that the proposedmethod allows you to get 4–5 % better solutions than its analogues.