Evolutionary Algorithms and Real-world Logistics

2021/2022

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

School of Data Analysis and Artificial Intelligence

Course type:

Elective course

When:

4 year, 1, 2 module

Instructor

Fedyanin, Denis

Программа дисциплины

Аннотация

Стремительное развитие крупномасштабных логистических систем приводит к ситуации, когда даже самые опытные специалисты (диспетчеры, сотрудники отдела планирования) не способны принять оптимальное решение. Это делает необходимым разработку систем принятия решений и систем поддержки принятия решений для логистических систем. Здесь следует подчеркнуть, что разнообразие требований и условий, возникающих при реализации конкретных систем принятия решений, делает каждую такую систему уникальной. С другой стороны, опыт создания систем такого типа указывает, что такого рода системам присущи некоторые общие черты, прежде всего, необходимость решения задач дискретной оптимизации большой размерности (“проклятие размерности”), что в практически значимых случаях предполагает применение эволюционных алгоритмов. В курсе рассматриваются возникающие здесь постановки задач дискретной оптимизации (как одно-, так и многокритериальной), современные подходы к решению задач этого класса (связанные преимущественно с), методы оценки и минимизации риска в логистических системах, методы управляемой самоорганизации – в целом предметом курса служит математика, необходимая для создания реальных логистических систем. Семинарские занятия будут посвящены разбору математических моделей и систем поддержки принятия решений для логистических проектов, выполненных как лектором, так и другими исследователями. В отличие от курса 2020 года в 2021 добавлены примеры применения алгоритмов не только для Python, но и для Excel. Также большее внимание будет уделено особенностям использования алгоритмов менеджерами не обладающими глубокими математическими знаниями или подготовкой в области разработки программного обеспечения.

Цель освоения дисциплины

• Знание элементов генетических алгоритмов: видов мутаций, кроссоверов, отбора, селекции и учета ограничений.
• Умение формулировать логистические задачи в терминах генов и хромосом для применения генетических алгоритмов
• Знание возможностей Python для решения разноообразных логистичексих задач (упаковка, распределение, маршрутизаций и др.) , умение и опыт его применения для решения таких задач
• Разобраться в структуре генетического алгоритма. Изучить методы решения типовых логистических задач эволюционными методами, на примере использования генетического алгоритма. Приобрести практические навыки решения таких задач на языке Python и Excel.

Планируемые результаты обучения

• Знание алгоритмов мутации: равномерная мутация, равномерная плотная мутация, оператор обменнной мутации, оператор зеркальной мутации, оператор транспозиции.
• Знание алгоритмов мутации: случайной мутации, оператор гауссовой мутации, арифметический оператор вещественного сдвига, геометрический оператор вещественного сдвига, BGA -оператор мутации, степенной оператор мутации
• Знание алгоритмов отбора: метод рулетки, метод пропорционального с остатком, метод турнирного отбора, метод рангового отбора, метод на основе элитизма
• Знание алгоритмов селекции: метод панмиксии, метод селективного отбора, инбридинг, аутбридинг
• Знание алгоритмов скрещивания (кроссоверы) с несколькими потомками: арифметический кроссовер, геометрический кроссовер, кроссоверы с тремя потомками
• Знание алгоритмов скрещивания (кроссоверы): одноточечный кроссовер, двухточечный кроссовер, однородный кроссовер, полуоднородный кроссовер
• Знание алгоритмов скрещивания (кроссоверы): триадный, оператор сегрегации (для четырех предков), плоский кроссовер, эвристический (вариант арифметического), расширенный линейный кроссовер, простейший кроссовер с двумя потомками
• Знание алгоритмов учета ограничений: метод смертельных штрафов, метод статических штрафов, сегрегированный генетический алгоритм, метод редукции Орвуша
• Знание и умение кодировать исходные данные логистических задач в виде хромосом. Понимание важности кодов Грея для кодирования двоичными генами.
• Знание способа использования генетических алгоритмов для эволюционного решения разнообразных логистических задач
• Знание элементов генетических алгоритмов: видов мутаций, кроссоверов, отбора, селекции и учета ограничений.
• Умение выбирать эволюционными методами маршрут минимальной длины для обхода всех вершин в сети
• Умение находить эволюционными методами циклы минимальной длины так, чтобы циклы не пересекались, а в каждом цикле суммарная емкость складов была не меньше, чем суммарная потребность потребителей.
• Умение определять эволюционными методами минимальное количество машин заданной грузоподъемности для одновременной перевозки всех товаров со склада
• Умение определять эволюционными методами минимальные расстояния между каждым потребителем и каждым складом в транспортной сети.
• Умение определять эволюционными методами план постройки дорог между несвязанными населенными пунктами так, чтобы можно было попасть из каждого в каждый и при этом суммарная длина дорог была наименьшей.
• Умение формулировать логистические задачи в терминах генов и хромосом для применения генетических алгоритмов
• Уметь выбирать оптимальное распределение товаров по машинам с учетом емкости машин и веса товаров эволюционными методами
• Уметь решать эволюционными методами задачу о назначениях (оптимальный выбор складов для доставки товара потребителям с учетом расстояний между каждым потребителем и каждым складом в транспортной сети)

Содержание учебной дисциплины

• Варианты задачи Vehicle Routing Problem и их связь с генетическими алгоритмами.
• Подходы к решению логистических задач генетическими алгоритмами.
• Структура генетических алгоритмов
• Представление данных в виде хромосом
• Алгоритмы мутации. Часть 1.
• Алгоритмы мутации. Часть 2
• Алгоритмы скрещивания (кроссоверы). Часть 2.
• Алгоритмы скрещивания (кроссоверы). Часть 1.
• Алгоритмы скрещивания (кроссоверы). Часть 3.
• Алгоритмы отбора
• Алгоритмы селекции
• Алгоритмы учета ограничений
• Пример 1. Задача о назначениях.
• Пример 2. Задача об упаковке.
• Пример 3. Задача о назначениях.
• Пример 4. Задача о расстоянии.
• Пример 5. Задача о классическом коммивояжере.
• Пример 6. Задача о покрытии циклами.
• Пример 7. Задача о дорогах.

Элементы контроля

• Домашнее задание 1
• Домашнее задание 2
• Домашнее задание 3
• Экзамен
• Оценка

Промежуточная аттестация

• 2021/2022 учебный год 2 модуль
  0.14 * Домашнее задание 1 + 0.18 * Оценка + 0.4 * Экзамен + 0.14 * Домашнее задание 2 + 0.14 * Домашнее задание 3

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

Рекомендуемая основная литература

• The Vehicle Routing Problem, edited by Paolo Toth, Daniele Vigo, 367 p., , 2002
• Современные алгоритмы поисковой оптимизации : алгоритмы , вдохновленные природой : учебное пособие, Карпенко, А. П., 2014

Рекомендуемая дополнительная литература

• Генетические алгоритмы : учеб. пособие для вузов, Гладков, Л. А., 2006
• Нейронные сети, генетические алгоритмы и нечеткие системы, Рутковская, Д., 2008