- PVSM.RU - https://www.pvsm.ru -
Приветствую уважаемое читатели!
В данной статье я хотел бы рассказать о том как я решал транспортную задачу при помощи генетического алгоритма.
Википедия формулирует задачу следующим образом — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе.
Например – необходимо спланировать доставку бутылей воды по городу, известны потребности каждого заказчика, грузоподъёмность транспортных средств и расстояния между точками.
Дальше можно добавлять различные ограничения – например временные окна доставки, исключить посещение некоторыми машинами некоторых точек и так далее. Добавить эти и другие ограничения в моих ближайших планах, а пока сервис решает задачу сформулированную в предыдущем абзаце.
В основе решения лежит параллельный генетический алгоритм. Каждый вариант решения представлен хромосомой, которая может быть скрещена с другой хромосомой или подвергнута мутации. В результате полученный ребенок добавляется к общей популяции. Размер популяции ограничен и наименее приспособленные хромосомы удаляются.
Параллельным алгоритм называется потому что несколько изолированных популяций хромосом развиваются одновременно. В определенные моменты времени, случайно выбранные хромосомы перемещаются между популяциями.
Каждая хромосома есть вариант решения проблемы и представлена в виде массива массивов, где каждый вложенный массив представляет один маршрут (1 ходку автомобиля). Каждый элемент массива — это заказчик, которому необходимо доставить груз:
Все маршруты явно начинаются со склада и неявно им заканчиваются.
Имеем 2 типа скрещиваний – случайный (Random Crossover) и однородный (Uniform Crossover)
Случайное скрещивание – произвольная часть произвольного маршрута от родителя 1 помещается в наилучшее место вставки для родителя 2. Наилучшее место вставки – то которое дает наименьшую длину.
Однородное скрещивание вычисляет индексы плотности для всех маршрутов родителей и поочередно добавляет маршруты с наименьшим индексом от родителей 1 и 2. Оставшиеся точки распределяются в места наилучшей вставки.
Алгоритм использует 2 типа мутации — случайные и направленные на наиболее отдаленные части мутации маршрута.
Случайные мутации вырезают часть случайной части маршрута и вставляют его в место, которое дает минимальное общее расстояние. Второй тип мутаций находит наиболее удаленных клиентов в случайных маршрутах и перемещает его в место наилучшей вставки.
После скрещивания и операций мутации, алгоритм пытается переместить точки каждого маршрута таким образом, чтобы длина маршрута была минимальной.
Приспособленность (качество) каждой хромосомы считается по формуле:
Фитнесс = общее расстояние + штраф за перегруз * перегруз + штраф за недогруз * недогруз
Для более быстрого решения, только уникальные хромосомы содержатся внутри каждой группы
Алгоритм завершает вычисления по достижению максимального количества эпох или при отсутствии улучшений за определенный % эпох
Ниже приведены результаты работы алгоритма на подмножестве стандартного набора задач. Первая цифра в названии проблемы – число точек, вторая – мин количество машин. B-n31-k5 – 31 точка при 5 машинах.
Результаты работы на 8 ядерном AMD (8350):
Результаты работы на всех тестовых данных находятся на странице проекта.
Решение написано на C# и состоит из ряда сервисов, баз данных и очередей:
Стек технологий:
1. .NET 4.5 / C# / WCF / WinService
2. Queue: RabbitMQ
3. DB: MongoDB
4. DI container: Autofac
5. Unit tests: MS Test / Rhino Mocks / Fluent assertions
.NET специфичный опыт которым я считаю нужным поделится:
1. В часто обращаемых участках кода не используйте свойств, а просто публичные переменные
2. Массивы зачастую быстрее списков (List) и словарей (Dictionary) даже при реализации в них операций вставки внутрь и удаления элементов
Текущее решение доступно бесплатно.
Список новой функциональности которая находится в разработке:
1. Получение расстояний по координатам точек
2. Добавление ограничений – по временным окнам, машинам и точкам доставки
Гугл содержит массу публикаций о решении задачи средствами генетических (и не только) алгоритмов. Вот названия некоторых из них:
1. Solving the Vehicle Routing Problem with Genetic Algorithms [1]
2. A hybrid algorithm for the Vehicle Routing Problem with Time Windows [2]
3. A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows [3]
Автор: acherednychenko
Источник [4]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/41893
Ссылки в тексте:
[1] Solving the Vehicle Routing Problem with Genetic Algorithms : http://etd.dtu.dk/thesis/154736/imm3183.pdf
[2] A hybrid algorithm for the Vehicle Routing Problem with Time Windows: http://www2.ic.uff.br/~satoru/conteudo/artigos/PAPER%20IESM2011-SABIR.pdf
[3] A Route-directed Hybrid Genetic Approach for the Vehicle Routing Problem with Time Windows: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.9531
[4] Источник: http://habrahabr.ru/post/191596/
Нажмите здесь для печати.