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

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

Алгоритм

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

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

Поэтому;

... -> [А] <-> [Б] <-> [С] <-> [Е] <-> [Ф] <-> [Д] <- ...

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

А: БДБ: переменный токС: БЫТЬД: ФАЭ: КФФ: ЭД

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

А: КБПЛОХОЙС: ФАД: БЫТЬЭ: ДФФ: ЕС

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

А: BCD = {B,D} ∪ {C,B}B: ACD = {A,C} ∪ {A,D}C: ABEF = {B,E} ∪ {F,A}D: ABEF = {F,A} ∪ {B,E}E: CDF = {C,F} ∪ {D,F}F: CDE = {E,D} ∪ {E,C}

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

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

алгоритм  эро  это     пусть  K  будет пустым списком    пусть  N  будет первым узлом случайного родителя.     while  length(  K  ) < length(Parent)  do          K  :=  K  ,  N  (добавляем  N  к  K  )        Удалить  N  из всех списков соседей         если   список соседей N  не пуст,  то             пусть  N  * будет соседом  N  с наименьшим количеством соседей в его списке (или случайным, если их несколько)         еще             пусть  N  * будет случайно выбранным узлом, которого нет в  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]