Search

Search Results

• SEARCH POPULATION ALGORITHM FOR VLSI ELEMENTS PLACEMENT

  B.K. Lebedev , O. B. Lebedev , V.B. Lebedev

  2020-11-22

  Abstract ▼

  The paper considers a population search algorithm for the placement of VLSI components.
  By analogy with the process of the emergence and formation of crystals from matter, the process
  of generating a solution by sequential manifestation and concretization of the solution based on an
  integral placer of alternatives is called the method of crystallization of a placer of alternatives.
  The solution Qk of the placement problem is represented as a bijective mapping Fk = A → P, each
  element of the set A corresponds to one single element of the set P and vice versa. The
  metaheuristic of crystallization of a placer of alternatives underlying the algorithm searches for
  solutions taking into account collective evolutionary memory, which means information reflecting
  the history of the search for a solution and the memory of the search procedure. A distinctive feature
  of the metaheuristic used is that it takes into account the tendency to use alternatives from the
  best found solutions. Compact data structures for storing solution interpretations and memory are
  proposed. An algorithm associated with evolutionary memory seeks to memorize and reuse ways
  to achieve better results. The developed algorithm belongs to the class of population. The iterative
  process of finding solutions includes three stages. At the first stage of each iteration, the constructive
  algorithm generates nq solutions Qk. The work of the constructive algorithm is based on the
  indicators of the main integral placer of alternatives – the matrix R, which stores the integral indicators
  of the solutions obtained at the previous iterations. The process of assigning an item to a
  position involves two stages. In the first stage, the element is selected, and in the second stage, the
  position pj. In this case, the restriction must be fulfilled: each element corresponds to one position
  pj. The estimate ξk of the solution Qk and the estimate of the utility δk of the set of positions Pk selected
  by the agents are calculated. The work uses a cyclical method of forming decisions.
  In this case, the accumulation of estimates of the integral utility δk in the main integral placer of
  alternatives R is performed after the complete formation of the set of solutions Q. At the second
  stage of the iteration, the estimates of the integral utility δk are increased in the main integral
  placer of alternatives − the matrix R. At the third stage of the iteration, the estimates of the utility
  δk of the integral placer of alternatives R are reduced by a priori a given value δ*. The algorithm
  ends after the specified number of iterations has been completed. Comparative analysis with other
  solution algorithms was carried out on standard test examples (benchmarks) of the IBM corporation,
  while the solutions synthesized by the CAF algorithm exceed the solution efficiency of the
  known methods by an average of 6%. The time complexity of the algorithm is O(n2)-O(n3)

• POPULATION ALGORITHM FOR CONSTRUCTING A TREE OF SOLUTIONS BY METHOD OF CRYSTALLIZATION OF ALTERNATIVES FIELD

  B.K. Lebedev , O.B. Lebedev , V. B. Lebedev

  2020-11-22

  Abstract ▼

  In some cases, it becomes necessary to establish a correspondence between the declared
  and actual value of a categorical variable on the basis of a set of object characteristics. In this
  case, there is a need for a classifier with an optimal sequence of the considered attributes with agiven value of the objective function. The target variable can be: yes, no, variety number, class
  number, etc. This paper solves the problem of constructing a classification model in the form of an
  optimal sequence of the considered attributes and their values included in the route from the root
  vertex to the terminal vertex with a given value of the target variable. If a classifier is required
  that includes the possibility of alternative answers, then first, independently from each other, optimal
  routes are built for each value of the target variable, and then these routes are combined
  ("glued") into a single binary decision tree. In the algorithm for constructing a classifier based on
  the method of crystallization of a placer of alternatives, each solution Qk is interpreted as an oriented
  route Mk on a binary decision tree. Let us call the ordinal number of an element in the directed
  route Mk the position siS={si|i=1,2,…,nA}. An element of the route Mk is the pair (xi, ui-),
  where xi corresponds to Ai. ui- in the route Mk is an edge outgoing from xi and corresponds to the
  value Ai chosen together with Ai. The second index of the element ui- is determined after the choice
  of Ai, placed in the position sj+1 adjacent to sj. The work of the decision tree construction algorithm
  is based on the use of collective evolutionary memory, which is understood as information
  reflecting the history of the search for a solution. The algorithm takes into account the tendency to
  use alternatives from the best solutions found. The peculiarities are the presence of an indirect
  exchange of information – stigmerges. The totality of data on alternatives and their assessments
  constitutes a scattering of alternatives. The key points of the analysis of alternatives in the process
  of evolutionary collective adaptation are considered. Experimental studies have shown that the
  developed algorithm finds solutions that are not inferior in quality, and sometimes surpass their
  counterparts by an average of 3–4 %. The time complexity of the algorithm, obtained experimentally,
  lies within O(n2)-O(n3).

• EVOLUTIONARY POPULATION METHOD FOR SOLVING THE TRANSPORT PROBLEM

  B.К. Lebedev, О.B. Lebedev, Е.О. Lebedevа

  2022-11-01

  Abstract ▼

  The paper considers an evolutionary population method for solving a transport problem
  based on the metaheuristics of crystallization of a placer of alternatives. We study a closed (or
  balanced) model of the transport problem: the amount of cargo from suppliers is equal to the total
  amount of needs at destinations. The goal of optimization is to minimize the cost (achieving a minimum
  of transportation costs) or distances and the criterion of time (a minimum of time is spent on
  transportation). The metaheuristics of the crystallization of a placer of alternatives is based on a
  strategy based on remembering and repeating past successes. The strategy emphasizes «collective
  memory», which refers to any kind of information that reflects the past history of development and
  is stored independently of individuals. An ordered sequence Dk of routes is considered as a code
  for solving the transport problem. The objects are routes, the alternatives are the set of positions P
  in the list, where np is the number of positions in the list Dk. The set of objects Dk corresponds to
  the set of all routes. The set of alternative states P of the object corresponds to the set of alternative
  options for placing the object in the list Dk. The operation of the population evolutionary algorithm
  for the crystallization of a placer of alternatives is based on a collective evolutionary
  memory called a placer of alternatives. A scattering of solution alternatives is a data structure
  used as a collective evolutionary memory that carries information about the solution, including
  information about the realized alternatives of agents in this solution and about the usefulness of
  the solution. A constructive algorithm for the formation of a reference plan by decoding the list Dk
  has been developed. At each step t, the problem of choosing the next route in the sequence Dk and
  determining the amount of cargo transported from the point of departure Ai to the point of destination
  Bj along this route is solved. The developed algorithm is population-based, implementing the
  strategy of random directed search. Each agent is a code for some solution of the transport problem.
  At the first stage of each iteration l, a constructive algorithm based on the integral placer of
  alternatives generates nk decision codes Dk. The formation of each decision code Dk is performed
  sequentially in steps by sequentially selecting an object and position. For the constructed solution
  code Dk, the solution estimate ξk and the utility estimate δk are calculated. An individual scattering
  of alternatives Rk is formed and a transition to the construction of the next solution code is formed.
  At the second stage of the iteration, the integral placer of alternatives formed at previous iterations
  from l to (l-1) is summed with all individual placers of alternatives formed at iteration l.
  At the third stage of iteration l, all integral utility estimates r*
  αβ of the integral placer of alternatives
  R*(l) are reduced by δ*. The algorithm for solving the transport problem was implemented in
  C++ in the Windows environment. Comparison of the values of the criterion, on test examples,
  with a known optimum showed that in 90% of the examples the solution obtained was optimal, in
  2% of the examples the solutions were 5% worse, and in 8% of the examples the solutions differed
  by less than 2%. The time complexity of the algorithm, obtained experimentally, lies within O(n2).