SOFTWARE SUBSYSTEM FOR SOLVING NP-COMPLEX COMBINATORIAL LOGIC PROBLEMS ON GRAPHS

Abstract

The paper is devoted to the development of the software for solving NP-hard and NP-hard combinatorial-logical problems on graphs. The paper contains a description of graphs combinatorial- logical problems. New multilevel search architectures such as simple combo, parallel combo, two-levels, integrated, and hybrid are proposed to effectively address them. These architectures are based on methods inspired by natural systems. The key difference between these architectures is the division of search into two or three levels and the use of various algorithms for evolutionary modeling and bioinspired search on them. This allows obtaining sets of quasi-optimal solutions to perform parallel processing and partially eliminate the problem of premature convergence. The article provides a detailed description of the developed software subsystem and its modules. As modules in the subsystem, there are five developed architectures and a set of developed algorithms for evolutionary modeling and bioinspired search, such as evolutionary, genetic, bee, ant, firefly and monkey. Thanks to its modular structure, the subsystem has the ability to design more than 50 different search combinations. This makes it possible to use all the advantages of bioinspired optimization methods for efficiently solving NP-complex combinatorial-logical problems on graphs. To confirm the effectiveness of the developed software subsystem, a computational experiment was carried out on test examples. The series of tests and experiments carried out have shown the advantage of using a software product for solving combinatorial-logical problems on graphs of large dimension, in comparison with known algorithms, which indicates the prospects of using this approach. The time complexity of the developed algorithms is O(nlogn)) at best, and O (n3) at worst.