Изменения

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