Право на ошибку - Журнал "Компьютерра"

«С. ЛЕМ
СУММА ТЕХНОЛОГИИ
ГЛАВА ВОСЬМАЯ
ПАСКВИЛЬ НА ЭВОЛЮЦИЮ
КОНСТРУКЦИИ, ОСНОВАННЫЕ НА ОШИБКАХ»

Впервые «Компьютерра» обратилась к теме эволюционных алгоритмов и «искусственной жизни» (A-life) в 1999 году («КТ» #289). С тех пор промышленное использование этих идей значительно расширилось. В своей статье Михаил Бурцев напоминает азы и рассказывает о нескольких новых приложениях, самое интригующее из которых, конечно же, эволюционный сетевой файрвол - анонсированный, но пока не выставленный на продажу. Будем надеяться, что разработчики не последуют примеру Джоан Роулинг, отложившей презентацию «Гарри Поттера пятого поколения» (книги «Орден Феникса») на неопределенный срок. Однако чтобы дать более ясное представление о сложности процессов эволюции, глубине проблем, которые возникают перед серьезным исследователем таких процессов (а стало быть, и перед инженером, пытающимся применить их для решения технических задач), мы сопроводили статью отрывками из новой книги крупнейшего теоретика неравновесных и открытых систем Юрия Климонтовича (см. врезку). - Л.Л.-М.

Попытки организовать искусственную эволюцию в вычислительной среде, основываясь на основных принципах биологической эволюции - принципах изменчивости и отбора, делались еще в 70-х годах прошлого столетия. Исследовалась эволюция машин Тьюринга, клеточных автоматов, был придуман ставший теперь классическим генетический алгоритм, но отсутствие достаточных вычислительных мощностей мешало распространению эволюционных алгоритмов. Ведь эволюция в природе «обсчитывается» на гигантской параллельной машине, состоящей из всех живых существ. Каждый новорожденный организм - это новое решение для определенной задачи. А какие вычислительные ресурсы были в ту пору у исследователей?..

Эволюционный алгоритм - это просто! Берем школьный учебник по биологии, открываем раздел о современном толковании теории Дарвина и заменяем слово «особь» на словосочетание «способ (параметры) решения», а словосочетание «внешняя среда» на «условия задачи», все остальные слова можно оставить без изменения. Теперь пытливый читатель легко может представить, как работает эволюционный алгоритм:

Генерируется множество, состоящее из различных способов(параметров) решения.
После тестирования из этого множества отбираются способы (параметры), отвечающие наилучшим решениям - таким, которые в наибольшей степени удовлетворяют условиям задачи.
Отобранные способы копируются в «следующее поколение», но не точно, а с некоторыми ошибками (аналог мутаций); при этом отдельные способы могут смешиваться друг с другом (кроссовер); затем следует
Возврат к шагу 1.

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

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

С ростом производительности компьютеров эволюционные алгоритмы приобрели широкую популярность, и в начале 90-х выделилось три основных направления в эволюционных вычислениях.

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

Сначала параметры алгоритмов подстраивались вручную. Известна история о некоем аспиранте по имени Оливер, который задавал параметры и запускал генетический алгоритм оптимизации весов для искусственной нейронной сети робота, а сам шел в паб. Затем появились методы самоорганизации параметров эволюционных алгоритмов. Теперь Оливер запускал генетический алгоритм для поиска оптимальных параметров генетического алгоритма оптимизации весов для искусственной нейронной сети робота и шел в паб. Оливер, наверно, вскоре спился бы при такой «научной работе», но помогли коллеги, доказавшие так называемую No Free Lunch Theorem, что в вольном переводе на русский звучит как «халявы не будет». Теорема утверждает, что для любого стохастического алгоритма поиска, к коим относятся и эволюционные алгоритмы, средняя эффективность равна простому случайному поиску. Другими словами, если нам необходимо решать задачи, которые не похожи друг на друга, то мы можем использовать эволюционный алгоритм с тем же успехом, что тыкать пальцем в небо.

Отсутствие халявы поохладило пыл наиболее активных адептов эволюционного компьютинга. Но ведь нам не обязательно нужен алгоритм, чтобы решать любые задачи, обычно мы имеем дело с задачами, относящимися к классу, который в теории эволюционных вычислений получил название «Real World Problems» (реальные задачи). Некоторые исследователи считают, что для реальных задач универсальный алгоритм существовать может ¹.

В последние годы отличным полигоном для эволюционных технологий стал Интернет. Так, в совместном проекте Колумбийского университета и университета штата Айова разработана мультиагентная система InfoSpiders предназначенная для поиска информации в Интернете. Инфопаучки сканируют сеть в поисках ресурсов, удовлетворяющих запросу пользователя. Тем, кто найдет «правильные» ресурсы, выдается энергия. Чем больше у паучка энергии, тем выше вероятность того, что он выживет и оставит потомство - так популяция инфопаучков эволюционирует.

Еще одна область применения генетических алгоритмов в Интернете - оптимизация сетевых экранов (firewall). Идея применить эволюционные методы для анализа сетевого трафика возникла у специалистов компании MASA Group, занимающихся разработкой компьютерных адаптивных систем. К тому времени компанией была создана библиотека алгоритмов по оптимизации, машинному обучению, а также по определению изменений в сложных образах (novelty detection). Специалисты MASA Group решили, что при защите сети основной упор надо делать не на сравнение сетевой активности с шаблонами известных атак, как в обычных экранах, а на определении отклонений от нормы в работе сети. Ведь если вторжение проводится новым способом, неизвестным системе, то обычный подход не сможет определить атаку. В результате сотрудничества MASA Group и MATRAnet эти идеи отлились в программный продукт M>Detect, который, по заверению представителей компаний, должен появиться на рынке осенью этого года.

Работа M>Detect состоит из нескольких этапов. На первом этапе система при помощи эволюционного алгоритма обучается «нормальному» режиму работы сети. К концу обучения формируется набор фильтров, описывающих разрешенные потоки данных. Теперь M>Detect может переходить к следящему режиму, в котором используется система распознавания новизны в образах (на основе временных окон разной длительности, что позволяет детектировать как «быстрые», так и «медленные» атаки). Как только в сетевом трафике возникают аномалии, программа отсылает системному администратору предупреждение и лог активности. Все это позволяет M>Detect обнаруживать сетевые атаки на ранней стадии, а также реагировать на неизвестные типы атак. Если предупреждение было ложным, то оператор переключает систему в режим «дообучения», что позволяет избежать повторного ложного срабатывания. По оценкам разработчиков, ложных предупреждений будет не больше одного-двух в сутки, при этом объем трафика может достигать 30 Гбайт/с, что, несомненно, является хорошим результатом ².

Но все ли так безоблачно, как расписывают разработчики? Представим себе, как будет работать администратор с экраном. После стадии обучения администратор устанавливает уровень «чувствительности» программы к аномалиям. Если чувствительность низка, то экран будет пропускать небольшие отклонения от нормы, и этим с успехом можно воспользоваться для организации атаки, занимающей довольно много времени, но не приводящей к значительным изменениям в трафике. С другой стороны, если установить высокую чувствительность, то администратора завалят сообщениями о ложных атаках, что, в конце концов, заставит его перейти к первому варианту. Найти здесь «золотую середину» - дело непростое.

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

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

Одна из наиболее активно развивающихся областей эволюционного компьютинга - эволюционная робототехника. И не удивительно, «выводить» новую породу роботов гораздо забавней, чем корпеть над конструкцией самостоятельно, да и время экономится. К тому же так приятно почувствовать себя Творцом.

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

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

Другое интересное применение технология построения эвоботов нашла в создании компьютерных игр. Современные компьютерные игры насыщены массой персонажей, которые взаимодействуют с игроком и между собой. Это всевозможные монстры, чудовища и прочая виртуальная нечисть. Как сделать их поведение непредсказуемым, индивидуальным и даже осмысленным? Предоставьте возможность поработать естественному отбору в виртуальном игровом мире, и вот она - новая реальность, игра стала гораздо богаче.

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

1 (обратно к тексту) - Разумеется, на практике реализация описанной выше общей схемы может быть довольно сложной и всегда определяется решаемой задачей. - Л.Л.-М.
2 (обратно к тексту) - Мы благодарны вице-президенту по развитию MASA Group Эммануэлю Шива (Emmanuel Chiva) за консультации. - Л.Л.-М.

Из работы «Критерий относительной степени упорядоченности или хаотичности открытых систем»>>