Эволюционные алгоритмы поиска эйлерова цикла в графе
Введение
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого [1] (до недавнего времени лучшим считался результат )[2]. При этом оптимальный (не эволюционный) алгоритм работает за . Здесь и далее — количество ребер в графе. Время работы эволюционных алгоритмов измеряется в количестве вычислений функции приспособленности, а время оптимального алгоритма — в итерациях.
После обзора предыдущих методов опишем представление графа, затем то, как устроена функция приспособленности и операция мутации, а потом адаптируем RLS и (1+1) EA стратегии для нашего случая.
Постановка задачи
| Определение: |
| Эйлеров цикл в графе — это цикл, проходящий по всем рёбрам графа ровно по одному разу. |
Задача — для заданного графа найти такой цикл. Здесь и далее рассматриваем неориентированный связный граф. Заметим, что это возможно тогда и только тогда, когда граф связный и степень каждой его вершины четна (для неориентированного графа).
Обзор методов
Перестановка ребер
Пусть для графа задан набор всех его ребер . На каждом шаге два случайно выбранных ребра меняются местами. Функция приспособленности — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное от количества ребер время.
Jump-оператор
Jump-оператор работает следующим образом. Для набора ребер оператор передвигает -й элемент на позицию и циклически сдвигает ребра между позициями и влево (если то вправо) . Таким образом, набор превратится в . Алгоритм с использованием jump-оператора работает за , где — количество ребер в графе.
Улучшенный jump-оператор
Лучших результатов можно достичь, если использовать только операции вида . Тогда время работы алгоритма будет .
Алгоритм
Представление графа
Пусть — неориентированный связный граф, — множество его вершин, — множество ребер; всего вершин , а ребер . Будем хранить ребра в виде списков смежности. Пусть — множество вершин, соединенных с ребром, — множество всех . Для каждой вершины введем также множество , хранящее в себе неупорядоченные пары вершин из . Обозначим через множество всех . Таким образом, если для всех вершин вершины из разбиты на пары в , то с точностью до первого ребра на задан порядок обхода: пара в означает, что придя из далее нужно идти в (или наоборот).
Рассмотрим пример.
Эйлерову циклу, проходящему по ребрам (2, 6, 7, 4, 3, 8, 5, 1) будет соответстовать множество такого вида:
Функция приспособленности
Функция приспособленности для эволюционного алгоритма поиска эйлерова цикла в графе выглядит так:
, где
— количество ребер в графе;
— размер множества ;
— количество путей (в том числе циклов) в .
Операция мутации
Операция мутации вводится для двух вершин и из . Как их выбрать описано в следующем разделе. Происходит она так:
- если , то ничего не делаем;
- если для и для нет пары, то добавляем к пару ;
- если и уже содержатся в как пара, то удалим ее;
- если уже добавлена в паре с некоторой вершиной , а не имеет пары, то удалим из и добавим ;
- если уже добавлена в паре с некоторой вершиной , а не имеет пары, то удалим из и добавим ;
- если уже добавлена в паре с некоторой вершиной , а уже добавлена в паре с некоторой , то удалим и из и добавим и ;
Выбор вершин для мутации
Пусть — степень вершины (количество ребер, которые из нее выходят), — средняя степень среди вершин , — максимальная степень среди вершин , а . Есть три способа выбрать две вершины для мутации.
Ориентированный на вершины
Сначала случайно выбираем из . Затем случайно и независимо выбираем и из . Вероятность выбрать пару в удовлетворяет соотношению:
Ориентированный на ребра
Выбираем случайно вершину из всех вершин во всех списках . Пусть она оказалась в . Далее случайно выбираем из . Вероятность выбрать пару в удовлетворяет соотношению:
Ориентированный на пары вершин
Выбираем случайно пару из всех пар для всех вершин во всех списках в . Пусть обе вершины присутствуют в . Тогда вероятность выбрать пару в удовлетворяет соотношению:
Эти три случая эквивалентны в случае разреженного графа (в котором ). В общем случае и лучший результат достигается для способа, который ориентирован на вершины.
Стратегии RLS и (1+1) EA
Эволюционный алгоритм поиска эйлерова цикла в графе работает следующим образом. Размер популяции возьмем равным одному; представление графа, операция мутации и функция приспособленности будут такими, как описано выше. Начальное заполнение множества можно сделать случаным образом или оставить пустым, на время работы алгоритма это не влияет.
Стратегия Randomized local search будет работать так: на каждом шаге к текущему индивиду (он один, так как в популяции только одна особь) применяется операция мутации. Если полученный индивид лучше текущего, он выбирается для дальнейшей работы, в противном случае ничего не происходит. Алгоритм работает до тех пор, пока функция приспособленности не минимизирована.
Псевдокод:
Initialize(M)
while (f(M) > 1) do
M′:=φ(M)
if f(M′) ≤ f(M)
then M := M′
Стратегия (1+1) evolutionary algorithm в классическом варианте применяет операцию мутации к каждому биту -битной строки с вероятностью . В текущем алгоритме применять изменения можно только последовательно, поэтому просто делают операцию мутации несколько раз.
Псевдокод:
Initialize(M)
while (f(M) > 1) do
M′ :=M
for i := 0 to k do //k — некоторое число
M′ := φ(M′)
if f(M′) ≤ f(M)
then M := M′
Время работы алгоритма
Докажем сначала следующее утверждение.
| Лемма: |
Пусть . Тогда множеству с функцией приспособленности соответствует путей. |
| Доказательство: |
| В множестве каждая вершина, не имеющая пары, является крайней в некотором пути. Таким образом, каждому отдельному пути в соответсвует пара вершин, поэтому |
Для RLS и (1+1) EA верны следующие оценки времени работы алгоритма:
для стратегии, ориентированной на вершины;
для стратегии, ориентированной на ребра;
для стратегии, ориентированной на пары.
Литература
- ↑ Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers. Proceeding GECCO '07 Proceedings of the 9th annual conference on Genetic and evolutionary computation, 1203-1210 (2007)
- ↑ B. Doerr, C. Klein, and T. Storch. Faster evolutionary algorithms by superior graph representation. In Proc. of the 2007 IEEE Symposium on Foundations of Computational Intelligence (FOCI), 245–250 (2007).
