Эволюционные алгоритмы поиска эйлерова цикла в графе

2012-06-19T22:13:14Z

188.134.48.45: /* Операция мутации */

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m*log(m))</tex> (до недавнего времени лучшим считался результат <tex>O(m^2*log(m))</tex>). При этом оптимальный (не эволюционный) алгоритм работает за <tex>O(m)</tex>. Здесь и далее <tex>m</tex> — количество ребер в графе.

Сначала опишем представление графа, затем то, как устроена фитнес функция и операция мутации, а потом адаптируем RLS и (1+1) EA стратегии для нашего случая.

=== Постановка задачи ===
{{Определение
|definition='''Эйлеров цикл в графе''' — это цикл, проходящий по всем рёбрам графа ровно по одному разу.
}}
Задача — для заданного графа найти такой цикл. Заметим, что это возможно тогда и только тогда, когда граф связный и степень каждой его вершины четна (для неориентированного графа).

=== Обзор методов ===
====Перестановка ребер ====
Пусть для графа <tex>G</tex> задан набор всех его ребер <tex>(e_1, e_2, \dots e_m)</tex>. На каждом шаге два случайно выбранных ребра меняются местами. Фитнес функция — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное от количества ребер время.
====Jump-оператор====
Jump-оператор работает следующим образом. Для набора ребер <tex>(e_1, e_2, \dots e_m)</tex> оператор <tex>jump(i,j)</tex> передвигает <tex>i</tex>-й элемент на позицию <tex>j</tex> и циклически сдвигает ребра между позициями <tex>i</tex> и <tex>j</tex> влево (если <tex>i > j</tex> то вправо) . Таким образом, набор <tex>(e_1, e_2, \dots e_m)</tex> превратится в <tex>(e_1, e_2, \dots e_{i-1}, e_{i+1}, \dots e_j, e_i, e_{j+1}, \dots e_m)</tex>. Алгоритм с использованием jump-оператора работает за <tex>O(m^5)</tex>, где <tex>m</tex> — количество ребер в графе.
====Улучшенный jump-оператор====
Лучших результатов можно достичь, если использовать только операции вида <tex>jump(i, 1)</tex>. Тогда время работы алгоритма будет <tex>O(m^3)</tex>.
=== Алгоритм ===
==== Представление графа ====
Пусть <tex>G</tex> — неориентированный связный граф, <tex>V</tex> — множество его вершин, <tex>E</tex> — множество ребер; всего вершин <tex>n</tex>, а ребер <tex>m</tex> . Будем хранить ребра в виде списков смежности. Пусть <tex>L_v</tex> — множество вершин, соединенных с <tex>v</tex> ребром, <tex>L</tex> — множество всех <tex>L_v</tex>. Для каждой вершины <tex>v</tex> введем также множество <tex>M_v</tex>, хранящее в себе неупорядоченные пары вершин из <tex>L_v</tex>. Обозначим через <tex>M</tex> множество всех <tex>M_v</tex>. Таким образом, если для всех вершин <tex>v</tex> вершины из <tex>L_v</tex> разбиты на пары в <tex>M_v</tex>, то с точностью до первого ребра на <tex>G</tex> задан порядок обхода: пара <tex>(u,w)</tex> в <tex>L_v</tex> означает, что придя из <tex>u</tex> далее нужно идти в <tex>w</tex> (или наоборот).

==== Фитнес функция ====
Фитнес функция для эволюционного алгоритма поиска эйлерова цикла в графе выглядит так:

<tex>f(M) = m - |M| + k</tex>, где

<tex>m</tex> — количество ребер в графе;

<tex>|M|</tex> — размер множества <tex>M</tex>;

<tex>k</tex> — количество путей в <tex>M</tex>.

