Open AccessModified swarm algorithm «ant tree» in the problem of diversification of tractor resources spaces
Author(s) -
Boris K. Lebedev,
Oleg B. Lebedev,
Оlga Purchina
Publication year - 2020
Publication title -
iop conference series. materials science and engineering
Language(s) - English
Resource type - Journals
eISSN - 1757-899X
pISSN - 1757-8981
DOI - 10.1088/1757-899x/918/1/012082
Subject(s) - ant colony optimization algorithms , computer science , mathematical optimization , swarm intelligence , tracing , ant colony , metaheuristic , decision tree , graph , algorithm , mathematics , theoretical computer science , artificial intelligence , particle swarm optimization , operating system
In this work, the problem of increasing traceability is solved by diversifying trace resources, which consists in using additional areas adjacent to the channels below and above, with a trace layer located above the “over-the-cell” cells. For a single-layer routing uses a new paradigm of combinatorial optimization – ant tree (trees ant colony optimization (T-ACO)), based on the ideas of adaptive behavior of ant colony. The decision tree is used as a decision search graph. An agent for the decision search graph does not create a route, but a tree, which in its structure coincides with the representation of the solution to the trace problem in the «over-the-cell» region. This eliminates the use of additional transformations in the decoding process of decisions that allow interpretation of decisions in the form of trees and allows you to discard a lot of «illegal» solutions, which leads to an increase in the quality of the solutions obtained. Using the tracing procedure in «over-the-cell» based on the ant algorithm allows you to unload the channel by 15-20%. The time complexity of the algorithm depends on the number of vertices n of the decision search graph, the number of agents y, the number of iterations l, and is defined as O (n 2 ·l·y) .