Могут ли эволюционные алгоритмы создавать машинный код?

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

Начнем с того, что я знаю: у меня университетское образование в области искусственного интеллекта, включая генетическое программирование и более широкий класс эволюционных алгоритмов, хотя я не особо с ними игрался с тех пор, как закончил десять лет назад. Интересно, можно ли использовать эти подходы для создания машинного кода для решения проблем (возможно, x86 или какой-то «произвольный» набор инструкций). Можем ли мы разработать сами алгоритмы, например вычисляющие квадратные корни или выводящие на экран приятные изображения? Можно ли использовать эволюционный алгоритм для создания полных компиляторов, создающих оптимизированный код (по размеру, скорости и т. д.)?

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

TLDR: Может ли когда-либо быть полезным использование эволюционных алгоритмов для создания своего рода машинного кода, и есть ли предыдущие примеры эволюционных алгоритмов в целом, дающих действительно интересные и удивительные результаты?

Ник


person Nicholas Hill    schedule 12.08.2012    source источник
comment
Я решил квадратное уравнение с помощью генетического алгоритма, а также я читал о генетическом алгоритме, вы также можете рисовать изображения случайным образом.   -  person Desire    schedule 12.08.2012
comment
Машинный код не является хорошим необработанным геномом для ГА из-за того, что подавляющее большинство случайных последовательностей изначально искажены (даже не запускаются, не говоря уже о том, чтобы делать что-то полезное). Это не значит, что ГА не могут можно использовать для создания интересного кода, но вам нужно тщательно выбирать характер генома (в частности, его интерпретацию) и функцию пригодности, которую вы хотите применить. Вы можете попробовать использовать машинный код, но я подозреваю, что у вас будут серьезные проблемы с конвергенцией.   -  person Dan Bryant    schedule 12.08.2012
comment
Я думаю, все зависит от того, что вы подразумеваете под созданием машинного кода. Вы всегда можете создать виртуальный набор инструкций, которые компилируются или транслируются в машинный код. Возьмем, к примеру, это: msdn.microsoft.com/en-us/magazine/cc163934. .aspx (украдено из stackoverflow.com/questions/14008/ хотя, строго говоря, они компилируют C#/.NET)   -  person JayC    schedule 12.08.2012
comment
Я читал в какой-то статье или книге о создании оптимального кода Forth, оценивающего выражение, с помощью GA. Это возможно.   -  person Alexey Frunze    schedule 12.08.2012


Ответы (3)


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

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

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

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

person johusman    schedule 12.08.2012
comment
На самом деле, сортирующие сети (предопределенный набор сравнений, гарантирующих сортировку n значений) были одними из первых успешных примеров высококомпетентных программ, созданных с использованием эволюционных методов. Дэнни Хиллис использовал эволюционный метод для создания очень хороших сетей сортировки: kk.org/outofcontrol/ch15 -d.html - person Larry OBrien; 14.08.2012

Может ли GP создавать исполняемый код? Конечно! Просто используйте ЛИСП.

Джон Коза давно установил, что генетическое программирование можно использовать для создания программ. http://www.genetic-programming.com/johkoza.html Он написал 2 очень толстые книги на эту тему.

Причина, по которой большая часть GP была выполнена на LISP, заключается в том, что машинный код чрезвычайно структурирован, поэтому невозможно выполнить сопоставление генома с феномом «Пусть 00000 будет MOV, пусть 00001 будет JNE и т. д.». Вместо этого вам приходится работать с более сложной кодировкой. S-выражения становятся действительно очевидными строительными блоками.

person Larry OBrien    schedule 13.08.2012

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

person Andreas    schedule 13.08.2012