Динамическая адаптация генетического алгоритма маршрутизации транспорта на больших сетях

Автор(ы): Захаров В.В., Мугайских А.В.

Название статьи: Динамическая адаптация генетического алгоритма маршрутизации транспорта на больших сетях

Выпуск: 73

Рубрика: Сетевые модели в управлении

Год: 2018

Библиография: Захаров В.В., Мугайских А.В. Динамическая адаптация генетического алгоритма маршрутизации транспорта на больших сетях // Управление большими системами. Выпуск 73. М.: ИПУ РАН, 2018. С.108-133. URL: https://doi.org/10.25728/ubs.2018.73.6

Дата опубликования: 31.05.2018

Ключевые слова: временная состоятельность, генетический алгоритм, задачи маршрутизации

Аннотация: Описывается процедура динамической адаптации генетического алгоритма для тестовых задач коммивояжёра на больших сетях, позволяющая получать более экономичные маршруты за то же время вычислений. Эффективность предложенной процедуры подтверждается результатами вычислительных экспериментов получения численного решения набора тестовых задач из библиотеки TSPLib и устойчивого уменьшения средней длины генерируемых решений по сравнению с решениями, предоставляемыми исходной эвристикой. Тем самым демонстрируется методика использования свойства временной несостоятельности эвристических алгоритмов для целей повышений уровня их эффективности. Оценка временной состоятельности эвристического алгоритма проводится с помощью нового критерия -- экспериментального уровня временной состоятельности.

Author(s): Zakharov V., Mugayskikh A.

Article title: Dynamic adaptation of genetic algorithm for the large-scale routing problems

Issue: 73

Year: 2018

Keywords: временная состоятельность, генетический алгоритм, задачи маршрутизации

Abstract: This paper is devoted to implementation of the dynamic adaptation procedure for genetic algorithm used for the traveling salesman problem on large-scale networks. It is shown that solutions obtained by genetic algorithm can be improved during its dynamic adaptation and allow finding the more effective routes for the equal time. To evaluate effectiveness of new approach computational experiments were performed on well-known benchmark instances from TSPLib. As a result, the experimental level of time consistency of improved solution considerably increases compare to basic one. Dynamically adapted genetic algorithm has demonstrated possibility to produce solutions with higher level of time consistency. At the same time proposed procedure reduces length of the one solution in certain experiment as well as average length of all routes in it.

В формате PDF
Обсудить статью в Интернет-конференции по проблемам управления

Просмотров: 2825; загрузок: 6006, за месяц: 21.

Назад