ВЕСТНИК ЮЖНОГО НАУЧНОГО ЦЕНТРА РАН, Том 1, №4,2005, стр. 87-92
— ЗАЩИТА ИНФОРМАЦИИ =====
УДК 628.3 + 621.3
БИОНИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
© 2005 г. В.В. Курейчик!
Рассматривается проблема решения задачи о коммивояжере. Для ее решения предлагаются модифицированные методы моделирования эволюции и бионического поиска. Это позволяет получать решение с локальными оптимумами за полиномиальное время. Сложность алгоритмов имеет в среднем квадратичный порядок.
Задача о коммивояжере является одной из ключевых задач искусственного интеллекта. Она нашла широкое применение в инженерных приложениях. Без каких-либо изменений в постановке эта задача используется для проектирования ЭВА и РЭА, разводки коммуникаций, разработки архитектуры вычислительных сетей и др. Кроме того, задача о коммивояжере (ЗК) имеет теоретическую ценность, являясь асимптотической оценкой исследования различных эвристических алгоритмов. Задача коммивояжера (Traveling Salesman problem - TSP) является NP-полной задачей [1-6]. Она заключается в нахождении кратчайшего гамильтонова цикла в графе. Предлагаются бионические подходы для решения этой задачи. В отличие от известных генетических алгоритмов решения данной задачи [2—4, 6] предлагается новая стратегия "эволюция-по-иск" "поиск-эволюция" и ее различные иерархические модификации. Разработана программная среда для решения этой задачи. Проведен вычислительный эксперимент и протестирована серия из 1 ООО графов на 100, 300, 500, 700 и 1 000 вершин. При этом временная сложность алгоритма не выходила из области полиномиальной сложности. В лучшем случае временная сложность алгоритма = O(nlogn), в худшем случае - О(п3), где п - число вершин графа.
ПОСТАНОВКА ЗАДАЧИ
Постановка задачи записывается следующим образом: коммивояжеру необходимо посетить W городов, не заезжая в один и тот же город дважды, и вернуться в исходный пункт по маршруту с минимальной стоимостью. Имеем: дан полный
1 Таганрогский государственный радиотехнический университет, г. Таганрог.
граф G = (X, U), где 1X1 = п - множество вершин (города), \U\ = т - множество ребер (возможные пути между городами). Дана матрица смежности R(i, j), где /, j £ 1,2,..., п, - задающая стоимости путей из вершины xt в х} Требуется найти перестановку из элементов множества X такую, что целевая функция (ЦФ) [1, 2, 5, 8]
ЦФ(ф)-/г(ф(1), ф(и)) +
+ 2{Я(ф(г),ф(/ + 1))}-»тт. ц)
Целевой функцией является суммарная стоимость ребер гамильтонова цикла заданного графа. Решение ЗК будем рассматривать для графов с весами на ребрах. Отметим, что значение ЦФ не зависит в частном случае от выбора вершины начала маршрута. Фиксация вершины-старта может быть использована для сужения пространства поиска, которое в этом случае равно (п - 1)! Поэтому в общем случае результаты решения ЗК чувствительны к выбору начальных условий. Время работы известных алгоритмов ЗК, основанных на полном переборе или на построении дерева решений (методы ветвей и границ и др. [1, 7-10]), растет экспоненциально в зависимости от числа вершин графа. Эти алгоритмы способны решать ЗК для малого числа вершин (п = 50) за полиномиальное время. Поэтому для решения ЗК с п > 50 используются различные эвристики.
Приведем ряд эвристик для эффективного решения ЗК [7-10].
Эвристика 1 - это предпочтение более невыгодного маршрута более выгодному с определенной вероятностью.
Эвристика 2 - анализ 50% случайных маршрутов и 50% маршрутов, использующих знания о решаемой задаче.
Эвристика 3 - если путь оказывается тупиковым, производится случайный выбор вершины
или же выбор ближайшей вершины из числа не рассмотренных для включения в ЗК.
Эвристика 4 - Получение различных наборов альтернативных решений и применение бионических методов для повышения качества решений.
ОПИСАНИЕ АРХИТЕКТУРЫ ПОИСКА
И ОСНОВНЫХ БЛОКОВ АЛГОРИТМА
Структурная схема бионического алгоритма решения ЗК на основе моделей эволюций Ч. Дарвина, Ж. Ламарка, де Фриза, К. Поппера и М. Кимуры [6, 10] приведена на рисунке 1. В алгоритме начальная популяция конструируется тремя способами: Аь А2, А3. В случае А! популяция решений (заданных путей) формируется случайным образом. В случае А2 популяция решений получается путем неоднократного применения последовательного алгоритма. Формирование популяции А3 производится совместно случайным и направленным образом. Отметим, что лицо, принимающее решение (ЛПР) на основе блока эволюционной адаптации, может создавать любое число популяций другими способами. В архитектуру (рис. 1) введен блок локального поиска, который позволяет получать локальные экстремумы в ЗК. Все генетические операторы ориентированы на использовании знаний о решаемой задаче. Блок редукции позволяет оставлять размер популяции постоянным для каждой генерации. После формирования популяции к каждому ее элементу применяются различные генетические операторы кроссинговера (ОК), инверсии, мутации (ОМ), сегрегации, транслокации. В данной схеме порядок выполнения генетических операторов зависит от внешней среды, блока эволюционной адаптации и может иметь любой установленный порядок. Генетический оператор по аналогии с оператором алгоритма -это средство отображения одного множества на другое. Другими словами, это конструкция, представляющая один шаг из последовательности действий генетического алгоритма. Это языковая конструкция, позволяющая на основе различных преобразований альтернативных решений (родителей) или их частей создавать новые решения (потомки). Блок эволюционной адаптации задает хаотичный (случайный) порядок выполнения генетических операторов. Заметим, что перед началом работы алгоритма предварительно вычисляется верхняя оценка минимального пути. После выполнения генетических операторов их результаты сравниваются с
оценкой. При получении искомых результатов алгоритм заканчивает свою работу. Затем формируется новая популяция, и процесс продолжается аналогично далее. Возможен выход из каждого оператора в отдельности при получении локального оптимума. Блок редукции варьирует размер популяции. При попадании в локальный оптимум предлагается выполнять следующие эвристики.
- Изменять глубину "горизонта".
- Постоянство одной хромосомы: из всех маршрутов, имеющих одинаковую длину, только один остается неизменным, над всеми другими выполняются модифицированные генетические операторы.
- Использовать различные обратные связи для изменения параметров генетического поиска.
Отметим, что такие генетические операторы и эвристики работают не всё время, а только в ситуациях, когда однообразие в популяции достигает высокого уровня. Совместная эволюция Ч. Дарвина, Ж. Ламарка, де Фриза и К. Поппера регламентирует и управляет процессом генетического поиска.
В основном цикле бионического алгоритма промежуточная популяция решений не создавалась, получаемый потомок замещал наихудшее решение (хромосому) в популяции. Двумя основными параметрами при решении задачи о коммивояжере, оценивающими эвристический алгоритм, являются скорость сходимости и близость получаемого решения к оптимальному (если оно известно) или же к лучшим стандартным решениям (бенчмаркам), полученным с помощью других эвристик (если оптимум не известен).
Существуют два основных генетических представления возможного решения: кодирование решения в виде списка вершин (последовательность посещаемых городов) или кодирование решения как списка ребер, образующих гамиль-тонов цикл (список использованных путей из города в город) [2-6]. Кроме этого интерес представляет матричное кодирование задачи о коммивояжере. В матрице единицами кодируются переходы между генами в хромосоме. Тогда популяция хромосом будет состоять из набора аналогичных матриц. Такое кодирование ввиду большого числа нулей избыточное, хотя является наглядным и удобным для преобразований. Предложим вместо матриц использовать списки связности. Это позволит получить набор простых строительных блоков. На данном наборе на основе оператора сегрегации и оператора инверсии можно эффективно получать новых допустимых потомков.
Рис. 1. Структурная схема алгоритма решения задачи о коммивояжере
Для задачи о коммивояжере существуют специально разработанные генетические операторы (ГО), позволяющие гарантированно получать из родителей допустимых потомков [2-4, 6]. Опишем модифицированный комбинированный ОК.
1. Случайным образом выбрать стартовую вершину в первом родителе.
2. Текущий родитель - первый родитель.
3. Тело комбинированного ОК определить
так. Выбрать, какая из соседних вершин (соседними являются вершины, расположенные в хромосоме справа и слева от рассматриваемой) в анализируемом родителе ближе к текущей вершине. Ближайшая из соседних вершин, не вошедшая в путь задачи о коммивояжере, становится новой текущей вершиной. Если только одна из двух соседних вершин не вошла в путь задачи о коммивояжере, то она становится текущей. Если обе соседние вершины являются посещен-
ными (тупиковая ситуация), то выбрать ближайшую из числа еще не посещенных.
4. Рассмотреть несколько ветвей дерева решений на основе заданной глубины поиска.
5. Повторять тело комбинированного ОК, пока все вершины не будут посещены. Потомок формируется как последовательность посещаемых вершин.
6. Конец работы алгоритма.
Опишем построение генетических операторов с использованием метода дихотомии. Они реализуются за счет механизма перебора точек разрыва [6]. Приведем нечеткий алгоритм построения ОК дихотомии (ОКД).
1. Пусть заданы две родительские хромосомы длины Ь.
2. Делим хромосому (отрезок Ь) пополам (при нечетном размере хромосомы в любую часть берется большее ближайшее число генов).
3. Точка разрыва определяет точку ОК дихотомии.
4. По правилам построения одноточечного ОК получаем две новых хромосомы-потомка.
5. Каждую половину хромосомы-потомка снова делим на две части. Процесс продолжаем аналогично до тех пор, пока не будет получено заданное количество хромосом-потомков или алгоритм по методу дихотомии завершится. При получении нереальных решений (хромосом с повторяющимися генами) производится восстановление реальных решений (повторяющи
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.