Каков наилучший способ выполнить векторное пересечение в генетическом алгоритме? - PullRequest
Новая
       34

Каков наилучший способ выполнить векторное пересечение в генетическом алгоритме?

5 голосов
/ 02 сентября 2011

Я использую генетический алгоритм «для изучения» лучших параметров для шашки / шашки AI.Эти параметры хранятся в векторе double. 

[x1 x2 x3 x4 x5 x6 x7 x8 x9]

На самом деле я делаю кроссовер, используя два простых метода: кроссовер с одной точкой и кроссовер с двумя точками.К сожалению, на мой взгляд, эти методы недостаточно хороши.

Например, если у меня есть генетический пул с: 

[10 20 1]
[30 10 9]
[100 1 10]

Если теоретический оптимум для значения x1 равен 50, я могу 'я никогда не найду его кроссовером.Моя единственная надежда состоит в том, чтобы породить мутацию с x1 = 50, достаточной для передачи в следующем поколении.

Итак, есть лучший способ выполнить кроссовер с массивом чисел?

Ответы [ 4 ]

5 голосов
/ 02 сентября 2011

Кажется, у вас проблема с кодировкой, а не кроссовер.Если вы хотите большей вариабельности в хромосоме - кодируйте данные в виде последовательности байтов (или даже битов).Предположим, у вас есть 3 целочисленных параметра, - тогда вы можете представить их как 3 * 4 = 12-байтовый вектор: 

{114,2,0,214, // first 32-bit int
14,184,220,7, // second 32-bit int
145,2,32,12,  // etc...
}

, тогда после пересечения ваши целые будут развиваться с большой изменчивостью.Также вы можете использовать не 1/2 точечное пересечение, а равномерное пересечение - когда в каждой точке хромосомы вы будете случайным образом выбирать, какую версию гена вы будете использовать.В таком случае вы получите еще большую изменчивость.Но имейте в виду, что слишком большая изменчивость в кроссовере также катастрофична, поскольку приводит к тому, что совокупность может никогда не достичь оптимального решения, потому что даже неоптимальное решение разделено большими случайными колебаниями в работе кроссовера. Стабилизированная эволюция является основным ключевым словом здесь.

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

HTH!

2 голосов
/ 02 сентября 2011

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

Например, смоделированный двоичный файл с eta = 0.5 даст (подразумевается рандомизация) от этих двух родителей 

[30 10 9]
[100 1 10]

Два ребенка 

[52 8 9]
[77 2 10]

Насколько я знаю, почти все основные платформы EC реализуют эти операторы (Open Beagle, ECJ, DEAP, EO и т. Д.)

2 голосов
/ 02 сентября 2011

Это действительно зависит от того, как функционирует фитнес.В кроссовере вы также можете усреднить значения (опять же, если это имеет смысл для функции пригодности), но, вероятно, это заставит алгоритм слишком легко сходиться к совокупности с очень похожими индивидуумами.

Я думаю, чтоэто мутация, которая должна приводить единичные значения к лучшим, вы должны получить 50 из-за мутации, если вы не можете получить ее из-за пересечения.

Рассмотрите возможность выполнения какого-либо локального поиска на одиночнома также отдельные лица (меметический алгоритм).

0 голосов
/ 02 сентября 2011

Алгоритм кроссовера в моем GA отличается от того, что вы используете - не лучше, а просто другой. В сумме, вместо подстановки, я кодировал кроссовер как операцию объединения / объединения массивов , в которой точка сплайсинга рандомизирована (а также «синхронизирована», так что когда две сплайсированные части собранный дочерний вектор, который в результате имеет ту же длину, что и каждый родительский.

Я думаю, что это гораздо проще объяснить в коде: 

DOMAIN_LENGTH = 14

def crossover(v1, v2):
    crossover_point = random.randint(1, DOMAIN_LENGTH-2)
    return v1[:crossover_point] + v2[crossover_point:]

# create a simple function to generate a couple of 'parent' vectors
>>> fnx = lambda v : [random.choice(range(10)) for c in range(DOMAIN_LENGTH)]

# now generate those parent vectors
>>> v1 = fnx(DOMAIN_LENGTH)
>>> v2 = fnx(DOMAIN_LENGTH)
>>> v1
  [7, 9, 5, 6, 6, 7, 6, 9, 8, 6, 6, 4, 5, 8]
>>> v2
  [2, 2, 9, 7, 1, 4, 6, 9, 0, 7, 1, 9, 3, 0]
>>> len(v1); len(v2)
  14
  14

# create the child vector via crossover
>>> child_01 = crossover(v1, v2)
>>> child_01
  [7, 9, 9, 7, 1, 4, 6, 9, 0, 7, 1, 9, 3, 0]
>>> len(child_01)
  14

так для:

  • размер домена (длина вектора) 5
  • a * crossover_point * из 2 и t
  • два родительских вектора представляют собой [4, 3, 2, 4, 8] и [1, 3, 1, 6, 3]

, то: 

# fragment contributed from first parent:
>>> f1 = p1[:2]
>>> f1
  [4, 3]

# fragment contributed from second parent:
>>> f2 = p2[2:]
>>> f2
  [1, 6, 3]

# now just concatenate the two fragments to produce the child fragment
>>> child = f1 + f2
>>> child
  [4, 3, 1, 6, 3]
>>> len(child) == len(p2)
  True
...