Вероятностный метод поиска оптимальных путей
Проблемы оптимизации очень важны как в научной, так и в промышленной сфере. Некоторыми реальными примерами этих проблем оптимизации являются планирование расписания, планирование распределения времени медсестер, планирование поездов, планирование мощностей, проблемы коммивояжера, проблемы маршрутизации транспортных средств, проблема планирования групповых магазинов, оптимизация портфеля и т. Д. Многие алгоритмы оптимизации разработаны для эта причина. Оптимизация колонии муравьев - одна из них. Оптимизация колонии муравьев - это вероятностный метод поиска оптимальных путей. В информатике и исследованиях алгоритм оптимизации муравьиной колонии используется для решения различных вычислительных задач.
Оптимизация колонии муравьев (ACO) была впервые представлена Марко Дориго в 90-х годах в его докторской диссертации. Тезис. Этот алгоритм представлен на основе поведения муравья при поиске пути между своей колонией и источником пищи. Изначально его использовали для решения известной задачи коммивояжера. Позже он используется для решения различных сложных задач оптимизации.
Муравьи - социальные насекомые. Живут колониями. Поведение муравьев контролируется целью поиска пищи. Во время поиска муравьи бродят по своим колониям. Муравей постоянно прыгает с места на место в поисках пищи. Во время движения он откладывает на земле органическое соединение, называемое феромоном. Муравьи общаются друг с другом с помощью феромоновых следов. Когда муравей находит какое-то количество еды, он несет столько, сколько может унести. При возврате он откладывает феромоны на пути в зависимости от количества и качества еды. Муравей чувствует запах феромона. Так что другие муравьи могут это почувствовать и пойти по этому пути. Чем выше уровень феромона, тем выше вероятность выбора этого пути, и чем больше муравьев следует по этому пути, тем больше увеличивается количество феромона на этом пути.
Давайте посмотрим на это на примере. Давайте рассмотрим, что есть два пути, чтобы добраться до еды из колонии. Сначала на земле нет феромона. Таким образом, вероятность выбора этих двух путей равна 50%. Представим, что два муравья выбирают два разных пути, чтобы добраться до еды, поскольку вероятность выбора этих путей составляет пятьдесят на пятьдесят.
Расстояния этих двух путей различны. Муравей, идущий по более короткому пути, доберется до еды раньше, чем другой.
Найдя еду, он уносит с собой немного еды и возвращается в колонию. Когда он отслеживает обратный путь, он откладывает феромон на земле. Муравей, идущий по более короткому пути, доберется до колонии раньше.
Когда третий муравей хочет выйти на поиски пищи, он будет следовать по пути, имеющему меньшее расстояние в зависимости от уровня феромона на земле. Поскольку на более коротком пути больше феромонов, чем на более длинном, третий муравей пойдет по пути, имеющему больше феромонов.
К тому времени, когда муравей, идущий по более длинному пути, вернулся в колонию, больше муравьев уже прошли по тропе с большим уровнем феромонов. Затем, когда другой муравей попытается добраться до места назначения (пищи) из колонии, он обнаружит, что каждый путь имеет одинаковый уровень феромона. Итак, он случайным образом выбирает один. Давайте рассмотрим, выберем вышеуказанный (на картинке ниже)
Повторяя этот процесс снова и снова, через некоторое время на более коротком пути будет больше феромонов, чем на других, и с большей вероятностью следовать по нему, и все муравьи в следующий раз пойдут по более короткому пути.
Для решения различных проблем с ACO предлагается три разные версии Ant-System:
Плотность муравьев и Количество муравьев. Феромон обновляется при каждом движении муравья из одного места в другое.
Цикл муравьев. Феромон обновляется после того, как все муравьи завершили свое путешествие.
Давайте посмотрим на псевдокод для применения алгоритма оптимизации муравьиной колонии. Искусственный муравей создан для поиска оптимального решения. На первом этапе решения проблемы каждый муравей создает решение. На втором этапе сравниваются пути, найденные разными муравьями. И на третьем этапе обновляется значение путей или феромон.
procedure ACO_MetaHeuristic is
while not_termination do
generateSolutions()
daemonActions()
pheromoneUpdate()
repeat
end procedure
Есть много проблем оптимизации, для которых вы можете использовать ACO для поиска оптимального решения. Некоторые из них:
- Проблема с маршрутизацией емкостного транспортного средства
- Задача стохастической маршрутизации транспортных средств (SVRP)
- Проблема с маршрутизацией автомобиля при приеме и доставке (VRPPD)
- Проблема планирования групповых магазинов (GSP)
- Проблема планирования распределения времени медсестер
- Задача перестановочного потока (PFSP)
- Проблема с присвоением частот
- Проблема распределения избыточности
- Задача коммивояжера (TSP)
Давайте посмотрим на математические термины ACO (обычно для задачи TSP).
Обновление феромона
Левая часть уравнения указывает количество феромона на заданном ребре x, y.
ρ - скорость испарения феромона
И последний член справа указывал на количество депонированного феромона.
Где L - стоимость длительности муравейника, а Q - постоянная величина.
использованная литература
- Оптимизация муравьиной колонии: введение и последние тенденции Кристиана Блюма
- Оптимизация муравьиной колонии Субвеш Райчанд
- Оптимизация муравьиной колонии
