Изменения
Нет описания правки
Способ нахождения эйлерова цикла, описанный в данной статье, является примером применения эволюционных алгоритмов на практике. Мы опишем вариант построения, время работы которого <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 стратегии для нашего случая.
=== Постановка задачи ===
=== Обзор методов ===
====Перестановка ребер ====
Пусть для графа <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> — количество ребер в графе.
Пусть <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>, где
==== Стратегии RLS и (1+1) EA ====
Эволюционный алгоритм поиска эйлерова цикла в графе работает следующим образом. Размер популяции возьмем равным одному; представление графа, операция мутации и фитнес функция приспособленности будут такими, как описано выше. Начальное заполнение множества <tex>M</tex> можно сделать случаным образом или оставить пустым, на время работы алгоритма это не влияет.
Стратегия Randomized local search будет работать так: на каждом шаге к текущему индивиду (он один, так как в популяции только одна особь) применяется операция мутации. Если полученный индивид лучше текущего, он выбирается для дальнейшей работы, в противном случае ничего не происходит. Алгоритм работает до тех пор, пока фитнес функция приспособленности не минимизирована.
Псевдокод:
