Чисто функциональный стиль действительно удобнее.
И он ликвидирует циклы типа for(i=0;i<bigvalue;i++) { expensive useless code }
которые приводят к резкой деградации производительности.
В императивном стиле вместо них есть команда push которая наполняет список и циклы по спискам, таким образом длинных бесполезных циклов практически нет.
В функциональном все вообще проще.
Но был один вариант ГП, который использовал side-effects и иногда срабатывал неплохо — с индексными переменными.
Для каждого экземляра задавался небольшой массив, обнуляемый в начале вычислений.
А среди функций были операторы read[i] и write[i,tree value], которые читали и писали значения в этот массив.
Кстати первыми популярными имплементациями ГП были программы на Лиспе, что не могло не наложить отпечаток на технологию.
Лисп достаточно практичен для ГП.
Т.е. надо определить точки интереса на изображении, обычный программист возьмет openCV и успокоится.
Но если надо шагнуть дальше и глубже — то можно перелопатить литературу и найти разные варианты определения точек интереса.
А можно потратить время и сделать так как в статье — определить какое конкретное решение лучше всего подходит для конкретной задачи.
Вот другой вариант citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.801
Написать процедуру кеширования на С.
Опять таки, в большинстве случаев все берут LRU, не особо задумываясь.
Но если скорость критична — то вот их решение, полученное GP на их конкретном потоке данных, будет намного лучше.
На другом потоке данных — возможно нет.
Хотя опять таки, как сделать.
Я сейчас как раз с изображениями работаю.
И вот допустим нам надо выделить особые точки и создать дескрипторы.
И на митинге один предлагает DoG, другой — SURF, третий ORB ну, как обычно.
В теории менеджмента один гуру должен встать и выбрать, сказав «да будет так», высосав решение из… скажем так, личного опыта.
Но можно построить грамматику, которая объединяет все предложения, определелить фитнесс-функцию и запустить ГП-поиск по всем вариантам решений, включая производные.
И получить объективный валидный результат, а не продукт, вытащенный из астрала медитирующим руководителем.
В ситуации, когда ложные решения стоят дорого, а область работы в тумане, такой подход сильно облегчает жизнь, несмотря на начальные затраты.
И самое главное, иногда такой подход позволяет наткнуться на неожиданное решение, которые бы при обычной работе осталось незамеченным.
Я имел в виду конечно классический МC, с запоминанием лучшего результата, не MCMC.
Со статфизикой не все так просто.
В статфизике другой подход — постулируемая неизмеримость микроскопических состояний и поиск макроскопических значений.
В типовых задачах ИИ проблема обычно ставится по другому.
Это не исключает использование методов физики в ИИ (тот же Simulated Annealing), но задачи все-таки не пересекаются.
И не забываем, что ни статфизика ни неравновесная термодинамика не так хорошо описывают процессы в живых системах, как нам бы хотелось.
С другой стороны методы статфизики достаточно обоснованы и математизированы, а метаэвристический инструментарий — это эмпирика в чистом виде.
Поэтому использование метаэвристик всегда несет в себе некоторый риск.
По поводу MCMC — есть много моделей, которые «честнее», но все они несут в себе некоторые неявные предположения о структуре функции распределения вероятностей.
В отличие от ГА, хотя разумеется можно найти специальные ландшафты, где он будет мягко говоря неэффективен при специально подобранных параметрах.
Но обычная ситуация — десятки тысяч измерений, мультимодальное распределение о котором известно лишь то, что оно очень сложное и имеет миллионы локальных экстремумов.
Если мы говорим об MH алгоритме, то с гауссовым начальным распределением он дает очень маленькую вероятность больших скачков по сравнению с ГА и следовательно имеет больше шансов попасть в локальный экстремум.
Если же мы говорим об MCMC вообще — то он не накапливает информацию о сложных связях и о истории поиска (для чего в ГА нужны интроны) — потому он и Марковский.
Скорость накопления информации в ГА достигает экспоненциальной. Это верхняя граница и она определена schemata theorem.
Для MCMC, насколько я понимаю, такая скорость возможна лишь в очень специфичных условиях.
ГА мне до близкого знакомства казались шаманством чистой воды, попыткой списать код у бога, вырвав страницу из исходников, без особого понимания смысла. Особенно если учесть мой крайне неудачный на то время опыт работы с еще одной попыткой списывания — нейронными сетями.
И после некоторых тестовых применений мнение мое не изменилось.
Я например пытался решить задачу плотного размещения UML-графа на плоскости — не то, чтобы не работало, но, дорого, глупо и не гарантирует результат.
Но когда разобрался, и очертил границы применения — то понял, что метод вполне рабочий.
Просто это наиболее близкая штука к тому, что называется «серебряной пулей», а в соответствии с теоремой NFL серебряные пули обычно или стоят дорого или кучность плохая или можно прострелить себе ногу очень странным и неожиданным образом.
:-)
ГП кстати обладает некоторыми человеческими свойствами — он часто бывает лжив и ленив и ловит программиста на ошибках.
:-)
Рассмотрим простую проблему — слева набор прямоугольников, справа набор эллипсов, найти процедуру, отличающую первые от вторых.
Нейронки или SVM построят сложную модель, которая что-то будет делать.
ГП ответит просто, правильно и неожиданно — основным отличием является то слева или справа находится фигура.
:-)
ГП использует неожидаемые или неявные зависимости, которые программист может просто не заметить в постановке или в обычном для нашей индустрии упрощении.
В этом качестве я использую его наиболее часто.
Исследовать пространство поиска например, чтобы затем уже найти более оптимальную процедуру.
Получить наиболее адекватный набор атрибутов для текста или картинки.
А дальше можно и специальные методы применять, быстрые и предсказуемые.
Я встречал например выбор алгоритма кеширования на реальных данных путем ГП.
Сам похожи почти не занимался, обычно структура более или менее понятна, а робастность решений найденных ГП часто под вопросом.
По поводу Монте-Карло, я могу сказать, что я сравнивал, ГА/ГП лучше практически всегда.
Я рассматриваю ГА — как МК с улучшенной сходимостью (благодаря теореме шим).
А ГП — как ГА в тьюринговски полном пространстве.
Это достаточно условная иерархия, особенно если учесть большое количество модификаций этих алгоритмов.
С Марковскими моделями, как и с Байесовскими сетями есть одна проблема.
Они отлично работают если они уже построены.
:-)
А строить их автоматизированной процедурой обычно достаточно затратно на реальных данных, не говоря уже о BigData. Т.е. понятно что если это полный связный граф, в вырожденных случаях например дерева или линейного графа строится нормально.
То, что я видел реально работающего было обычно достаточно убого и строилось с учетом экспертных мнений, здравого смысла и других вариантов генератора случайных чисел.
Априорное знание — страшная вещь.
:-)
Собственно поэтому я с такими моделями практически и не работал, ну там Chou-Liu дерево максимум сделаю, так и то, CART часто давал лучшую аппроксимацию.
Вот кстати на старой винде их экспертная система помощи так работает — и что-то я мало встречал кому эта помощь помогла.
Плюс был опыт когда мой тупейший алгоритм на базе полунаивного Байеса скрещенного с бубном побил тщательно спроектированную HMM.
Роль бубна правда осталась неясна.
:-)
Хотя специально курс PGM прошел — чтобы проверить, может я что-то не понимаю, вроде популярная техника.
Но имхо в генетике проблема не в этом.
Сходится она достаточно неплохо для серебряной пули.
Но если бы она могла эффективно делать декомпозицию пространства поиска на декартово произведение — уменьшая тем самым сложность — вот это было бы то, что надо.
И если бы она могла выделять и сохранять крупные структурные блоки для последующего использования — это тоже было бы отлично.
Сложный блок имеет больше вероятности развалиться при мутации или кроссовере.
И воэтому при приближении к решению — скорость падает, причем экспоненциально.
Я решал это «перенормировкой», выделением случайных блоков из особо успешных программ как новых генов.
Но решалось плохо и уже серебряной пулей не было.
Хотя возможно там есть еще потенциал.
Лет десять назад это было модно — искать такие расширения ГП.
Сейчас вроде поутихло.
PS
Варианты ГП кстати в проектировании железа очень часто используют.
Но там есть т.н. cartesian genetic programming, такой комбинаторный вариант.
Версий ГП вообще over 9000.
Если классы эквивалентности вырождены, то на экстремум ведет один единственный путь. Поэтому в таких случаях сходимость тяжелая.
Можно сказать, что ГП использует обобщенный вариант «атаки дней рождения» — стыкуя отдельные блоки.
Но если классы эквивалентности большие, то это еще ничего не значит.
В случае допустим добавления тригонометрии ГП начинает искать приближенные решения там, где есть точные и такие функции «отравляют» пространство поиска и сильно увеличивают его.
Поэтому я делаю обычно так — выбираю минимальный базис при широких правилах конструирования, так чтобы информация больше кодировалась в связях и перестановках, а не в единицах генома.
И кстати STGP (strongly type GP) лучше сходится.
Вообще теория ГП обычно останавливается на аналоге теоремы шим, которая говорит, что да, при сферических условиях в ваккуме алгоритм сходится максимум экспоненциально. Ну еще понятие эффективного фитнесса есть, но как его считать — не всегда ясно.
Хотя там очень много дополнительных условий, например термин «катастрофа ошибок», который знают биологи, в ГП я никогда не встречал.
Соответственно рулит голая эмпирика, что не может не сказываться на результатах.
Я использовал ГП много раз, в конце 90-х для торговых роботов, это было первое мое использование, но это были конечно игрушки, хотя и рабочие. Накатал свой вариант с блекджеком и шлюхами на С, наигрался.
Из последних (хотя там ближе к grammatical evolution — GE варианту — линейный геном на произвольной грамматике) вот например классификаторы малвари в форме decision tree были года три назад.
Интересно что на небольших сетах (4-5К) получившийся классификатор заруливал и CART и SVM.
Но как только сет начинал расти — все, качество падало или требовало огромных вычислительных ресурсов за счет уменьшения сходимости.
Использовал GP для набора рандомных атрибутов под decision tree классификаторы, очень неплохо выходило, но сильно долго, и много дубликатов получалось, а хорошую фитнесс функцию, учитывающую mutual information всех предыдущих атрибутов так и не удалось создать.
Ну и для генерации тестовых последовательностей использовал, типа фаззера или автоматического тестирования — перенаправляю вывод на вход тестируемой программы и запускаю все под valgrind'ом на недельку.
Потом смотрю логи, где упало или память утекла.
Но это тоже больше к GE уже относится.
Вообще имхо GP хорош когда надо найти приближенное приемлимое решение. По мере приближения к глобальному оптимуму сходимость падает и доводить до конца не всегда есть смысл.
Ну и есть интересное применение, когда фитнесс-функции не существует аналитически, например когда полезность определяется лайками пользователей.
Т.е. робот генерирует варианты решений, а люди их оценивают.
Сейчас я делаю свой вариант, который использует GP/GE частично, но основой является скорее GMDH схема, это работает пока только на классификаторах.
Но тут подробнее рассказать не могу — не исключено что будет реальный патент.
По первому вопросу — упрощение иногда используется (оператор edit) но обычно неэффективно.
Его есть смысл использовать когда результат уже получен и его надо упростить.
Кроме того часто используется parsimony pressure — добавление в фитнесс-функцию пенальти на сложность.
Ну и есть еще методы, прямо учитывающие MDL.
Отдельный вопрос — добро или зло code bloat
Иногда специально вставляют в исходный набор функций возможность формирования интронов.
Считается (но обоснований я не встречал), что в интронах накапливается генетический материал для скачкообразной макроэволюции.
Т.е. там хранятся последовательности, которые где-то когда-то пригодились, но пока не нужны и могут выстрелить позже.
По второму вопросу — даже введение дополнительных функций начинает сильно тормозить процесс, например если мы ищем полином, но добавили тригонометрию — сходимость падает, за счет ложных приближенных решений.
Но тут зависит от ландшафта.
Нам надо найти один единственный пример из многих классов эквивалентности.
И чем больше этот класс — тем больше вероятность его нахождения по разным траекториям.
Вообще попытки задать однозначное представление и свести классы эквивалентности к одному единственному экземпляру сразу снижают сходимость.
Это все однако не теория, а просто мой личный опыт использования таких систем.
Следует еще понимать, что для сложных задач ГП не проводит разделения пространства на независимые компоненты (хотя было много попыток в этом направлении, те же ADF или применение eCGA из ГА-мира).
И потому сходимость на очень сложных задачах плохая и сами задачи решать крайне затратно.
Кто сможет обойти это ограничение — получит большой приз.
в 90-х был любопытный вариант теста Тьюринга обладающий намного большей практической ценностью.
Сравнивали использование патентов, часть из которых были человеческие, часть — сгенерированные ИИ (в частности ГП).
ИИ кстати повторил многие человеческие решения.
Статейку писать сложно, у меня тут уже лежит недописанная статейка по искусственным иммунным системам, добавлять еще сверху в очередь задач бессмысленно.
Хроническая нехватка времени, увы.
Я думаю что по всему что я перечисли есть более простые и компактные источники информации, но советовать тут сложно, я учился по тому что привел а другого и не знаю.
Может кто посоветует что попроще.
Вроде в книжках по AI были описания разных типов ГП, но обычно они очень поверхностные и недостаточны для полной реализации.
Работаю, деньги за это получаю.
Собственно стало скучно просто применять очередной паттерн проектирования в очередной типовой задаче, вот в какой-то момент и мигрировал в эту область.
Ну и ленив я, зачем писать программы, когда программы могут написать все за меня.
:-)
По ссылкам — дальше много буков.
Во первых надо различать GP (генетическое программирование) и GA (генетические алгоритмы).
Ваш случай — GP и это самый интересный вариант.
Стоила на момент выхода очень дорого (по тем временам), а за ней вышли еще три тома по той же цене, поэтому бумажные версии мне дорога как память — экономил на обедах.
:-)
Быстрый поиск нашел ее на здесь
Надеюсь не умрет от хабраэффекта.
Первые 70 страниц можно пропустить.
Но можно и не пропускать.
Книгу весьма рекомендую, автор использует лисп-деревья, но это никак не влияет на читаемость, тем более что кода написанного человеком в книге вообще практически нет, только выращенный и только для примеров.
Но вся механика и все варианты реализации и экспериментов описаны отлично и очень детально.
Включая очень экзотические эксперименты.
Например эксперименты по самозарождению сексуальной эволюции из обрывков программ.
Или сколько процентов реальных патентов полученных роботами превосходят аналоги полученные человеком.
При этом книга совершенно не научпоп.
И относительно мало теории, но много практических рекомендаций, например магическое число 7 ввел именно он, метод половинной инициализации тоже его.
Т.е. для инженера практика, которого не интересует очередное доказательство теоремы, а интересно чтобы работало — самое то.
Я по ней сразу свою реализацию на С накатал с шахматами и балеринами.
Обычно по теоретическим монографиям такое редко получается — вылезают разные грабли, тут же описаны все нюансы и мелочи.
Но там описан только геном в виде дерева.
Т.е. есть набор функций (константы как частный случай) с фиксированным количеством аргументов, результат каждой функциии может быть аргументом другой функции — и так далее.
И кстати с линейным геномом, который более удобен и сегодня более популярен у меня никогда не получалось таких результатов как с деревом, оно более эффективно, тем более что я там тоже кое что допилил от себя.
В каком-то смысле книга уже устарела, но как база — я просто лучше не знаю.
И для многих практических задач ее хватает с головой.
Потом есть такой метод как AIMGP, на его основе делались первые автономные роботы-трейдеры, вот тут автор сделал такую конторку www.tradingsystemlab.com/introgeneticprograms.aspx
Когда она открылась, лицензия на одного клиента стоила емнип 60 килобаксов
Там суть похожа, но геном — это линейная последовательность ассемблерных команд, с рядом ограничений против зацикливания.
Т.е. примерно как у вас реализовано.
Ссылку не дам, искать надо по «Nordin AIMGP formal description», но в открытом доступе чего-то не нашел.
Есть еще такая штука как Grammatical Evolution.
Достаточно привлекательная, ей задается грамматика языка и она по ней строит правильные программы и проверяет их.
Но чего-то она у меня не показала столь хороших результатов как первый вариант, я ее тоже наваял и несколько пожалел о потраченном времени.
Есть в википедии даже.
Ну и есть over9000 модификаций, каждый придумывает свою версию, Cartesian GP (CGP), Stronlty typed GP (STGP), в общем там свои тараканы.
Это что касается собственно эволюции самих особей.
Но есть еще социальное взаимодействие особей — помимо сексуального, используемого GP.
Не все ж программам личной жизнью заниматься, общественная тоже должна быть.
И тут уже начинается вивариум от «меметических алгоритмов» до каких-то совершенно странных метаэвристических изысков.
И туда лучше без критического мышления и без подготовки не лезть, ибо туфты там много.
Nonlinear Dynamics of Crime and Violence in Urban Settings jasss.soc.surrey.ac.uk/15/1/2.html
Это с псевдокодами симуляции и картинками примерно как у вас.
Sympathy and Punishment: Evolution of Cooperation in Public Goods Game jasss.soc.surrey.ac.uk/14/4/20.html
Это почему общество основанное на кооперации не выживает если состоит из классов производителей и воров
Но выживает если появляются менты, наказывающие воров и получающие за это мзду от кооператоров.
:-)
PUSH достаточно серьезно проработан под эти задачи.
Например такая деталь — в обычном языке случайно сгенерированный цикл приведет к долгому выполнению программы или зависанию.
А в PUSH циклы реализуются по обходу стека.
Вообще достаточно интересный язык, я только первую версию ковырял, сейчас уже третья.
Выбор родителей для скрещивания делается так.
Берется N случайных особей и из них выбирается с лучшим фитнессом.
N по традиции обычно равно 7.
:-)
Скрещивание обычно делается одно- или двух-точечным кроссовером, в данной задаче мне кажется надо использовать оба.
Для одноточечного в ДНК каждого родителя выбирается случайная точка, которая делит ДНК на две части — голову и хвост. У двух потомков голова и хвост комбинируются так, чтобы они были от разных родителей, при этом голова остается головой и хвост остается хвостом.
Для двухточечного выбираются две точки в ДНК, обмен проходит аналогично — середина одного родительского ДНК вставляется в середину другого родителя.
Собственно это типовой вариант для генетического программирования.
Ну и повторюсь, может удастся убрать точечные мутации, заменив их на скрещивание со случайной ДНК.
Но это уже экспериментировать надо.
Если надо сылок накидать — пишите, но основные моменты были исследованы в схемах с tree-based genomes а у вас геном линейный, там есть отличия в параметрах.
Например для генома-дерева кроссовер совсем по другому выглядит и сходится быстрее.
Есть смысл примерить на эту задачу язык PUSH (видел реализацию на sf.net), он придуман как раз для таких вещей. И обязательно вставить кроссовер, обычный или двухточечный, организмы смогут обмениваться информацией, сходимость к фитнессу резко повышается. В некоторых вариантах мутации становятся вообще ненужными, т.к. имитируются кроссовером со случайным геномом.
Вообще это задачки для классического ГП. Ваш подход ближе к AIMGP или решению en.wikipedia.org/wiki/Santa_Fe_Trail_problem
А вот кстати один древний проект alife с 3д визуализацией www.framsticks.com/
куча видео, проект очень старый.
Когда-то вел список таких, интересовался темой, сейчас посмотрел — почти все дохлое.
Вообще тема древняя но по прежнему интересная.
Мне когда-то было интересно прикрутить генетику к вот этому: sodaplay.com/
Там организмы более живенькие.
А если сделать фенотип организма L-системой, то будет и живенько и красиво.
Лично я (лет десять назад) когда требовалась шаблонизация на С делал макросы на m4.
Этот пример выглядел бы так.
sums.h.m4:
dnl $Id$
m4_divert(0)
#pragma GCC dependency "sums.c.m4"
m4_divert(-1)
m4_define([sums_template],[
//! computes a:=a+b where a and b are two $1 arrays of length n
void sums_$1(int n, $1 *a, $1 *b);
])
m4_divert(0)
m4_include(sums.list)
sums.c.m4:
dnl $Id$
m4_divert(0)
#pragma GCC dependency "sums.c.m4"
m4_divert(-1)
m4_define([sums_template],[
void sums_$1(int n, $1 *a, $1 *b)
{
/* computes a:=a+b where a and b are two $1 arrays of length n */
int i;
for(i=0;i<n;i++) a[[i]]+=b[[i]];
}
])
m4_divert(0)
m4_include(sums.list)
Собственно я и сейчас так часто делаю, когда надо.
Имхо препроцессор С уж очень малофункционален, приходится делать так.
С другой стороны возможностей у такого подхода намного больше чем у темплайтов.
В конце концов, почему код должны писать программисты а не роботы-кодогенераторы?
:-)
А в сочетании с FCBF фильтром — вообще вещь классная.
Можно тупо брать случайные паттерны — все равно работает.
Причем далеко не только в sentiment analysis, практически любая классификация относительно длинных текстов.
Это эволюция до ГП.
Вместо кроссовера используется аггломерация.
Т.е. если программа находит паттерн в другой программе, то она инкорпорирует найденную в себя или выполняет ее в своем контексте.
Это намного менее жесткие требования чем кроссовер.
И более похожие на биологию и полимеризацию в химии.
А по ограничениям ГП, все верно.
В ГП много чего нет, инкрементное обучение или даже простой дрейф концепции для него практически не работает.
Но при этом работает в природе, где есть много не учитываемого ГП — тот же горизонтальный перенос генов.
С кроссовером кстати есь такой момент, что он нужен как дополнительная эвристика.
Стартуя с МонтеКарло можно получить на выходе репликатор.
Что при обеспечении передачи информации с шумом ниже шенноновского порога гарантирует мутации.
И стартует примитивную дарвиновскую динамику, дающую лучшую сходимость чем Монте-Карло.
Т.е. дарвиновская динамика получается с вероятностью 100%, если шум не нулевой и меньше порога.
Следующий этап — кроссовер или его аналоги связанные с взаимодействием экземпляров.
До него каждый был сам за себя и никак не взаимодействовал с соседями, разве что борясь за ресурс.
После — популяция меняет динамику.
И вот насколько закономерно возникает прямое взаимодействие геномов в дарвиновской системе без кроссовера — это вопрос.
И насколько закономерно это взаимодействие переходит в кроссовер, вообще насколько кроссовер является универсальным методом или частным случаем.
В живой системе есть ведь и восстановление поврежденных участков ДНК, а в ГП — нету таких аналогов.
На практике я часто использую ГП (точнее уже давно GE — grammatical evolution), как генератор гипотез.
До определенного предела он работает очень хорошо.
Дальше — надо про него забывать.
По поводу тьюринговской полноты агентов (безотносительно ГП) — тут вот такая штука.
Если мы ставим задачу оптимального агента в дискретном времени,, то получается что
1. Он должен рассчитать оптимальную стратегию за один тик смены внешних условий (хотя оптимальная стратегия может быть просто ожиданием завершения расчета с переносом действий в будущее).
2. Процесс расчета не должен занять памяти/ресурсов больше определенного конечного значения.
Т.е. по крайней мере эта часть агента (расчет стратегии) уже не может являеться алгоритмически полной просто в силу условий задачи.
Тут есть лазейка в том, что конечный автомат может выдавать на выходе текст, представляющий собой алгоритмически полную программу для UTM.
Но я бы ее не переоценивал.
Разумным кажется искать решение не в области алгоритмически полных программ а в области автоматов.
Но есть и промежуточное решение.
Вероятностные автоматы, недетерминированные языки и прочий вивариум, не вспоминаемый в приличном обществе. Причем вероятностные программы зачастую имеют лучшую эффективность в среднем, чем детерминированные.
А теорема Туракайнена об эквивалентности имеет место похоже не для всех объектов подобного класса, тут надо смотреть подробнее.
Я встречал точку зрения, что вероятностные автоматы и их аналоги не являются конструктивными объектами. Не то чтобы я понимал почему так, в споры интуиционистов и конструктивистов эмпирику лучше не лезть — побьют представители обоих партий.
:-)
Но я бы искал решение задачи именно в этой области — недетерминированных конечных вычислительных структур с гарантированным временем выполнения — автоматов, языков, каких-либо других объектов.
Да, разумеется, ГП этоне ГА.
Но насчет полноты — как сделать.
Язык PUSH, насколько я понимаю, полный — циклы там заменены на проход по списку.
И на практике он часто дает очень неплохое качество, например на небольших объемах он выводил мне деревья решений намного лучше чем C4.5 или CART.
Мне сложно представить себе нейронную сеть, которая вывела бы в символьной форме корни квадратного уравнения.
ГП это может.
Разумеется в ГП может быть получен любой алгоритм, так же как и любой алгоритм может быть получен методом Монте-Карло за бесконечное время.
:-)
Проблема в цене вопроса.
И сложностей там хватает, да.
Практически со всем согласен, на уровне интуиции, без доказательств, дедукция мне тоже кажется неэффективной.
Да и пробовали ее по всякому, ранний ИИ ее включал в разных вариантах, а результат не очень-то соответствовал.
Нельзя сказать что там проверили все, но чтобы найти новое придется перелопатить много.
В следующем году я планирую вернутся к генетическому программированию.
В этом подходе есть несколько позитивных моментов.
1. Тьюриговская полнота модели.
2. Не очень хорошее покрытие теорией, что дает возможность найти что-то новое, теоремы шим не хвататет для полного понимания процесса.
3. Тот простой факт, что природа со всеми ее ресурсами так же пошла по этому пути. И что даже живые нейронные сети появились из генома, не говоря уде об естественом интеллекте (что бы этот термин не означал).
4. Ряд интересных наблюдений в биологии.
Вот с последним пунктом достаточно весело получается.
Как ни странно, биологи знают то, что не учитывают математики.
В математической и инженерной литературе например рекомендуют параметры ГП просто подбирать (!).
А в биологических моделях предполагается что
1. Передача информации от родителя к потомку формирует канал связи с Шенноновским ограничением (если учитывать мутации как шум). Если частота мутаций перекрывает ширину канала, то популяция теряет информацию.
2. В живых системах практически всегда реальный объем передаваемой информации лежит очень близко к шенноновскому порогу, на уровне выше 99%.
Достаточно интересная точка зрения с частичным математическим анализом может быть найдена еще в одной старой книжке лауреата Нобелевки по химии: lib.mexmat.ru/books/9491
Причем там он показывает вариант решения самоорганизации с другой стороны, непривычной математикам, хотя и пользуясь матаппаратом в полной мере и решая проблему потенциально неограниченного накопления информации в живых системах.
А ведь проблема модулярности и неограниченного накопления информации в ГА и ГП есть, и стоит очень остро, реально ГП отлично создает структуры, а ГП с локальной оптимизацией — законченные модели.
Но — на относительно небольших объемах данных, уменьшая сходимость по мере приближения к оптимуму.
Если же заставить его выделять общие крупноблочные структуры, доказывать что эти структуры составляют полный базис и разрешить системе расти вверх, укрупняя блоки и накапливая информацию, то проблема «серебряной пули» может быть и решена.
Может быть и нет.
Но то, что есть сегодня в публикациях (eCGA, CGP, ADF и многие другие) работает на отдельных задачах. А более общего метода нет.
PS
В любом случае хочу пожелать вам удачи в вашем поиске.
Как эмпирик, я хорошо представляют какие задачи можно будет решать подобными инструментами, созданными теоретиками.
Это серьезная работа, которая стоит хорошего приза.
И он ликвидирует циклы типа for(i=0;i<bigvalue;i++) { expensive useless code }
которые приводят к резкой деградации производительности.
В императивном стиле вместо них есть команда push которая наполняет список и циклы по спискам, таким образом длинных бесполезных циклов практически нет.
В функциональном все вообще проще.
Но был один вариант ГП, который использовал side-effects и иногда срабатывал неплохо — с индексными переменными.
Для каждого экземляра задавался небольшой массив, обнуляемый в начале вычислений.
А среди функций были операторы read[i] и write[i,tree value], которые читали и писали значения в этот массив.
Кстати первыми популярными имплементациями ГП были программы на Лиспе, что не могло не наложить отпечаток на технологию.
Лисп достаточно практичен для ГП.
faculty.hampshire.edu/lspector/push3-description.html
faculty.hampshire.edu/lspector/push.html
sourceforge.net/projects/push-evolve/
PUSH дает возможность вместо использования циклов (которые в ГП сильно тормозят весь процесс) — проход по спискам, ну и еще много других плюшек.
Вот кстати пример такого подхода в анализе изображений.
cienciascomp.cicese.mx/evovision/olague_EC_MIT.pdf
Т.е. надо определить точки интереса на изображении, обычный программист возьмет openCV и успокоится.
Но если надо шагнуть дальше и глубже — то можно перелопатить литературу и найти разные варианты определения точек интереса.
А можно потратить время и сделать так как в статье — определить какое конкретное решение лучше всего подходит для конкретной задачи.
Вот другой вариант
citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.801
Написать процедуру кеширования на С.
Опять таки, в большинстве случаев все берут LRU, не особо задумываясь.
Но если скорость критична — то вот их решение, полученное GP на их конкретном потоке данных, будет намного лучше.
На другом потоке данных — возможно нет.
Хотя опять таки, как сделать.
Я сейчас как раз с изображениями работаю.
И вот допустим нам надо выделить особые точки и создать дескрипторы.
И на митинге один предлагает DoG, другой — SURF, третий ORB ну, как обычно.
В теории менеджмента один гуру должен встать и выбрать, сказав «да будет так», высосав решение из… скажем так, личного опыта.
Но можно построить грамматику, которая объединяет все предложения, определелить фитнесс-функцию и запустить ГП-поиск по всем вариантам решений, включая производные.
И получить объективный валидный результат, а не продукт, вытащенный из астрала медитирующим руководителем.
В ситуации, когда ложные решения стоят дорого, а область работы в тумане, такой подход сильно облегчает жизнь, несмотря на начальные затраты.
И самое главное, иногда такой подход позволяет наткнуться на неожиданное решение, которые бы при обычной работе осталось незамеченным.
Со статфизикой не все так просто.
В статфизике другой подход — постулируемая неизмеримость микроскопических состояний и поиск макроскопических значений.
В типовых задачах ИИ проблема обычно ставится по другому.
Это не исключает использование методов физики в ИИ (тот же Simulated Annealing), но задачи все-таки не пересекаются.
И не забываем, что ни статфизика ни неравновесная термодинамика не так хорошо описывают процессы в живых системах, как нам бы хотелось.
С другой стороны методы статфизики достаточно обоснованы и математизированы, а метаэвристический инструментарий — это эмпирика в чистом виде.
Поэтому использование метаэвристик всегда несет в себе некоторый риск.
По поводу MCMC — есть много моделей, которые «честнее», но все они несут в себе некоторые неявные предположения о структуре функции распределения вероятностей.
В отличие от ГА, хотя разумеется можно найти специальные ландшафты, где он будет мягко говоря неэффективен при специально подобранных параметрах.
Но обычная ситуация — десятки тысяч измерений, мультимодальное распределение о котором известно лишь то, что оно очень сложное и имеет миллионы локальных экстремумов.
Если мы говорим об MH алгоритме, то с гауссовым начальным распределением он дает очень маленькую вероятность больших скачков по сравнению с ГА и следовательно имеет больше шансов попасть в локальный экстремум.
Если же мы говорим об MCMC вообще — то он не накапливает информацию о сложных связях и о истории поиска (для чего в ГА нужны интроны) — потому он и Марковский.
Скорость накопления информации в ГА достигает экспоненциальной. Это верхняя граница и она определена schemata theorem.
Для MCMC, насколько я понимаю, такая скорость возможна лишь в очень специфичных условиях.
ГА мне до близкого знакомства казались шаманством чистой воды, попыткой списать код у бога, вырвав страницу из исходников, без особого понимания смысла. Особенно если учесть мой крайне неудачный на то время опыт работы с еще одной попыткой списывания — нейронными сетями.
И после некоторых тестовых применений мнение мое не изменилось.
Я например пытался решить задачу плотного размещения UML-графа на плоскости — не то, чтобы не работало, но, дорого, глупо и не гарантирует результат.
Но когда разобрался, и очертил границы применения — то понял, что метод вполне рабочий.
Просто это наиболее близкая штука к тому, что называется «серебряной пулей», а в соответствии с теоремой NFL серебряные пули обычно или стоят дорого или кучность плохая или можно прострелить себе ногу очень странным и неожиданным образом.
:-)
ГП кстати обладает некоторыми человеческими свойствами — он часто бывает лжив и ленив и ловит программиста на ошибках.
:-)
Рассмотрим простую проблему — слева набор прямоугольников, справа набор эллипсов, найти процедуру, отличающую первые от вторых.
Нейронки или SVM построят сложную модель, которая что-то будет делать.
ГП ответит просто, правильно и неожиданно — основным отличием является то слева или справа находится фигура.
:-)
ГП использует неожидаемые или неявные зависимости, которые программист может просто не заметить в постановке или в обычном для нашей индустрии упрощении.
В этом качестве я использую его наиболее часто.
Исследовать пространство поиска например, чтобы затем уже найти более оптимальную процедуру.
Получить наиболее адекватный набор атрибутов для текста или картинки.
А дальше можно и специальные методы применять, быстрые и предсказуемые.
Должен же где-то у программиста лежать бубен…
:-)
ГА делает тоже самое, но быстрее.
ГА ищет более «разумно», оно включает в себя локальные изменения (мутации) и дальние прыжки — кроссовер.
А так — то же самое, случайный поиск.
Поэтому ГА и является «серебряной пулей».
Ну или почти серебряной.
Сам похожи почти не занимался, обычно структура более или менее понятна, а робастность решений найденных ГП часто под вопросом.
По поводу Монте-Карло, я могу сказать, что я сравнивал, ГА/ГП лучше практически всегда.
Я рассматриваю ГА — как МК с улучшенной сходимостью (благодаря теореме шим).
А ГП — как ГА в тьюринговски полном пространстве.
Это достаточно условная иерархия, особенно если учесть большое количество модификаций этих алгоритмов.
С Марковскими моделями, как и с Байесовскими сетями есть одна проблема.
Они отлично работают если они уже построены.
:-)
А строить их автоматизированной процедурой обычно достаточно затратно на реальных данных, не говоря уже о BigData. Т.е. понятно что если это полный связный граф, в вырожденных случаях например дерева или линейного графа строится нормально.
То, что я видел реально работающего было обычно достаточно убого и строилось с учетом экспертных мнений, здравого смысла и других вариантов генератора случайных чисел.
Априорное знание — страшная вещь.
:-)
Собственно поэтому я с такими моделями практически и не работал, ну там Chou-Liu дерево максимум сделаю, так и то, CART часто давал лучшую аппроксимацию.
Вот кстати на старой винде их экспертная система помощи так работает — и что-то я мало встречал кому эта помощь помогла.
Плюс был опыт когда мой тупейший алгоритм на базе полунаивного Байеса скрещенного с бубном побил тщательно спроектированную HMM.
Роль бубна правда осталась неясна.
:-)
Хотя специально курс PGM прошел — чтобы проверить, может я что-то не понимаю, вроде популярная техника.
Но имхо в генетике проблема не в этом.
Сходится она достаточно неплохо для серебряной пули.
Но если бы она могла эффективно делать декомпозицию пространства поиска на декартово произведение — уменьшая тем самым сложность — вот это было бы то, что надо.
И если бы она могла выделять и сохранять крупные структурные блоки для последующего использования — это тоже было бы отлично.
Сложный блок имеет больше вероятности развалиться при мутации или кроссовере.
И воэтому при приближении к решению — скорость падает, причем экспоненциально.
Я решал это «перенормировкой», выделением случайных блоков из особо успешных программ как новых генов.
Но решалось плохо и уже серебряной пулей не было.
Хотя возможно там есть еще потенциал.
Лет десять назад это было модно — искать такие расширения ГП.
Сейчас вроде поутихло.
PS
Варианты ГП кстати в проектировании железа очень часто используют.
Но там есть т.н. cartesian genetic programming, такой комбинаторный вариант.
Версий ГП вообще over 9000.
Если классы эквивалентности вырождены, то на экстремум ведет один единственный путь. Поэтому в таких случаях сходимость тяжелая.
Можно сказать, что ГП использует обобщенный вариант «атаки дней рождения» — стыкуя отдельные блоки.
Но если классы эквивалентности большие, то это еще ничего не значит.
В случае допустим добавления тригонометрии ГП начинает искать приближенные решения там, где есть точные и такие функции «отравляют» пространство поиска и сильно увеличивают его.
Поэтому я делаю обычно так — выбираю минимальный базис при широких правилах конструирования, так чтобы информация больше кодировалась в связях и перестановках, а не в единицах генома.
И кстати STGP (strongly type GP) лучше сходится.
Вообще теория ГП обычно останавливается на аналоге теоремы шим, которая говорит, что да, при сферических условиях в ваккуме алгоритм сходится максимум экспоненциально. Ну еще понятие эффективного фитнесса есть, но как его считать — не всегда ясно.
Хотя там очень много дополнительных условий, например термин «катастрофа ошибок», который знают биологи, в ГП я никогда не встречал.
Соответственно рулит голая эмпирика, что не может не сказываться на результатах.
Я использовал ГП много раз, в конце 90-х для торговых роботов, это было первое мое использование, но это были конечно игрушки, хотя и рабочие. Накатал свой вариант с блекджеком и шлюхами на С, наигрался.
Из последних (хотя там ближе к grammatical evolution — GE варианту — линейный геном на произвольной грамматике) вот например классификаторы малвари в форме decision tree были года три назад.
Интересно что на небольших сетах (4-5К) получившийся классификатор заруливал и CART и SVM.
Но как только сет начинал расти — все, качество падало или требовало огромных вычислительных ресурсов за счет уменьшения сходимости.
Использовал GP для набора рандомных атрибутов под decision tree классификаторы, очень неплохо выходило, но сильно долго, и много дубликатов получалось, а хорошую фитнесс функцию, учитывающую mutual information всех предыдущих атрибутов так и не удалось создать.
Ну и для генерации тестовых последовательностей использовал, типа фаззера или автоматического тестирования — перенаправляю вывод на вход тестируемой программы и запускаю все под valgrind'ом на недельку.
Потом смотрю логи, где упало или память утекла.
Но это тоже больше к GE уже относится.
Вообще имхо GP хорош когда надо найти приближенное приемлимое решение. По мере приближения к глобальному оптимуму сходимость падает и доводить до конца не всегда есть смысл.
Ну и есть интересное применение, когда фитнесс-функции не существует аналитически, например когда полезность определяется лайками пользователей.
Т.е. робот генерирует варианты решений, а люди их оценивают.
Сейчас я делаю свой вариант, который использует GP/GE частично, но основой является скорее GMDH схема, это работает пока только на классификаторах.
Но тут подробнее рассказать не могу — не исключено что будет реальный патент.
Его есть смысл использовать когда результат уже получен и его надо упростить.
Кроме того часто используется parsimony pressure — добавление в фитнесс-функцию пенальти на сложность.
Ну и есть еще методы, прямо учитывающие MDL.
Отдельный вопрос — добро или зло code bloat
Иногда специально вставляют в исходный набор функций возможность формирования интронов.
Считается (но обоснований я не встречал), что в интронах накапливается генетический материал для скачкообразной макроэволюции.
Т.е. там хранятся последовательности, которые где-то когда-то пригодились, но пока не нужны и могут выстрелить позже.
По второму вопросу — даже введение дополнительных функций начинает сильно тормозить процесс, например если мы ищем полином, но добавили тригонометрию — сходимость падает, за счет ложных приближенных решений.
Но тут зависит от ландшафта.
Нам надо найти один единственный пример из многих классов эквивалентности.
И чем больше этот класс — тем больше вероятность его нахождения по разным траекториям.
Вообще попытки задать однозначное представление и свести классы эквивалентности к одному единственному экземпляру сразу снижают сходимость.
Это все однако не теория, а просто мой личный опыт использования таких систем.
Следует еще понимать, что для сложных задач ГП не проводит разделения пространства на независимые компоненты (хотя было много попыток в этом направлении, те же ADF или применение eCGA из ГА-мира).
И потому сходимость на очень сложных задачах плохая и сами задачи решать крайне затратно.
Кто сможет обойти это ограничение — получит большой приз.
Сравнивали использование патентов, часть из которых были человеческие, часть — сгенерированные ИИ (в частности ГП).
ИИ кстати повторил многие человеческие решения.
Хроническая нехватка времени, увы.
Я думаю что по всему что я перечисли есть более простые и компактные источники информации, но советовать тут сложно, я учился по тому что привел а другого и не знаю.
Может кто посоветует что попроще.
Вроде в книжках по AI были описания разных типов ГП, но обычно они очень поверхностные и недостаточны для полной реализации.
Собственно стало скучно просто применять очередной паттерн проектирования в очередной типовой задаче, вот в какой-то момент и мигрировал в эту область.
Ну и ленив я, зачем писать программы, когда программы могут написать все за меня.
:-)
По ссылкам — дальше много буков.
Во первых надо различать GP (генетическое программирование) и GA (генетические алгоритмы).
Ваш случай — GP и это самый интересный вариант.
Сам я его изучал по вот этой книжке.
Стоила на момент выхода очень дорого (по тем временам), а за ней вышли еще три тома по той же цене, поэтому бумажные версии мне дорога как память — экономил на обедах.
:-)
Быстрый поиск нашел ее на здесь
Надеюсь не умрет от хабраэффекта.
Первые 70 страниц можно пропустить.
Но можно и не пропускать.
Книгу весьма рекомендую, автор использует лисп-деревья, но это никак не влияет на читаемость, тем более что кода написанного человеком в книге вообще практически нет, только выращенный и только для примеров.
Но вся механика и все варианты реализации и экспериментов описаны отлично и очень детально.
Включая очень экзотические эксперименты.
Например эксперименты по самозарождению сексуальной эволюции из обрывков программ.
Или сколько процентов реальных патентов полученных роботами превосходят аналоги полученные человеком.
При этом книга совершенно не научпоп.
И относительно мало теории, но много практических рекомендаций, например магическое число 7 ввел именно он, метод половинной инициализации тоже его.
Т.е. для инженера практика, которого не интересует очередное доказательство теоремы, а интересно чтобы работало — самое то.
Я по ней сразу свою реализацию на С накатал с шахматами и балеринами.
Обычно по теоретическим монографиям такое редко получается — вылезают разные грабли, тут же описаны все нюансы и мелочи.
Но там описан только геном в виде дерева.
Т.е. есть набор функций (константы как частный случай) с фиксированным количеством аргументов, результат каждой функциии может быть аргументом другой функции — и так далее.
И кстати с линейным геномом, который более удобен и сегодня более популярен у меня никогда не получалось таких результатов как с деревом, оно более эффективно, тем более что я там тоже кое что допилил от себя.
В каком-то смысле книга уже устарела, но как база — я просто лучше не знаю.
И для многих практических задач ее хватает с головой.
Потом есть такой метод как AIMGP, на его основе делались первые автономные роботы-трейдеры, вот тут автор сделал такую конторку www.tradingsystemlab.com/introgeneticprograms.aspx
Когда она открылась, лицензия на одного клиента стоила емнип 60 килобаксов
Там суть похожа, но геном — это линейная последовательность ассемблерных команд, с рядом ограничений против зацикливания.
Т.е. примерно как у вас реализовано.
Ссылку не дам, искать надо по «Nordin AIMGP formal description», но в открытом доступе чего-то не нашел.
Есть еще такая штука как Grammatical Evolution.
Достаточно привлекательная, ей задается грамматика языка и она по ней строит правильные программы и проверяет их.
Но чего-то она у меня не показала столь хороших результатов как первый вариант, я ее тоже наваял и несколько пожалел о потраченном времени.
Есть в википедии даже.
Ну и есть over9000 модификаций, каждый придумывает свою версию, Cartesian GP (CGP), Stronlty typed GP (STGP), в общем там свои тараканы.
Это что касается собственно эволюции самих особей.
Но есть еще социальное взаимодействие особей — помимо сексуального, используемого GP.
Не все ж программам личной жизнью заниматься, общественная тоже должна быть.
И тут уже начинается вивариум от «меметических алгоритмов» до каких-то совершенно странных метаэвристических изысков.
И туда лучше без критического мышления и без подготовки не лезть, ибо туфты там много.
Хотя вот есть например такое издание как jasss.soc.surrey.ac.uk/JASSS.html специализирующееся на Agent Based Modeling (ABM)
Со своими фреймворками и симуляторами.
Например вас наверное заинтересует вот такая публикация jasss.soc.surrey.ac.uk/14/2/5.html
Названия статей там говорят сами за себя
Nonlinear Dynamics of Crime and Violence in Urban Settings
jasss.soc.surrey.ac.uk/15/1/2.html
Это с псевдокодами симуляции и картинками примерно как у вас.
A Virtual Laboratory for the Study of History and Cultural Dynamics
jasss.soc.surrey.ac.uk/14/4/19.html
Sympathy and Punishment: Evolution of Cooperation in Public Goods Game
jasss.soc.surrey.ac.uk/14/4/20.html
Это почему общество основанное на кооперации не выживает если состоит из классов производителей и воров
Но выживает если появляются менты, наказывающие воров и получающие за это мзду от кооператоров.
:-)
A Computational Model of Worker Protest
jasss.soc.surrey.ac.uk/14/3/1.html
В общем интересный такой журнальчик, после его статей можно свой оккупай начинать.
:-)
Тоже рекомендую.
Это я к тому привел, чтобы вы не думали, что то, что вы написали — просто игрушка.
На похожих игрушках просчитываются многие реальные серьезные вещи.
Например такая деталь — в обычном языке случайно сгенерированный цикл приведет к долгому выполнению программы или зависанию.
А в PUSH циклы реализуются по обходу стека.
Вообще достаточно интересный язык, я только первую версию ковырял, сейчас уже третья.
Берется N случайных особей и из них выбирается с лучшим фитнессом.
N по традиции обычно равно 7.
:-)
Скрещивание обычно делается одно- или двух-точечным кроссовером, в данной задаче мне кажется надо использовать оба.
Для одноточечного в ДНК каждого родителя выбирается случайная точка, которая делит ДНК на две части — голову и хвост. У двух потомков голова и хвост комбинируются так, чтобы они были от разных родителей, при этом голова остается головой и хвост остается хвостом.
Для двухточечного выбираются две точки в ДНК, обмен проходит аналогично — середина одного родительского ДНК вставляется в середину другого родителя.
Собственно это типовой вариант для генетического программирования.
Ну и повторюсь, может удастся убрать точечные мутации, заменив их на скрещивание со случайной ДНК.
Но это уже экспериментировать надо.
Если надо сылок накидать — пишите, но основные моменты были исследованы в схемах с tree-based genomes а у вас геном линейный, там есть отличия в параметрах.
Например для генома-дерева кроссовер совсем по другому выглядит и сходится быстрее.
Вообще это задачки для классического ГП. Ваш подход ближе к AIMGP или решению en.wikipedia.org/wiki/Santa_Fe_Trail_problem
А вот кстати один древний проект alife с 3д визуализацией
www.framsticks.com/
куча видео, проект очень старый.
Когда-то вел список таких, интересовался темой, сейчас посмотрел — почти все дохлое.
Вообще тема древняя но по прежнему интересная.
Мне когда-то было интересно прикрутить генетику к вот этому: sodaplay.com/
Там организмы более живенькие.
А если сделать фенотип организма L-системой, то будет и живенько и красиво.
Этот пример выглядел бы так.
sums.h.m4:
sums.c.m4:
А вот строка для мейкфайла:
Ну и файл с определениями:
sums_template(float)
sums_template(double)
sums_template(int)
Собственно я и сейчас так часто делаю, когда надо.
Имхо препроцессор С уж очень малофункционален, приходится делать так.
С другой стороны возможностей у такого подхода намного больше чем у темплайтов.
В конце концов, почему код должны писать программисты а не роботы-кодогенераторы?
:-)
Поменьше халоймеса в коде и побольше гешефта с проектов!
Можно тупо брать случайные паттерны — все равно работает.
Причем далеко не только в sentiment analysis, практически любая классификация относительно длинных текстов.
citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.7571
Это эволюция до ГП.
Вместо кроссовера используется аггломерация.
Т.е. если программа находит паттерн в другой программе, то она инкорпорирует найденную в себя или выполняет ее в своем контексте.
Это намного менее жесткие требования чем кроссовер.
И более похожие на биологию и полимеризацию в химии.
А по ограничениям ГП, все верно.
В ГП много чего нет, инкрементное обучение или даже простой дрейф концепции для него практически не работает.
Но при этом работает в природе, где есть много не учитываемого ГП — тот же горизонтальный перенос генов.
С кроссовером кстати есь такой момент, что он нужен как дополнительная эвристика.
Стартуя с МонтеКарло можно получить на выходе репликатор.
Что при обеспечении передачи информации с шумом ниже шенноновского порога гарантирует мутации.
И стартует примитивную дарвиновскую динамику, дающую лучшую сходимость чем Монте-Карло.
Т.е. дарвиновская динамика получается с вероятностью 100%, если шум не нулевой и меньше порога.
Следующий этап — кроссовер или его аналоги связанные с взаимодействием экземпляров.
До него каждый был сам за себя и никак не взаимодействовал с соседями, разве что борясь за ресурс.
После — популяция меняет динамику.
И вот насколько закономерно возникает прямое взаимодействие геномов в дарвиновской системе без кроссовера — это вопрос.
И насколько закономерно это взаимодействие переходит в кроссовер, вообще насколько кроссовер является универсальным методом или частным случаем.
В живой системе есть ведь и восстановление поврежденных участков ДНК, а в ГП — нету таких аналогов.
На практике я часто использую ГП (точнее уже давно GE — grammatical evolution), как генератор гипотез.
До определенного предела он работает очень хорошо.
Дальше — надо про него забывать.
По поводу тьюринговской полноты агентов (безотносительно ГП) — тут вот такая штука.
Если мы ставим задачу оптимального агента в дискретном времени,, то получается что
1. Он должен рассчитать оптимальную стратегию за один тик смены внешних условий (хотя оптимальная стратегия может быть просто ожиданием завершения расчета с переносом действий в будущее).
2. Процесс расчета не должен занять памяти/ресурсов больше определенного конечного значения.
Т.е. по крайней мере эта часть агента (расчет стратегии) уже не может являеться алгоритмически полной просто в силу условий задачи.
Тут есть лазейка в том, что конечный автомат может выдавать на выходе текст, представляющий собой алгоритмически полную программу для UTM.
Но я бы ее не переоценивал.
Разумным кажется искать решение не в области алгоритмически полных программ а в области автоматов.
Но есть и промежуточное решение.
Вероятностные автоматы, недетерминированные языки и прочий вивариум, не вспоминаемый в приличном обществе. Причем вероятностные программы зачастую имеют лучшую эффективность в среднем, чем детерминированные.
А теорема Туракайнена об эквивалентности имеет место похоже не для всех объектов подобного класса, тут надо смотреть подробнее.
Я встречал точку зрения, что вероятностные автоматы и их аналоги не являются конструктивными объектами. Не то чтобы я понимал почему так, в споры интуиционистов и конструктивистов эмпирику лучше не лезть — побьют представители обоих партий.
:-)
Но я бы искал решение задачи именно в этой области — недетерминированных конечных вычислительных структур с гарантированным временем выполнения — автоматов, языков, каких-либо других объектов.
Но насчет полноты — как сделать.
Язык PUSH, насколько я понимаю, полный — циклы там заменены на проход по списку.
И на практике он часто дает очень неплохое качество, например на небольших объемах он выводил мне деревья решений намного лучше чем C4.5 или CART.
Мне сложно представить себе нейронную сеть, которая вывела бы в символьной форме корни квадратного уравнения.
ГП это может.
Разумеется в ГП может быть получен любой алгоритм, так же как и любой алгоритм может быть получен методом Монте-Карло за бесконечное время.
:-)
Проблема в цене вопроса.
И сложностей там хватает, да.
Да и пробовали ее по всякому, ранний ИИ ее включал в разных вариантах, а результат не очень-то соответствовал.
Нельзя сказать что там проверили все, но чтобы найти новое придется перелопатить много.
В следующем году я планирую вернутся к генетическому программированию.
В этом подходе есть несколько позитивных моментов.
1. Тьюриговская полнота модели.
2. Не очень хорошее покрытие теорией, что дает возможность найти что-то новое, теоремы шим не хвататет для полного понимания процесса.
3. Тот простой факт, что природа со всеми ее ресурсами так же пошла по этому пути. И что даже живые нейронные сети появились из генома, не говоря уде об естественом интеллекте (что бы этот термин не означал).
4. Ряд интересных наблюдений в биологии.
Вот с последним пунктом достаточно весело получается.
Как ни странно, биологи знают то, что не учитывают математики.
В математической и инженерной литературе например рекомендуют параметры ГП просто подбирать (!).
А в биологических моделях предполагается что
1. Передача информации от родителя к потомку формирует канал связи с Шенноновским ограничением (если учитывать мутации как шум). Если частота мутаций перекрывает ширину канала, то популяция теряет информацию.
2. В живых системах практически всегда реальный объем передаваемой информации лежит очень близко к шенноновскому порогу, на уровне выше 99%.
Достаточно интересная точка зрения с частичным математическим анализом может быть найдена еще в одной старой книжке лауреата Нобелевки по химии: lib.mexmat.ru/books/9491
Причем там он показывает вариант решения самоорганизации с другой стороны, непривычной математикам, хотя и пользуясь матаппаратом в полной мере и решая проблему потенциально неограниченного накопления информации в живых системах.
А ведь проблема модулярности и неограниченного накопления информации в ГА и ГП есть, и стоит очень остро, реально ГП отлично создает структуры, а ГП с локальной оптимизацией — законченные модели.
Но — на относительно небольших объемах данных, уменьшая сходимость по мере приближения к оптимуму.
Если же заставить его выделять общие крупноблочные структуры, доказывать что эти структуры составляют полный базис и разрешить системе расти вверх, укрупняя блоки и накапливая информацию, то проблема «серебряной пули» может быть и решена.
Может быть и нет.
Но то, что есть сегодня в публикациях (eCGA, CGP, ADF и многие другие) работает на отдельных задачах. А более общего метода нет.
PS
В любом случае хочу пожелать вам удачи в вашем поиске.
Как эмпирик, я хорошо представляют какие задачи можно будет решать подобными инструментами, созданными теоретиками.
Это серьезная работа, которая стоит хорошего приза.