The development of methods and algorithms for solving a routing problem is being implemented over the years, but it is still a topical problem. This is, primarily, due to the fact that this problem is NP-complete, and to develop a universal algorithm for finding an exact optimal solution during a reasonable time is difficult. In this regard, in order to reduce the algorithm time complexity (ATC), the development of sequential and parallel bionic algorithms for solving the transportation problems based on the evolutionary strategies is prospective. The bionic algorithms (BA) have proved their efficiency at the solution of the time-consuming tasks of optimization, approximation, and intellectual data processing. Benefits include the possibility to perform the genetic and evolutionary search, as well as the fact that BA consist in parallel generation of the quasioptimal alternative decision sets with possible "migration" of decisions between these sets. Schemes that differ from the known ones in the outlining structure and recording the parameter variation are proposed for the bionic search simulation. The investigation of the developed bionic algorithms for solving transportation problems show the advantage in the solution quality compared to the known methods. The developed algorithms allow obtaining a set of alternative quasioptimal results with the polynomial time complexity. The transformation of the population size during the transition from one iteration to another in the process of the bionic algorithm operation is presented.
Разработка методов и алгоритмов для решения задачи трассировки осуществляется на протяжении многих лет, но по-прежнему является актуальной. Это связано, в первую очередь, с тем, что эта задача является NP -полной, и разработать универсальный алгоритм, позволяющий находить точное оптимальное решение за приемлемое время, затруднительно. В связи с этим, с целью снижения временной сложности алгоритма (ВСА), актуальным является разработка последовательных и параллельных бионических алгоритмов для решения задач транспортного типа на основе эволюционных стратегий. Бионические алгоритмы (БА) доказали свою эффективность при решении трудоемких задач оптимизации, аппроксимации, интеллектуальной обработки данных. К преимуществам можно отнести возможность выполнения эволюционного и генетического поиска, а также то, что БА состоит в параллельной генерации наборов квазиоптимальных альтернативных решений с возможной «миграцией» решений между этими наборами. Для моделирования бионического поиска предложены схемы, отличающиеся от известных структурой построения и учетом вариации параметров. В работе приведен процесс преобразования размера популяции при переходе из одной итерации в другую в процессе работы бионического алгоритма. Проведенные исследования разработанных бионических алгоритмов решения задач транспортного типа показали преимущество по качеству решений в сравнении с известными методами. Разработанные алгоритмы позволяют получать набор квазиоптимальных альтернативных результатов
The authors declare that there are no conflicts of interest present.