==== Операция мутации ====
Операция мутации вводится для двух вершин <tex>u</tex> и <tex>w</tex> из <tex>L_v</tex>. Как их выбрать описано в [http://neerc.ifmo.ru/wiki/index.php?title=%D0%AD%D0%B2%D0%BE%D0%BB%D1%8E%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D1%8D%D0%B9%D0%BB%D0%B5%D1%80%D0%BE%D0%B2%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%B2_%D0%B3%D1%80%D0%B0%D1%84%D0%B5#.D0.92.D1.8B.D0.B1.D0.BE.D1.80_.D0.B2.D0.B5.D1.80.D1.88.D0.B8.D0.BD_.D0.B4.D0.BB.D1.8F_.D0.BC.D1.83.D1.82.D0.B0.D1.86.D0.B8.D0.B8 следующем разделе]. Происходит она так:
* если <tex>u=w</tex>, то ничего не делаем;
* если для <tex>u</tex> и для <tex>w</tex> нет пары, то добавляем к <tex>M_v</tex> пару <tex>(u,w)</tex>;
* если <tex>u</tex> и <tex>w</tex> уже содержатся в <tex>M_v</tex> как пара, то удалим ее;
* если <tex>u</tex> уже добавлена в паре с некоторой вершиной <tex>p</tex>, а <tex>w</tex> не имеет пары, то удалим <tex>(u,p)</tex> из <tex>M_v</tex> и добавим <tex>(u,w)</tex>;
* если <tex>w</tex> уже добавлена в паре с некоторой вершиной <tex>p</tex>, а <tex>u</tex> не имеет пары, то удалим <tex>(w,p)</tex> из <tex>M_v</tex> и добавим <tex>(u,w)</tex>;
* если <tex>u</tex> уже добавлена в паре с некоторой вершиной <tex>p</tex>, а <tex>w</tex> уже добавлена в паре с некоторой <tex>k</tex>, то удалим <tex>(u,p)</tex> и <tex>(w,k)</tex> из <tex>M_v</tex> и добавим <tex>(u,w)</tex> и <tex>(p,k)</tex>;

==== Выбор вершин для мутации ====
Пусть <tex>d(v)</tex> — степень вершины <tex>v</tex> (количество ребер, которые из нее выходят), <tex>d(G)</tex> — средняя степень среди вершин <tex>G</tex>, <tex>\Delta G</tex> — максимальная степень среди вершин <tex>G</tex>, а <tex>\delta d(G) = \frac{1} {2m} \sum_{v \in V}d(v)^2</tex>.
Есть три способа выбрать две вершины для мутации.

'''Ориентированный на вершины'''

Сначала случайно выбираем <tex>v</tex> из <tex>V</tex>. Затем случайно и независимо выбираем <tex>u</tex> и <tex>w</tex> из <tex>L_v</tex>. Вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению:

<tex>p = \frac{1} {d(v)^2n} = \frac{d(G)} {2d(v)^2m} \ge \frac{d(G)} {2 \Delta (G)^2m}</tex>

'''Ориентированный на ребра'''

Выбираем случайно вершину <tex>u</tex> из всех <tex>2m</tex> вершин во всех списках <tex>L</tex>. Пусть она оказалась в <tex>L_v</tex>. Далее случайно выбираем <tex>w</tex> из <tex>L_v</tex>. Вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению:

<tex>p = \frac{1} {2d(v)m} \ge \frac{1} {2 \Delta (G)m}</tex>

'''Ориентированный на пары вершин'''

Выбираем случайно пару <tex>(u,w)</tex> из всех пар для всех <tex>2m</tex> вершин во всех списках в <tex>L</tex>. Пусть обе вершины присутствуют в <tex>L_v</tex>. Тогда вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению:

<tex>p = \frac{1} {2\delta d(G)m} </tex>

Эти три случая эквивалентны в случае разреженного графа (в котором <tex>d(G) = \delta d(G) = \Delta (G)</tex>). В общем случае <tex>d(G) \le \delta d(G) \le \Delta (G)</tex> и лучший результат достигается для способа, который ориентирован на вершины.

==== Стратегии RLS и (1+1) EA ====
Эволюционный алгоритм поиска эйлерова цикла в графе работает следующим образом. Размер популяции возьмем равным одному; представление графа, операция мутации и фитнес функция будут такими, как описано выше. Начальное заполнение множества <tex>M</tex> можно сделать случаным образом или оставить пустым, на время работы алгоритма это не влияет.

Стратегия Randomized local search будет работать так: на каждом шаге к текущему индивиду (он один, так как в популяции только одна особь) применяется операция мутации. Если полученный индивид лучше текущего, он выбирается для дальнейшей работы, в противном случае ничего не происходит. Алгоритм работает до тех пор, пока фитнес функция не минимизирована.

Псевдокод:
Initialize(M)
while (f(M) > 1) do
M′:=φ(M)
if f(M′) ≤ f(M)
then M := M′

Стратегия (1+1) evolutionary algorithm в классическом варианте применяет операцию мутации к каждому биту <tex>n</tex>-битной строки с вероятностью <tex> \frac{1} {n}</tex>. В текущем алгоритме применять изменения можно только последовательно, поэтому просто делают операцию мутации несколько раз.

Псевдокод:
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 верны следующие оценки времени работы алгоритма:

<tex>O(\frac{\Delta(G)^2} {d(G)}*m*log(m))</tex> для стратегии, ориентированной на вершины;

<tex>O(\Delta(G)*m*log(m))</tex> для стратегии, ориентированной на ребра;

<tex>O(\delta d(G)*m*log(m))</tex> для стратегии, ориентированной на пары.

Викиконспекты - Вклад участника [ru]

Эволюционные алгоритмы поиска эйлерова цикла в графе