Концепции практического использования генетических алгоритмов

Предисловие


На написание статьи вдохновили две публикации:

Захотел изложить свои мысли и свой взгляд на этот вопрос именно как практик от программирования «с математическим бэкграундом». Это будет повествование «на пальцах». Специалистом в генной инженерии не являюсь и сужу по поверхностным описаниям механизмов функционирования живых клеток и ДНК.
Возможно оно и к лучшему. Первым впечатлением от «Обзора методов эволюции нейронных сетей» было таким: «достаточно сложно написано, а деталей практической реализации не нашел или пропустил». Пришлось копать дальше. В частности, нашел описание кроссинговера — побитовое, о котором в упомянутой выше публикации сказано:
"… т.к. использование стандартных бинарных операторов, как правило, приводит к частому появлению нежизнеспособных решений". В моем понимании это звучало бы так: «такой метод не даст ожидаемый результат скрещивания, а породит мутанта».
Почитав такие же описания реализаций некоторых ключевых моментов ГА, решил изложить свое видение проблемы.

Кроссинговер


Первое, с чем я не согласился — это реализация кроссинговера через побитовую операцию. Для меня такой метод является неприемлемым как минимум по двум причинам:
  • неустойчивый результат;
  • неуправляемая мутация.

Интуитивно я понимал, что с очень большой вероятностью такой подход даст плохой результат, во всяком случае для задач автоматического управления. Представьте, если корень или полюс одной системы автоматического управления (САУ) будет побитово «пересечен» с соответствующим параметром другой САУ. В результате почти наверняка получится неустойчивая САУ, т.к. для ее устойчивости требуется достаточно тонкая настройка коэффициентов дифференциальных уравнений. А для этой области стабильность регулятора и четкий контроль его параметров очень важны.
Мое понимание механизма кроссинговера таково. На определенной стадии деления клетки молекулы ДНК из двух гомологичных хромосом (с одной и той же последовательностью аллельных генов) сближаются друг с другом, образуя двойную спираль (тут я не имею в виду спиральную структуру самой ДНК). Появляется вероятность, что в определенном месте этой спирали совпадут «начала» двух аллельных генов (гены, отвечающие за одно и то же свойство; могу ошибаться) и также существует вероятность, что в этом месте произойдет слипание двух молекул, а после «разлипания» с вероятностью 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
Поделиться публикацией

