КОНТРОЛЬ- Проблема коммивояжера - это проблема особого рода. Здесь продавец, который должен путешествовать между N городами. Порядок, в котором он это делает, его не волнует, если он посещает каждого один раз во время своего путешествия и заканчивает там, где был вначале. Каждый город связан с другим близлежащими городами или узлами самолетами, дорогой или железной дорогой. Это своего рода проблема жесткой оптимизации. Сложность можно увидеть на рисунке ниже -

Очевидно, что решение этой проблемы с использованием метода грубой силы занимает O (n!) времени, а при использовании динамического программирования сложность времени составляет O (n² * 2 ^ n). Так что решить эту проблему очень сложно. Для близкой оптимизации я использовал генетический алгоритм, который представляет собой своего рода алгоритм аппроксимации.

ЦЕЛЬ- Создание веб-приложения, которое показывает оптимальный путь для набора пунктов назначения, которые вводятся посетителем / пользователем. Я дал ссылку на Github для этого проекта ниже -

Github- https://github.com/HACKERSHUBH/Path-Finder

Предварительные требования: HTML, CSS, Javascript

Я разработал этот проект двумя способами: в режиме статических пунктов назначения и в режиме динамических пунктов назначения.

Метод статических пунктов назначения - сценарий Python, который берет набор данных о городах / достопримечательностях / посещаемых местах и ​​прогнозирует оптимальный путь для покрытия всех городов, включенных в набор данных.

Метод динамических пунктов назначения. Я разработал веб-приложение, которое позволяет выбрать нужный город в удобной для пользователя форме и прогнозировать оптимальный путь только для городов, в которые вошел пользователь.

Давайте начнем!

Прежде всего, я хотел показать вам рабочую демонстрацию проекта.

Реализация вышеуказанной проблемы-

Структура каталогов выглядит так:

Генетический алгоритм - GA отлично подходит для решения сложных задач поиска. Они используются для создания продуктов невероятно высокого качества благодаря их способности искать наилучшее соответствие по огромной комбинации параметров. они могут искать среди различных комбинаций материалов и дизайнов, чтобы найти идеальное сочетание обоих, которое может привести к более прочному, легкому и в целом лучшему конечному продукту. Генетические алгоритмы основаны на процессе эволюции путем естественного отбора, который наблюдался в природе.

Основные параметры генетического алгоритма

Базовый процесс генетического алгоритма:

  1. Инициализация - создайте начальную популяцию. Эта популяция обычно формируется случайным образом и может быть любого желаемого размера - от нескольких особей до тысяч.
  2. Оценка - затем оценивается каждый член совокупности, и мы вычисляем «пригодность» для этого человека. Значение пригодности рассчитывается исходя из того, насколько хорошо оно соответствует нашим желаемым требованиям. Эти требования могут быть простыми: «более быстрые алгоритмы лучше» или более сложными: «более прочные материалы лучше, но они не должны быть слишком тяжелыми».
  3. Выбор - мы хотим постоянно улучшать общую физическую форму нашего населения. Отбор помогает нам в этом, отбрасывая плохие конструкции и оставляя в популяции только лучших людей. Существует несколько различных методов отбора, но основная идея та же, что делает более вероятным, что для нашего следующего поколения будут выбраны более подходящие люди.
  4. Кроссовер - во время кроссовера мы создаем новых людей, комбинируя аспекты выбранных нами людей. Мы можем думать об этом как о имитации того, как секс работает в природе. Есть надежда, что, объединив определенные черты двух или более особей, мы создадим еще более «приспособленное» потомство, которое унаследует лучшие черты каждого из своих родителей.
  5. Мутация. Нам нужно добавить немного случайности в генетику наших популяций, иначе каждая комбинация решений, которые мы можем создать, будет в нашей исходной популяции. Мутация обычно работает путем внесения очень маленьких случайных изменений в геном человека.
  6. И повторяем! - Теперь у нас есть следующее поколение, и мы можем начать снова со второго шага, пока не достигнем условия завершения.

Прекращение

Есть несколько причин, по которым вы захотите прекратить поиск решения вашего генетического алгоритма. Наиболее вероятная причина в том, что ваш алгоритм нашел достаточно хорошее решение, отвечающее заранее определенным минимальным критериям. Причинами предложения для завершения могут быть ограничения, такие как время или деньги, или мы можем заранее определить количество итераций, до которых будет работать алгоритм.

Решая указанную выше проблему, следует помнить о двух важных правилах:

  1. Каждый город нужно посетить ровно один раз
  2. Мы должны вернуться в начальный город, поэтому наше общее расстояние необходимо рассчитать соответствующим образом.

Подход

Давайте начнем с нескольких определений, перефразированных в контексте TSP:

  • Джин: город (в координатах (x, y)).
  • Индивидуальный (также известный как «хромосома»): один маршрут, удовлетворяющий указанным выше условиям.
  • Население: набор возможных маршрутов (т. е. сбор людей).
  • Родители: два маршрута, которые объединяются для создания нового маршрута.
  • Пул спаривания: набор родителей, которые используются для создания нашей следующей популяции (таким образом, создавая новое поколение маршрутов).
  • Фитнес: функция, которая сообщает нам, насколько хорош каждый маршрут (в нашем случае, насколько короткое расстояние).
  • Мутация: способ внести изменения в нашу популяцию, случайным образом поменяв местами два города на маршруте.
  • Элитарность: способ передать лучших людей следующему поколению.

Поскольку пользователи выбирают точки назначения на карте Google с помощью маркера, нам нужна матрица расстояний.

Если пользователю нужно его текущее местоположение, он должен нажать кнопку «Местоположение» на веб-сайте. Я также использую различные режимы движения, такие как:

  • Автомобиль
  • Велосипед

Я также использую, должен ли пользователь преодолевать шоссе во время поездки или нет, поэтому есть также режим включения или выключения шоссе. затем я создаю массив данных о продолжительности для различных типов режимов движения. код для этого -

Теперь идет код генетического алгоритма с параметрами:

Теперь мы применяем мутацию, кроссовер к текущей популяции и возвращаем популяцию потомства. После этого мы находим наиболее приспособленного индивидуума на каждой итерации, применяем турнирный отбор, а затем выбираем наиболее приспособленный индивидуальный индекс.

Это завершает код генетического алгоритма для решения задачи коммивояжера. Хотя это приближенный алгоритм поиска кратчайшего маршрута, но его временная сложность намного меньше по сравнению с другими подходами.

Использованная литература-

Получайте лучшие предложения по программному обеспечению прямо в свой почтовый ящик