Dore: Ogre

Кстати

Я очарован идеей генетического программирования (Koza 1992, 1994 и далее).

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

Причин, кроме ограниченной производительности компьютеров, именно для такого трудоемкого подхода нет. Вообще же предлагается осознать, что конечным результатом этой деятельности (как и результатом решения всех остальных задач) будет компьютерная программа, правильно решающая квадратные уравнения. Соотвественно, ее поиск можно вести непосредственно в пространстве всевозможных компьютерных программ. А именно, надо составить набор из 10,000 квадратных уравнений с корнями (тренировочные данные, подготовленные экспертами), а дальше генерировать всевозможные программы (синтаксически корректные наборы разнообразных операторов типа goto, if-then-else, циклов, арифметических операций и проч.) случайным образом, и остановиться на той из них, которая решает тренировочные уравнения с наименьшей суммарной ошибкой. Обширный опыт применения этого метода в самых разнообразных предметных областях показывает, что она окажется ничтожно мала, а найденный таким образом алгоритм будет хорошо обобщаться на все остальные квадратные уравнения, которые может потребоваться решить в будущем.

Генерировать случайные программы друг из друга предлагается методами, аналогичными известным алгоритмам генетической оптимизации, но именно эта частность меня не очень заинтересовала.
  • Current Mood: happy happy
То, о чем Вы пишете, гораздо старше генетического программирования, суть которого именно в генетической оптимизации. Например, это довольно близко к идее сложности Комогорова и связанной с ней Minimum Description Length.
Примеры чего? Были (и есть) различные алгоритмы осножанные на этих идеях, которые работали.
Unfortunately, this approach only works for totally trivial programs. Anything complicated requires running evolution for, like, forever, and the results are such that nobody can understand how and why it works.

The best software evolution method so far (the only one which managed to generate solution to Blocks World problem) is Eric Baum's Hayek Machine.
По-моему, это придумали лет 40 назад ;-)
Просто вспомнил, как во времена IBM-360 взахлеб обсуждали с одним фанатом-программистом дальнейшие перспективы, и такой "естественный отбор программ" был помянут как хорошо известная идея ;-)

А началось то обсуждение с ЛИСПа, как сейчас помню. Я о нем тогда услышал впервые и впечатлился :-)