DEVELOPMENT OF A MODIFIED MODEL OF ADAPTIVE BEHAVIOR OF A ROY OF PARTICLES FOR ISSUING A MAXIMUM CLICK IN A GRAPH
A method is proposed for solving the problem of highlighting the maximum clique in a graph based on a modified model of adaptive behavior of a swarm of particles. The particle swarm method is a stochastic optimization method somewhat similar to evolutionary algorithms. This method does not model evolution, but swarm and pack behavior of animals. Unlike population methods, the particle swarm method works with one static population, whose members gradually improve with the advent of information about the search space. As a data structure that carries information about the solution, a sequence is used, which is the order in which the solution is formed, which is called a priority list. A priority list is a coded solution, in terms of a genetic algorithm, a “chromosome”. The priority list is an indirect decision coding scheme. The transition from the priority list to the decision is made using a decoder. A decoder is an operator that allows you to switch from an indirect (numerical) coding scheme for solving a problem to a phenotype. In fact, a priority list is an interpretation of a solution in a particular subject area. The search procedures in the space of solutions, the mechanisms of behavior of the modernized swarm of particles are described. The key problem that was solved in this paper is related to the development of the structure of an affine position space that allows us to display and search for interpretations of solutions with integer parameter values. In contrast to the canonical particle swarm method, in order to reduce the weight of affine bonds, by moving the particle to a new position in the affine solution space, a directed mutation operator has been developed, the essence of which is to change the integer values of the genes in the chromosome. The temporal complexity of the algorithm obtained experimentally coincides with theoretical studies and for the considered test problems is О(n2) - О(n3). The probability of obtaining a global optimum was 0.94. On average, launching a program provides solutions that differ from the optimal solution by less than 1.5 %. The results show that the proposed approach is an acceptable alternative for solving combinatorial problems.