Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки
Маршрутом является путь между городами, по которому перевозится определенный логистический объект. Необходимо найти оптимальный обход городов, побывав в каждом городе ровно один раз. Оптимальным считается маршрут, по которому возможно доставить логистический объект, в кратчайшие сроки (или предусмотренные сроки) с минимальными затратами, а также с минимальным вредом для объекта доставки. Время работы линейного поиска для N городов равно факториалу числа N. Необходимо использовать эвристический поиск, который хоть и не гарантирует нахождение единственного решения, но выдает оптимальный результат за установленное время поиска. В качестве эвристического поиска предлагается использовать генетический алгоритм. За счет использования функции мутации, скрещивания и отбора лучших результатов, генетические алгоритмы позволяют оптимизировать определенные виды NP-полных задач. Несмотря на то, что задача коммивояжера является NP-полной, она широко применяется в прикладных транспортных системах.
Генетический алгоритм (ГА) представляет собой метод оптимизации, основанный на концепциях естественного отбора и генетики. В этом подходе переменные, характеризующие решение, представлены в виде ген в хромосоме. ГА оперирует конечным множеством решений (популяцией) — генерирует новые решения как различные комбинации частей решений популяции, используя такие операторы, как отбор, рекомбинация (кроссинговер) и мутация. Новые решения позиционируются в популяции в соответствии с их положением на поверхности исследуемой функции.
Для реализации этого используют моделирование эволюции (естественного отбора) или если проще — борьбы за выживание. Тогда нам остается организовать некоторую среду — популяцию, населить её решениями — особями, и устроить им борьбу. Для этого нужно определить функцию, по которой будет определяться сила особи — качество предложенного ею решения. Основываясь на этом параметре можно определить каждой особи, количество оставляемых ею потомков, или вероятность того, что эта особь оставит потомка. [1]
Разработка генетического алгоритма начинается с конструирования двоичной хромосомы, представляющей возможные решения этой задачи. Традиционно генетические алгоритмы используют для этого двоичные строки фиксированной длины. Например, для нашей задачи коммивояжера с четырьмя городами, которые надо поочередно посетить, проще всего было бы выделить по 2 бита на каждый город, получив 8-битовую хромосому. Можно построить множество случайных строк из 8 бит, интерпретируя их как маршруты объезда городов.
Таблица 1
Chromosome | Meaning
_____________________________________________________
00110010 | Auckland Wellington Auckland Napier
10101100 | Napier Napier Wellington Auckland
10100101 | Napier Napier New Plymouth New Plymouth
01010101 | New Plymouth New Plymouth New Plymouth New Plymouth
Но эта хромосома слишком проста для задачи коммивояжера любого размера. Один из ее недостатков заключается в том, что большинство двоичных строк из 8 бит не соответствуют допустимым маршрутам. Как видно из таблицы 1, мы можем получить маршруты, проходящие через некоторые города дважды, а через другие — ни разу. Можно было бы рассматривать и такие «не-решения», с тем чтобы настоящие решения вытеснили их в процессе эволюции, но в дальнейшем мы увидим, что это неэффективный путь. Лучше придумать другую кодировку, чтобы любая двоичная строка представляла допустимый (но, конечно, не всегда разумный) маршрут в задаче коммивояжера.
Таблица 2
Chromosome | Meaning
_________________________________________________
10111 | Napier Auckland New Plymouth Wellington
00110 | Auckland New Plymouth Napier Wellington
10101 | Auckland New Plymouth Napier Wellingt
01011 | New Plymouth Napier Wellington Auckland
Вот одна из таких кодировок: первые два бита — номер первого города в маршруте, вторые два бита — номер того из оставшихся трех городов, который посещается вторым, пятый бит определяет выбор из оставшихся двух городов, а на номер последнего, четвертого города битов выделять не нужно. Мы получаем 5-битовую хромосому. В таблице 2 показаны несколько таких хромосом и соответствующих им маршрутов. Заметим, что и здесь возникает небольшая проблема, так как вторые два бита могут представлять четыре различных числа, которые надо сопоставить трем различным городам. С этим можно справиться, решив, что и 11, и 00 соответствуют первому из этих трех городов. Не очень удачное решение, так как оно вдвое повышает шансы наугад выбрать именно этот город, но пока это нам не очень мешает.
Сконструировав хромосому, мы без всякого труда можем построить 500 случайно выбранных маршрутов в нашей задаче коммивояжера, сгенерировав 500 случайных 5-битовых чисел. Но ведь мы как раз и мечтали свести программирование к минимуму при решении трудных задач. Значит, цель достигнута? Разумеется, это зависит от того, насколько хороши полученные таким путем решения. Другими словами, затратит ли наш коммивояжер минимально возможное время на свои переезды из города в город, если воспользуется некоторыми из предлагаемых маршрутов?
В нашем случае ответ, скорее всего, будет утвердительным. 5 бит могут представлять лишь 32 различных числа, поэтому среди нескольких сот случайных маршрутов, наверное, будет и оптимальный. Пространство поиска возможных решений очень мало. К сожалению, трудные для современных компьютеров задача коммивояжера относятся к нескольким сотням объектов: например, городов или скважин, которые необходимо пробурить, и т. д. В этом случае объем пространства поиска приближается по порядку величины к числу атомов в известной части вселенной, и, по всей вероятности, даже лучшее из пятисот выбранных наугад решений окажется очень плохим. Вот здесь и начинает работать эволюция.
Нам нужно каким-то образом сымитировать «выживание сильнейших» (survival of the fittest), позволяя лучшим хромосомам жить, а не самых лучших обрекая на гибель. Традиция разработки генетических алгоритмов предписывает выбирать каждое последующее поколение (то есть совокупность определенного количества хромосом) путем стохастической, но целенаправленной селекции. Для этого мы должны знать, как отличить хорошие хромосомы от плохих.
Реализация генетического алгоритма предполагает задание функции приспособленности, или фитнес-функции (fitness function). Эта функция получает на вход двоичную хромосому и возвращает число, показывающее, насколько хороша эта хромосома. В реализованном автором генетическом алгоритме решения задачи коммивояжера сначала определяется наихудшая хромосома (отвечающая самому длинному из маршрутов) и измеряется длина этого маршрута (в километрах). Полученное число умножается на 1,1 и объявляется плохой длиной, по отношению к которой оценивается качество остальных хромосом: приспособленность хромосомы вычисляется как разность между плохой длиной и длиной маршрута, заданного данной хромосомой. В результате этих несколько запутанных вычислений каждой хромосоме ставится в соответствие ее приспособленность (fitness) — число, которое оказывается сравнительно маленьким для плохих (длинных) маршрутов и сравнительно большим для хороших (коротких) маршрутов.
В двух случаях генетические алгоритмы очень хороши. Первый случай: когда не известен способ точного решения задачи. Если мы знаем, как оценить приспособленность хромосом, то всегда можем заставить генетический алгоритм решать эту задачу. Второй случай: когда способ для точного решения существует, но он очень сложен в реализации, требует больших затрат времени и денег, то есть, попросту говоря, дело того не стоит. Пример — создание программы для составления персонального расписания на основе техники покрытия множеств с использованием линейного программирования.
Несмотря на то, что конструирование хромосом и фитнес-функций может потребовать значительных усилий, генетические алгоритмы легко реализуются даже с нуля и способны решать широкий круг задач. Используя аналогию с развитием живых организмов от простых форм к более сложным, генетические алгоритмы приблизились к тому, чтобы стать общим методом решения задач. Другие «природоподобные» парадигмы, такие как моделирование отжига (simulated annealing) и табу-поиск (taboo search), тоже позволяют решать аналогичные задачи. [2]
1. Генетический алгоритм. http://www.codenet.ru/progr/alg/Smart/Genetic-Algorithms.php
2. Генетические алгоритмы: почему они работают? когда их применять? РОСС КЛЕМЕНТ . "Компьютерра" №11 от 16 марта 1999 года
- Ссылка для цитирования: Обобщённая задача коммивояжёра для определения рациональных маршрутов поставки // .
Комментарии (0)
RSS свернуть / развернутьАвтор топика запретил добавлять комментарии