Генерация кода по генетическим алгоритмам

Ответ 1

Если вы уверены, что хотите это сделать, вы хотите генетическое программирование, а не генетический алгоритм. GP позволяет вам разрабатывать древовидные программы. То, что вы сделали бы, это дать ему кучу примитивных операций (while ($ register), read ($ register), increment ($ register), декремент ($ register), divide ($ result $numator $denominator), print, progn2 (это GP говорит для "выполнить две команды последовательно" )).

Вы можете создать что-то вроде этого:

progn2(
  progn2(
    read($1)
    while($1
      progn2(
        while($1
          progn2( #add the input to the total
            increment($2)
            decrement($1)
          )
        )
        progn2( #increment number of values entered, read again
          increment($3)
          read($1)
        )
      )
    )
  )
  progn2( #calculate result
    divide($1 $2 $3)
    print($1)
  )
)  

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

* Есть способы обойти это, но, как правило, не очень далеко от него.

Ответ 2

Это можно сделать, но очень плохо работает для большинства приложений.

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

К сожалению, правильность программы совершенно не непрерывна. Является ли программа, которая останавливается с ошибкой X на линии А лучше, чем одна, которая останавливается с ошибкой Y на линии B? Ваша программа может быть от одного символа от правильного и все еще прерываться с ошибкой, в то время как тот, который возвращает постоянный жесткий код, может, по крайней мере, пройти один тест.

И это даже не касается вопроса о том, что сам код не является непрерывным при модификации...

Ответ 3

Ну, это очень возможно, и @Jivlain правильно указывает в своем (приятном) ответе, что генетическое программирование - это то, что вы ищете (а не простые генетические алгоритмы).

Генетическое программирование - это область, которая еще не достигла широкой аудитории, частично из-за некоторых осложнений, которые @MichaelBorgwardt указывает в его ответе. Но это просто осложнения, это далеко не так, что это невозможно сделать. Исследования по этой теме продолжаются более 20 лет.

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

Здесь хороший учебник по генетическому программированию от Koza и Poli от 2003 года.

Для недавней ссылки вы можете взглянуть на Полевое руководство по генетическому программированию (2008).

Ответ 4

С учетом этого вопроса область генетического программирования немного продвинулась, и были предприняты некоторые дополнительные попытки разработать код в конфигурациях, отличных от древовидных структур традиционного генетического программирования. Вот лишь некоторые из них:

• PushGP - разработанный с целью развития модульных функций, таких как использование человеческих кодеров, программы в этой системе хранят все переменные и код на разных стеках ( по одному для каждого типа переменной). Программы записываются путем нажатия и выталкивания команд и данных из стеков.
• FINCH - система, которая развивает байт-код Java. Это было очень полезно для развития игровых агентов.
• Различные алгоритмы начали разрабатывать код С++, часто с шагом, на котором исправлены ошибки компилятора. Это привело к смешанным, но не совсем бесперспективным результатам. Вот пример.
• Avida - система, в которой агенты развивают программы (в основном логические логические задачи), используя очень простой ассемблерный код. На основании старых (и менее универсальных) Tierra.

Ответ 5

Язык не является проблемой. Независимо от языка, вы должны определить какой-то более высокий уровень мутации, иначе он будет навсегда учиться.

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

Если вы пытались создать программу сортировки, и у вас были операции высокого уровня, такие как "своп", "переместить" и т.д., тогда у вас будет гораздо больше шансов на успех.

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

Ответ 6

Удачи вам в этом.

Конечно, вы могли бы написать программу "мутации", которая читает программу и случайно добавляет, удаляет или изменяет некоторое количество символов. Затем вы можете скомпилировать результат и посмотреть, лучше ли результат, чем исходная программа. (Однако мы определяем и измеряем "лучше".) Конечно, в 99,9% случаев результатом были бы ошибки компиляции: синтаксические ошибки, переменные undefined и т.д. И, конечно, большинство остальных было бы дико неверно.

Попробуйте очень простую задачу. Скажем, начните с программы, которая читает в двух номерах, добавляет их вместе и выводит сумму. Скажем, что целью является программа, которая читает в трех числах и вычисляет сумму. Насколько продолжительная и сложная такая программа, конечно, зависит от языка. Скажем, у нас есть язык очень высокого уровня, который позволяет нам читать или писать номер только с одной строкой кода. Тогда стартовая программа состоит всего из 4 строк:

read x
read y
total=x+y
write total

Простейшей программой для достижения желаемой цели было бы что-то вроде

read x
read y
read z
total=x+y+z
write total

Таким образом, благодаря случайной мутации мы должны добавить "read z" и "+ z", всего 9 символов, включая пробел и новую строку. Давайте упростим нашу мутационную программу и скажем, что она всегда вставляет ровно 9 случайных символов, что они гарантированно находятся в правильных местах и ​​что она выбирает из набора символов всего из 26 букв плюс 10 цифр плюс 14 специальных символов = 50 символов. Каковы шансы, что он выберет правильные 9 персонажей? 1 в 50 ^ 9 = 1 в 2.0e15. (Хорошо, программа будет работать, если вместо "read z" и "+ z" она вставит "read w" и "+ w", но тогда я делаю это легко, предположив, что это волшебным образом вставляет точно правильное количество символов и всегда вставляет их в нужные места. Поэтому я считаю, что эта оценка по-прежнему щедрая.)

1 в 2.0e15 - довольно небольшая вероятность. Даже если программа запускается тысячу раз в секунду, и вы можете быстро протестировать результат, вероятность составляет всего 1 в 2.0e12 в секунду, или 1 в 5.4e8 в час, 1 в 2.3e7 в день. Держите его в течение года, и шанс на успех по-прежнему составляет всего лишь 1 из 62 000.

Даже умеренно грамотный программист должен иметь возможность сделать такое изменение, что, десять минут?

Обратите внимание, что изменения должны входить как минимум в "пакеты", которые являются правильными. То есть, если мутация генерирует "reax z", то только один символ находится вдали от "read z", но он все равно будет генерировать ошибки компиляции, и так потерпит неудачу.

Аналогично добавление "read z", но изменение вычисления на "total = x + y + w" не сработает. В зависимости от языка вы либо получите ошибки для переменной undefined, либо, в лучшем случае, у нее будет какое-то значение по умолчанию, например ноль, и дайте неверные результаты.

Вы могли бы, я полагаю, теоретизировать инкрементные решения. Возможно, одна мутация добавляет новый оператор чтения, а затем будущая мутация обновляет вычисление. Но без расчета дополнительное чтение бесполезно. Как будет оцениваться программа, чтобы определить, что дополнительное чтение является "шагом в правильном направлении"? Единственный способ, которым я это вижу, - заставить интеллектуального читать код после каждой мутации и посмотреть, не изменилось ли изменение к желаемой цели. И если у вас есть умный дизайнер, который может это сделать, это должно означать, что он знает, какова желаемая цель и как ее достичь. В этот момент было бы гораздо эффективнее просто внести желаемые изменения, а не ждать, пока это произойдет случайно.

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

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

Ответ 7

Самая большая точка продажи генетических алгоритмов, как вы говорите, заключается в том, что они являются грязными.. Они не имеют лучшей производительности или математического фона, но даже если вы не знаете, как решить свою проблему, пока вы можете определить ее как проблему оптимизации, вы сможете превратить ее в GA.

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

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

Ответ 8

Я хочу просто дать вам предложение. Я не знаю, как бы вы были успешны, но, возможно, вы могли бы попытаться разработать core war бот с генетическим программированием. Ваша фитнес-функция проста: просто позвольте ботам соревноваться в игре. Вы можете начать с известных ботов и, возможно, нескольких случайных, а затем подождать и посмотреть, что произойдет.