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

Введение

Задача размещения вершин графа на линейке является NP-полной[1]. Это означает то, что на данный момент не существует универсального алгоритма, который мог бы находить решение за полиномиальное время.
Данная задача имеет теоретическую ценность теории алгоритмов. Ее ценность заключается в том, что если будет найдет «полиномиально быстрый» алгоритм решение данной задачи, то и любая другая задача из класса NP может быть решена также «быстро», а это в свою очередь докажет равенство классов и . До недавнего времени не существовало эффективного метода поиска решений NP-полных задач. С появлением эволюционного моделирование стало возможно находить квазиоптимальные решение за «приемлемое время».


Обоснования выбора генетического алгоритма:

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

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

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

(1)

Здесь — позиции элементов (вершин графа) в линейке, — расстояние между вершинами в линейке.

Общая суммарная длина ребер графа вычисляется формулой[2]:

(2)

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

Описание алгоритма

Генетические алгоритмы предназначены для решения задач оптимизации. В основе генетических алгоритмов лежит метод случайного направленного поиска. Для нашей задачи мы будем использовать классическую модель ГА, предложенную в 1975 г. Джоном Холландом (John Holland) в Мичиганском университете[3].

Схема алгоритма Холланда:

1. Сгенерировать исходную популяцию, состоящую из особей;
2. Оценить приспособленность хромосом в популяции на основе целевой функции ;
3. Выполнить операцию селекции;
4. Применить генетические операторы (мутация, скрещивание);
5. Сформировать новую популяцию;
6. Если критерий останова алгоритма не достигнут, перейти к шагу 2, иначе завершить работу;

Кодирование решений

Для начала нам нужно выбрать способ представления графа в виде хромосомы. Проанализировав различные способы кодирования, было выбрано кодирование перестановка: такой способ выбран по причине того, что нам нужно чтобы гены в хромосоме не повторялись. Приведем кодирование решений: имеется вектор , — количество вершин графа, как показано на рис. 1. Таким образом мы определили кодирование решений(хромосом).


Рис. 1. Кодировка хромосомы

Стратегия отбора

В качестве метода селекции был выбран турнирный отбор[4]. Данный метод можно описать следующим образом: из популяции, содержащей особей, выбирается случайным образом особей и лучшая особь записывается в промежуточную популяцию (между выбранными особями проводится турнир). Это операция повторяется раз. Затем особи в полученной промежуточной популяции скрещиваются (также случайным образом). С ростом параметра ужесточается отбор между особями, т.к. если у особи низкий показатель приспособленности, у нее нет шансов «завести потомство». Преимуществом данной стратегии является то, что она не требует дополнительных вычислений и упорядочивания особей в популяции по возрастанию приспособленности.

Оператор скрещивания

В качестве оператора скрещивания (кроссинговера) был выбран модифицированный одноточечный[5] кроссинговер. По принципу работы оператора похож на одноточечный кроссинговер Холанда но т. к. нам нельзя чтобы гены в хромосоме после скрещивания повторялись использовался модифицированный оператор кроссинговера. Например у нас имеются пара хромосом-родителей. Случайным образом выберем точку разреза , . После того как была выбрана точка разреза, мы переносим все гены до точки разреза из родителя 1 в первого потомка, а из родителя 2 во второго потомка. Для того чтобы закончить потомка нам нужно заполнить вторую часть хромосом; для этого мы начинаем переносить гены после точки разреза из родителя 1 во второго потомка, а из родителя 2 в первого, но когда мы встречаем повторяющийся ген в потомке мы его пропускаем, так двигаясь до самого конца генов родителей. Если у нас получается так, что гены потомка еще не до конца заполнены, то мы начинаем брать гены сначала родителя, т. е. делаем цикличный сдвиг хромосомы в лево. Проиллюстрируем все выше сказанное. Например у нас имеется точка разреза , хромосомы-родители рис. 2.


Рис. 2. Хромосомы-родители

Теперь применим к ним описанный оператор кроссинговера рис. 3.


Рис. 3. Хромосомы-потомки

Таким образом мы получили двух потомков со схожими значениями приспособленности.

Оператор мутации

Оператор мутации в генетических алгоритмах используется для того, что бы «выбивать» решения из локальных оптимумов, которые далеки от глобальных.
Для мутации генов использовался простой способ обмена двух генов. Например у нас есть такая хромосома рис. 4. Теперь выберем случайно два гена и поменяем их местами рис. 5.


Рис. 4. Хромосома до мутации


Рис. 5. Хромосома после мутации

Параметры генетического алгоритма

Параметры подбирались методом проб и ошибок: алгоритм запускался с разными значениями параметров. Значение параметра считается «хорошим» если решения получились «хорошими». Вполне приемлемые результаты получались со следующими параметрами:

• порог вероятности мутации 0,01-0,1;
• размер популяции 20-30;
• параметр (количество особей в турнире);

Заполнение исходной популяции выполнялось случайным образом.

Экспериментальные исследования

Отладка и тестирование проводились на ЭВМ типа IBM PC с процессором Intel Core i3 с ОЗУ-4Гб. Язык программирования C++. Были проведены исследования по определению эффективности предложенного генетического алгоритма. Проведенные экспериментальные исследования показали преимущество использования генетического алгоритма стандартным методам. Следующий пример показывает эффективность данного метода, на неком графе с . На рис. 6. случайная хромосома с общей суммарной длинной ребер .


Рис. 6. Случайная хромосома

После запуска алгоритма на 15 поколений общая суммарная длинна стала рис. 7.


Рис. 7. Лучшая хромосома на 15 поколении

Если перебрать все варианты размещения для данного графа легко убедится, что целевая функция графа принимает меньшее значения при таком размещении. На самом деле целевая функция для данного графа является многоэкстремальной и мы просто нашли один из ее экстремумов.

Заключение

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

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

1. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ.

2. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М.: ФИЗМАТЛИТ, 2003. — С. 264-275.

3. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. Michigan Press, 1975.

4. Цой Ю.Р. Стратегии отбора и формирования нового поколения [Электронный ресурс] / Ю. Цой. — Режим доступа: www.qai.narod.ru/GA/strategies.html

5. Панченко, Т. В. Генетические алгоритмы: учебно-методическое пособие / под ред. Ю. Ю. Тарасевича. — Астрахань: Издательский дом«Астраханский университет», 2007. — С. 20.