Транспортная задача для минимизации затрат с использованием генетического алгоритма - PullRequest
Новая
       23

Транспортная задача для минимизации затрат с использованием генетического алгоритма

0 голосов
/ 03 декабря 2018

Я новичок в генетическом алгоритме, и вот простая часть того, над чем я работаю

Есть фабрики (1,2,3), и они могут обслуживать любого из следующих клиентов (ABC) иТранспортные расходы приведены в таблице ниже.Существуют фиксированные затраты на A, B, C (2,4,1) 

     A   B   C
1    5   2   3
2    2   4   6
3    8   5   5

. Как решить транспортную проблему, чтобы минимизировать стоимость, используя генетический алгоритм

Ответы [ 2 ]

0 голосов
/ 14 декабря 2018

Как уже упоминалось в ответе Нейдеккеноби, в этом случае пространство поиска решения слишком мало, т. Е. Всего 8 возможных решений ["ABC", "BCA", "CAB", "BAC", "CBA", "ACB"].Я предполагаю, что это только упрощенная версия вашей проблемы, и ваша проблема на самом деле содержит больше фабрик и клиентов (но количество фабрик и клиентов одинаково).В этом случае вы можете просто использовать специальную мутацию и кроссовер, чтобы избежать невозможного решения для повторяющихся клиентов, например, ["ABA", 'CCB', etc.].

Для мутации я предлагаю использовать своповую мутацию, то есть случайным образом выбрать двух клиентов, поменять местами их соответствующие фабрики (позиции):

A BC мутировать в A CB

A B C преобразовать в C B A

0 голосов
/ 03 декабря 2018

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

Итак, сначала вам нужно внедрить свою хромосому.В вашей ситуации давайте примем сторону клиентов или заводов.Давайте возьмем клиентов.Ваше решение будет выглядеть так:

1 -> A

2 -> B

3 -> C

Итак, ваш пример хромосомы "ABC",Затем создайте другую хромосому (например, «BCA»). Теперь вам нужна функция подгонки, которую вы хотите минимизировать / максимизировать.Эта функция вычислит шанс размножения ваших хромосом.В вашей ситуации это будет общая стоимость.Напишите функцию, которая вычисляет стоимость для данной фабрики и данного клиента.

Теперь, что вы собираетесь сделать, это:

  • Выберите 2 хромосомы, взвешенные случайным образом.(Веса рассчитываются с помощью функции подбора)
  • Выберите индекс из 2 хромосом и создайте новые хромосомы, используя их переключенные части.
  • Если новые хромосомы имеют недопустимые части (например, "ABA" в вашемситуации), сделайте фиксирующий ход (например, сделайте одно из «A», «C»).Мы называем это «мутацией».
  • Добавьте вашу новую хромосому в набор хромосом, если ее там не было раньше.
  • Перейдите к первому процессу снова.

Вы будете делать это в течение нескольких итераций.У вас могут быть тысячи хромосом.Когда вы думаете, «этого достаточно», остановите процесс и отсортируйте хромосомный набор по возрастанию / убыванию.Первая хромосома будет вашим результатом.

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

Только для вашей ситуации возможный набор хромосом очень мал, поэтому я гарантирую, что вы найдете оптимальный в секунду илидва.Поскольку весь набор хромосом для вас ["ABC", "BCA", "CAB", "BAC", "CBA", "ACB"].

В общем, вам нужно 3 информации для применения генетического алгоритма:

  • Какой должна быть моя хромосома?(И начальный набор хромосом)
  • Какая у меня функция подгонки?
  • Как сделать пересечение в моих хромосомах?

Есть еще кое-что, о чем нужно заботитьсяОб этой проблеме:

  • Без мутаций генетический алгоритм может придерживаться локального оптимума.Это все еще может использоваться для задач оптимизации с ограничениями.
  • Даже если хромосома существует с очень низким шансом выбора для перекрестного перехода, вы не должны сортировать и обрезать набор хромосом до конца итераций,В противном случае вы можете застрять в локальном экстремуме или, что еще хуже, вместо обычного глобального оптимума вы можете получить обычный вариант решения.
  • Чтобы ускорить процесс, выберите несходные исходные хромосомы.Без достаточного количества мутаций поиск глобального оптимума может быть настоящей болью.
...