Комментарии 11
На самом деле интересен не бизнес анализ проблемы, а решение той же множественно й VRP задачи (у вас на рисунке с грузоперевозками) через современные и не очень методы: ветви и границы, много этапный метод ЦЛП или RL , генетика и тп.
Есть три эффективных подхода, которыми решаются практические задачи дискретной оптимизации: local search, integer programming, constraint programming. Конкретно про VRP, есть книжки и статьи, где рассмотрены подходы к решению. Но это считается решённой проблемой, поэтому полезные статьи довольно старые. Китайцы любят публиковать всякий мусор для решения задач дискретной оптимизации, как раз через RL, генетику и отжиг и прочие мета-эвристики, имеющие в среднем комбинаторную сложность.
NP трудные задачи не имеют решения на основе локального поиска или ЦЛП и тп. Только определённое приближение к оптимуму или при малой размерности точное находят. Локальный поиск вам не найдёт нормальное решение без комбинации с глобальным поиском и вероятностной схемой сэмплирования. А вот эти все RL, генетика отжиг и по метаэвристики и есть комбо из глобального и локального поиска. Даже метод ветвей и границ комбинируют с этим.
NP трудные задачи в общем случаи не имеют решения, кроме как эквивалентного по сложности полному перебору. Не очень понимаю, что вы этим хотели сказать. Но если вам нужны глобальные оптимумы на больших задачах, то единственный вариант это integer programming. А по поводу local search в купе с tabu мета-характеристикой, среди аппроксимирующих алгоритмов - он бил рекорды на TSP.
Что такое "глобальный поиск", есть ссылка на определение? RL, генетика и отжиг, в принципе не масштабируются, когда пространство состояний становится слишком большим, начисто сливая локальному поиску с хорошей мета-характеристикой типа tabu search.
Поиск табу тоже кстати относится к метаэвристркам ну и имеет завязку на марковские процессы. Хотите теории идите почитайте Пантелеева Методы Глобальной оптимизации или Волкова метаэврестические алгоритмы оптимизации. Первый МАИ учебник для ВТузов, второй МГТУ им Баумана для ВТузов. Ничего не знаю про проблемы масштабирования у меня их не было. Решал задачи разной размерности, и ничего. Да время растёт и оно и будет расти для NP трудных от масштаба, но если запрогать грамотно будет за удобоваримое время сходится. Могу скинуть свой диссерт по NP задачам. Решал на NP задаче размещения скважин. Кстати тоже юзаю табу + метаэвристики а-ля метод потопа, метод пчелиной колонии или алгоритм муравья от Дориго. Все они это смесь локального и глобального поиска. Локальный это когда вы ищете в рамках текущего решения улучшения его в локальной окрестности. Глобальный когда вы случайно кидаете к точек и в рамках их делаете локальный для каждой точки. Обычно это равно методу эксплуатации решения - локальный поиск и исследования глобальный в RL.
Ссылки: https://top-technologies.ru/ru/article/view?id=36941
https://books.google.ge/books/about/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B3%D0%BB%D0%BE%D0%B1%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D0%BE%D0%BF%D1%82.html?id=nR8sDwAAQBAJ&redir_esc=y
Последняя ссылка про учебник Пантелеева, по мне просто топ. Да и в принципе по запросу: методы глобального и локального поиска, метаэвристики вам откроется чудный мир с методами:табу, локальный поиск, swap-k-swap, генетика, иммунные системы, роевый интеллект, отжиг, алгоритм муравьиной колонии и тп.
я уж не знаю откуда там взялась эта терминология, но она не очень грамотная. Глобальный поиск должен гарантированно давать глобальный оптимум. Или что в нем тогда глобального? Не застревает в каком-то классе локальных оптимумов? Методы локального поиска с мета-характеристиками глобальный оптимум гарантировать не могут, в отличии от методов integer programming.
Вопрос системы отсчёта. В моей системе обучения было чёткое понятие. Для алгоритмов поиска есть локальный в рамках улучшения текущей точки и глобальный поиск доп кандидатов вокруг не в окрестности текущего решения.
Ну и кто говорит, что Ваша система верная?
Нет, я просто не встречал этого термина ни в одном иностранном учебнике или статье, применительно к данной проблеме(дискретной оптимизации) в том виде как его интерпретируете вы. Если поискать что-то в духе "global search/optimization" то найдете гораздо больше примеров укладывающихся в мое толкование термина. Но да ладно, спорить не вижу смысла.
Введение в математическую оптимизацию на примере компании Recruit. Часть 4