Search

Search Results

• EVOLUTION ALGORITHM FOR PARTITION BY METHOD OF CRYSTALLIZATION OF ALTERNATIVES FIELD

  B.K. Lebedev, O.B. Lebedev, Е. О. Lebedevа

  2020-07-20

  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.