MULTI-MEMETIC ANT DISCRETE OPTIMIZATION ALGORITHM

Abstract

The work deals with the task of constructing a multi-meme ant algorithm (AA), which includes
the development of 5 memes and the choice of an expedient strategy for using one meme or another
from a swarm of available memes. The work of discrete optimization AA is illustrated by the example
of the problem of splitting a graph into subgraphs, which is widely used in solving problems such asclustering, coloring, selection of clicks, matching, partitioning of VLSI, etc. Given a graph G (X,U),
where X is the set of vertices, |X|=n, U is the set of edges. It is necessary to divide the set X into subsets
X1 and X2, X1X2=X, X1X2=, Xi.. To search for a solution to the problem, a complete solution
search graph (SSG) R (X,E) is used. In contrast to the canonical paradigm of the AA, the agent for the
SSG R(X,E) does not construct a route, but forms a subgraph. At the first stage of each iteration of the
MA, the constructive algorithm (meme) of each agent forms the set X1k. In all memes, the formation of
the set X1k is carried out sequentially (step by step). At each step t, the agent applies a probabilistic selection
rule for the next vertex to include it in the generated set X1k(t). In the first meme, the search for
solutions is carried out on the SSG R (X,E), and the pheromone is deposited on the set of edges E. The
main difference between the second meme and the first one is that the full search graph R(X,E) is excluded
from the search process by the decision agent. Pheromone is deposited only on the vertices of the
graph G(X,U). This leads to a sharp reduction in the number of pheromone points and, consequently, in
memory, since the number of edges of the graph R(X,E) is significantly greater than the number of vertices.
The peculiarity of the third meme M3 is that two indicators φi1k and φi2k are formed at the vertex xi of
the graph G(X,U): φi1k is the total level of the pheromone delayed by xi, only when xi was in X1k(t ); φi2k
is the total level of pheromone deposited on xi, only in cases when xi was not included in X1k(t). The indicator
φ1i characterizes for the vertex xi the preference of the node X1k(t). The fourth meme differs from
the third one in that the agent generates two parallel sets X1k(t) and X2k(t) in parallel. In the fifth meme,
an approach based on the decomposition of the data structure in the processes of forming the X1kX
vertex set and the pheromone deposit is used to reduce the overall laboriousness of the search procedure.
In the modified approach, the pheromone is deposited on the graph R(X,E), and the formation of a
subset of the X1kX vertices is carried out on the oriented graph B(X,V). Two approaches to constructing
an adaptive multimeme algorithm using a swarm of memes are proposed. Multimemeic hybridization
leads to an algorithm with self-adaptive properties, since in the search process memes compete with
each other, and the winner at this stage of the search is used in subsequent iterations. By increasing the
search efficiency, the hybrid algorithm makes it possible to reduce the number of agents in the system
and thereby increase its speed.