Предисловие
На написание статьи вдохновили две публикации:
Захотел изложить свои мысли и свой взгляд на этот вопрос именно как практик от программирования «с математическим бэкграундом». Это будет повествование «на пальцах». Специалистом в генной инженерии не являюсь и сужу по поверхностным описаниям механизмов функционирования живых клеток и ДНК.
Возможно оно и к лучшему. Первым впечатлением от «Обзора методов эволюции нейронных сетей» было таким: «достаточно сложно написано, а деталей практической реализации не нашел или пропустил». Пришлось копать дальше. В частности, нашел описание кроссинговера — побитовое, о котором в упомянутой выше публикации сказано:
"… т.к. использование стандартных бинарных операторов, как правило, приводит к частому появлению нежизнеспособных решений". В моем понимании это звучало бы так: «такой метод не даст ожидаемый результат скрещивания, а породит мутанта».
Почитав такие же описания реализаций некоторых ключевых моментов ГА, решил изложить свое видение проблемы.
Кроссинговер
Первое, с чем я не согласился — это реализация кроссинговера через побитовую операцию. Для меня такой метод является неприемлемым как минимум по двум причинам:
- неустойчивый результат;
- неуправляемая мутация.
Интуитивно я понимал, что с очень большой вероятностью такой подход даст плохой результат, во всяком случае для задач автоматического управления. Представьте, если корень или полюс одной системы автоматического управления (САУ) будет побитово «пересечен» с соответствующим параметром другой САУ. В результате почти наверняка получится неустойчивая САУ, т.к. для ее устойчивости требуется достаточно тонкая настройка коэффициентов дифференциальных уравнений. А для этой области стабильность регулятора и четкий контроль его параметров очень важны.
Мое понимание механизма кроссинговера таково. На определенной стадии деления клетки молекулы ДНК из двух гомологичных хромосом (с одной и той же последовательностью аллельных генов) сближаются друг с другом, образуя двойную спираль (тут я не имею в виду спиральную структуру самой ДНК). Появляется вероятность, что в определенном месте этой спирали совпадут «начала» двух аллельных генов (гены, отвечающие за одно и то же свойство; могу ошибаться) и также существует вероятность, что в этом месте произойдет слипание двух молекул, а после «разлипания» с вероятностью 50% две молекулы «обменяются хвостами». Далее, видимо, только одна из хромосом будет участвовать в развитии новой особи. Тут я недостаточно четко представляю всю механику.
Таким образом, кроссинговер в моем понимании передает целую группу генов от одной хромосомы в другую. С этим процессом даже связаны исследования по созданию карт ДНК. В основе лежит вывод из описания механизма кроссинговера: гены, близкие друг к другу в линейной структуре ДНК с большей вероятностью переходят от родителя к потомству совместно, а гены, расположенные далеко друг от друга, часто разделяются при репликации ДНК (кажется это происходит на стадии митоза клетки). Поэтому я считаю, что точка соприкосновения для кроссинговера должна искаться не побитово, а находиться между генами. В ДНК для этого имеются «интроны». Иначе у «черной мухи» и «синей мухи» получился бы ребенок с копытами.
Гены
Смысл и содержание генов в зависимости от поставленной задачи могут быть различными. В ТАУ под геном может пониматься некий высокоуровневый параметр качества регулирования (например, корень характеристического уравнения передаточной функции, полоса пропускания, частота среза, перерегулирование и т.д.) и правило, по которому этот параметр отразится на конечной реализации САУ. Если рассматривать задачу создания игры, в которой мир, персонажи и геймплей завязаны на генетические алгоритмы (про это ниже), то картина становится еще красивее. Тут гены должны иметь пакетную структуру в которой кодируются тип этого гена — за что он отвечает (например, это ген для формирование скелета аватара или ген формирования рельефа локации, или что-то другое), что этот ген создает (поведенческое правило, инструкцию по генерации структуры чего либо, правило взаимосвязи каких-либо характеристик объекта между собой и пр.), условные блоки и значения параметров. Получается своеобразная иерархическая кодировка генов. В соответствии с этой схемой мы получаем гены различной длины, являющиеся массивами чисел, в общем случае массив байт, хотя это и не обязательно. Мне такая схема кажется наиболее приближенной к реальности (к природе). Вместо массива байт, ген можно представить в виде структуры, содержащей энумераторы (C#, enum), строки и дробные числа.
Еще хочется оговориться про особенности работы ДНК в случае двуполого ( а может и о трех-, четырех- и т.д.) размножения, а также про «доминантные» и «рецессивные».
Судя по имеющейся информации, есть хромосомы, которые передаются рождаемой особи в зависимости от пола. Если пол зачатой особи будет «женским», то передается одна хромосома, а если мужским, то другая. Как выбирается набор генов, содержащийся в «половых» хромосомах, для меня неважно. Да и сама эта идея к области ТАУ трудно применима. Теоретически я могу использовать этот механизм для адаптации регуляторов под меняющиеся условия: поменялся режим движения (у спорткаров есть, к примеру, режим города и спортивный) — меняю «пол» особи САУ. Но потребуется хранить настройки и предусмотреть особый алгоритм перехода с одного регулятора на другой.
В играх такой механизм очень даже хорошо применим. Интересно реализовать «смену пола» и посмотреть на метаморфозы, происходящие с персонажем. В принципе, неочень сложно и составить список генов, которые будут зависеть от пола. Важно будет обеспечить межполовой баланс. Таким образом в игре можно будет отказаться от «расизма», играя межполовыми различиями. Но тогда игровой мир будет очень сильно отличаться от нашего (нет рас и имеется 3, 4, 5 и/или более полов). Кому-то понравится, а кому-то нет.
Про доминантные и рецессивные гены. Принято считать, что рецессивные гены как бы спят внутри ДНК (их в каждой из хромосом две от каждого из родителей), т.е. если от отца получен доминантный ген, то материнский спит. Оказывается это верно не всегда. При исследованиях генетических заболеваний выяснено, что мутированные рецессивные гены с паталогией все равно оказывают воздействие на организм, но намного меньшее, чем в случае их доминирования. Для области разработки игр это позволит заложить в ядро игры условия, при которых рецессивные гены будут участвовать в модификации геймплея по принципу генетических заболеваний, передающихся по мужской или женской линии (передающихся половым путем, — шутка юмора).
Практическое использование
ТАУ и фильтрация шумов
Своя рубашка ближе к сердцу. Я занимаюсь исследованиями в области цифровой обработки навигационной информации в условиях высокой интенсивности шумов в датчиках. Поэтому главными вопросоми к ГА у меня являются следующие: «возможно ли их практическое применение в сфере ТАУ» и «насколько выгодным будет их использование»?
Существует подход для решения проблемы «стохастического оценивания» измеряемых параметров через создание измерительных блоков с информационной избыточностью [1] (количество датчиков больше числа измеряемых параметров). В таких случаях, к примеру, можно применять многомерный вариант фильтра Калмана (или наблюдающее устройство идентификации Льюиньбергера) для обработки сигналов, поступающих от датчиков. И тут требуется подобрать (в случае НУИ Льюиньергера) или определить (в случае ФК) математическую модель динамического объекта (модель датчика). Помимо параметров модели датчиков нужна еще и информация об измерительном шуме и помехах динамического процесса (внутренних шумах датчиков) — дисперсии и ковариации шумов. Все эти параметры определяют эффективность фильтрации и итоговую полосу пропускания измерительной системы. Существуют различные методы выбора этих параметров. Сложнее всего подобрать дисперсии и ковариации внутренних шумов датчиков. Их измерить нельзя.
А что если применить ГА для подбора оптимальных значений? Тут есть сложности. Во-первых, эти алгоритмы требуют серьезных вычислительных мощностей. По сути это перебор всевозможных комбинаций значений. Так будучи студентом я подбирал параметры передаточной функции, т.е. приводил решение к ответу. Знал примерно как должна выглядеть АЧХ, оставалось подобрать в MatLAb'е параметры, которые мне эту АЧХ «нарисуют». Но САУ — это бортовой вычислитель, малопотребляющий и не очень-то производительный компьютер, а то и вообще просто совокупность частотных фильтров на операционных усилителях. Во-вторых, реализованная в виде БЦЭВМ САУ, постоянно производит вычисление управляющих воздействий. Если ее мощность невелика, то некогда будет «играть в жизнь». Получается, что тут ГА неприменимы?
Хочется верить, что применимы. Параметры подвижного объекта меняются медленно во времени. Если в БЦЭВМ встроена операционная система с многопоточностью, то можно запустить ГА в фоновом режиме. Возможно вообще эти параметры САУ потребуется один раз вычислить — при ее калибровке в лабораторных условиях или при полунатурных испытаниях. Дополнительно можно ГА скомплексировать с каким-либо алгоритмом минимизации функций многих переменных (например, градиентные методы [2]), с помощью которых можно симулировать процесс самообучения или адаптации между стандартными процедурами ГА: селекция, мутация, кроссинговер.
Однако все равно остается одна серьезная проблема. Шумы — стохастические процессы. Поэтому трудно что-либо кроме устойчивости регулятора и замкнутой системы оценивать аналитически. А статистический подход подразумевает работу с большими выборками данных. В результате вычисление фитнесс-функции приводит опять же к большому количеству вычислений.
Однажды мне приходилось моделировать процесс конденсации газа на зеркальную поверхность и определять параметры параболических дифференциальных уравнений с частными производными через оптимизацию функционала методом наискорейшего спуска. В этом градиентном методе требуется вычислять на каждом шаге моделирования производные по всем направлениям (частные производные). Т.к. аналитического решения уравнения у меня не было, то приходилось определять производные численно. При этом процесс распределен по вертикальной оси, а численная устойчивость требовала разбить этот отрезок на достаточно большое количество сегментов. В результате требовалось очень большое количество вычислений. Спасала очень малая скорость течения процесса. В области автоматического управления такого спасения нет.
Индустрия развлечений
Это можно назвать моим хобби. Очень интересно наблюдать за самоорганизацией смоделированного искусственного мира. В публикации [5] наткнулся на упоминание одной игры на космическую тему, в которой оружие эволюционирует с помощью ГА на основе статистики использования «моделей-предков». А что, если применить ГА и принципы клеточных автоматов в области MMORPG в целом? Затея масштабная, но крайне интересная. Если удастся все или большинство аспектов геймплея завязать на ГА, то мы получим одно глобальное правило (уравнение), описывающее вселенную. Пусть игровую, но все же…
Как я это вижу на уровне концепции? Игрок создает аватара с некоторым базовым набором генов. Каждый ген имеет иерархическую пакетную структуру и используется при генерации персонажа, а, возможно и локаций. В генах записаны правила, по которым для определенных уже сгенерированных узлов создаются все новые и новые узлы. Под узлами тут можно понимать что угодно (см. описание процедуры генерации графов в [3]). Вот пример:
1. Ген, отвечающий за тип скелета персонажа: позвоночный, беспозвоночный и пр, будет применен для какого-то базового (зачаточного?) состояния. От этого гена зависит количество (число «мест прикрепления» конечностей) и вид конечностей (у осьминого-подобных персонажей будут щупальцы, у позвоночных — лапы/руки/ноги с костями и т.д.).
2. Ген конечностей — применяется для скелетов определенного типа (скелет, у которого имеются «placeholder'ы» для конечностей). В этом гене, к примеру, могут содержаться описания базовых параметров: относительная длина/толщина/прочность и т.д.
3. Ген мускулатуры — по нему создается мышечная система персонажа.
4. И так далее…
Недавно узнал о проекте Google, который здесь кстати упомянуть: Google Body Browser.
По этой концепционной модели можно реализовать внешнюю, анимационную часть игры. Вот появился на экране скелет. Вот он обрастает мясом, нервами, сосудами и т.п. Красиво и интересно! Внутри эта концепция выливается в нечто другое.
Имеется некоторая начальная система свойств. Также в виде генов задаются общие правила, по которым одни свойства влияют на другие, т.е. ненаправленная нейросеть, граф и т.д. По этим правилам и текущему значению ДНК персонажа начинается генерация конкретных его характеристик в игре: очки жизни, сила, ловкость, скорость, интелект и пр. На те же ГА завязывается и эволюция персонажа.
"Получил много экспериенса и заработал левелап" (Властелин Колец, в переводе от Гоблина)…
и вместо распределения перков игрок выбирает автоэволюцию или вручную правит ДНК, которая при этом открыта не полностью и расшифрована частично (игра в рулетку). Тут можно применить принцип, на котором основаны «NetHack»-подобные игры. При создании персонажа создается новый случайный набор соответствий между конкретным геном и соответствующими ему кодами типа, подтипа и пр. В начале игры пользователь не знает ничего о ДНК своего аватара. Постепенно (с каждым уровнем) игрок узнает все больше информации о ДНК. Смерть аватара должна быть перманентной, но аватаров может быть несколько. При этом можно по имеющейся записи ДНК (частичной) попытаться снова сгенерировать любимого «тамагоча».
В конечном итоге некоторым набором генов будут определяться характеристики персонажа (упомянуты выше), реакция его на определенные события и условия (другой персонаж рядом — свой он или чужой; «запах» другого персонажа — симпатия или агрессия и т.д.), особенности его поведения — характер и многое другое. Если все эти характеристики будут связаны друг с другом через гены в ДНК достаточно «сбалансированным» алгоритмом, то удастся создать интересный геймплей.
Заключение
В данной статье изложены лишь мои мысли. Явных результатов и категоричных выводов не представлено. Что-то из этого мне предстоит использовать, а что-то может оказаться «пустышкой». Возможно это выльется в создание того или иного программного продукта. Пока говорить рано. Но я хочу отреагировать на послание типа «может кто-то из читателей продолжит исследования данного вопроса». В этом духе выразился автор одной из упомянутых статей. Мне эта тема достаточно интересна и кажется весьма перспективной. Пространства для творчества здесь очень много.
Спасибо за внимание! Ваши вопросы, комментарии…
Список литератры
1. Водичева Л.В. Повышение надежности и точности бесплатформенного инерциального измерительного блока при избыточном количестве измерений / Л.В. Водичева // Гироскопия и навигация. 1997. № 1. С. 55-67.
2. http://www.nsc.ru/rus/textbooks/akhmerov/mo/3.html
3. Живые графы
4. Обзор методов эволюции...
5. habrahabr.ru/blogs/games/63967
6. habrahabr.ru/blogs/popular_science/84529
