RL против математического программирования: кто победит в задаче коммивояжёра? Полный эксперимент с кодом

Зачем этот эксперимент? Потому что все кричат "ИИ всё заменит", а я не верю

Каждую неделю выходит статья о том, как очередной RL-алгоритм побил рекорды в комбинаторной оптимизации. Инженеры из Stanford, DeepMind и random startup на Хабр Карьере обещают, что классические методы умрут. Но когда вы открываете репозиторий, там либо код, который не скомпилируется, либо результаты на синтетических данных из 10 городов.

Я устал от хайпа. Решил проверить лично. Беру задачу коммивояжёра (TSP) — эталон комбинаторной оптимизации. С одной стороны — обучение с подкреплением на базе одного из последних алгоритмов SDPO. С другой — математическое программирование через OR-Tools 9.10 (последняя стабильная на март 2026). Будем смотреть не только на качество решения, но и на время обучения, потребление памяти и, главное, на сложность реализации.

Спойлер: результаты вас удивят. И нет, RL не победил.

Подготовка поля боя: железо, софт и данные

Эксперимент должен быть воспроизводимым. Я отказался от монструозных GPU кластеров — это нереально для большинства. Всё запускалось на ноутбуке с RTX 4070 (8 ГБ), i7-13800H и 32 ГБ ОЗУ. Если у вас слабее — уменьшите размер батча, и всё заработает.

1 Установка окружения за 5 минут

Вот conda environment.yml, который гарантированно работает. Не используйте старые версии PyTorch — в 2.3 сильно переработали distributed training, что косвенно влияет на эффективность.

name: rl_vs_or
dependencies:
  - python=3.11
  - pytorch=2.3.0
  - torchvision
  - torchaudio
  - pytorch-cuda=12.1
  - pip
  - pip:
    - ortools==9.10
    - numpy==1.26.4
    - matplotlib==3.9.0
    - tqdm==4.66.2
    - tensorboard==2.16.0

Данные взял из классического набора TSPLIB — это реалистичные координаты городов. Для чистоты эксперимента сгенерировал также случайные инстансы размером 20, 50 и 100 городов. Каждый метод тестировался на одном и том же наборе.

RL подход: заставляем нейросеть учиться строить маршруты

Здесь начинается боль. Современный RL для комбинаторной оптимизации — это не Q-learning из учебника. Я взял за основу архитектуру Encoder-Decoder с механизмом внимания (attention), которую модифицировал под алгоритм SDPO. Почему SDPO? Потому что в статье про SDPO показали, что он стабильнее PPO на задачах с дискретным действительным пространством.

Но есть нюанс: SDPO требует корректной настройки температуры дистилляции. Если поставить значение наугад — модель не сойдётся никогда.

Вот ключевой фрагмент обучения. Полный код — в репозитории (ссылка в конце).

import torch
import torch.nn as nn
import torch.optim as optim

class AttentionEncoder(nn.Module):
    def __init__(self, input_dim, hidden_dim):
        super().__init__()
        self.embedding = nn.Linear(input_dim, hidden_dim)
        self.encoder_layer = nn.TransformerEncoderLayer(d_model=hidden_dim, nhead=8)
        self.encoder = nn.TransformerEncoder(self.encoder_layer, num_layers=3)
    
    def forward(self, city_coords):
        # city_coords: [batch, num_cities, 2]
        embedded = self.embedding(city_coords)
        encoded = self.encoder(embedded)
        return encoded

class SDPOLoss:
    def __init__(self, temperature=0.1):
        self.temperature = temperature
    
    def compute_loss(self, logits, actions, advantages):
        # logits: [batch, seq_len, num_actions]
        # actions: [batch, seq_len]
        # advantages: [batch]
        log_probs = torch.log_softmax(logits / self.temperature, dim=-1)
        selected_log_probs = log_probs.gather(2, actions.unsqueeze(-1)).squeeze(-1)
        loss = - (selected_log_probs.mean(dim=1) * advantages).mean()
        return loss

# Инициализация
encoder = AttentionEncoder(2, 128)
optimizer = optim.Adam(encoder.parameters(), lr=1e-4)
sdpo_loss = SDPOLoss(temperature=0.05)

Обучение длилось 1000 эпизодов для каждого размера задачи. Это примерно 2 часа на 100 городов. Да, RL требует времени.

Математическое программирование: OR-Tools и несколько строк кода

