Arxiv/Learning (Re-)Starting Solutions for Vehicle Routing Problems 2020 2008.03424 — различия между версиями

«Learning (Re-)Starting Solutions for Vehicle Routing Problems 2020 2008.03424»^{скачать}

Ключевой проблемой при решении задачи комбинаторной оптимизации является то, как направлять агента (то есть решателя), чтобы эффективно исследовать огромный поиск пространства.

Традиционные подходы часто основаны на перечислении (например, исчерпывающий, случайный или запретный поиск) или должны ограничить исследование довольно ограниченным области (например, единственный путь, как в итерационных алгоритмах). В этой статье мы показать, что можно использовать машинное обучение для ускорения исследования.

В частности, сеть ценностей обучена оценивать варианты решений, которые обеспечивает полезную структуру (т. е. приблизительную поверхность значений) над пространство поиска; затем эта сеть ценностей используется для проверки решений, чтобы помочь агент оптимизации черного ящика для инициализации или перезапуска для навигации по пространство поиска желаемых решений.

Эксперименты показывают, что предложенный алгоритм «Learn to Restart» дает многообещающие результаты в решении «Проблемы маршрутизации емкостных транспортных средств (CVRP)».