Изменения
Нет описания правки
<tex>m</tex> — количество ребер в графе;
<tex>|M|</tex> — размер множества <tex>M</tex>;
<tex>k</tex> — количество путей в <tex>M</tex>.
==== Операция мутации ====
Операция мутации вводится для двух вершин <tex>u</tex> и <tex>w</tex> из <tex>L_v</tex>. Как их выбрать описано в следующем разделе. Происходит она так:
* если для <tex>u</tex> и для <tex>w</tex> нет пары, то добавляем к <tex>M_v</tex> пару <tex>(u,w)</tex>;
* если <tex>u</tex> и <tex>v</tex> уже содержатся в <tex>M_v</tex> как пара, то удалим ее;
* если <tex>u</tex> в паре с некоторой если вершиной <tex>p</tex>, а <tex>w</tex> без пары, то удалим <tex>(u,p)</tex> из <tex>M_v</tex> и добавим <tex>(u,w)</tex>;* если <tex>w</tex> в паре с некоторой если вершиной <tex>p</tex>, а <tex>u</tex> без пары, то удалим <tex>(w,p)</tex> из <tex>M_v</tex> и добавим <tex>(u,w)</tex>;* если <tex>u</tex> в паре с некоторой если вершиной <tex>p</tex>, а <tex>w</tex> в паре с некоторой <tex>k</tex>, то удалим <tex>(u,p)</tex> и <tex>(w,k)</tex> из если <tex>M_v</tex> и добавим <tex>(u,w)</tex> и <tex>(p,k)</tex>;
Если после операции мутации фитнес функция уменьшилась, то операцию не применяют.
==== Выбор вершин для мутации ====
Напомним, что <tex>d(v)</tex> — степень вершины <tex>v</tex> (количество ребер, которые из нее выходят). Пусть <tex>d(G)</tex> — средняя степень среди вершин <tex>G</tex>, <tex>∆G</tex> — максимальная степень среди вершин <tex>G</tex>, а <tex>δd(G) = \frac{1} {2m} \sum_{v \in V}d(v)^2</tex>
===Литература===
* [http://rain.ifmo.ru/~tsarev/teaching/ea-2012/lectures/p1203-doerr.pdf Doerr B., Johannsen D. Adjacency List Matchings - An Ideal Genotype for Cycle Covers]
