УДК 004

Оптимизация построения маршрута с помощью генетического алгоритма

Матвеева Анна Вячеславовна – студент Финансового университета при Правительстве Российской Федерации.

Аннотация: В статье рассмотрено определение, перечислены основные отличия от традиционных алгоритмов и представлены основные шаги генетического алгоритма. Данные алгоритмы применяются для решения разных видов задач, в том числе и для решения задачи оптимизации построения маршрутов. Основная задача – определить самый длинный маршрут и минимизировать его, тогда в результате будет получено наилучшее решение. В статье описаны основные компоненты и шаги для решения задачи нахождения оптимального маршрута с помощью генетического алгоритма.

Ключевые слова: генетический алгоритм, мутация, скрещивание.

Генетический алгоритм – один из видов алгоритмов, основанный на принципах эволюции в природе. Благодаря имитации процесса естественного отбора алгоритм способен решить задачи поиска, оптимизации и обучения. Генетические алгоритмы могут решать задачи со сложным математическими характеристиками и с большим числом параметров.

Генетические алгоритмы имеют ряд отличий от традиционных алгоритмов оптимизации и поиска решения задач:

• поддерживают популяции решений, т. е. генетический поиск ищет несколько решений, а не единственное. Алгоритм поиска сохраняет множество индивидуумов, которые входят в текущее поколение, а на каждой из последующих итераций формируется следующее поколение индивидуумов.
• используют генетическое представлений решений, т. е. работают с кодированными представлениями, так называемыми хромосомами. Хромосомы определяют такие операции как скрещивание и мутация.
• используют функции приспособленности, т. е. генетический алгоритм находит таких индивидуумов, у которых оценка вычисляемой функции максимальна. Основное отличие от традиционных алгоритмов заключается в том, что генетические алгоритмы анализируют только значение, возвращенное функцией, а не какую-либо другую информацию. Данная особенность позволят генетическим алгоритмам работать с трудными функциями, которые сложно или невозможно продифференцировать.
• поддерживают вероятностное поведение, т. е. правила применяемые в генетическом алгоритме от перехода поколения к поколению являются вероятностными.

Описание основных этапов при создании генетического алгоритма:

1. Формирование начальной популяции.

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

2. Вычисление функции приспособленности для каждого индивидуума.

Функция приспособленности вычисляется первый раз для начальной популяции, а далее для нового поколения после применения операторов отбора, мутации и скрещивания. С помощью генетического алгоритма в основном решаются задачи максимизации функции приспособленности, для решения задачи минимизации при вычислении приспособленности необходимо инвертировать найденное значение.

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

Генетический алгоритм в основном используют для задач поиска наилучшего решения или для решения комбинаторной оптимизации, что подходит под решение задач логистики, а именно поиска оптимального маршрута.

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

Основные компоненты для решения задачи нахождения оптимального маршрута:

• список адресов для доставки, полученный от клиента при оформлении доставки;
• количество транспортных средств от разных транспортных компаний;
• адрес магазина или склада, откуда начинается и заканчивается маршрут.

Цель задачи – создать оптимальные маршруты и минимизировать общую длину маршрута. Маршруты строятся для определенного магазина, поэтому начальной точкой для всех маршрутов является один и тот же магазин.

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

Количество способов построения пути только для одного маршрута с n заявками (для каждой заявки свой адрес и метка на карте) равно: (n-1)!/2.

Хромосомой для генетического алгоритма будет являться список из последовательности заявок в маршруте.

Решение задачи будет представлено в виде списка с числами от 0 до (n-1) + (m-1), где n – количество заявок, адресов, указанных в заявках, и m – количество свободных транспортных средств.

Первые n чисел (начиная с 0) являются индексами заявок, а последние m-1 являются разделителями между сформированными маршрутами.

После разделения индексов на маршруты из списка необходимо убрать номер начальной точки, а именно магазина или склада, т. к. он не относится к маршруту. Однако при подсчете длины маршрута необходимо вновь подставить индекс магазина или склада в начало и конец маршрута, т. к. водители начинают и заканчивают погрузку в одном месте.

Таким образом, использование генетического алгоритма при построении маршрутов позволит повысить эффективность работы сотрудников, сократить время создания маршрутов, повысить количество заявок и ускорить процесс доставки.

Списоклитературы

1. Eyal Wirsansky, Hands-On Genetic Algorithms with Python - Applying genetic algorithms to solve real-world deep learning and artificial intelligence problems.
2. Боронихина Е. А., Сибирякова В.А., Сравнение методов решения задачи коммивояжера – Информационные технологии и математическое моделирование И74.
3. Рутковская Д. Пилиньски М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы.