Изменения

Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <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> — количество ребер в графе. Время работы эволюционных алгоритмов измеряется в количестве вычислений функции приспособленности, а время оптимального алгоритма — в итерацияхэлементарных операциях.

Пусть для графа <tex>G</tex> задан набор всех его ребер <tex>(e_1, e_2, \dots e_m)</tex>. На каждом шаге два случайно выбранных ребра меняются местами. Функция приспособленности — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное от количества ребер время <refname = "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-оператор работает следующим образом. Для набора ребер <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> — количество ребер в графе. 

<tex>M_a = {(b,ec); (ce,d)}</tex>

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

Предположим, что значение функции приспособленности в данный момент <tex>k</tex>. Тогда путей не менее <tex>k/2</tex>. Если путь является циклом, то в нем есть хотя бы одна вершина, соединяющая данный путь с каким-то другим, то есть найдется пара <tex>O(u, w)</tex>, к которой можно применить мутацию и уменьшить количество путей. Если путь не является циклом, то так же найдется пара, при применении к которой мутации либо уменьшится количество путей, либо путь замкнется в цикл. Количество мутаций, которые уменьшают функцию приспособленности <tex>\Omegafrac{\Delta(kG)</tex>. Как следствие, вероятность выбрать подходящую пару <tex>\Omega^2} {d(q G)} \cdot k)</tex>, где <tex>q</tex> — вероятность выбрать подходящую пару. Поэтому ожидаемое время достижения улучшения будет <tex>O(m \frac{1} {k cdot log \cdot q}, m)</tex>. Изначально значение функции приспособленности не более <tex>2m</tex>. Суммируя по всем <tex>k</tex> без учета констант получаем:для стратегии, ориентированной на вершины;

<tex>O(\sum_{k=1}^{m} \frac{1} {k Delta(G) \cdot q} = \frac{1} {q} \sum_{k=1} ^{m} \frac{1} {k} = O(\frac{1} {q}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>p2m</tex> для разных стратегий выбора пар вершин . Суммируя по всем <tex>k</tex> без учета констант получаем следующие оценки времени работы алгоритма:

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

Подствляя вместо <tex>O(\Delta(G) \cdot m \cdot log \, m )q</tex> различные <tex>p</tex> для стратегии, ориентированной на ребра;разных стратегий выбора пар вершин получаем требуемые оценки времени работы алгоритма.}}

Для случая, когда <tex>M</tex> — разбиение графа на несколько циклов, время работы алгоритма для стратегии, ориентированной на ребра будет <tex>O(\delta d(G) \cdot m \cdot log \, m )</tex> для стратегии, ориентированной . Получить такое разбриение можно разбив вершины во всех списках смежности на парыслучайным образом.