Эволюционные алгоритмы поиска эйлерова цикла в графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
Пусть <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>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>, где
+
Фитнес функция для эволюционного алгоритмы поиска эйлерова цикла в графе выглядит так:  
 +
 
 +
<tex>f(M) = m - |M| + k</tex>, где
 +
 
 
<tex>m</tex> — количество ребер в графе;
 
<tex>m</tex> — количество ребер в графе;
 +
 
<tex>|M|</tex> — размер множества <tex>M</tex>;
 
<tex>|M|</tex> — размер множества <tex>M</tex>;
 +
 
<tex>k</tex> — количество путей в <tex>M</tex>.
 
<tex>k</tex> — количество путей в <tex>M</tex>.
 
==== Операция мутации ====
 
==== Операция мутации ====

Версия 02:03, 19 июня 2012

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

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

Задача — для заданного графа найти такой цикл. Заметим, что это возможно тогда и только тогда, когда граф связный и степень каждой его вершины четна.

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

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

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

Алгоритм

Идея

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

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

Пусть [math]G[/math] — неориентированный связный граф, [math]V[/math] — множество его вершин, [math]E[/math] — ребер; всего вершин [math]n[/math], а ребер [math]m[/math] . Будем хранить ребра в виде списков смежности. Пусть [math]L_v[/math] — множество вершин, соединенных с [math]v[/math] ребром, [math]L[/math] — множество всех [math]L_v[/math]. Для каждой вершины [math]v[/math] введем также множество [math]M_v[/math], хранящее в себе неупорядоченные пары вершин из [math]L_v[/math]. Обозначим через [math]M[/math] множество всех [math]M_v[/math]. Таким образом, если для всех вершин [math]v[/math] вершины из [math]L_v[/math] разбиты на пары в [math]M_v[/math], то с точностью до первого ребра на [math]G[/math] задан порядок обхода: пара [math](u,w)[/math] в [math]L_v[/math] означает, что придя из [math]u[/math] далее нужно идти в [math]w[/math] (или наоборот).

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

Фитнес функция для эволюционного алгоритмы поиска эйлерова цикла в графе выглядит так:

[math]f(M) = m - |M| + k[/math], где

[math]m[/math] — количество ребер в графе;

[math]|M|[/math] — размер множества [math]M[/math];

[math]k[/math] — количество путей в [math]M[/math].

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

Операция мутации вводится для двух вершин [math]u[/math] и [math]w[/math] из [math]L_v[/math]. Как их выбрать описано в следующем разделе. Происходит она так:

  • если [math]u=w[/math], то ничего не делаем;
  • если для [math]u[/math] и для [math]w[/math] нет пары, то добавляем к [math]M_v[/math] пару [math](u,w)[/math];
  • если [math]u[/math] и [math]v[/math] уже содержатся в [math]M_v[/math] как пара, то удалим ее;
  • если [math]u[/math] в паре с некоторой если вершиной [math]p[/math], а [math]w[/math] без пары, то удалим [math](u,p)[/math] из [math]M_v[/math] и добавим [math](u,w)[/math];
  • если [math]w[/math] в паре с некоторой если вершиной [math]p[/math], а [math]u[/math] без пары, то удалим [math](w,p)[/math] из [math]M_v[/math] и добавим [math](u,w)[/math];
  • если [math]u[/math] в паре с некоторой если вершиной [math]p[/math], а [math]w[/math] в паре с некоторой [math]k[/math], то удалим [math](u,p)[/math] и [math](w,k)[/math] из если [math]M_v[/math] и добавим [math](u,w)[/math] и [math](p,k)[/math];

Если после операции мутации фитнес функция увеличилась, то операцию не применяют.

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

Напомним, что [math]d(v)[/math] — степень вершины [math]v[/math] (количество ребер, которые из нее выходят). Пусть [math]d(G)[/math] — средняя степень среди вершин [math]G[/math], [math]\Delta G[/math] — максимальная степень среди вершин [math]G[/math], а [math]\delta d(G) = \frac{1} {2m} \sum_{v \in V}d(v)^2[/math]. Есть три способа выбрать две вершины для мутации.

Ориентированный на вершины

Сначала выбираем случайно [math]v[/math] из [math]V[/math]. Затем случайно и независимо выбираем [math]u[/math] и [math]w[/math] из [math]L_v[/math]. Вероятность [math]p[/math] выбрать пару [math](u,w)[/math] в [math]L_v[/math] удовлетворяет соотношению:

[math]p = \frac{1} {d(v)^2n} = \frac{d(G)} {2d(v)^2m} \ge \frac{d(G)} {2 \Delta (G)^2m}[/math]

Ориентированный на ребра

Выбираем случайно вершину [math]u[/math] из всех [math]2m[/math] вершин во всех списках [math]L[/math]. Пусть она оказалась в [math]L_v[/math]. Далее случайно выбираем [math]w[/math] из [math]L_v[/math]. Вероятность [math]p[/math] выбрать пару [math](u,w)[/math] в [math]L_v[/math] удовлетворяет соотношению:

[math]p = \frac{1} {2d(v)m} \ge \frac{1} {2 \Delta (G)m}[/math]

Ориентированный на пары вершин

Выбираем случайно пару [math](u,w)[/math] из всех пар для всех [math]2m[/math] вершин во всех списках в [math]L[/math]. Пусть обе вершины присутствуют в [math]L_v[/math]. Тогда вероятность [math]p[/math] выбрать пару [math](u,w)[/math] в [math]L_v[/math] удовлетворяет соотношению:

[math]p = \frac{1} {2\delta d(G)m} [/math]

Время работы алгоритма

Для RLS и (1+1) EA верны следующие оценки времени работы алгоритма:

[math]O(\frac{\Delta(G)^2} {d(G)}*m*log(m))[/math] для стратегии, ориентированной на вершины;

[math]O(\Delta(G)*m*log(m))[/math] для стратегии, ориентированной на ребра;

[math]O(\delta d(G)*m*log(m))[/math] для стратегии, ориентированной на пары.

Литература