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

Если вы уверены, что хотите это сделать, вам нужно генетическое программирование, а не генетический алгоритм. GP позволяет вам развивать программы с древовидной структурой. Что бы вы сделали, так это дали бы ему набор примитивных операций (в то время как($register), чтение($register), увеличение($register), уменьшение($register), деление($result $numerator $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)
  )
)  

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

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

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

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

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

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

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

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

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

Вот хороший учебник по генетическому программированию от Козы и Поли, датированный 2003 годом.

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

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

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

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

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

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

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

Самое большое преимущество генетических алгоритмов, как вы говорите, то, что они чертовски просты. У них не лучшая производительность или математическая подготовка, но даже если вы понятия не имеете, как решить свою проблему, пока вы можете определить ее как задачу оптимизации, вы сможете ее решить. в ГА.

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

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

Удачи с этим.

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

Попробуйте решить очень простую задачу. Скажем, начнем с программы, которая считывает два числа, складывает их и выводит сумму. Предположим, что целью является программа, которая считывает три числа и вычисляет сумму. Насколько длинной и сложной будет такая программа, конечно же, зависит от языка. Допустим, у нас есть язык очень высокого уровня, который позволяет нам читать или записывать числа всего одной строкой кода. Тогда стартовая программа состоит всего из 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. (Хорошо, программа будет работать, если вместо «прочитать z» и «+z» она вставит «прочитать w» и «+w», но тогда я упрощаю задачу, предполагая, что она волшебным образом вставляет точно нужное количество символов. и всегда вставляет их в нужные места.Так что я думаю, что эта оценка все еще щедра.)

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

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

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

Точно так же добавление «прочитать z», но изменение расчета на «total=x+y+w» не сработает. В зависимости от языка вы либо получите ошибки для неопределенной переменной, либо в лучшем случае она будет иметь какое-то значение по умолчанию, например ноль, и даст неправильные результаты.

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

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

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

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