Задача коммивояжёра: генетический алгоритм и LKH

Задача коммивояжёра (TSP): пройти все N городов по одному разу и вернуться в начало кратчайшим путём. Маршрут — это перестановка \pi=(\pi_1,\dots,\pi_N), и нужно минимизировать суммарную длину рёбер \ell(\pi).

Ниже — три постановки разного масштаба и два класса решателей: генетический алгоритм (общий метод) и Lin–Kernighan–Helsgaun (специализированная TSP-эвристика).

1 Деревня из 40 домов

Маршрут эволюционирует за 200 поколений генетического алгоритма (популяция 80, OX-скрещивание, swap/reverse-мутация, элитизм). Длина пути падает с 29.2 до 8.7 (-70\%).

Тот же запуск в формате split — слева маршрут, справа кривая длины \ell(\pi) по поколениям:

2 16 городов-миллионников России

Реальная задача: координаты крупнейших городов России (от Санкт-Петербурга до Красноярска), расстояния по сфере Земли (haversine). Длина маршрута падает с 19 100 до 9 820 км (-49\%) за 200 поколений того же генетического алгоритма.

3 pcb442: реальная задача сверления печатной платы

Бенчмарк TSPLIB pcb442 (Groetschel/Juenger/Reinelt, 1991): 442 отверстия, известный оптимум 50\,778 единиц.

3.1 Memetic 1+1 ES: общий оптимизатор с локальным поиском

Оптимизатор OnePlusOne из nevergrad генерирует кандидата через random-keys, каждый кандидат полируется полным 2-opt (JIT через numba). При застое — double-bridge perturbation и рестарт.

Выходит на 54\,154 единиц (gap +6.65%). 2-opt-плато для этого класса методов пробить нельзя без chain edge exchange.

3.2 LKH-3: специализированная TSP-эвристика

LKH-3 (Lin–Kernighan–Helsgaun) — chain edge exchange переменной глубины. Доступ через биндинг elkai.

Выходит точно на TSPLIB-оптимум 50\,778 единиц (gap 0%) за десятки секунд. Общие методы оптимизации с 2-opt-эвристикой это плато пробить не могут — нужна специализированная процедура поиска по семейству k-opt move’ов.