СРАВНИТЕЛЬНЫЙ АНАЛИЗ ОПЕРАТОРОВ КРОССОВЕРА PMX, CX И OX НА ПРИМЕРЕ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

Abstract

Задача коммивояжера (Travelling Salesman Problem, TSP) – одна из самых известных NP-трудных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через все указанные города ровно один раз с последующим возвратом в исходный город. Генетический алгоритм (ГА) является одним из лучших методов, который используется для решения различных NP-трудных задач, таких, как TSP. Стандартные операторы кроссовера (1-Point Crossover, k-Point Crossover и др), порождают потомков, которые в общем случае не являются перестановками. Цель статьи заключается в отыскании наилучшего возможного результата кроссинговера комбинаторной задачи оптимизации, при заданных двух родительских решениях, закодированных в виде перестановок. В работе проводится экспериментальное исследование операторов оптимальной рекомбинации PMX, CX и OX для задачи TSP. Экспериментальные результаты показывают превосходство оператора кроссовера PMX, поскольку он находит наиболее оптимальное решение.