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).