Генетические алгоритмы для решения задачи коммивояжера

УКД 004.031.43

Генетические алгоритмы для решения
задачи коммивояжера
Путинцев С.С., студент 535ст гр.; Шелиманова Ж.В., студент 5456 гр.
Национальный аэрокосмический университет
им. Н.Е. Жуковского «ХАИ»

В настоящее время актуальна задача дискретного программирования - выбор топологии кольцевой локальной сети. Для решения подобного рода задач существуют различные методы и алгоритмы. К их числу относятся генетические алгоритмы. Генетический алгоритм (ГА) использует идеи эволюционного развития в природе. В нем используются механизмы генетического наследования и аналог естественного отбора. ГА является разновидностью эволюционных вычислений. Отличительной особенностью ГА является использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Задача коммивояжёра (ЗК) является классической задачей комбинаторной оптимизации. ЗК заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу, с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (поиск минимума суммы весов ребер гамильтонового цикла) и матрица весов ребер задачи.
Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
В докладе приводится краткая история возникновения ГА, описание принципов работы и использования такой технологии для решения ЗК. Проводится сравнение программных средств для решения ЗК на основе генетических алгоритмов и методов случайного подбора маршрутов, реализованных на языке ООП, с решением данной задачи посредством программы MATLAB.
*Научные руководители доцент, к.т.н., И.В Лысенко; доцент, к.т.н,
А.В. Шостак