47
правок
Изменения
Нет описания правки
====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><ref>F. Neumann. Expected runtimes of evolutionary algorithms for the Eulerian cycle problem. In Proc. of the 2004 IEEE Congress on Evolutionary Computation (CEC), 904–910 (2004).</ref>, где <tex>m</tex> — количество ребер в графе.
====Улучшенный jump-оператор====
Лучших результатов можно достичь, если использовать только операции вида <tex>jump(i, 1)</tex>. Тогда время работы алгоритма будет <tex>O(m^3)</tex> <ref>B. Doerr, N. Hebbinghaus, and F. Neumann. Speeding up evolutionary algorithms through restricted mutation operators. In Proc. of the 9th International Conference on Parallel Problem Solving From Nature (PPSN), volume 4193 of LNCS, 978–987 (2006).</ref>.
