Оптимальный размер популяции, частота мутаций и частота спаривания в генетическом алгоритме - PullRequest
Новая
       21

Оптимальный размер популяции, частота мутаций и частота спаривания в генетическом алгоритме

8 голосов
/ 12 ноября 2010

Я написал игровую программу для соревнования, которая опирается на 16 «констант» с плавающей точкой. Изменение константы может и будет иметь драматическое влияние на стиль игры и уровень успеха.

Я также написал простой генетический алгоритм для генерации оптимальных значений для констант. Однако алгоритм не генерирует «оптимальные» константы.

Возможные причины:

  • В алгоритме есть ошибки (пока это исключено!)
  • Население малое
  • Высокий уровень мутаций
  • показатель спаривания мог бы быть лучше

Алгоритм выглядит так:

  • Сначала создается начальная популяция
  • Присвоены начальные константы для каждого члена (на основе моего смещения, умноженного на случайный коэффициент от 0,75 до 1,25)
  • Для каждого поколения члены населения объединены в пару для игрового матча
  • Победитель клонируется дважды, если вничью оба клонируются один раз
  • Клонирование мутирует один ген, если random () меньше частоты мутаций
  • Мутация умножает случайную константу со случайным коэффициентом между 0,75 и 1,25
  • С фиксированными интервалами, в зависимости от скорости спаривания, члены спарены и гены смешаны

Мои текущие настройки:

  • Население: 40 (до низкого уровня)
  • Уровень мутаций 0,10 (10%)
  • Скорость матов 0,20 (каждые 5 поколений)

Каковы были бы лучшие значения для численности населения, коэффициента мутаций и коэффициента спаривания?

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

P.S .: Игровое соревнование под вопросом, если кому-то интересно: http://ai -contest.com /

Ответы [ 2 ]

2 голосов
/ 12 ноября 2010

Используйте платформу GAUL, это действительно легко, так что вы можете извлечь свою целевую функцию, чтобы подключить ее к GAUL. Если у вас многоядерный компьютер, вы можете использовать omp (openMP) при компиляции для распараллеливания ваших оценок (что, я полагаю, отнимает много времени). Таким образом, вы можете иметь большую численность населения. http://gaul.sourceforge.net/

Обычно они используют высокий кроссовер и низкую мутацию. Поскольку вы хотите творчества, я предлагаю вам высокую мутацию и низкий кроссовер. http://games.slashdot.org/story/10/11/02/0211249/Developing-emStarCraft-2em-Build-Orders-With-Genetic-Algorithms?from=rss

Будьте очень осторожны с функцией мутации, чтобы оставаться в поиске пространства (внутри 0,75, 1,25). Используйте случайную функцию GAUL, такую ​​как random_double (min, max). Они действительно хорошо разработаны. Создайте свою собственную функцию мутации. Убедись, что родители умерли!

Тогда вы можете захотеть объединить это с симплексом (Nelder-Mead), включенным в GAUL, потому что генетическое программирование с низким кроссовером найдет неоптимальное решение.

2 голосов
/ 12 ноября 2010

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

Вы можете рассмотреть

  1. Наличие (намного!) Меньшей мутации
  2. Предоставление мутации фиксированного диапазона
  3. Распределение размеров мутаций по-разному - например, вы можете использовать нормальное распределение со средним значением 1.

R.A. Фишер однажды сравнил размер мутации с фокусировкой в ​​микроскоп. Если вы измените фокус, вы, возможно, движетесь в правильном или неправильном направлении. Однако, если вы достаточно близки к оптимальному значению и сильно его развернули - либо вы пойдете в неверном направлении, либо промахнетесь по цели. Так что более тонкий твик, как правило, лучше!

...