Перевод названия: Самоконфигурируемые алгоритмы для задач комбинаторной оптимизации
Тип публикации: статья из журнала
Год издания: 2017
Идентификатор DOI: 10.17516/1997-1397-2017-10-4-463-473
Ключевые слова: travelling salesman problem, genetic algorithm, ant colony optimization, intelligent water drops algorithm, self-configuration, задача коммивояжера, генетический алгоритм, муравьиный алгоритм, алгоритм "умных капель воды", самоконфигурация
Аннотация: In this work authors introduce and study the self-configuring Genetic Algorithm (GA) and the selfconfiguringAntColony Optimization(ACO) algorithmandapplythemtooneofthemostknowncombinatorial optimization task -Travelling Salesman Problem (TSP). The estimation of suggestedalgorithms performance is fulfilled on well-known benchmark TSP aПоказать полностьюnd then compared with other heuristics such as Lin-Kernigan (3-optlocal search) and IntelligentWaterDrops algorithm (IWDs). Numerical experiments show that suggested approach demonstrates thecompetitiveperformance. Both adaptive algorithms show good results on these problems as they outperform other algorithms with their settings with averageperformance. Вданнойработе авторы предлагаютиисследуютсамоконфигурируемые генетический алгоритм (GA) и алгоритм муравьиных колоний (ACO) и применяют их к одной из наиболее известных задач комбинаторной оптимизации - задаче коммивояжера (TSP). Оценка работоспособности предложенных алгоритмов проводится на известных тестовых вариантах TSP, а затем сравнивается с другими эвристиками, а именно с эвристикой Лина-Карнигана (локальный поиск с 3-заменой)иалгоритмом"умных капель воды". Численные эксперименты показывают, что предложенный подходдемонстрирует сопоставимуюработоспособность.Обаадаптивных алгоритма показывают хорошие результаты на данных задачах, т.к. они превосходят другие алгоритмы с настройками, дающими среднюю эффективность.
Журнал: Журнал Сибирского федерального университета. Серия: Математика и физика
Выпуск журнала: Т. 10, № 4
Номера страниц: 463-473
ISSN журнала: 19971397
Место издания: Красноярск
Издатель: Федеральное государственное автономное образовательное учреждение высшего образования Сибирский федеральный университет