Как мы можем реализовать конструкции цикла в генетическом программировании?

Ну, это сложно. Генетическое программирование (оригинальная GP в стиле Koza) лучше всего подходит для программирования в функциональном стиле, т. е. в нем нет внутреннего состояния выполнения, и каждый узел представляет собой функцию, которая возвращает (и, возможно, принимает) значения, как lisp. Это проблема, когда узел представляет собой какой-то цикл — непонятно, что должен возвращать узел.

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

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

Что касается способа обработки результатов цикла, вы можете перейти от GP к строго типизированному GP или STGP для краткости. По сути, это GP с типами. Тогда ваш цикл может быть эффективной функцией, которая возвращает список значений (например, чисел), и у вас могут быть другие функции, которые принимают такие списки и вычисляют другие значения...

Существует еще один алгоритм GP (мой любимый), называемый Grammatical Evolution (или GE), который использует контекстно-свободную грамматику для создания программ. Его можно использовать для кодирования информации о типе, как в STGP. Вы также можете определить грамматику таким образом, чтобы можно было генерировать классические C-подобные циклы for и while. Некоторые его расширения, такие как динамически определяемые функции, могут использоваться для динамической реализации переменных.

Если есть что-то непонятное, просто прокомментируйте ответ, и я постараюсь его прояснить.

Проблема с ответом zegkjan заключается в том, что существует несколько способов снять шкуру с кошки.

На самом деле существует более простое, а иногда и лучшее решение для создания структур данных GP, чем деревья коза, вместо использования стеков.

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

0: PUSH TERMINAL X
1: PUSH TERMINAL X
2: MULTIPLY (A,B)

Повторение этой программы даст вам:

step1: DATASTACK X
step2: DATASTACK X, X
step3: DATASTACK X^2

После того, как вы выполнили все операторы списка программ, вы просто удаляете количество элементов из стека, которое вам нужно (таким образом вы можете получить несколько значений из программы GP). Это оказывается быстрым и чрезвычайно гибким методом (локальность памяти, количество параметров не имеет значения или количество возвращаемых элементов), который вы можете реализовать довольно быстро.

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

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

0: PUSH TERMINAL X
1: START_LOOP 2
2: PUSH TERMINAL X
3: MULTIPLY (A, B)
4: DECREMENT_LOOP_NOT_ZERO

step1: DATASTACK X
       LOOPSTACK 
step2: DATASTACK X
       LOOPSTACK [1,2]
step3: DATASTACK X, X
       LOOPSTACK [1,2]
step4: DATASTACK X^2
       LOOPSTACK [1,2]
step5: DATASTACK X^2
       LOOPSTACK [1,1]
step6: DATASTACK X^2, X
       LOOPSTACK [1,1]
step7: DATASTACK X^3
       LOOPSTACK [1,1]
step8: DATASTACK X^3
       LOOPSTACK [1,0]

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