SWARM-INTELLIGENCE-BASED ALGORITHM OF CONNECTIONS PERMUTATION BETWEEN PINS
Yuriy Olegovich Chernyshev, Оlga Purchina, Аnna Poluyan, Фугаров Дмитрий Дмитриевич, Alina Victorovna · 2015
From a mathematical point of view routing is the most complicated problem of selection from a vast number of optimal solution choices. Development of methods and algorithms for solving the routing problem is carried out for many years though the issue is still relevant. This is due to the fact that, first of all, this is a nondeterministic polynomial time complete problem (so called NP-complete problem), and thus to develop a universal algorithm for finding the exact optimal solution within a reasonable time is quite a challenging task. The emergence of new, more sophisticated computer equipment, giving powerful computing resources, as well as exclusive standards of the projected devices is the driving force behind the development of new algorithms for solving the routing problem. There are several approaches to solve NP-complete problems. The first class of algorithms includes methods, which explicitly or implicitly provide for the exponential running time of the algorithm. These include full enumeration method, linear and nonlinear programming, etc. The second class includes the so-called heuristic algorithms allowing one to get reasonably good solutions within an acceptable time. A comparative analysis of the methods and algorithms for the first two classes showed that these algorithms do not guarantee the global result. The operation of such algorithms is completed or after a local optimum, or after an implementation of a predetermined number of steps. The third class includes algorithms of randomly directed search, based on the concepts of modeling [1]. They allow you to obtain a set of alternative solutions, and as a result of their analysis to obtain optimal and quasi-optimal results. These algorithms use a simulation of evolution and natural selection methods, observed among living organisms in nature to select the strongest. These methods allow you to create extremely flexible, fast and efficient data analysis tools. In this regard, in the paper we use the developments based on these technologies. For the study we proposed to use swarm algorithm of the redistribution of connections between terminals on the basis of integration of models of adaptive behavior of an ant colony and collective alternative adaptation. We propose the swarm algorithm of connection permutation between pins based on the integration of two models: an adaptive behavior of ant colony and collective alternative adaptation. The essence of the integration of these models is that in the course of performing the search procedure the certain procedures of the ant colony algorithm are alternating with collective alternative adaptation. The conducted experimental studies have confirmed the effectiveness of the proposed paradigm.