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

Постановка задачи

Определение:

Эйлеров цикл в графе — это путь, проходящий по всем рёбрам графа ровно по одному разу. Задача — для заданного графа найти такой путь.

Предыдущие результаты

Перестановка ребер

Пусть для графа [math]G[/math] задан набор всех его ребер [math](e_1, e_2, \dots e_m)[/math]. На каждом шаге два случайно выбранных ребра меняются местами. Фитнес-функция — длина максимального пути в множестве ребер. Алгорим работает за экспоненциальное от количества ребер время.

Jump-оператор

Jump-оператор работает следующим образом. Для набора ребер [math](e_1, e_2, \dots e_m)[/math] оператор [math]jump(i,j)[/math] передвигает [math]i[/math]-й элемент на позицию [math]j[/math] и циклически сдвигает ребра между позициями [math]i[/math] и [math]j[/math] влево (если [math]i \gt j[/math] то вправо) . Таким образом набор [math](e_1, e_2, \dots e_m)[/math] превратиться в [math](e_1, e_2, \dots e_{i-1}, e_{i+1}, \dots e_j, e_i, e_{j+1}, \dots e_m)[/math]. Работает за [math]O(m^5)[/math], где [math]m[/math] — количество ребер в графе.

Улучшенный jump-оператор

Лучших результатов можно достичь, если использовать только операции вида [math]jump(i, 1)[/math]. Тогда время работы будет [math]O(m^5)[/math].

Алгоритм

Идея

Основная мысль — изменить структуру хранения графа. Ниже будет показан алгоритм, работающий за [math]O(m*log(m))[/math] (ранее лучшим считался результат [math]O(m^2*log(m))[/math] )

Представление графа

Фитнес функция

Операция мутации

Выбор вершин для мутации

Литература

• Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers