| Popis: |
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 rikRi, 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 ejE 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 ahigher 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. |
