Уточнение решений задачи коммивояжера генетическими мутациями

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

У

Уточнение решений задачи коммивояжера генетическими мутациями

А. М. Долженко

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

Ключевые слова: задача коммивояжера; жадный алгоритм; генетический алгоритм; мутации.

Введение© Долженко А. М., Бутрина Е. Г., 2013

В зависимости от выбранного алгоритма и времени, отводимого на выполнение задачи, численные методы могут иметь низкую точность. Поэтому следует разрабатывать алгоритмы для уточнения полученных с их помощью решений. Одно из направлений такого уточнения - применение генетических преобразований над полученными результатами. Обзор литературы [2, 4, 5, 8, 9] показал, что подобный подход к оптимизации не используется на практике. В источниках [1, 3, 6, 11] можно встретить только обратный метод - уточнение генетического алгоритма жадным. Считаем, что эксперименты по применению методов уточнения позволят:

- выявить причины неточностей решений численных методов;

- установить правила, по которым требуется проводить уточнения;

- определить средний процент уменьшения (или увеличения, в зависимости от типа задачи) значения целевой функции после уточнения.

1. Постановка задачи

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

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

Общая постановка задачи коммивояжера. Имеется n городов, известны расстояния между этими городами. Требуется определить маршрут движения, при котором каждый из городов войдет в маршрут только один раз и при этом будет пройдено минимально возможное расстояние.

2. Причины неточностей численных решений

Покажем решение для симметричной незамкнутой задачи коммивояжера.

Сгенерируем случайным образом 20 точек на координатной плоскости. Рассмотрим решение, полученное жадным методом (рис. 1).

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

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

Рис. 1. Решение задачи коммивояжера жадным алгоритмом

Практическое применение численных методов показывает, что могут появиться решения, имеющие пересечения участков, расположенных далеко друг от друга по маршруту следования (рис. 2).

Рис. 2. Решения, имеющие пересечения участков, расположенных далеко друг от друга

Очевидно, что применение модификаций на соседних участках не избавит от подобного рода "отклонений" от оптимального маршрута. Здесь же требуется не поменять местами узлы, а переписать в обратном порядке целый участок цепи - точки, находящиеся на "петле", образованной пересечением отрезков. Например, на рис. 2 имеем начальное решение

1-7-3-12-19-2-18-10-14-13-11-15-20-6-8-4-17-9-16-5.

Очевидно, что более короткому маршруту будет соответствовать маршрут

1-7-4-8-6-20-15-11-13-14-10-18-2-19-12-3-17-9-16-5.

Как видно, для оптимизации маршрута, точки, расположенные на позициях с 3 по 16, переставлены в обратном порядке.

Проведем анализ решений, получаемых кластерным методом. Применение этого алгоритма состоит в объединении объектов в достаточно большие кластеры, используя расстояние между объектами [7]. Проведем разбиение на кластеры точек, представленных на рис. 1. Решим задачу нахождения оптимального маршрута внутри каждого кластера (рис.3).

Рис. 3. Решение задачи коммивояжера внутри каждого кластера

Объединим полученные решения (рис. 4).

Рис. 4. Решение задачи коммивояжера кластерным методом

Как видно, при связи кластеров образуются ребра очень большой длины (A,B,C на рис. 4). Это связано с неправильным начальным делением на группы: принадлежность точки к той или иной группе определяется по среднему расстоянию до геометрического центра группы без учета направления и характера движения [7]. В этом случае будем пользоваться тем же способом, что и в жадных решениях - выполнять перестановки близлежащих узлов. Это позволит перегруппировать точки, находящиеся в местах соединения кластеров, и сделать переходы между ними более "мягкими".

3. Модификация численных решений

Адаптация генетического алгоритма для решаемой задачи

Решение на рис. 1 представлено в виде последовательности чисел, соответствующих номерам городов:

1-2-7-16-12-19-11-13-3-5-6-10-15-9-17-4-20-14-18-8.

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

В задаче коммивояжера имеется особенность, связанная с начальным формированием особей, - все хромосомы одной особи различны. Это ограничение накладывается условием "каждый из городов войдет в маршрут только один раз".

Количество особей в начальной популяции выбирается в зависимости от имеющихся вычислительных ресурсов и числа n. В различных ситуациях это число может быть от 10n до 20n в зависимости от общего допустимого числа комбинаций. Шаг выполнения классического генетического алгоритма состоит из трех стадий [5, 9].

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

2. Скрещивание особей путем кроссовера [5,9]. Данная стадия алгоритма не может быть применена при решении задачи коммивояжера, так как это приведет к потере некоторых хромосом и невыполнению условия их уникальности в особи.

Рассмотрим пример такого скрещивания.

Особь 1:

1-2-7-16-12-19-11-13-3-5-6-10-15-9-17-4-20-14-18-8

