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

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

2012-06-20T09:47:42Z

217.66.152.140:

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex><ref>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)</ref> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot log\,m)</tex>)<ref>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). IEEE, 2007.</ref>. При этом оптимальный (не эволюционный) алгоритм работает за <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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

=== Литература ===
<references/>

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

2012-06-20T09:45:36Z

217.66.152.140:

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex><ref>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
Pages 1203-1210</ref> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot log\,m)</tex>)<ref>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), pages 245–250. IEEE, 2007.</ref>. При этом оптимальный (не эволюционный) алгоритм работает за <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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

=== Литература ===
<references/>

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

2012-06-20T09:37:57Z

217.66.152.140: /* Введение */

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex><ref>Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers</ref> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot log\,m)</tex>)<ref>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), pages 245–250. IEEE, 2007.</ref>. При этом оптимальный (не эволюционный) алгоритм работает за <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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

=== Литература ===
<references/>

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

2012-06-20T09:36:51Z

217.66.152.140:

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex> <ref>Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers</ref> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot log\,m)</tex>) <ref>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), pages 245–250. IEEE, 2007.</ref>. При этом оптимальный (не эволюционный) алгоритм работает за <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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

=== Литература ===
<references/>

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

2012-06-20T09:35:15Z

217.66.152.140: /* Введение */

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex> <ref>Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers</ref> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot log\,m)</tex>)<ref>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), pages 245–250. IEEE, 2007.<\ref>. При этом оптимальный (не эволюционный) алгоритм работает за <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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

=== Литература ===
<references />

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

2012-06-20T09:32:56Z

217.66.152.140:

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex> <ref>Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers</ref> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot 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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

=== Литература ===
<references />

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

2012-06-20T09:26:47Z

217.66.152.140:

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot 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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

=== Литература ===
1. [[ http://www.google.ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CEwQFjAA&url=http%3A%2F%2Fhalma.mpi-inf.mpg.de%2Fintranet%2Fag1%2Fag1publ.nsf%2F2a58943dc07cf5f2c125729f00364aec%2F%255C%24FILE%2FDoerrJohannsen_2007_AdjacencyListMatchings-AnIdealGenotypeForCycleCovers.pdf&ei=7ZfhT834OqmEmQWTwfHaAw&usg=AFQjCNGEN04hWu3jSLTiYX_DTmpJtqJI_g&sig2=Rm0Y8vZC4NKNn3Sf7X-Ang | Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers ]]

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

2012-06-20T09:21:44Z

217.66.152.140:

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot 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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

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

2012-06-20T09:17:52Z

217.66.152.140:

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot 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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;

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

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

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

2012-06-20T09:16:22Z

217.66.152.140: /* Введение */

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m \cdot log \, m )</tex> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot 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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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> для стратегии, ориентированной на пары.

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

2012-06-20T09:15:45Z

217.66.152.140: /* Введение */

=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <tex>O(m*log(m))</tex> (до недавнего времени лучшим считался результат <tex>O(m^2 \cdot 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>. Как их выбрать описано в
[[Эволюционные алгоритмы поиска эйлерова цикла в графе#Выбор вершин для мутации|следующем разделе]].
Происходит она так:
* если <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> для стратегии, ориентированной на пары.