EVOLUTION ALGORITHM FOR PARTITION BY METHOD OF CRYSTALLIZATION OF ALTERNATIVES FIELD

Abstract

The operation of the partitioning algorithm is based on the use of collective evolutionary
memory, which means information that reflects the history of the search for a solution and is
stored independently of individuals. The algorithm associated with evolutionary memory seeks to
memorize and reuse ways to achieve better results. The collective evolutionary memory of the
partitioning 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 algorithm
and the number δ indicating the usefulness of the implemented alternative when constructing solutions
at previous iterations of the algorithm. The team does not have centralized management, and
its features are the presence of indirect exchange of information. Indirect exchange consists in
performing certain actions, at different times, during which some parts of evolutionary memory
change 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 a
mapping Fk=V→X, is represented as a bipartite subgraph Dk and is formed by sequentially assigning
elements 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 an
element to a node involves two stages. In the first stage, agent ai is selected, and in the second
stage, the node. In this case, the restriction must be fulfilled: each agent of the set A corresponds
to one unique node of the set V. The estimate ξk of the solution Qk and the utility estimate δk of the
set 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 alternatives
R* by the value δk. At the third stage, the utility estimates δk of the integral placer of alternatives are
reduced by μ. The paper uses the cyclic method of forming decisions. In this case, the building up of
estimates of the integral utility δk of the set of positions P is performed after the complete formation
of the set of solutions Q at iteration l. Experimental studies were carried out on the basis of formed
test cases with the optimal solution obtained earlier. The results obtained were compared with the
results obtained by other well-known algorithms for dividing circuits into parts. For comparison, a
set of standard benchmarks was formed. After analyzing the results, we can conclude that the proposed
method allows you to get 4–5 % better solutions than its analogues.