Комментарии 16

    +1
    >Явных результатов и категоричных выводов не представлено
    Почему тогда топик называется «Практическое использование генетических алгоритмов»???
    Мне было интересно прочитать практические примеры от первого лица, а вы так просто вводите людей в заблуждение
      +1
      Предполагается продолжение. Ваш довод резонный. Сменю название, чтоб стало сразу ясно. Спасибо.
        0
        я наслушавшись рекламы 10 лет назад не мог понять, почему я не догоняю как генетический алгоритм куда-то применить.

        Но удалось увидеть одну реализацию — вот нашел… пока не начали в этом чуде баги фиксить. Написал бы человек перебор какой-то с отсечениеями обычными — это не круто. А так взял «намутировал — так же в книгах пишут», в популяцию трупов пускал — они у него потом оживали (имею ввиду рождались за допустмой областью, а потом запихивались в нее). У меня это ассоциировалось не с тем, что родился человек с немного другим цветом волос скажем, а с тем, что автор алгоритма смотрел, что же получится, если животное без почек родится, или с тремя головами.

        Но самое интересное это то что в области с оптимальными решениями ничего не рождалось — баг был. Но поскольку думали что генетический алгоритм лучше знает, то и багов никто не искал. Случайно обнаружили.
        0
        Представьте, если корень или полюс одной системы автоматического правления (САУ) будет побитово «пересечен» с соответствующим параметром другой САУ. В результате почти наверняка получится неустойчивая САУ, т.к. для ее устойчивости

        правильно понимаю, что в топике нет ответа на вопрос как проводить кроссинговер для ваших задач?
        Знал примерно как должна выглядеть АЧХ, оставалось подобрать в MatLAb'е параметры, которые мне эту АЧХ «нарисуют». Но САУ — это бортовой вычислитель, малопотребляющий и не очень-то производительный компьютер, а то и вообще просто совокупность частотных фильтров на операционных усилителях.

        Наверное все-таки надо научиться применять ГА для данной задачи на Matlab чтобы получать хоть какое-то решение.
          +1
          В явном виде нет, если говорить о конкретных шагах. Но идея несложная. Если стоит задача синтеза оптимального регулятора, то в генах я закодирую конечное число корней и полюсов передаточной функции. В ходе эволюций и скрещиваний будут проводиться манипуляции именно с этими параметрами. Также можно играться с перереглированием и другими параметрами. По сути это будут числа внутри генов. При мутациях эти числа генерируются случайно. При скрещивании новая особь получит аллельные гены от обоих родителей с разными значениями фитнесс функции. Можно предположить, что взвесив по этим значениям значение корня или полюса, или другого параметра, я получу некий гибрид. Контролировать такой процесс легче, чем побитовый кроссинговер.
          Нужно будет вопросу кроссинговера уделить побольше внимания.
            +1
            Фишка в том, что в реальной ДНК между генами очень много «неиспользуемого» места, поэтому при кроссовере вероятность того что ген разорвётся мала, чаще рвётся это межгенное пространство. Причём такое строение ДНК возникло благодаря всё тем же генетическим алгоритмам, т.к. только такое строение ДНК обеспечивает надёжную передачу информации потомкам.

            Чтобы не хранить так много «избыточной» межгенной информации и ускорить появление потомков с нужными свойствами, низкоуровневое битовое представление редко используется. Хотя это довольно заманчиво, получить геном устойчивый к мутациям с помощью таких нехитрых способов, но тут встаёт вопрос о саморепликации. Без неё геному не будет резона изобретать устойчивые способы кодирования, если любой мусор и так будет передаваться потомкам.
              0
              Фишка в том, что в реальной ДНК между генами очень много «неиспользуемого» места, поэтому при кроссовере вероятность того что ген разорвётся мала, чаще рвётся это межгенное пространство.

              Мне все-таки кажется, что «точка слипания» ищется по заведомо длинной последовательности нуклеотидов. Вероятность разрыва генов сведена к нулю должна быть. Все таки ген кодирует белок. В случае разрыва одного гена и присоединения хвоста от другого получится совсем другой белок. Был сигнальный белок, а станет костная ткань (или нечто подоюное).
              Но в любом случае для практики использования в искусственных (виртуальных) мирах, игродельстве и т.д. нет необходимости точно следовать примеру природы. Она нам подсказывает, а мы подхватываем и синтезируем нечто похожее.
          0
          Вот красивый генетический алгоритм
          en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform
              +1
              Что-то подобное обещали реализовать в DarkSpore?
                0
                ЭХХХХ Опередили… :) Не нашел там пока деталей реализации… Спасибо за ссылку.
                0
                ИМХО

                Вам нужно в рассуждениях спуститься еще на одну ступень ниже.
                Чем гены занимаются в ДНК? Грубо? Кодируют белки и время их включения/выключения. Почему у человека две ноги и две руки? При формировании плода в определенный период времени считывается определенная последовательность молекул, которые посредством РНК превращаются в белок, который запускает рост ног. Ноги выросли — начинает вырабатывается белок, который останавливает синтез того, предыдущего ну и т.д.
                  0
                  Об этом я тоже дамал и думаю… Но тут механизм похитрее. Нужно есть слона по кусочкам. Такой механизм формирования организма очень интересен…
                  превращаются в белок, который запускает рост ног. Ноги выросли — начинает вырабатывается белок, который останавливает синтез того, предыдущего ну и т.д.

                  в продолжение последовательности…
                  «Сформировались первичные половые признаки — запускается процесс формирования вторичных (например, кошелек или машина у мужчин)»
                  0
                  Интересно было прочитать данную статью, всегда интересовало применение более современных алгоритмов в области ТАУ.
                  В статье упоминается градиентный метод в сравнении с генетическим, хочу не много добавить, что градиентный метод сильно зависит от начальных условий в отличие от генетических алгоритмов. Поэтому с помощью градиентного метода не всегда можно сразу найти все решения.
                    0
                    Я к тому и описал Градиентную оптимизацию как дополнение к ГА. Сам сталкивался с этим недостатком. Часто попадаешь в локальные минимумы. Но в ТАУ объекты часто не на столько нелинейны. Исключение — управление тепловыми процессами и т.п., где система уравнений нелинейная (используется матрица Якоби). К тому же проблему выбора НУ как раз и решают ГА.
                    0
                    Спасибо, давно ждал подобную статью
                    Меня интуресует вопрос кодирования алгоритмов в генах. Имеет ли это смысл и как кодировать алгоритмы различной длинны. То есть можно попытаться делать днк различной длинны или же делать иерархию генов в виде общий алгоритм-частный случай алгоритма… Вобщем все правильные вопросы вы подняли, осталось найти ответы…

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое