Я пишу систему генетического программирования (GP) (в C, но это небольшая деталь). Я читал много литературы (Koza, Poli, Langdon, Banzhaf, Brameier и др.), Но есть некоторые детали реализации, которые я никогда не видел. Например:
Я использую устойчивое состояние, а не подход поколений, прежде всего для использования всей памяти компьютера, а не резервной половины для промежуточного населения.
Q1. В GP, в отличие от GA, когда вы выполняете кроссовер, вы выбираете двух родителей, но вы создаете одного ребенка или два, или это ваш свободный выбор?
Q2. В устойчивом состоянии GP, в отличие от системы поколений, какие члены населения делают дети, созданные кроссовером, заменяют? Это то, что я не видел. Это два родителя, или это два других, случайно выбранных члена? Я могу понять, если это последнее, и что вы можете использовать отрицательный выбор турнира, чтобы выбирать членов для замены, но разве это не создало бы преждевременную конвергенцию? (После события кроссовера население содержит двух родительских родителей плюс двух детей этих родителей, а два других случайных члена удаляются. Элитизм присущ.)
Q3. Есть ли веб-форум или список рассылки, посвященный GP? Как ни странно, я его не нашел. Yahoo GP group используется почти исключительно для анонсов, форум Poli/Langdon Field Guide почти бесшумный, и обсуждения в GP на общих/игровых сайтах программирования, таких как gamedev.net, очень просты.
Спасибо за любую помощь, которую вы можете предоставить!
Во-первых, расслабьтесь.
В GP нет "правильных" методов. GP больше искусства, чем науки. Попробуйте множество схем и выберите те, которые лучше всего работают.
Q1:1, 2 или многие. Вы выбираете.
Q2: Заменить, 1, 2, все. Или попробуйте элитизм.
Q3: Вы, вероятно, не найдете форумов, обсуждающих эти вопросы b/c, нет правильных/лучших ответов. К сожалению.
PS. В моих исследованиях кроссовер никогда не выполнялся хорошо...
Если вы можете прочитать Python, вы можете взглянуть на Pyevolve. Я в основном участвую в этом на стороне GA, но он также поддерживает GP. Может быть, вы можете получить там какой-нибудь намек.
Q1 - ваш выбор, но один ребенок, вероятно, будет более распространенным. Каждый раз, когда вы делаете выбор лотереи родителей, вы применяете давление выбора, которое вы хотите.
Q2: Отрицательный выбор турниров - это точно правильный подход. Да, потеря людей с низкой плотностью населения изначально вызывает быстрое сближение, но как только ваше население попадает в труднодоступную часть пространства для решения, оно не будет таким вырезанным и высушенным, которое теряет турнир/лотереи. То, что вы должны остерегаться, - это застой генофонда; Я предлагаю контролировать энтропию генома для отслеживания его неоднородности. "Елитизм присущ" - Ну, да, это точка!;-)
Q3: comp.ai.genetic, вероятно, лучший выбор. Иногда тема поднимается на форумах разработки игр, например, на Gamasutra.
P.S. Генетическое программирование в C?!? Как вы подтверждаете жизнеспособность потомства? Выполнение генетического программирования на негомиконическом языке является реальной проблемой.
Обратите внимание на MetaOptimize.com для ваших потребностей в стеках.
Как говорит Рэй, это в основном зависит от вас, но, как правило, в стационарной настройке вы создадите только одно потомство.
Опять у вас есть опции. Я бы не стал заменять родителей. Если они были выбраны родителями на основе их пригодности, вы могли бы устранить некоторых из наиболее приспособленных членов населения. Проще всего просто случайно выбрать человека для замены. В качестве альтернативы вы можете заменить человека с наименьшей степенью соответствия, но это может привести к преждевременной конвергенции. Другой вариант - использовать ту же стратегию выбора, которую вы используете для выбора родителей, но используйте обратную пригодность, чтобы она была более удобной для людей.
Вы можете попробовать comp.ai.genetic для USENET (и Группы Google).
Похоже, что некоторые из ваших вопросов не обязательно специфичны для генетического программирования; если это так, вам может быть повезло, обратившись к людям в NEAT Users Group.
В основном они обсуждают алгоритм нейроэволюции дополняющих топологий (или NEAT), который является генетическим алгоритмом, используемым для развития нейронных сетей. Но такие темы, как элитарность и стратегии кроссовера, довольно общие и могут применяться как к алгоритмам GA, так и к GP.
В противном случае, как сказал Дэн и Рэй, многие из этих решений принимаются после экспериментов с одним конкретным программным обеспечением и доменом. Попробуйте применить свой алгоритм к различным проблемам и обращать внимание на то, как он себя ведет - через некоторое время вы, вероятно, разработаете интуицию для того, что работает, а что нет.
Я бы создал неограниченное количество потомков, но только на основе успеха, и пусть пожилые члены населения умирают. Отсутствие пригодности также может привести к ранней смерти. Это похоже на естественный порядок.
Q1. In GP, as opposed to GA, when you perform crossover you select two parents but
do you create one child or two, or is that a free choice you have?
Да, это ваш выбор; но, как правило, не рекомендуется создавать много людей с одинаковыми родителями, поскольку различия между отдельными тенденциями, создаваемыми одними и теми же родителями, будут очень ограниченными и могут стоить скорость обработки и память, которые могли быть потрачены на других лиц, демонстрирующих разные тенденции и поведение, требующее анализа (но создание большего числа людей не может быть проблемой, если процесс эволюции близок к достижению конечной точки).
Q2. In steady state GP...
Желательно заменить людей на основе ранжирования, предоставленного принятой вами функцией фитнеса.