Matrix Replication in Combinatorial Problems

The paper is devoted to applied methods for finding the global extremum in high-dimensional combinatorial problems. It is stated that the solution of these problems, for example, in the case of automated design decision-making, is reduced to solving an NP-complete optimization problem. It is assumed that the low efficiency of evolutionary and metaheuristic algorithms for solving this problem is caused by the fact that the goal function's global extremum is not accompanied by a trail of local extrema, but is located in isolation. To overcome this difficulty, it is proposed to introduce into the evolutionary search algorithm the mechanism of matrix replication, which explains well the evolutionary processes at the prebiological stage of the life's origin. The applied properties of the matrix replication mechanism are formulated, which are subject to algorithmization. Procedures for a genetic algorithm with matrix replication have been developed, various methods of matrix formation have been studied, and practical recommendations for choosing their number and size have been given. It is shown that the introduction of the matrix replication mechanism into the search algorithm makes it possible to split the original combinatorial problem into a number of subproblems of smaller dimension. It is substantiated that an independent solution of each subproblem with a fixed matrix increases the probability of finding a global extremum. A practical example of solving the problem of finding the optimal route for a cutting tool is given. The high efficiency of the proposed method in finding the global combinatorial extremum is confirmed.