Оператор рекомбинации ребер

Оператор рекомбинации ребер ( ERO ) — это оператор, который создает путь , похожий на набор существующих путей (родителей), просматривая ребра, а не вершины. Основное применение этого метода - скрещивание в генетических алгоритмах , когда необходим генотип с неповторяющимися последовательностями генов, например, для задачи коммивояжера . Он был описан Даррелом Уитли и другими в 1989 году. ^[1]

Алгоритм

ERO основан на матрице смежности , в которой перечислены соседи каждого узла в любом родителе.

Например, в задаче коммивояжера, такой как изображенная, карта узлов для родителей CABDEF и ABCEFD (см. иллюстрацию) генерируется путем взятия первого родителя, скажем, «ABCEFD», и записи его непосредственных соседей, включая тех, которые катятся вокруг конца строки.

Поэтому;

... -> [A] <-> [B] <-> [C] <-> [E] <-> [F] <-> [D] <- ...

... преобразуется в следующую матрицу смежности , поочередно беря каждый узел и перечисляя его подключенных соседей;

A: B D
B: A C
C: B E
D: F A
E: C F
F: E D

При выполнении той же операции со вторым родительским элементом (CABDEF) получается следующее:

A: C B
B: A D
C: F A
D: B E
E: D F
F: E C

Затем следует объединить эти два списка и игнорировать любые дубликаты. Это так же просто, как взять элементы каждого списка и добавить их для создания списка уникальных конечных точек ссылок. В нашем примере создание этого;

A: B C D         = {B,D} ∪ {C,B}
B: A C D         = {A,C} ∪ {A,D}
C: A B E F       = {B,E} ∪ {F,A}
D: A B E F       = {F,A} ∪ {B,E}
E: C D F         = {C,F} ∪ {D,F}
F: C D E         = {E,D} ∪ {E,C}

В результате получается еще одна матрица смежности , в которой хранятся ссылки для сети, описываемой всеми ссылками в родителях. Обратите внимание, что здесь можно использовать более двух родителей, чтобы обеспечить более разнообразные связи. Однако этот подход может привести к неоптимальным путям.

Затем для создания пути K используется следующий алгоритм: ^[2]

algorithm ero is
    let K be the empty list
    let N be the first node of a random parent.

    while length(K) < length(Parent) do
        K := K, N   (append N to K)
        Remove N from all neighbor lists

        if' Ns neighbor list is non-empty then
            let N* be the neighbor of N with the fewest neighbors in its list (or a random one, should there be multiple)
        else
            let N* be a randomly chosen node that is not in K

        N := N*

Чтобы пройти пример, мы случайным образом выбираем узел из родительских начальных точек {A, C}.

() -> A. Мы удаляем A из всех множеств соседей и обнаруживаем, что наименьшее из B, C и D равно B={C,D}.
АБ. Наименьшими наборами C и D являются C={E,F} и D={E,F}. Мы случайно выбираем Д.
АБД. Наименьшими являются E={C,F}, F={C,E}. Мы выбираем Ф.
АБДФ. С={Е}, Е={С}. Мы выбираем С.
АБДФК. Наименьший набор — E={}.
АБДФЦЕ. Длина дочернего элемента теперь такая же, как и у родителя, так что мы закончили.

Обратите внимание, что единственное ребро, введенное в ABDFCE, — это AE.

Сравнение с другими операторами

Рекомбинация ребер обычно считается хорошим вариантом для решения таких задач, как задача коммивояжера. В исследовании 1999 года, проведенном в Университете Страны Басков , рекомбинация ребер дала лучшие результаты, чем все другие операторы кроссовера, включая частично отображенный кроссовер и циклический кроссовер . ^[3]

Ссылки

^ Уитли, Даррелл; Тимоти Старквезер; Д'Энн Фукей (1989). «Проблемы планирования и коммивояжер: оператор рекомбинации генетических ребер». Международная конференция по генетическим алгоритмам . стр. 133–140. ISBN 1-55860-066-3 .
^ Даррелл Уитли, Тимоти Старквезер и Дэниел Шейнер: Коммивояжер и планирование последовательностей: качественные решения с использованием генетической краевой рекомбинации в Л. Дэвисе (ред.): Справочник по генетическим алгоритмам . Ван Ностранд Рейнхольд, Нью-Йорк, 1991 г.
^ П. Ларраньяга и др.: Генетические алгоритмы для задачи коммивояжера: обзор представлений и операторов . Обзор искусственного интеллекта, том 13, номер 2, апрель 1999 г., стр. 129−170

[1] Уитли, Даррелл; Тимоти Старквезер; Д'Энн Фукей (1989). «Проблемы планирования и коммивояжер: оператор рекомбинации генетических ребер». Международная конференция по генетическим алгоритмам . стр. 133–140. ISBN 1-55860-066-3 .

[2] Даррелл Уитли, Тимоти Старквезер и Дэниел Шейнер: Коммивояжер и планирование последовательностей: качественные решения с использованием генетической краевой рекомбинации в Л. Дэвисе (ред.): Справочник по генетическим алгоритмам . Ван Ностранд Рейнхольд, Нью-Йорк, 1991 г.

[3] П. Ларраньяга и др.: Генетические алгоритмы для задачи коммивояжера: обзор представлений и операторов . Обзор искусственного интеллекта, том 13, номер 2, апрель 1999 г., стр. 129−170

[1]

[2]

[3]