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

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

Статус: Курс по выбору

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

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

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

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

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

Охват аудитории: для своего кампуса

Преподаватели: Федянин Денис Николаевич

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

Кредиты: 4

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

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

Аннотация

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

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

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

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

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