OPTIMIZATION BASED ON COMBINING MODELS OF ADAPTIVE BEHAVIOR OF A SWARM OF AGENTS

Abstract

A bionic search architecture has been developed to solve the problem of placing VLSI elements
based on the hybridization of the algorithms of a bee colony and a swarm of chromosomes,
which allows you to get out of "local holes" and increases the convergence of the placement algorithm. The initial iterations are implemented by the bee algorithm to provide a broad overview of
the search area, and the final iterations are implemented by the chromosome swarm algorithm,
which ensures the exact localization of the extremum found by the bee algorithm. Agents are represented
as a population of chromosomes, which are genotypes for solving the placement problem.
The paper describes a modified paradigm of a swarm of chromosomes, which, in contrast to the
canonical method, provides the possibility of searching for solutions in the affine space of positions
with integer values of the parameters. In the search population method of optimization by a
swarm of chromosomes, the agents of the population are chromosomes. The chromosome is the
genotype of the optimization object. The essence of the search procedure is the successive change
of the states of the object of optimization (chromosome) by the directed mutation operator and the
search for the optimal state. An affine-relaxation model (ARM) of a swarm of chromosomes is
proposed - this is a graph whose vertices correspond to chromosomes, and arcs correspond to
affine bonds between them. The transition of the chromosome to a new state is carried out using a
relaxation procedure. In the work, the directed mutation operator acts as a means of changing the
solution, the essence of which is to change the integer values of genes in the chromosome. The
purpose of the transition is to reduce the weight of the affine bond between chromosomes. The
mechanisms of the directed mutation operator are described. A modified structure of the bee algorithm
is proposed. For each base chromosome, a probabilistic choice of a set of chromosomes
located in the vicinity of the base chromosome is implemented. It is possible to improve the quality
of the developed algorithm by adjusting the values of the control parameters. The time complexity
of the algorithm for fixed values of the population size and the number of generations is O(n). In
general, the dependence of the running time of the hybrid algorithm is O(n2) – O(n3).