MATRIX REPLICATION IN NP-COMPLETE PROBLEMS OF COMBINATORIAL OPTIMIZATION
Authors: Подвальный С.Л. , Васильев Е.М. 
Published: October 2022

Ставится задача повышения вероятности нахождения глобального экстремума в NP-полных задачах комбинаторной оптимизации большой размерности. Показано, что комбинаторный характер формирования вариантов решений приводит к изолированному расположению глобального экстремума в области определения функции цели. Указанное обстоятельство существенно снижает эффективность эволюционных алгоритмов поиска, основанных на воспроизведении свойств наследственности и изменчивости в биологической эволюции. В связи с этим предложено ввести в упомянутые алгоритмы механизм матричной репликации. В соответствии с гипотезой М. Эйгена, этот механизм характерен для добиологического этапа возникновения жизни и заключается в формировании макромолекул путём их наращивания элементарными блоками по принципу сигнатуры - самоинструкции. Проанализированы свойства матричной репликации, раскрыто содержание алгоритмических процедур, необходимых для её реализации: построение матриц репликации, осуществление независимой эволюции для каждого варианта матрицы; отбор лучших вариантов. Получены количественные оценки многообразия вариантов возможных матриц и вариантов решений с ними. Даны рекомендации по выбору длины матрицы и их количеству при решении практических задач. Отмечено, что введение матрицы репликации в алгоритм генетического поиска снижает размерность исходной задачи на длину этой матрицы и, как следствие, сводит решение исходной задачи к решению конечного ряда подзадач меньшей размерности. Представлен пример использования механизма матричной репликации для решения NP-полной задачи нахождения оптимального маршрута, и подтверждена эффективность применения этого механизма при поиске глобального экстремума

The task is to increase the probability of finding a global extremum in NP-complete high-dimensional combinatorial optimization problems. We show that the combinatorial nature of the formation of solutions leads to an isolated location of the global extremum in the domain of the goal function. This circumstance significantly reduces the efficiency of evolutionary search algorithms based on the reproduction of the properties of heredity and variability in biological evolution. In this regard, we propose to introduce a matrix replication mechanism into the mentioned algorithms. In accordance with the hypothesis of M. Eigen, this mechanism is characteristic of the prebiological stage of the emergence of life, and consists in the formation of macromolecules by building them up with elementary blocks according to the principle of signature - self-instruction. We analyzed the properties of matrix replication and disclosed the content of the algorithmic procedures necessary for its implementation: the construction of replication matrices, the implementation of independent evolution for each variant of the matrix; selection of the best options. We obtained quantitative estimates of the variety of options for possible matrices and solutions with them. We give recommendations on the choice of the length of the matrix and their number in solving practical problems. We note that the introduction of a replication matrix into the genetic search algorithm reduces the dimension of the original problem by the length of this matrix and, as a result, reduces the solution of the original problem to solving a finite number of subproblems of lower dimension. We presented an example of using the matrix replication mechanism for solving the NP-complete problem of finding the optimal route and confirmed the efficiency of using this mechanism in the search for a global extremum