Возможности использования элитных особей при решении задачи коммивояжера моделью Гольдберга

Целью данной работы является исследование актуальной задачи коммивояжера, которая является NP сложной задачей дискретной оптимизации. Показано, что для достижения поставленной цели пригодны лишь эвристические методы. Для решения задачи представлен результат совместного использования муравьиного (МА) и генетического (ГА) алгоритмов. Особенностью предложенного генетического алгоритма является то, что задача решается только с помощью различных мутаций (без кроссовера). Исследуемый ГА был улучшен введением элитарной стратегии. Испытания проводились на графах средней и большой размерности. Элитная особь, получаемая с помощью муравьиного алгоритма, в среднем улучшалась на 11 %. Показано, что эффективность генетического алгоритма напрямую зависит от количества особей в поколении и количества итераций алгоритма. Ввод элитарной стратегии улучшил получаемые значения целевой функции более чем в 2 раза. Увеличение числа запусков МА при выборе элиты позволило повысить эффективность алгоритма приблизительно на 2 %.