Лабораторная работа №7

«Генетические алгоритмы. Задача коммивояжера».

 

Цель работы:Научиться использовать генетические алгоритмы для решения конкретных задач на примере задачи коммивояжера.

 

Теоретические сведения:

Задача коммивояжера — это классический пример тестовой задачи для методов ис­кусственного интеллекта и компьютерных наук вообще. Пространство состояний этой задачи для N городов вклю­чает N! возможных состояний. Формулировка задачи достаточно проста: коммивояжеру требуется посетить N городов. Для каждой пары городов по маршруту сле­дования установлена стоимость (например расстояние). Требуется найти путь минимальной стоимости, который начинается из некоторого города, обеспечивает посещение остальных городов ровно по одному разу и возврат в точку отправления.

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

Как можно решить эту задачу с помощью генетического алгоритма? Во-первых, можно выбрать представление для маршрута посещения городов, а также подобрать ис­пользуемые генетические операторы. В то же время выбор критерия качества в данном случае достаточно прост - требуется оценить лишь длину пути. После этого маршруты можно упорядочить по длине — чем короче, тем лучше.

Рассмотрим несколько очевидных представлений, которые имеют достаточно сложные последствия. Предположим, необходимо посетить девять городов 1, 2, ..., 9. Тогда путь можно представить упорядоченным списком из девяти целых. Представим порядковый номер каждого города строкой из четырех битов: 0001, 0010,..., 1001. Тогда выражение

0001 0010 0011 0100 0101 0110 0111 1000 1001

представляет последовательность посещения городов по возрастанию их порядковых номеров. Пробелы в этом выражении поставлены только для простоты восприятия. Какие генетические операторы можно использовать для решения этой задачи? Скрещивание однозначно не подходит, поскольку получаемая в результате строка, скорее всего, не будет представлять собой путь, при котором каждый город посещается только один раз. Действительно, при скрещивании некоторые города выпадут из последовательности, другие встретятся в ней дважды. Что можно сказать о мутации? Предположим, что крайний слева бит в обозначении шестого города 0110 изменится на 1. Тогда полученное число 1110 будет соответствовать порядковому номеру 14, который не входит в допустимый перечень городов. Инвертирование городов в выражении пути в данном случае является допустимой операцией, однако достаточно ли ее для получения необходимого решения? Одним из способов поиска минимального пути является генерирование и оценка всех возможных перестановок из N элементов в списке городов. Поэтому генетические операторы должны обеспечить возможность получения этих перестановок.

Задачу коммивояжера можно решить и по-другому: проигнорировать битовое представление и присвоить городам обычные порядковые номера 1,2,..., 9. Путь между этими городами будет представлять собой некоторую последовательность девяти цифр, а соответствующие генетические операторы позволят формировать новые пути. В этом случае мутация как слу чайньй обмен двух городов в маршруте будет допустимой операцией, но скрещивание по-прежнему окажется бесполезным. Обмен фрагментов маршрута на другие фрагменты того же пути либо любой оператор, меняющий местами номера городов маршрута (без удаления, добавления или дублирования городов), окажется достаточно эффективным. Однако при таких подходах невозможно обеспечить сочетание лучших родительских свойств в потомке, поскольку для этого требуется формировать его на основе двух родителей.

Многие исследователи разработали операторы скрещивания, устраняющие эти проблемы и позволяющие работать с упорядоченным списком посещаемых городов. Например, в работе [Davis, 1985] определен оператор, получивший название упорядоченного скрещивания (order crossover). Допустим, имеется девять городов 1,2,..., 9, порядок следования которых представляет очередность их посещения.

В процессе упорядоченного скрещивания потомок строится путем выбора подпоследовательности городов в пути одного из родителей. В нем также сохраняется относительный порядок городов другого родителя. Сначала выбираются две точки сечения, обозначенные символом |, которые случайным образом устанавливаются в одних и тех же позициях каждого из родителей. Местоположение точек сечения выбирается случайным образом, однако для каждого из родителей эти точки совпадают. Например, если для двух родителей p1 и р2 точки сечения располагаются после 3-го и 7-го городов

р1 = (192|4657|83),

р2 = (459|1876|23),

то два потомка cl и с2 получаются следующим образом. Сначала для каждого из потомков копируются фрагменты строк родителей, расположенные между точками сечения.

с1=(ххх|4657|хх),

с2=(ххх|1876|хх).

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

234591876.

Поскольку города 4, 6, 5 и 7 не учитываются (они уже входят в состав первого потом­ка), получается укороченный ряд 2, 3, 9, 1, 8, который и подставляется в cl с сохранени­ем порядка следования этих городов в р2:

с1 = (239|4657|18).

Аналогично получим второй потомок

с2=(392|1876| 45).

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

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

с1 =(23914657118)

после инвертирования его средней части примет вид

с1=(239|7564|18).

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