Self-configuring Nature Inspired Algorithms for Combinatorial Optimization Problems
View/ Open:
URI (for links/citations):
https://elib.sfu-kras.ru/handle/2311/34758Author:
Semenkina, Olga Ev.
Popov, Eugene A.
Semenkina, Olga Er.
Семенкина, Ольга Е.
Попов, Евгений А.
Семенкина, Ольга Э.
Date:
2017-12Journal Name:
Журнал Сибирского федерального университета. Математика и физика. Journal of Siberian Federal University. Mathematics & Physics;2017 10 (4)Abstract:
In this work authors introduce and study the self-configuring Genetic Algorithm (GA) and the self-
configuring Ant Colony Optimization (ACO) algorithm and apply them to one of the most known combi-
natorial optimization task – Travelling Salesman Problem (TSP). The estimation of suggested algorithms
performance is fulfilled on well-known benchmark TSP and then compared with other heuristics such as
Lin-Kernigan (3-opt local search) and Intelligent Water Drops algorithm (IWDs). Numerical experiments
show that suggested approach demonstrates the competitive performance. Both adaptive algorithms show
good results on these problems as they outperform other algorithms with their settings with average per-
formance В данной работе авторы предлагают и исследуют самоконфигурируемые генетический алгоритм
(GA) и алгоритм муравьиных колоний (ACO) и применяют их к одной из наиболее известных
задач комбинаторной оптимизации — задаче коммивояжера (TSP). Оценка работоспособности
предложенных алгоритмов проводится на известных тестовых вариантах TSP, а затем срав-
нивается с другими эвристиками, а именно с эвристикой Лина-Карнигана (локальный поиск с
3-заменой) и алгоритмом "умных капель воды". Численные эксперименты показывают, что пред-
ложенный подход демонстрирует сопоставимую работоспособность. Оба адаптивных алгоритма
показывают хорошие результаты на данных задачах, т.к. они превосходят другие алгоритмы с
настройками, дающими среднюю эффективность
Collections:
Metadata:
Show full item recordRelated items
Showing items related by title, author, creator and subject.
-
Нечеткие кластеры с объемными прототипами в тематической обработке данных дистанционного зондирования Земли
Бучнев, А.А.; Пяткин, В.П.; Buchnev, Aleksey A.; Pyatkin, Valeriy P. (Сибирский федеральный университет. Siberian Federal University, 2017-09)Рассматривается технология нечеткой кластеризации данных дистанционного зондирования Земли (ДЗЗ) расширенными алгоритмами С-средних и Густафсона-Кесселя. Расширения алгоритмов состоят в использовании объемных прототипов ... -
A Recursive Algorithm for Estimating the Correlation Matrix of the Interference Based on the QR Decomposition (RETRACTED)
Tyapkin, Valery N.; Dmitriev, Dmitry D.; Gladyshev, Andrey B.; Zverev, Peter Yu.; Тяпкин, Валерий Н.; Дмитриев, Дмитрий Д.; Гладышев, Андрей Б.; Зверев, Пётр Ю. (Сибирский федеральный университет. Siberian Federal University, 2020-03)Many tasks of digital signal processing require the implementation of matrix operations in real time. These are operations of matrix inversion or solving systems of linear algebraic or dif- ferential equations (Kalman ... -
On Accuracy of Approximation for the Resource Constrained Shortest Path Problem
Soldatenko, Aleksandr A.; Солдатенко, Александр А. (Сибирский федеральный университет. Siberian Federal University, 2019-10)The paper we considers the Resource Constrained Shortest Path problem (RCSP). This problem is NP- hard extension of a well-known shortest path problem in the directed graph G = (V;E). In the RCSP problem each arc e from ... -
Legal Qualification as a Logical Method of Cognition
Vlasenko, Valerii N.; Власенко, В.Н. (Сибирский федеральный университет. Siberian Federal University., 2016-01)The article examines in detail the logic basis of legal qualification, the major stage of application of the law, the means of specification of the provisions of the rule of law. Two blocks of logic rules to be observed ... -
Development of Bachelor`S Physical Culture Competences
Manzheley, Irina V.; Cherniakova, Svetlana N.; Манжелей, И.В.; Чернякова, С.Н. (Сибирский федеральный университет. Siberian Federal University., 2014-07)The subject of the research is to find ways for improving physical education of students in accordance with the current challenges based on the competence-building approach. The purpose of the paper is to develop a structure ...