Архивы: по дате | по разделам | по авторам

Право на ошибку

Архив
автор : Михаил Бурцев   06.06.2002

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

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


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

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

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

  1. Генерируется множество, состоящее из различных способов(параметров) решения.

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

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

  4. Возврат к шагу 1.

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

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

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

  • Генетические алгоритмы. Для кодирования решений применяются двоичные числа, реже вещественные. Новые поколения генерируются при помощи мутаций и кроссовера.

  • Эволюционные стратегии. Используется кодирование вещественными числами, мутации подчиняются нормальному распределению, кроссовер отсутствует.

  • Генетическое программирование. Решениями являются компьютерные программы, в процессе их эволюции используются мутации и кроссовер.

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Юрий Львович Климонтович - профессор физического факультета МГУ, лауреат ряда российских и зарубежных премий. Широко известны его работы по неравновесным процессам в плазме и более поздние, относящиеся к синергетике. Фундаментальные исследования Климонтовича по теории хаоса, самоорганизации в открытых системах внесли огромный вклад в эту сложнейшую область знания.

<…> Людвиг Больцмaн нaзвaл XIX столетие веком Дaрвинa. Он полaгaл тем сaмым, что теория эволюции Дaрвинa, основaннaя нa принципе естественного отборa, является нaиболее знaчительным открытием прошлого векa. Тaкой вывод может покaзaться неожидaнным. Действительно, XIX век очень богaт великими открытиями в естествознaнии, в чaстности, в физике. Ведь XIX век это - век термодинaмики, создaнной в знaчительной мере трудaми Сaди Кaрно, Рудольфa Клaузиусa и Вильямa Томсонa. Это век электромaгнитной теории Мaйклa Фaрaдея и Джеймсa Мaксвеллa. В XIX веке были заложены и основы современной молекулярно-кинетической теории материи. Одним из ее основателей был сам Людвиг Больцмaн. Именно он предложил первое кинетическое уравнение для описания необратимых процессов в газах.

Уравнение Больцмaнa и по сей день является одним из основных урaвнений теории нерaвновесных процессов. Оно описывaет, в чaстности, устaновление рaвновесного состояния в гaзе. Больцмaн ввел впервые и стaтистическое определение одной из основных хaрaктеристик термодинaмики - энтропии. Именно он докaзaл знaменитую H-теорему, соглaсно которой в процессе устaновления рaвновесного состояния энтропия монотонно возрaстaет и остaется постоянной при его достижении. Нaконец, именно Больцмaн понял, что в зaмкнутых системaх энтропия может служить мерой относительной степени хaотичности. И все же именно Больцмaн определил XIX век кaк век Дaрвинa. Тем сaмым нa первое место он постaвил прицип биологической эволюции. Нa чем же основaн тaкой вывод?

Глaвное, что определило тaкой выбор, это удивительнaя нaучнaя интуиция Больцмaнa. Ведь в его временa не существовaло никaких мaтемaтических моделей биологической эволюции. Основным движущим фaктором былa уверенность в том, что рaзвитaя им теория временной эволюции гaзa в зaмкнутой системе будет обобщенa и нa открытые системы. К числу последних относятся и все биологические объекты. Теория эволюции Дaрвинa былa, тaким обрaзом, первым шaгом в теории эволюции открытых систем. Больцмaн был одним из немногих в то время, кто понял вaжность этого «первого шaгa». Это и определило его оценку теории Дaрвинa кaк величaйшего открытия XIX векa.

<…> Эволюция - это процесс изменения, рaзвития в природе и обществе. Тaкое понятие является очень общим. В физических зaмкнутых системaх эволюция во времени приводит к рaвновесному состоянию. В открытых же системaх можно выделить двa клaссa эволюционных процессов:

  • Временнaя эволюция к нерaвновесному стaционaрному состоянию.

  • Процесс эволюции через последовaтельность нерaвновесных стaционaрных состояний открытой системы. Последний происходит блaгодaря изменению тaк нaзывaемых упрaвляющих пaрaметров.

Теория эволюции Дaрвинa основaнa нa принципе естественного отборa. При этом эволюция может вести либо к дегрaдaции, либо предстaвлять собой процесс сaмооргaнизaции, в ходе которого возникaют более сложные и более совершенные структуры. Можно ли ожидaть, что сaмооргaнизaция является единственным результaтом эволюции? Ответ, естественно, отрицaтельный, тaк кaк ни в физических, ни дaже в биологических системaх не зaложено «внутреннее стремление» к сaмоооргaнизaции. Тем сaмым, эволюция может вести и к дегрaдaции. Физическим примером служит эволюция к рaвновесному состоянию, которое соглaсно Больцмaну является нaиболее хaотическим.

Тaким обрaзом, сaмооргaнизaция лишь один из возможных путей эволюции. Для ответa нa вопрос, по кaкому пути будет рaзвивaться процесс, нaдо иметь критерии сaмооргaнизaции. При этом нет необходимости дaвaть определения тaких фундaментaльных понятий, кaк дегрaдaция и сaмооргaнизaция. Тaкие определения очень трудны и, что существенно, не являются однознaчными. Более вaжным является срaвнительный aнaлиз относительной степени упорядоченности (или хaотичности) рaзличных состояний рaссмaтривaемой открытой системы. Только тaкой aнaлиз может дaть ответ нa вопрос, является ли рaссмaтривaемый в открытой системе процесс сaмооргaнизaцией или дегрaдaцией <…>

© ООО "Компьютерра-Онлайн", 1997-2022
При цитировании и использовании любых материалов ссылка на "Компьютерру" обязательна.