Оператор реберной рекомбинации - Edge recombination operator
Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) (Узнайте, как и когда удалить этот шаблон сообщения)
|
В оператор реберной рекомбинации (ERO) - оператор, создающий дорожка это похоже на набор существующих путей (родителей), глядя на ребра, а не на вершины. Основное применение этого - для кроссовер в генетические алгоритмы когда необходим генотип с неповторяющимися последовательностями генов, например, для задача коммивояжера. Это было описано Даррелл Уитли и другие в 1989 году.[1]
Алгоритм
ERO основан на матрица смежности, в котором перечислены соседи каждого узла в любом родительском элементе.
Например, в задаче коммивояжера, такой как изображенная, карта узлов для родителей CABDEF и ABCEFD (см. Иллюстрацию) создается путем взятия первого родителя, скажем, 'ABCEFD', и записи его ближайших соседей, включая тех, которые выпадают. вокруг конца строки.
Следовательно;
... -> [A] <-> [B] <-> [C] <-> [E] <-> [F] <-> [D] <- ...
... преобразуется в следующий матрица смежности взяв каждый узел по очереди и перечислив его подключенных соседей;
A: B DB: A CC: B ED: F AE: C FF: E D
При той же операции, выполняемой для второго родителя (CABDEF), создается следующее:
A: C BB: A DC: F AD: B EE: D FF: E C
Затем следует сделать союз из этих двух списков и игнорируя любые дубликаты. Это так же просто, как взять элементы каждого списка и добавить их, чтобы создать список уникальных конечных точек ссылок. В нашем примере генерация this;
A: 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 быть первым узлом случайного родителя. пока длина(K) <длина (Родитель) делать K := K, N (добавить N к K) Удалять N из всех списков соседей если'Nсписок соседей не пуст тогда позволять N* быть соседом N с наименьшим количеством соседей в списке (или случайным, если их несколько) еще позволять N* быть случайно выбранным узлом, не входящим в K N := N*
Чтобы пройти через пример, мы случайным образом выбираем узел из родительских начальных точек, {A, C}.
- () -> A. Удаляем A из всех соседних множеств и обнаруживаем, что наименьшим из B, C и D является B = {C, D}.
- AB. Наименьшие множества C и D - это C = {E, F} и D = {E, F}. Мы случайным образом выбираем D.
- ABD. Наименьшими являются E = {C, F}, F = {C, E}. Мы выбираем F.
- ABDF. C = {E}, E = {C}. Мы выбираем C.
- ABDFC. Наименьший набор - E = {}.
- ABDFCE. Длина дочернего элемента теперь такая же, как у родителя, так что мы закончили.
Обратите внимание, что в ABDFCE введено только ребро AE.
Сравнение с другими операторами
Рекомбинация кромок обычно считается хорошим вариантом для решения таких задач, как задача коммивояжера. В исследовании 1999 г. Университет Страны Басков, реберная рекомбинация дала лучшие результаты, чем все другие операторы кроссовера, включая частично отображенный кроссовер и велосипедный кроссовер.[3]
Рекомендации
- ^ Уитли, Даррелл; Тимоти Старквезер; Д'Анн Фуке (1989). «Задачи планирования и коммивояжер: оператор генетической рекомбинации края». Международная конференция по генетическим алгоритмам. С. 133–140. ISBN 1-55860-066-3.
- ^ Даррелл Уитли, Тимоти Старквезер и Дэниел Шэнер: Коммивояжер и планирование последовательности: качественные решения с использованием генетической пограничной рекомбинации в Л. Дэвисе (ред.): Справочник по генетическим алгоритмам. Ван Ностранд Рейнхольд, Нью-Йорк, 1991 год.
- ^ П. Ларраньяга и др.: Генетические алгоритмы задачи коммивояжера: обзор представлений и операторов. Обзор искусственного интеллекта, том 13, номер 2, апрель 1999 г., стр. 129−170
Реализации
- «Оператор пограничной рекомбинации» (Python)