Особь 2:

1-10-13-5-4-19-17-14-20-3-8-7-6-16-12-11-2-15-18-9

Одна из дочерних особей (при обмене, например, 3, 6 и 10 хромосом) может выглядеть следующим образом:

1-10-7-5-4-19-17-14-20-5-8-7-6-16-12-11-2-15-18-9.

Как можно заметить, в полученной особи отсутствуют хромосомы с номерами 13 и 3, а хромосомы с номерами 5 и 7 присутствуют 2 раза. Соответственно, два города будут пройдены дважды, а в два коммивояжер не попадет. Повторное применение подобных операций приведет к еще большему изменению начального "генофонда" особей.

3. Мутация - применение оператора мутации (чаще всего инвертирование произвольно выбранного бита в особи популяции), необходимого для выхода популяции из локального экстремума [5, 9]. Такая операция применяется для защиты от преждевременной сходимости, когда потомство популяции будет формироваться на основе родителей, сгенерированных в области локального максимума (а не минимума, или, наоборот, в зависимости от критерия оптимизации).

В рассматриваемой задаче операция мутации также приведет к потере и дублированию хромосом. Рассмотрим на примере.

Особь до мутации:

1-2-7-16-12-19-11-13-3-5-6-10-15-9-17-4-20-14-18-8

Особь после мутации 17-й хромосомы:

1-2-7-16-12-19-10-13-3-5-6-10-15-9-17-4-21-14-18-8

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

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

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

В нашем случае мутация должна проводиться путем случайной перестановки хромосом внутри особи.

Особь до мутации:

1-2-7-16-12-19-11-13-3-5-6-10-15-9-17-4-20-14-18-8

Особь после мутации:

1-2-7-16-12-19-11-13-3-5-6-20-15-9-17-4-10-14-18-8

Как можно наблюдать на примере, потери хромосом в таком случае не происходит.

Процесс эволюции популяций может продолжаться до бесконечности. Поэтому для любой задачи, использующей генетический алгоритм, следует ввести условие останова. Критерием останова может служить [5, 9]:

1) заданное количество поколений (проводить операцию отбора и мутации заданное число раз - от 2n до 10n, в зависимости от решаемой задачи);

2) время выполнения (прекращать выполнение задачи по истечении некоторого интервала времени - от 1 до 20 с);

3) схождение популяции (в случае, когда можно точно установить, что найденное значение оптимальное или соответствует оптимальному с отклонением 5-10 %).

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

Итоговым решением является наиболее приспособленная популяция.

Порядок проведения мутаций

Вернемся к примеру на рис. 1. Рассмотрим несколько направлений, в которых следует выполнять генетические преобразования.

1. Видим, что на маршруте движения 10-15-9-17-4 образуется две петли, свидетельствующие о неоптимальности предложенного решения. Очевидно, что путь 10-9-17-15-4 короче полученного.

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

Так, в рассматриваемом примере поменяем местами хромосомы 9 и 17, которые следуют одна за другой. Получим решение с одной точкой пересечения, представленное на рис. 5.

Теперь меняем хромосомы 9 и 15, отстоящие друг от друга на одну позицию. Получаем решение без пересечений (рис. 6, область I). Практическое применение мутаций, направленных на устранение пересечений, показывает, что значение целевой функции при этом уменьшается на 2.5-4%.

2. Проведем избавление от ребер большой длины, полученных на различных этапах жадных решений или при объединении кластеров. Подвергнув мутации решение на рис. 4 путем перестановки хромосом 1 и 2, получим решение, представленное на рис. 6 (область II).

Рис. 5. Выполнение одной модификации над численным решением

задача коммивояжер мутация численный

Рис. 6. Выполнение нескольких модификации над численным решением

Проведя мутации на участке 12-19-11-13-3, получим еще более короткий маршрут (рис. 6, область III).

После преобразований 1 и 2 значение целевой функции уменьшается на 4-6%.

3. Теперь приведем алгоритм уточнения решения, полученного на рис. 2. Для выбранного случайным образом отрезка ломаной пути определяем, пересекает его какой-либо другой отрезок или нет. Для этого находим координаты пересечения прямых, которым принадлежат рассматриваемые отрезки (отрезки задаются координатами вершин (х1; у1) и (х2; у2) - координаты вершин первого отрезка, (х3; у3) и (х4; у4) - координаты вершин второго отрезка):

,(3.1)

. (3.2)

Для того чтобы отрезки пересекались необ-ходимо и достаточно выполнение следующих условий [10]:

(((x1?x)&(x2?x) & (x3?x) & (x4?x))||((y1?y) & &(y2?y) & (y3?y) & (y4?y))), (3.3)

k1=k2, (3.4)