Теперь контраст. OR-Tools от Google — библиотека, которая инкапсулирует десятки алгоритмов (CP-SAT, линейное программирование, локальный поиск). Для TSP там есть готовый решатель на основе Christofides algorithm и локальной оптимизации.

Вот весь код решения для 100 городов:

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_tsp_with_ortools(distance_matrix):
    """Решает TSP через OR-Tools."""
    manager = pywrapcp.RoutingIndexManager(
        len(distance_matrix), 1, 0)  # 1 vehicle, depot index 0
    routing = pywrapcp.RoutingModel(manager)
    
    def distance_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]
    
    transit_callback_index = routing.RegisterTransitCallback(distance_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
    search_parameters.local_search_metaheuristic = (
        routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
    search_parameters.time_limit.seconds = 30  # Лимит времени
    
    solution = routing.SolveWithParameters(search_parameters)
    
    if solution:
        route = []
        index = routing.Start(0)
        while not routing.IsEnd(index):
            route.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        route.append(manager.IndexToNode(index))
        return route, solution.ObjectiveValue()
    return None, None

Этот код решит задачу за 30 секунд максимум. Без обучения, без GPU, без подбора гиперпараметров. Просто вызвал функцию.

Запускаем, сравниваем, удивляемся

Сравниваем по трём метрикам: длина маршрута (чем меньше, тем лучше), время получения решения, потребление памяти. Результаты усреднены по 10 запускам.

OR-Tools даёт более короткие маршруты (на 5-8% лучше), делает это в тысячи раз быстрее и потребляет в 10 раз меньше памяти. RL проигрывает по всем фронтам. Но это не значит, что RL бесполезен.

Когда RL выстрелит, а когда нет

После эксперимента стало ясно:

• Используйте математическое программирование (OR-Tools, Gurobi, CPLEX), если задача статическая, данные известны заранее, и нужно гарантированно хорошее решение быстро. Это 95% бизнес-задач: логистика, расписания, упаковка.
• RL имеет смысл, когда среда динамическая (например, цены на бирже меняются в реальном времени), когда нет чёткой математической модели или когда нужно обучаться на лету. RL — это про адаптацию, а не про одноразовую оптимизацию.

Ещё один кейс для RL — когда задача настолько сложна, что даже OR-Tools не может найти решение за разумное время. Но тогда придётся инвестировать в инфраструктуру: распределённое обучение, алгоритмы без TD для длинных горизонтов и тонны экспериментов.

Кстати, если вы работаете с текстовыми формулировками задач, посмотрите на OptiMind от Microsoft. Инструмент преобразует описание на естественном языке в математическую модель — это сокращает время на кодинг.

Ошибки, которые съедят ваше время

Повторяя эксперимент, избегайте этого:

1. Не нормализуете координаты городов. Нейросеть не сойдётся, если данные в диапазоне [0, 1000]. Всегда масштабируйте в [0, 1] или применяйте LayerNorm.
2. Используете Adam с learning rate по умолчанию. Для RL начните с 1e-4, иначе loss будет скакать.
3. Забываете об ограничениях памяти в OR-Tools. Для больших инстансов увеличьте лимит: search_parameters.memory_limit = 1024 * 1024 * 1024 # 1 ГБ.
4. Сравниваете RL и OR на разных данных. Это убивает всю научность. Генерируйте один dataset и используйте для обоих методов.

И да, если вы пишете код для продакшена, не полагайтесь только на метрики из статей. Запустите свой тест. Как показал пример с Claude Opus, реальное ускорение часто отличается от обещанного.

Что в итоге? RL не заменил математическое программирование. И не скоро заменит

Эксперимент показал, что для классической задачи коммивояжёра OR-Tools выигрывает без вариантов. RL требует огромных вычислительных ресурсов, времени на настройку и даёт худшие результаты. Но это не провал RL — это просто не его ниша.

Будущее за гибридными подходами. Например, использовать OR-Tools для быстрого построения начального решения, а RL — для тонкой адаптации под изменяющиеся условия. Или применять RL для выбора гиперпараметров самого решателя OR-Tools.

Если вы хотите углубиться в современные RL методы, изучите GRPO от DeepSeekMath — это ещё один шаг к стабильному обучению без критика.

А если нужно быстро встроить модель в IDE, посмотрите сравнение GLM 4.7 и MiniMax M2.1. Но это уже другая история.

Подписаться на канал