Лучший способ изменить дерево выражений symboli c в алгоритме geneti c

Question

Я создаю GA для прогноза временных рядов в python. Допустим, у меня есть большое дерево символов c, например:

['avg', ['diff', 'x', ['avg', 'pi', 24.90887042555513]], [ 'sqrt', ['max', ['mul', ['diff', 53.79502493321837, 'e'], ['mul', 0.5144978394070354, 46.36225530228578]], 44.34745373778043], ['sqrt', ['diff', ['avg', 20.424103573006004, 67.68047383230076], ['div', 35.70761733351755, 76.63350676737794]], 6.6143363501814605]]]

Что является хорошим способом случайного мутирования?

1) только мутировать только один случайный узел? или использовать вероятность, чтобы решить, сколько, если и когда произойдет мутация?

2) я должен мутировать, добавляя ветви, или просто отдельное значение (листовой узел)

3) как я должен go о реализации этого механизма? через рекурсивный механизм? или построить индекс формы дерева как-нибудь и случайным образом выбрать гнездо для мутирования?

Заранее спасибо

Answer 1

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

В вашем случае требуется, чтобы вы сделали следующие 4 вещи:

1. изменение всех чисел на некоторую случайную величину.
2. Посмотрите на каждое число индивидуально и с небольшой вероятностью измените его на x или замените его новым случайным выражением (желательно только глубиной 1, чтобы предотвратить выражение становится огромным).
3. Просмотрите все переменные и с небольшой вероятностью измените их на случайное число или новое случайное выражение (желательно снова с глубиной 1).
4. Удалите некоторые выражения случайным образом.

1, 2 и 3 только изменяют листья и не требуют от вас построения дерева, но могут быть реализованы путем линейного перемещения по строке.

С помощью несколько упрощений 4. также можно реализовать без создания дерева:

Вместо удаления случайного выражения достаточно Можно удалить только те выражения, которые содержат только числа (например, ['mul', 4, 5]), поскольку вместе с процессами 1,2,3 дерево выражений все еще можно преобразовать в любое другое возможное дерево. Удалить выражения, содержащие только цифры, довольно просто, поскольку вы можете просто вычислить выражение: ['mul', 4, 5] = 4*5 = 20.

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

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