где k1 и k2 - тангенсы угла наклона отрезков к положительному направлению оси ОХ, определяемые по формулам

k1:=(x2-x1)/(y2-y1), (3.5)

k2:=(x4-x3)/(y4-y3). (3.6)

Если указанные условия выполняются, то переставляем в обратном порядке участок пути, расположенный между вершинами с координатами (х1 ; у1) и (х4; у4).

Результирующий алгоритм

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

Шаг 1. Введем значение n - размер особи.

Шаг 2. Введем в виде матрицы А(n x n) расстояния между узлами.

Шаг 3. Определим размер популяции - P.

Шаг 4. Определим число поколений - К.

Шаг 5. Составим начальную популяцию особей Х1 … ХР из решений, полученных численным методом. Если применялся только один стохастический алгоритм, то полученное решение дублируется Р раз и начальная популяция будет состоять из одинаковых особей - клонов. При этом особи популяции соответствуют обязательному условию: каждая хромосома H1 … Hn, входящая в состав особи, не должна дублироваться, т. е. все хромосомы должны присутствовать в особи в любом порядке, но только один раз.

Шаг 6. Считаем целевые функции С1 … СР для всех особей популяции. Целевой функцией задачи коммивояжера будет функция суммирования расстояний между узлами с номерами H1H2, H2H3, … , Hn-1Hn, соответствующими хромосомам в составе особи. Запоминаем минимальное значение целевой функции - Min и хромосому Х, соответствующую этому значению.

Выполним K раз шаги 7-11 для каждой особи Х1 … ХР популяции.

Шаг 7. Сгенерируем случайным образом два целых положительных числа б и в, такие что 1?б<в?n и в-б<3.

Шаг 8. Если в-б=2, тогда поменяем местами хромосомы Hб и Hв, входящие в состав особи. Переходим на шаг 11.

Шаг 9. Если в-б=1, то определим, пересекается ли отрезок HбHв с каким-либо отрезком HiHj, входящим в состав ломаной H1H2H3…Hn-1Hn. Если да, то переставим в обратном порядке хромосомы с номерами от в до i включительно, если в < i, или от j до б включительно в противном случае.

Шаг 10. Если отрезок HбHв не пересекает другие звенья пути, то меняем местами хромосомы Hб и Hв.

Шаг 11. Считаем целевые функции полученных после мутаций особей популяции. Запоминаем минимальное из всех рассчитанных значений - Min и хромосому Х, соответствующую этому значению.

Шаг 12. Завершаем цикл.

Решением поставленной задачи будет являться особь Х, имеющая значение целевой функции Min.

Заключение

Численные методы дают решение, не всегда близкое к оптимальному, а поэтому полученные значения требуют уточнения. Один из способов, позволяющих приблизить полученное значение к оптимальному, - применение генетических мутаций над результирующим набором параметров. Случайные перестановки хромосом результирующего вектора позволят "вытолкнуть" решение из локального минимума и дать более точный результат. Данная статья содержит результат сравнений решений задачи коммивояжера, полученных двумя методами ("Жадным" и "Кластерным"). Приводится алгоритм применения генетических мутаций для уточнения решений задачи коммивояжера, полученных численными методами.

Список литературы

Алгулиев Р.М., Алыгулиев Р.М. Генетический подход к оптимальному назначению заданий в распределенной системе // Искусственный интеллект. 2004. Вып. 4. С.79-88.

Батищев Д.И. Генетические алгоритмы решения экстремальных задач. Нижний Новгород: Нижегород. гос. ун-т. 1995. 62 c.

Витковски Т., Эльзвай С., Антчак А. Исследование переменных и параметров генетического алгоритма для планирования производства // Проблемы управления и информатики. 2004. Вып. 1. С.136-144.

Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков: ОСНОВА. 1997. 112 с.

Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: ФИЗМАТЛИТ. 2006. 320 с.

Доронин В.А. Применение генетического алгоритма для оптимизации складских запасов // Материалы IХ науч.-техн. семинара. М.: МИЭМ. 2006. С.117-122.

Котович Н.В. Алгоритмы кластеризации образов символов // Тр. ИСА РАН. 2008. Т. 38.

Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование // Известия РАН. Сер. ТиСУ. 2002. Вып.1. С.127-137.

Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие / под ред. Ю.Ю.Тарасевича. Астрахань: Изд. дом "Астраханский университет". 2007. 87 с.

Просветов Г.И. Линейная алгебра и аналитическая геометрия. Задачи и решения. 2-е изд., доп. М.: Альфа-Пресс. 2009. 208 с.

Солодовников И.В., Доронин В.А. Генетический алгоритм для поиска логических закономерностей в данных // Информационные технологии. М.: "Новые технологии". 2005. Вып. 7. С. 11-18.

Размещено на Allbest.ru