6.6. Решение задач о коммивояжере методами моделирования эволюций

Задача о коммивояжере в английской интерпретации TSP является классической NP-полной задачей [90, 161, 182]. Она заключается в нахождении кратчайшего гамильтонова цикла в графе. Задача о коммивояжере нашла широкое применение в инженерных приложениях. Без каких-либо изменений в постановке, она используется для проектирования разводки коммуникаций, разработки архитектуры вычислительных сетей и др. Кроме того, она имеет теоретическую ценность, являясь асимптотической оценкой исследования различных эвристических алгоритмов, которые могут быть затем применены для решения более сложных задач комбинаторной оптимизации, например, квадратичной задачи о назначениях, частным случаем которой является задача о коммивояжере.

Рассмотрим постановку задачи.

В неформальном виде задача о коммивояжере трактуется следующим образом: коммивояжеру необходимо посетить W городов, не заезжая в один и тот же город дважды, и вернуться в исходный пункт по маршруту с минимальной стоимостью. Более строго имеем: дан граф G = (X, [/), где \Х\ = п — множество вершин (города), \U\ = т — множество ребер (возможные пути между городами), показанный на рис. 6.46. Дана матрица чисел і?(г, j), где г, j <Е 1, 2,..., п, представляющих собой стоимость переезда из вершины хі в Xj.

Требуется найти перестановку из элементов множества X, такую что ЦФ:

Если граф не является полным, то дополнительными ограничениями являются:

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

Запишем матрицу смежности графа G = (X, U), где \Х\ = 7, \U\ = 21 (рис. 6.46). Для пути ір(1) = (1, 2,3,4, 5,6, 7) (хромосома р\) имеем ЦФ: Fitness(^(l)) = 1+1+1+1+1+1+1 = 7, а для пути ^(2) = (7, 2, 5,4,3,6,1) (хромосомаР2), имеем ЦФ: Fitness(^(2)) = 3 + 6 + 1 + 1 + 5 + 3+1 = 20. Следовательно, маршрут ср(1) предпочтительнее, чем <£>(2), с точки зрения

заданной ЦФ. Отметим, что значение ЦФ Fitness (ср) не зависит в частном случае от выбора вершины — начала маршрута. Например, Fitness(^(3)) = = Fitness(^(l)) = 7, где ср(3) = (2,3,4, 5,6, 7,1) (хромосома рз), являясь инвариантом для всех возможных циклических сдвигов и, следовательно, существуют п равнозначных маршрутов:

Фиксация вершины-старта может быть использована для сужения пространства поиска, которое в этом случае равно (п — 1)!. Поэтому в общем случае задача о коммивояжере чувствительна к выбору начальных условий. В этой связи для создания структуры алгоритма эффективно используются методы ЭМ, описанные в предыдущих, разделах.

NP-полнота задачи о коммивояжере подразумевает, что поиск ведется в пространстве, растущем от п экспоненциально. Соответственно, время работы алгоритмов, основанных на полном переборе или на построении дерева решений (методы ветвей и границ, золотого сечения и др.), растет экспоненциально в зависимости от числа вершин графа. Эти алгоритмы способны решать задачу для малого числа вершин (п « 20) за полиномиальное время. Поэтому для решения сложных задач о коммивояжере используются различные эвристики.

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

Кратко рассмотрим классификацию алгоритмов, применяемых для решения задачи о коммивояжере. Эвристические алгоритмы могут быть условно разбиты на два класса — класс, работающий только с одним решением (например, моделирование отжига) и класс, работающий с множеством (популяцией) решений (например, ГА и ЭМ).

Первый класс алгоритмов обычно имеет более высокую скорость сходимости, но в общем случае неспособен к выходу из многих локальных оптимумов. Второй класс эвристических алгоритмов осуществляет параллельный поиск в нескольких точках пространства решений. Алгоритмы этого класса имеют значительно больше шансов найти оптимальное решение, но параллельный поиск обычно имеет временную сложность большего порядка. Наиболее известными представителями этого класса являются ГА с жадными стратегиями и с по с л е д овате льным случайным или направленным преобразованием специальных матриц [182, 183]. Жадные стратегии применяются иерархически: на уровне алгоритма, на уровне блока, на уровне генетического оператора.

Опишем эволюционные стратегии, которые являются комбинацией ГА, эволюционного программирования, эволюций Ч. Дарвина, Ж. Ламарка, де Фриза и К. Поппера, а также методов локального поиска.

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

Первый способ кодирования более прост. При таком кодировании в позиции і-й хромосомы находится і-й посещенный город (г-я вершина графа). Для графа G (рис. 6.46) приведем два возможных решения при таком методе кодирования:

Здесь в первой строке записаны номера вершин графа, а во второй строке — случайная подстановка, определяющая одно из возможных решений. Одной из характерных особенностей задачи о коммивояжере, как, впрочем, и большого ряда других задач, является ограничение на возможные комбинации значений в хромосоме. В этом случае имеем: один и тот же город не может быть посещен дважды и все города должны быть посещены. Таким образом, если применить ПГА с обычными одноточечным или двухточечным ОК, то в общем случае полученные решения (потомки) будут, скорее всего, нереальными. Например, для графа G (рис. 6.46) возьмем из популяции Р = {pi, Р2, Рз ? Р4, Р5 } две хромосомы (решения задачи о коммивояжере) р^, р$:

Применим простой ОК. Пусть точка ОК находится между третьим и четвертым геном в хромосоме. Тогда получим следующих двух потомков:

Очевидно, что решения pq, Ѵг не являются допустимыми, так как в pq повторяется ген 1 и отсутствует ген 6, а в ру повторяется ген 6 и отсутствует ген 1, т. е. в решении задачи о коммивояжере содержатся города, посещаемые дважды и не посещаемые ни разу.

Интерес, представляет матричное кодирование задачи о коммивояжере. Например, для хромосомы р^ матрица запишется:

Как видно из матрицы, единицами кодируются переходы между генами в хромосоме. Для хромосомы р$ матрица задачи о коммивояжере примет

вид:

Тогда популяция хромосом будет состоять из набора аналогичных матриц. Такое кодирование в виду большого числа нулей избыточное, хотя является наглядным и удобным для преобразований. Отметим, что применение стандартных генетических операторов для такой кодировки является неэффективным в виду большого количества получаемых несуществующих потомков. Предложим вместо матриц использовать списки связности. Это позволит получить набор строительных блоков. На данном наборе на основе оператора сегрегации и оператора инверсии можно эффективно получать новых допустимых потомков. Например, на основе R(p±) запишем набор строительных блоков: 1-4; 2-3; 3-5; 4-2; 5-7; 7-6; 6-1. Применив операторы сегрегации и инверсии, получим новую допустимую хромосому р$ :4176532с ЦФ: Fitness(^(8)) = 20.

Основное преимущество представления задачи о коммивояжере в виде матрицы смежности то, что оно дает возможность анализировать шаблоны, которые применимы для n-размерной оптимизации ГА. Шаблоны, определенные в терминах единственной определенной позиции, соответствуют естественным строительным блокам, т. е. элементам. Например, шаблон (##### 7 #) есть множество всех изменений, в котором элемент 6,

соответствующий гену 7, имеет место, а остальные позиции шаблона могут быть определены случайным образом. Обобщим основные моменты анализа шаблонов ГА в отсутствии оператора репродукции и ОМ. Генерация для всех представленных шаблонов в популяции определится по формуле:

где М(Я, t) — количество представителей шаблонов Н за время t; u(Hjt) — производительность шаблонов Н за время t; u(Pjt) — средняя производительность популяции за время t. Элементы любой части шаблона конкурируют против других элементов этой части. Это приводит к сокращению размерности пространства поиска и построению больших строительных блоков высокой производительности.

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

Жадные стратегии применяются, когда искомый объект строится по частям (в нашем случае из строительных блоков). Жадная стратегия делает на каждом шаге «локально оптимальный» выбор. Алгоритмы на основе жадных стратегий работают быстрее, чем алгоритмы динамического программирования. Однако жадная стратегия не всегда дает оптимальное решение. Задача обладает свойством оптимальности для подзадачи, если оптимальное решение задачи содержит оптимальные решения ее подзадач.

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

Приведем алгоритм построения модифированного жадного ОК для задачи о коммивояжере:

1.   Для каждой пары хромосом случайным образом выберем точку жадного ОК и в качестве номера стартовой вершины графа возьмем номер отмеченного гена в хромосоме.

2.   Сравним частичную стоимость путей, ведущих из текущих вершин в хромосомах-родителях и выберем из них кратчайший.

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

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

5.   Повторяем пункты 2 и 3 пока не будет построен гамильтонов цикл с минимальной суммарной стоимостью ребер.

6.   Конец работы алгоритма.

Решение-потомок в этом алгоритме формируется как последовательность вершин графа в том порядке, в котором они становились текущими.

В данном жадном ОК использовано знание о задаче, что выбор кратчайшего пути обычно предпочтителен. Однако подобное простое предположение не всегда приводит к оптимуму, поскольку иногда требуется пренебречь локальным выигрышем ради достижения глобальной цели. Жадные ОК, основанные на знаниях о задаче, улучшают скорость сходимости, однако часто препятствуют выходу из локальных минимумов. Стандартный жадный ОК легко устраняет все плохие изменения, получаемые ОМ. Такие решения приводят к неэффективному использованию популяции. Существует несколько путей избежать этой ситуации: изменить архитектуру ГА или же не помещать такие решения в популяцию. Могут быть предприняты следующие меры:

Эвристика 1 — это предпочтение более «невыгодного» маршрута более выгодному с определенной вероятностью;

Эвристика 2 — взятие около 50% генетического материала от каждого из родителей.

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

Опишем видоизменненый модифицированный жадный ОК:

1.   Случайным образом выбрать стартовую вершину в первом родителе.

2.   Текущий родитель — первый родитель.

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

4.   Повторять пункт 3 пока все вершины не будут посещены. Потомок формируется как по следовательно сть посещаемых вершин.

5.   Конец работы алгоритма.

Покажем пример работы алгоритма для графа G (рис. 6.46). Пусть популяция состоит из двух хромосом (P9j'Pio)'

Для р9 ЦФ: Fitness(^(9)) = 22, а для рю ЦФ: Fitness(^(10)) = 15. Далее стрелка над одной из вершин в каждом из родителей обозначает, что данная вершина является текущей. Жадный ОК с изменяемой вероятностью принятия плохих решений требует настройки этой вероятности, если это константа, или же определения специальной функции для ее ав-

томатического изменения во время работы. В данном примере использован 50-процентный жадный ОК. На первом этапе вершина 5 выбрана стартовой и является текущей для обоих родителей. Согласно алгоритму следующей вершиной в путь выбирается вершина 3 , соседняя 5, имеющая кратчайший путь (5-3).

На следующем шаге в путь включается вершина 6, так как путь (5-3-6) имеет лучшее значение ЦФ, чем путь (5-3-7), после применения 50-про- центного жадного ОК. Далее в путь включается вершина 7 и частичный путь задачи о коммивояжере имеет вид (5-3-6-7).

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

Далее в путь включается вершина 4, соседняя вершине 1в первом текущем родителе. Тогда имеем путь (5-3-6-7-1—4).

Осталась не рассмотренной вершина 2, которая автоматически включается в путь задачи о коммивояжере. Тогда имеем хромосому потомок рц\ 5 3 6 7 1 4 2 с ЦФ: Fitness(^(ll)) = 26. В связи с тем, что потомок рц имеет значение ЦФ худшее, чем у родителей рд, рю, он в популяцию не включается. Снова в текущем родителе рд выбираем текущую вершину 7 и после нескольких шагов жадного ОК получаем хромосому-потомок рі2: 7 6 5 4 3 2 1 с ЦФ: Fitness(^(12)) = 7, что соответствует глобальному оптимуму. Такие жадные ОК не всегда позволяют получать глобальные оптимумы, поэтому необходимо использовать множество разработанных генетических операторов и нестандартные архитектуры генетического поиска.

На рис. 6.47 приведена структурная схема алгоритма для решения задачи о коммивояжере. Данная схема аналогична схеме алгоритма решения задачи размещения. В отличие от нее предлагается следующее. Введен блок локального поиска, который позволяет получать локальные экстремумы. Все генетические операторы ориентированы на использование знаний о решаемой задаче, причем изменен порядок использования генетических операторов. В задаче о коммивояжере решающую роль играют ОК и его модификации, поэтому ОК в данной схеме примеряется первым.

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

В схеме рис. 6.47 возможно уменьшение «жадности» ОК, что разнообразит популяцию, если есть добавление нового генетического материала с высокими ЦФ, производимого случайными факторами или же дополнительными эвристиками. После достижения локального оптимума в популяции наблюдается большое число одинаковых маршрутов. В этой связи может наступить преждевременная сходимость. Эта проблема тесно связана с потерей разнообразия в популяции. Одним из источников однообразия является появление «су пер-хромо сом», которые в течении многих поколений доминируют в ней. Имеется ряд путей частичного решения этой проблемы, например, изменение алгоритма селекции или же модификация генетического оператора рекомбинации.

Например, факт нахождения в локальном (глобальном) экстремуме может быть установлен, когда К первых хромосом в популяции имеют одинаковую длину маршрута. Это К называется элитным числом. Предполага-

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

•    постоянство одной хромосомы: из всех маршрутов, имеющих одинаковую длину, только один остается неизменным. Над всеми другими выполняются модифицированные генетические операторы;

•    неизменность хромосомы с наилучшей ЦФ: из всех маршрутов только наилучший остается неизменным. Над всеми другими выполняются модифицированные генетические операторы.

Модифицированные генетические операторы — это полная или частичная рандомизация решения. Такие изменения в популяции могут разрушать хромосомы с высоким значением ЦФ. Однако в двух предложенных эвристиках лучшее решение в популяции остается неизменным.

Отметим, что такие генетические операторы и эвристики работают не все время, а. только в ситуациях, когда однообразие в популяции достигает высокого уровня. Совместная эволюция Ч. Дарвина, Ж. Ламарка, де Фриза и К. Поппера регламентирует и управляет таким процессом генетического поиска.

Отметим, что в описанном алгоритме был использован набор методов селекции. В основном цикле ГА промежуточная популяция решений не создавалась, получаемый потомок замещал наихудшую хромосому в популяции. Следует отметить, что модифицированные генетические операторы инверсии и ОМ оказывают большое влияние на получение эффективных результатов. Отметим, что отличительной особенностью рассмотренного ГА является способность хорошо работать на популяциях с малым числом хромосом, что уменьшает сложность и временную сложность алгоритма. Подобное улучшение связано с высокой степенью использования миграции популяции в виде регулярных адаптаций, выполняемых рассмотренными выше генетическими операторами. Полученные результаты в генетическом решении задачи о коммивояжере позволяют говорить об эффективности метода и целесообразности использования аналогичных подходов в решении других задач оптимизации.