Алгоритм интеллекта

Напомню вкратце суть генетического алгоритма. Есть такой метод - случайный поиск. Генерируется случайное решение, оценивается, потом случайно изменяется. Если результат стал лучше, решение запоминается. После чего цикл повторяется. Используется такой метод, когда непонятно как вычислять решение "по науке". Получается очень долго. А если завести параллельно большое количество разных решений? Для тех из них, которые прогрессируют в успехе (качество решений хорошее или повышается со временем или по сравнению с "соседями"), создаём экземпляры-копии, и изменяем (случайно) эти экземпляры потихоньку. Те из решений, которые на фоне остальных выглядят плохо, или не повышают качество решения со временем, те экземпляры мы подвергаем всё большим случайным изменениям или вовсе удаляем, а на их место ставим вновь сгенерированные случайные решения. Естественно, плохие решения имеют меньшую вероятность быть размноженными. Есть ещё одна операция (тоже применяется случайно), когда от двух разных решений откусывается по кусочку, и эти два кусочка склеиваются в новое решение. Называется скрещивание. Чем лучше решение, тем больше вероятность, что оно подвергнется скрещиванию. В итоге можно скачком получить решение, которое имеет лучший результат, чем оба его родителя. Но может случиться и наоборот. Если решение получилось лучше, то оно в дальнейшем размножается, если хуже - то такое решение, с большой вероятностью удаляется. Наиболее эффективен такой поиск, когда мы знаем структуру решения, и применяем операции случайного изменения (мутации) и скрещивания не кромсая решение по битикам, а с учётом этой структуры.

За счёт того, что решения не просто ведутся параллельно, а постоянно сравниваются и обмениваются друг с другом, такой поиск выдаёт фантастический скачок производительности по сравнению со случайным поиском и оказывается способным перемалывать самые трудные задачи. Казалось бы, типичное случайное решение в среднем ничего интересного из себя не представляет, и эффективность его крайне низка. Но стоит только множеству решений начать взаимодействовать между собой, как нетипичный результат (хорошее решение) быстро появляется и прогрессирует. Это к слову о том, что Пенроуз советует изучать хаотические процессы в среднем, изучать типичные случаи, упирая на то, что кроме типичных случаев они ничего не могут породить, что, конечно, несправедливо. Такой поиск представляет собой иллюстрацию принципа масштаба, один из типичных гармонизирующихся процессов.

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

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

К сожалению, дальше состояние дел по этой теме я не отслеживал, и больше ничего рассказать не могу. Желающие могут поискать по словосочетанию "genetic programming". Поэтому же, дальше мы выходим за пределы изученного и вступаем в область предположений. Вполне возможно, что-то из этих предположений уже известно, и я занимаюсь изобретением велосипеда. Но всё равно интересно.:)

Посмотрим, какие свойства у программ, полученных с помощью генетического алгоритма. Такие программы могут иметь в себе бесконечные (или очень длинные) циклы, поэтому оценка пригодности должна выкидывать программы, которые работают очень долго, не выдавая видимого результата. Ход, в общем-то, правильный, но он, к сожалению, выкидывает потенциально интересные длинные логические цепочки (как их учесть ещё будет). Дальше, при скрещивании ветви программы будут бездумно кромсаться, порождая зачастую бессмысленный код. И если для простой задачи это не такая уж проблема, то для задач более сложных, получится или большое количество негодных решений, потому что самое небольшое изменение способно напрочь испортить работоспособность программы, и вероятно, в итоге толку будет мало. Или в программе будет большое количество избыточных веток, "хлама", который будет невообразимым образом сочетаться друг с другом в правильное решение. Этот "хлам" в процессе эволюции научиться переживать вносимые изменения, таким образом, чтобы изменение не ломало фатально программу. Но в любом случае, нам придётся распрощаться с идеей "тонких" логических цепочек, которые бы представляли собой такие же чёткие программы, какие пишет человек. То, что получится в результате автоматического написания программ, будет далеко от таких цепочек. Конечно, появятся алгоритмы data mining, которые смогут этот противоречивый ворох минимизировать в ясный алгоритм, но этот ясный алгоритм, для дальнейшего совершенствования в автоматическом режиме, надо будет вернуть обратно в "размазанный" вид (или размазывание произойдёт само, в процессе дальнейшего обучения). И есть подозрение, что вытащенный с помощью data mining-а алгоритм, будет иметь более узкий "кругозор" чем его исходный, "размазанный" вариант. Похожее явление описывалось в предыдущих частях про распознавание образов.

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

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

Вот и получилась самая простая версия искусственного интеллекта, вполне применимая в разных играх, в т.ч. компьютерных, в экспертных системах и системах управления процессами. Подойдёт такое и для моделирования black-box процессов с внутренней памятью, вместо Марковских моделей (это такие процессы, у которых видно, что на входе и выходе, но внутреннее состояние и процессы непонятны, чёрный ящик по-нашему).

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