7.4. Исследование задачи о коммивояжере

Алгоритм был исследован на целом ряде тестовых задач о коммивояжере с наилучшими результатами, приведенных в литературе — Oliver’s-30, Eiloii’s-50 иЕі1оіі’8-75 [182,183]. Приведем интерфейс программы решения задачи о коммивояжере (рис. 7.19).

Окно (рис. 7.19) разделено на три основных части. В левой показывается конфигурация маршрута коммивояжера. В правой верхней части — координаты маршрута по осям х ш у. Здесь (5,6) — координаты вершины 28 анализируемого графа по осям х и у соответственно. Величина 63 означает предельную координату по оси х для размещения графа, а 69 — по оси у соответственно. В правой нижней части окна приводится график изменения ЦФ. В задаче с 30 городами описанный алгоритм на основе эволюции Поппера и жадных стратегий совместно с генетическим поиском после

нескольких генераций всегда находит оптимальное решение. Оптимальное решение в этой задаче находится в среднем за 2000 итераций.

 

Конфигурации маршрута решения для 30 городов показана на рисунке 7.20. Приведем список городов, заданных координатами, в порядке проведения пути (здесьа(6, с) означает, что а — вершина, Ьшс — координаты):

Известно, что наилучший путь коммивояжера составлял 423 условных единицы. Наилучший результат, полученный после испытаний алгоритма, составил 419.

Лучший путь для графа на 50 вершин (Eilon’s-50) составлял 428 условных единиц, а для графа на 75 вершин (Eilon’s-75) — 545. Описанный алгоритм определил конфигурации наилучших маршрутов. Они показаны на рис. 7.21 ирис. 7.22, соответственно.

Новое лучшее решение графа на 50 вершин (Eiloii’s-50) равно 425:

Новое лучшее решение графа на 75 вершин (Eiloii’s-75) равно 535:

Показатели по тестам являются лучшими в сравнении со всеми имеющимися в научной литературе (Oiiver’s-30 — 419, Eilon’s-50 — 425, Eilon’s- 75 — 535) по решению задачи коммивояжера.

Была протестирована серия из 100 графов на 200, 400, 600, 800 и 1000 вершин. При этом временная сложность алгоритма не выходила из области полиномиальной сложности. В лучшем случае временная сложность алгоритма 0(п logn), в худшем случае — f^O(n^). Отметим, что отличительной особенностью ГА является способность хорошо работать на

популяциях с малым числом хромосом, что уменьшает время реализации алгоритма. Подобное улучшение связано с использованием различных комбинаций моделей эволюций, блоком адаптации, различными обратными связями, локальным поиском, новыми и модифицированными операторами, а также обменом информацией с внешней средой. Полученные результаты в генетическом решении позволяют говорить об эффективности метода и целесообразности использования в решениях других задач оптимизации.