In the proposed bioinspired approach to solving combinatorial logic problems on graphs, such as finding a maximal matching, an independent set of vertices (an internally stable set), and a maximal clique, a modified ant colony paradigm has been used. Unlike classical algorithms, which often operate directly on the initial graph, the search space is represented as a star graph. This significantly impacts the search efficiency, allowing agents to explore more effectively various combinations of vertices. The selection of a star graph is based on its convenience for representing a set of possible solutions and the ability to parallelize efficiently computations. Each vertex of the star graph can correspond to a partial or complete solution to the initial graph problem. The problem of finding an independent set, for example, can be formulated as the problem of partitioning a vertex set into two subsets: the independent set and its complement. An edge in a star graph connects two vertices representing partial solutions that differ by the addition or removal of one vertex from the independent set. This ensures a smooth transition between different search states. The initial state is characterized by a uniform distribution of pheromone on all edges of the star graph, ensuring the initial non-directionality of the search. The algorithm operates iteratively, and each iteration consists of three stages. A key element is the presence of memory in the agents: each agent “remembers” the amount of pheromone associated with each edge of the star graph, allowing it to make “better” decisions in subsequent iterations. The first stage is the solution construction stage. Using a constructive heuristic algorithm (e.g., a “greedy” algorithm or a local search algorithm), each agent attempts to find a solution in the search space represented by the star graph. The quality of the found solution is estimated using an appropriate criterion (e.g., the size of the independent set or the weight of the maximal matching). This estimate directly correlates with the amount of pheromone “deposited” by the agent on the edges of the star graph that led to a given solution. Higher-quality solutions lead to greater pheromone deposition. The second stage is the collective learning stage. The pheromone “deposited” by each agent on the corresponding edges in the buffer memory is summed with the pheromone already present in the global (collective) memory. This ensures the accumulation of information about the most promising areas of the search space. The third stage is the pheromone evaporation stage. It is necessary to prevent premature convergence to local optima. Pheromone evaporation simulates the gradual “forgetting” of information about less successful solutions, which facilitates exploration of a wider region of the search space. An experimental study has shown that the time complexity of the algorithm has a quadratic dependence on the size of the initial graph, which is confirmed by theoretical estimates. This makes the proposed algorithm comparable in efficiency to other known methods for solving similar problems, especially for sufficiently large graphs. However, it should be noted that the algorithm’s performance is highly dependent on the selection of parameters, such as the pheromone evaporation rate, the agent population size, and the design algorithm used in the first stage. Further research could be aimed at optimizing these parameters and adapting the algorithm to various types of graphs and problems.
Лебедев et al. (Mon,) studied this question.