Метабиология: как случайным образом изменить алгоритм, чтобы убедиться, что новая версия будет действительной и остановится?

Question

Я пытаюсь взломать симуляцию эволюции в соответствии с моделью метаболизма Грегори Чейтина.

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

Мои вопросы:

• Какой наилучший язык полного набора можно сделатьэто?
• Есть ли какая-либо техника из генетического программирования, которая уже решала эту проблему?

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

---

Я думал о чем-то вроде:

x <- x + 1
x <- x - 1
y <- x
if x != 0 goto label

это полная проверка и ее очень легко изменить.Что ты думаешь?

Answer 1

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

Как указал Роберт Б., набор функций, полных по Тьюрингу, удовлетворит вашу первую часть, но нет решения проблемы, когда вы допускаете возможность циклов. Однако, если вы удалите циклы как возможность, вы можете сгенерировать дерево выражений, которое может предоставлять вам выходные данные каждый раз, когда вы вводите в него некоторые входные данные. Дерево выражений имеет конечный размер и гарантированное завершение, или думать об этом иначе: чтобы получить дерево выражений с бесконечным временем выполнения, потребуется, чтобы дерево выражений имело бесконечные узлы (что потребовало бы, чтобы у вас было бесконечное ОЗУ или диск).

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

Answer 2

То, что вы ищете здесь, это «Грамматическая эволюция», которая будет приложением генетического программирования к развивающимся рабочим компьютерным программам.Это хороший сайт: http://www.grammatical -evolution.com / .Кроме того, вы можете посмотреть на эволюцию более базовых вычислительных механизмов, таких как FPGA, введя «генетическое программирование FPGA» в Google.

Answer 3

Ну, первая часть вашего вопроса о алгоритмах, которые являются действительными. Если вы определяете столько функций, сколько вам необходимо для обеспечения полноты по Тьюрингу (например, +, -, *, /, X, Y, Retval, loop, if), то вы удовлетворяете первую часть. Я рекомендую использовать функции более высокого уровня, потому что есть определенные структуры, которые будут развиваться снова и снова, и вы ускорите эволюцию, если просто включите ее в список функций для начала. Например, цикл можно разложить на if и goto, но с помощью цикла вы сэкономите ценную энергию эволюции, а также обеспечите валидность.

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

Answer 4

LISP. Ну, любой гомойкальный язык. Но ЛИСП. Прочитайте книги Козы http://www.genetic -programming.com /