Изменения
→Введение
=== Введение ===
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <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).</ref>. При этом оптимальный (не эволюционный) [[Алгоритм построения Эйлерова цикла|алгоритм]] работает за <tex>O(m)</tex>. Здесь и далее <tex>m</tex> — количество ребер в графе. Время работы эволюционных алгоритмов измеряется в количестве вычислений функции приспособленности, а время оптимального алгоритма — в итерацияхэлементарных операциях.
После обзора предыдущих методов опишем представление графа, затем то, как устроена функция приспособленности и операция мутации, а потом адаптируем RLS и (1+1) EA стратегии для нашего случая.
=== Обзор методов ===
====Перестановка ребер ====
Пусть для графа <tex>G</tex> задан набор всех его ребер <tex>(e_1, e_2, \dots e_m)</tex>. На каждом шаге два случайно выбранных ребра меняются местами. Функция приспособленности — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное от количества ребер время<ref name = "Neumann">F.Neumann. Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. In Proc. of the 2004 IEEE Congress on Evolutionary Computation (CEC), 904–910 (2004).</ref>.
====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> <ref name = "Neumann" />, где <tex>m</tex> — количество ребер в графе.
====Улучшенный jump-оператор====
Лучших результатов можно достичь, если использовать только операции вида <tex>jump(i, 1)</tex>. Тогда время работы алгоритма будет <tex>O(m^3)</tex><ref>B.Doerr, N. Hebbinghaus, and F. Neumann. Speeding up evolutionary algorithms through restricted mutation operators. In Proc. of the 9th International Conference on Parallel Problem Solving From Nature (PPSN), volume 4193 of LNCS, 978–987 (2006).</ref>.
=== Алгоритм ===
==== Представление графа ====
Пусть <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> (или наоборот).
Рассмотрим пример.
Эйлерову циклу, проходящему по ребрам (2, 6, 7, 4, 3, 8, 5, 1) будет соответстовать множество <tex>M</tex> такого вида:
<tex>M_a = {(b,ec); (ce,d)}</tex>
<tex>M_b = {(a,f)}</tex>
==== Стратегии RLS и (1+1) EA ====
Эволюционный алгоритм поиска эйлерова цикла в графе работает следующим образом. Размер популяции возьмем равным одному; представление графа, операция мутации и функция приспособленности будут такими, как описано выше. Начальное заполнение множества <tex>M</tex> можно сделать случаным образом или оставить пустым, на время работы алгоритма это не влияет.
Стратегия Randomized local search будет работать так: на каждом шаге к текущему индивиду (он один, так как в популяции только одна особь) применяется операция мутации. Если полученный индивид лучше текущего, он выбирается для дальнейшей работы, в противном случае ничего не происходит. Алгоритм работает до тех пор, пока функция приспособленности не минимизирована.
==== Время работы алгоритма ====
<tex>O(\frac{\Delta(G)^2} {d(G)} \cdot m \cdot log \, m)</tex> для стратегии, ориентированной на вершины;
<tex>O(\delta d(G) \cdot m \cdot log \, m )</tex> для стратегии, ориентированной на пары.
|proof=Предположим, что значение функции приспособленности в данный момент <tex>k</tex>. Тогда путей не менее <tex>k/2</tex>. Если путь является циклом, то в нем есть хотя бы одна вершина, соединяющая данный путь с каким-то другим, то есть найдется пара <tex>(u, w)</tex>, к которой можно применить мутацию и уменьшить количество путей. Если путь не является циклом, то так же найдется пара, при применении к которой мутации либо уменьшится количество путей, либо путь замкнется в цикл. Количество мутаций, которые уменьшают функцию приспособленности <tex>\Omega(k)</tex>. Как следствие, вероятность выбрать подходящую пару <tex>\Omega(q \cdot k)</tex>, где <tex>q</tex> — вероятность выбрать подходящую пару. Поэтому ожидаемое время достижения улучшения будет <tex>O(\frac{1} {k \cdot q})</tex>. Изначально значение функции приспособленности не более <tex>2m</tex>. Суммируя по всем <tex>k</tex> без учета констант получаем:
<tex>\sum_{k=1}^{m} \frac{1} {k \cdot q} = \frac{1} {q} \sum_{k=1} ^{m} \frac{1} {k} = O(\frac{1} {q}log \, m)</tex>
Подствляя вместо <tex>q</tex> различные <tex>p</tex> для разных стратегий выбора пар вершин получаем требуемые оценки времени работы алгоритма.
}}
Для случая, когда <tex>M</tex> — разбиение графа на несколько циклов, время работы алгоритма для стратегии, ориентированной на ребра будет <tex>O(m \cdot log \, m )</tex>. Получить такое разбриение можно разбив вершины во всех списках смежности на пары случайным образом.
=== Литература ===
<references/>
