Разработка программы использования генетических алгоритмов для решения транспортной задачи
ВВЕДЕНИЕ
В условиях свободного рынка важной становится оптимизация производства и бизнеса для повышения конкурентоспособности продуктов и услуг. Ранее планы разрабатывались «на глаз», но в середине XX века появился математический аппарат линейного программирования, который позволяет составлять планы обоснованно и с максимальным результатом. Транспортная задача является одним из видов линейного программирования и широко применяется в теории и практике на транспорте и в промышленности, особенно для рационализации производства и планирования грузопотоков.Сегодня, в эпоху изменения рынка, линейное программирование не всегда эффективно при решении задач за короткий срок. Поэтому процесс создания новых моделей и методик, основанных на генетических алгоритмах, становится актуальным для решения подобных задач, особенно в международных перевозках, когда требуется управлять огромным объемом информации и пунктами назначения. Естественные аналоги, такие как генетические алгоритмы, могут быть эффективнее при решении сложных задач благодаря их совершенствованию в течение многих лет эволюции.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ…………………………………………………………………………6
1. Транспортная задача……………………………………………………………7
1.1. Понятие транспортной задачи………………………………………………...7
1.2. Постановка транспортной задачи……………………………………………9
1.3. Метод северо-западного угла………………………………………………..11
1.4. Метод минимального элемента……………………………………………...12
1.5. Метод Фогеля…………………………………………………………………14
1.6. Метод потенциалов…………………………………………………………..15
2. Генетический алгоритм………………………………………………………...17
2.1. Общие сведения………………………………………………………………17
2.2. Основная терминология в генетических алгоритмах……………………...20
2.3. Репродукция………………………………………………………………….22
2.4. Оператор скрещивания………………………………………………………24
2.5. Мутация………………………………………………………………………26
2.6. Виды и разновидности генетических алгоритмов…………………………28
2.7. Муравьиный алгоритм………………………………………………………30
2.8. Применение генетических алгоритмов в транспортных задачах…………32
3. Реализация……………………………………………………………………...33
3.1. Реализация генетического алгоритма……………………………………….33
3.2. Постановка и решение задачи………………………………………………35
3.2.1 Решение методом северо-западного угла…………………………………36
3.2.2 Решение задачи методом минимального элемента………………………40
3.3. Выбор среды разработки……………………………………………………44
3.4. Реализация алгоритма на Python…………………………………………….46
4. Тестирование……………………………………………………………………49
ЗАКЛЮЧЕНИЕ……………………………………………………………………51
СПИСОК ИСТОЧНИКОВ………………………………………………………..52
ПРИЛОЖЕНИЕ А………………………………………………………………...53
ПРИЛОЖЕНИЕ Б…………………………………………………………………55
ПРИЛОЖЕНИЕ В…………………………………………………………………66
ПРИЛОЖЕНИЕ Г…………………………………………………………………77
СПИСОК ИСТОЧНИКОВ
Эволюционные вычисления: Учебное пособие / Ю. А. Скобцов, Д. В. Сперанский— М.: Национальный Открытый Университет «ИНТУИТ» 2015. —331с.
Вычислительный интеллект: лабораторный практикум / Ю. А. Скобцов. – СПб.: ГУАП, 2022. – 141 с.
Гвоздинский Анатолий Николаевич, Мельник Сергей Владимирович Эволюционный подход к решению оптимизационных задач транспортного типа // АСУ и приборы автоматики. 2009. №147. URL: https://cyberleninka.ru/article/n/evolyutsionnyy-podhod-k-resheniyu-optimizatsionnyh-zadach-transportnogo-tipa (дата обращения: 14.05.2023).
Линейное программирование: транспортные и сетевые модели: учеб. пособие / О. В. Болотникова, Д. В. Тарасов, Р. В. Тарасов. — Пенза: Изд-во ПГУ, 2016 — 88 с.
Норенков И. П., Арутюнян Н. М. Эволюционные методы в задачах выбора проектных решений // Машиностроение и компьютерные технологии. 2007. №9. URL: https://cyberleninka.ru/article/n/evolyutsionnye-metody-v-zadachah-vybora-proektnyh-resheniy (дата обращения: 24.05.2023).
Виноградов Дмитрий Валерьевич Области применения эволюционных алгоритмов // Вестник МГУП. 2016. №2. URL: https://cyberleninka.ru/article/n/oblasti-primeneniya-evolyutsionnyh-algoritmov (дата обращения: 26.05.2023).
Курейчик В. М. Генетические алгоритмы // Известия ЮФУ. Технические науки. 1998. №2. URL: https://cyberleninka.ru/article/n/geneticheskie-algoritmy (дата обращения: 26.05.2023).
Генетический алгоритм: теория и практика: учеб. пособие / М. В. Бураков. – СПб.: ГУАП, 2008.
Боборыкин В.А. Математические методы решения транспортных задач. СПб.: СЗПИ, 2014.
Помимо вышеперечисленных алгоритмов существуют еще и муравьиные алгоритмы.Муравьиные алгоритмы – это методы решения задач, которые имитируют поведение муравьев в природе. Они используются для оптимизации сложных задач, таких как распределение ресурсов, поиск путей в лабиринтах и т. д.Один из основных принципов муравьиных алгоритмов заключается в том, что каждый муравей выполняет свою задачу независимо от других муравьев. Каждый муравей имеет свою цель и движется к ней, используя информацию, которую он получает от других муравьев и окружающей среды.Муравьиные алгоритмы работают следующим образом:1. Создание популяции муравьев, каждый из которых имеет свою уникальную цель.2. Определение начального состояния популяции.3. Определение расстояния между муравьем и его целью.4. Определение направления движения муравья в зависимости от его цели и расстояния до нее.5. Определение нового состояния популяции на основе информации, полученной от муравьев.6. Повторение шагов 3-5, пока оптимальное решение задачи не будет достигнуто.Одним из ключевых преимуществ муравьиных алгоритмов является их способность находить оптимальные решения сложных задач. Кроме того, они могут работать с большим количеством переменных и ограничений, что делает их особенно полезными для решения сложных проблем в различных областях науки и техники.Однако, как и любой другой алгоритм, муравьиные алгоритмы имеют свои недостатки. Например, они могут быть медленными и требовать большого количества ресурсов для работы.