Подходы оптимизации (метаэвристический, основанный на графике, MILP)
Я очень плохо знаком с алгоритмами, сейчас работаю над некоторыми проблемами оптимизации маршрутов и натолкнулся на некоторые статьи о следующих подходах:
Метаэвристический подход, основанный на населении (генетический алгоритм, оптимизация колоний муравьев и т. Д.), Основанный на одном решении (итеративный локальный поиск)
Графовый подход на примере алгоритма A *
Смешанный целочисленный подход линейного программирования
Меня немного смущает связь между этими подходами, например, используем ли мы GA для решения MILP, или все они - просто отдельные подходы?
Заранее спасибо!!
1 ответ
Смешанное целочисленное линейное программирование - это больше класс задач, чем алгоритм. Он состоит из всех проблем, которые сводятся к максимизации функции стоимости, которая является линейной и имеет целочисленные значения. Эти предположения облегчают создание алгоритмов, которые решают эту очень специфическую проблему, и я думаю, что именно об этом вы и говорите в "MILP Approach". Реализация может сильно отличаться, потому что специфичные для проблемы оптимизации могут быть применимы поверх хорошего общего решения.
Основанный на графе труднее определить, потому что все алгоритмы, использующие теорию графов, не делают явным то, что они используют граф, но для доказательства правильности или оптимальности может потребоваться использование некоторых нетривиальных теорем о графах.
Метаэвристика - это класс алгоритмов, предназначенных для расширения эвристики. Эвристика - это "практический" подход к проблеме, который не гарантирует оптимальности, но достаточен для достижения ближайшей цели. Метаэвристика поднимает уровень абстракции на один уровень выше: вместо того, чтобы напрямую рассуждать о проблеме, вы будете строить решения для этой проблемы (например, отдельные лица в ГА) и рассуждать о них (то есть развивать свое население в ГА).
Оптимизация маршрута может относиться к любой из трех категорий, вам нужно быть более точным, прежде чем я смогу ответить правильно, но вот несколько примеров:
Проблемы максимизации потока: линейное программирование.
Например: каждый маршрут вашей сети может использовать не более k грузовиков, и вы хотите перевезти свой песок из пункта A в пункт B за наименьшее возможное время, сколько грузовиков вы можете отправить на каждом пути? Один путь может разделиться на два более ограниченных пути, или сократиться, и ваши грузовики застрянут в середине пути, или даже слиться и т. Д. (Обратите внимание, что он все еще основан на графике)
Кратчайший путь, самый длинный путь, количество путей: на основе чистого графика.
Поиск в глубину и в ширину (я полагаю, вы уже это знаете) может решить огромное количество проблем на основе графов без необходимости в более сложном подходе. Например, * это только расширенная версия DFS. При оптимизации маршрутов сеть маршрутов, скорее всего, представлена в виде графика, поэтому это может быть хорошей отправной точкой.
Задача коммивояжера: метаэвристика
TSP в основном находит путь, который посещает все города ровно один раз. Это гораздо сложнее, чем кажется (NP-полная, если это звонит в колокол). Метаэвристика очень эффективна, потому что эффективное решение не известно. Генетические алгоритмы, оптимизация муравьиных колоний и имитационный отжиг - все они дают довольно хорошие результаты, если их правильно реализовать. Итеративный локальный поиск, как вы цитировали, может использоваться для локальной индивидуальной оптимизации, например, между каждым раундом глобальной оптимизации, что дает лучшие результаты.
Я сожалею, что мои три примера относятся к проблемам, связанным с графами, но они также показывают, что графы могут помочь решить невероятное количество проблем, даже если термин " граф" явно не указан в формулировке задачи.
Все три проблемы также связаны с оптимизацией маршрута, все зависит от того, какую оптимизацию вы ищете. Ваша проблема может быть лучше всего решена с помощью одного из этих трех методов, или, возможно, путем объединения двух (например, локальной оптимизации LP для метаэвристики).