PARALLEL AND CONSISTENT BIOINSPIRED ALGORITHM FOR CONSTRUCTION OF A STEINER MINIMAL TREE

Abstract

The paper considers a parallel sequential approach to constructing a minimal Steiner tree.
The developed algorithm is based on a general approach, consisting in the decomposition of a
connecting network and its presentation in the form of a combination of two-terminal connections.
For the chain ti on the set of vertices Xi, |Xi|=ni of the graph G, using the Prim algorithm, we construct
the minimal connecting tree Ri={rik|i=1, 2, …, ni-1}. For each edge rikRi, a route sik is
formed that connects on the graph G a pair of vertices corresponding to the edge rik. Each route sik
corresponds to the set Г(sik) of edges of G. The problem of constructing a minimal Steiner tree
reduces to the problem of constructing and choosing an s-route sik on the graph G, for each edge
rik. For each agent located at the vertex pi, the coordinates of the vertex pj to which the s-route is
laid are determined and the possible directions of its movement along the edges of the orthogonal
graph G=(V,E) are determined, which ensure the construction of the s-route of minimum length.
The quality of the route built by the agent will be determined by the presence of common sections
with routes built by other agents of the cluster. The more common sections of the route with routes
constructed by other cluster agents, the smaller the total length of the Steiner tree ribs. The decomposition
of the problem in the framework of a parallel-sequential approach allowed us to
avoid the problem of the sequence of routing and organize a collective adaptation system with a
high degree of appropriate behavior and convergence. A feature of the presented ant algorithm for
constructing a minimal Steiner tree is that the ant colony is divided into clusters and the search for
a specific solution to the problem is carried out by a population of ant clusters. The task of ants
constructing each cluster Aσ of the Steiner tree is reduced to the problem of constructing and selecting
in the graph G the set of Mσ s-routes covering the minimal Steiner tree. In contrast to the
canonical paradigm of the ant colony, a modified greedy strategy is proposed for constructing an
oriented route on the solution representation model. The concept of collective adaptation (adaptive
behavior) of an agent cluster used in the above approach is as follows. The global goal of the
team (agent cluster) is to build a minimal Steiner tree. The local goal of each agent is to build a
route of maximum cost, that is, a route that maximally matches the routes built by other agents of
the cluster, which indirectly contributes to the achievement of the global goal of the team. The
state of each edge ejE of the graph of the search for G solutions is described by two parameters
hj and dj. The values of the indicators hj and dj are updated by increasing at each iteration after all
the clusters of agents build Steiner trees. For the first time, the composite structure of pheromone
and the differentiated method of its deposition are used. Each ant in the group marks the path

(edges of the route) with two types of pheromone: pheromone-1 and pheromone-2. This provides a
higher probability of localization of the global extremum of the problem. The time complexity of
this algorithm at one iteration is defined as O(n2). After all the actions are completed, the agent
with the best solution is found in the iteration, which is remembered. Next, the transition to the
next iteration.