Применение эволюционных алгоритмов в логистике

Бакалавриат 2020/2021

Статус: Курс по выбору (Управление логистикой и цепями поставок в бизнесе)

Направление: 38.03.02. Менеджмент

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

Где читается: Высшая школа бизнеса

Когда читается: 4-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Преподаватели: Громов Василий Александрович, Федянин Денис Николаевич

Язык: русский

Кредиты: 4

Контактные часы: 40

Полная версия программы учебной дисциплины

Аннотация

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

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

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

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

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

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

Варианты задачи Vehicle Routing Problem и их связь с генетическими алгоритмами.
Анализ математических постановок вариантов задачи VRP и использования одного из эволюционных методов (генетического алгоритма) для их решения.
Структура генетических алгоритмов
Описывается структура и элементы генетического алгоритма: методы мутации, варианты кроссоверов, методы отбора, методы селекции и учета ограничений.
Подходы к решению логистических задач генетическими алгоритмами.
Формулировка и анализ способа решения типовых логистических задач генетическими алгоритмами
Представление данных в виде хромосом
Кодирование исходных данных логистической задачи в виде хромосомы: с двоичными, целочисленными или вещественными генами. Коды Грея.
Алгоритмы мутации. Часть 1.
Равномерная мутация, равномерная плотная мутация, оператор обменнной мутации, оператор зеркальной мутации, оператор транспозиции.
Алгоритмы мутации. Часть 2
Cлучайная мутации, оператор гауссовой мутации, арифметический оператор вещественного сдвига, геометрический оператор вещественного сдвига, BGA -оператор мутации, степенной оператор мутации
Алгоритмы скрещивания (кроссоверы). Часть 1.
Одноточечный кроссовер, двухточечный кроссовер, однородный кроссовер, полуоднородный кроссовер
Алгоритмы скрещивания (кроссоверы). Часть 2.
Триадный оператор скрещивания, оператор сегрегации (для четырех предков), плоский кроссовер, эвристический (вариант арифметического), расширенный линейный кроссовер, простейший кроссовер с двумя потомками
Алгоритмы скрещивания (кроссоверы). Часть 3.
Арифметический кроссовер с двумя потомками, геометрический кроссовер с двумя потомками, кроссоверы с тремя потомками
Алгоритмы отбора
Метод рулетки, метод пропорционального с остатком, метод турнирного отбора, метод рангового отбора, метод на основе элитизма
Алгоритмы селекции
Метод панмиксии, метод селективного отбора, инбридинг, аутбридинг
Алгоритмы учета ограничений
Метод смертельных штрафов, метод статических штрафов, сегрегированный генетический алгоритм, метод редукции Орвуша
Пример 1. Задача о назначениях.
Применение эволюционных методов к задаче о назначениях (оптимальный выбор складов для доставки товара потребителям с учетом расстояний между каждым потребителем и каждым складом в транспортной сети)
Пример 2. Задача об упаковке.
Применение эволюционных алгоритмов для выбора оптимального распределения товаров по машинам с учетом емкости машин и веса товаров.
Пример 3. Задача о назначениях.
Применение эволюционных алгоритмов для определения минимального количества машин заданной грузоподъемности для одновременной перевозки всех товаров со склада
Пример 4. Задача о расстоянии.
Применение эволюционных алгоритмов для определения минимального расстояния между каждым потребителем и каждым складом в транспортной сети.
Пример 5. Задача о классическом коммивояжере.
Применение эволюционных алгоритмов к выбору маршрута минимальной длины для обхода всех вершин в сети.
Пример 6. Задача о покрытии циклами.
Применение эволюционных алгоритмов к выбору циклов минимальной длины так, чтобы циклы не пересекались, а в каждом цикле суммарная емкость складов была не меньше, чем суммарная потребность потребителей.
Пример 7. Задача о дорогах.
Применение эволюционных алгоритмов для определения плана постройки дорог между несвязанными населенными пунктами так, чтобы можно было попасть из каждого в каждый и при этом суммарная длина дорог была наименьшей.

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

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

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

Промежуточная аттестация (2 модуль)
0.14 * Домашнее задание 1 + 0.14 * Домашнее задание 2 + 0.14 * Домашнее задание 3 + 0.18 * Оценка + 0.4 * Экзамен

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