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

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

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

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

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

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

Пусть для графа [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](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(1)}[/math]

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

Алгоритм

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

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

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

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