Генетические алгоритмы: как сделать кроссовер в «подмножестве» задач?

Question

У меня есть проблема, которую я пытаюсь решить с помощью генетических алгоритмов.Проблема заключается в выборе некоторого подмножества (скажем, 4) из 100 целых чисел (эти целые числа являются просто идентификаторами, которые представляют что-то еще).Порядок не имеет значения, решение проблемы - это набор целых чисел, а не упорядоченный список.У меня хорошая функция пригодности, но у меня проблемы с функцией кроссовера.

Я хочу иметь возможность соединить следующие две хромосомы:

[1 2 3 4] и [3 4 56] во что-то полезное.Ясно, что я не могу использовать типичную функцию кроссовера, потому что у моих детей могут быть дубликаты, которые будут представлять неверные решения.Каков лучший метод кроссовера в этом случае.

Answer 1

Просто игнорируйте любой элемент, который встречается в обоих наборов (т.е. в их пересечении.), То есть оставляйте такие элементы неизменными в обоих наборах.

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

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

Answer 2

Поскольку порядок не имеет значения, просто соберите все числа в массив, отсортируйте массив, выбросьте дубликаты (отсоединив их от связанного списка, или установив их в отрицательное число, или как угодно).Перемешайте массив и возьмите первые 4 числа.

Answer 3

Иногда полезно дать вашему решению выйти за пределы, чтобы ваш поиск быстрее сходился.Вместо того чтобы делать набор из 4 уникальных целых чисел обязательным для вашей хромосомы, сделайте количество целых чисел (и их уникальность) частью фитнес-функции.

Answer 4

Чтобы объединить наборы A и B, вы можете выбрать результирующий набор S вероятностным образом так, чтобы вероятность того, что x находится в S, равна (число наборов из A, B, которые содержат x) / 2. Это будет гарантированно содержит пересечение и содержится в объединении, и будет иметь ожидаемое количество элементов 4.

Answer 5

Я действительно не знаю, что вы имеете в виду под "типичным кроссовером", но я думаю, что вы могли бы использовать кроссовер, аналогичный тому, который часто используется для перестановок:

• take m целых от первого родителя ( m <<em> n , где n - количество целых в ваших наборах)
• сканирует второй и заполняет из него ваше подмножествос ( нм ) свободными (не входящими в подмножество) вставками.

Таким образом, у вас будет n вставок от первого и nm int от второго родителя, без дублирования.

Звучит как настоящий кроссовер для меня :-).

Полагаю, было бы полезно не выполнять какие-либо шаги для упорядоченных множеств (или использовать итератор, в котором порядок возвращаемых элементов каким-либо образом коррелирует с естественным упорядочением целых чисел), в противном случае либо меньшие, либо большие числа получатболее высокий шанс быть в ребенке делает ваш поиск предвзятым.

Если это лучший метод, зависит от проблемы, которую вы хотите решить ...