Привет !!!. Я Паритош, работаю специалистом по анализу данных в Индии. Не стесняйтесь связаться со мной, это мой профиль linkedin. Недавно у меня появилась прекрасная возможность поработать над проблемой коммивояжера с использованием генетического алгоритма. Не стесняйтесь задавать любые вопросы.
Задача коммивояжера состоит из продавца и набора городов. Продавец должен посетить каждый из городов, начиная с определенного (например, родного города) и возвращаясь в тот же город. Проблема в том, что коммивояжер хочет минимизировать общую продолжительность поездки.
О генетическом алгоритме:
Генетический алгоритм запускается с набора решений (представленных хромосомами), называемых популяцией. Решения из одной популяции берутся и используются для формирования новой популяции. Новая популяция будет лучше старой. Решения, которые отбираются для формирования новых решений (потомков), выбираются в соответствии с их пригодностью, и чем больше они подходят, тем больше у них шансов на воспроизведение. Это повторяется до тех пор, пока не будет выполнено какое-либо условие, например количество популяций или улучшение наилучшего решения.
Генетический алгоритм - это парадигма, которая зарекомендовала себя как уникальный подход к решению различных математических задач, которых не удалось решить другим математическим оптимизаторам градиентного типа. Оптимизация муравьиной колонии была успешно применена к большому количеству сложных задач комбинаторной оптимизации. .
Генетический алгоритм будет выполнять следующие действия:
1. Создайте случайные расстояния для разных городов.
2. Определите физическую форму.
3. Выберите пул для спаривания.
4. Порода
5. Мутировать
6. Повторить
Подход:
Шаг 1: загрузите библиотеки.
Шаг 2. Создайте случайные расстояния для разных городов.
Шаг 3. создайте начальную популяцию.
Шаг 4. Определите физическую форму
Чтобы смоделировать наше «выживание наиболее приспособленных», мы можем использовать Fitness для ранжирования каждого человека в популяции. Нашими выходными данными будет упорядоченный список с идентификаторами маршрутов и каждой связанной оценкой пригодности.
Шаг 5. Выберите пул для спаривания.
мы будем использовать выходные данные от rankPathes, чтобы определить, какие маршруты выбрать в нашей функции perform_selection.
функция perform_selection возвращает список идентификаторов маршрутов, который мы можем использовать для создания пула сопряжения в функции do_mating_pool.
Теперь мы создадим наш пул сопряжения с помощью функции perform_selection, мы можем создать пул сопряжения. Мы просто извлекаем выбранных людей из нашей популяции.
Шаг 6. Порода
мы создадим следующее поколение в процессе под названием кроссовер (также известный как «селекция»). Операторы кроссовера и мутации используются для внесения разнообразия в популяцию.
Созданы различные методы кроссовера, чтобы получить оптимальное решение как можно раньше при минимальном количестве поколений. Выбор оператора кроссовера больше влияет на производительность генетического алгоритма.
Мы используем функцию do_breed_population, чтобы заполнить остальную часть следующего поколения.
Шаг 7. Мутация
Мутация - это операция дивергенции. Он предназначен для того, чтобы время от времени вырывать одного или нескольких членов популяции из локального минимального / максимального пространства и потенциально обнаруживать лучшее минимальное / максимальное пространство.
По сути, кроссовер и мутация - это процесс, который позволяет найти решение проблемы. Новые решения находятся из старых решений в процессе кроссовера и мутации, во многом подобно тому, что происходит в природе с хромосомами. Итак, новые решения являются порождением старых решений или потомками старых решений.
мы будем использовать обменную мутацию. Это означает, что с заданной малой вероятностью два города поменяются местами на нашем маршруте. Мы сделаем это для одного человека в нашей функции do_mutation:
Затем мы можем расширить функцию do_mutation для работы с новой популяцией.
Шаг 8. Повторите.
Давайте соберем эти части вместе, чтобы создать функцию, которая создает get_following_gen.
Шаг 9. Создайте наш генетический алгоритм.
Шаг 10. Запустите и проверьте результаты.
Зайдите на мой GitHub здесь, чтобы увидеть полный пример.
Это мой первый пост в блоге. Я буду рад получить любой конструктивный отзыв, который поможет мне стать лучше и мотивирует писать больше блогов. Если у вас есть какие-либо вопросы или вам нужна помощь, не стесняйтесь обращаться ко мне через
Электронная почта: [email protected]
Linkedin: https://www.linkedin.com/in/paritosh-kumar-b8ab61141/
Хлопайте, если вам понравился этот пост. Спасибо !!!!
