«А.С. Потапов ТЕХНОЛОГИИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА Учебное пособие Санкт-Петербург 2010 Потапов А.С. Технологии искусственного интеллекта – СПб: СПбГУ ИТМО, 2010. – 218 с. Пособие содержит описание трех базовых проблем ...»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

А.С. Потапов

ТЕХНОЛОГИИ ИСКУССТВЕННОГО

ИНТЕЛЛЕКТА

Учебное пособие Санкт-Петербург 2010 Потапов А.С. Технологии искусственного интеллекта – СПб: СПбГУ ИТМО, 2010. – 218 с.

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

Предназначено для студентов, обучающихся по направлению подготовки 200600 – «Фотоника и оптоинформатика».

Рекомендовано к печати УМО по образованию в области приборостроения и оптотехники в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки 200600 – «Фотоника и оптоинформатика».

В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет». Министерством образования и науки Российской Федерации была утверждена Программа развития государственного образовательного учреждения высшего профессионального образования «СанктПетербургский государственный университет информационных технологий, механики и оптики» на 2009–2018 годы.

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

Сами исследователи выделяют две основные цели своей работы – это (1) автоматизация человеческой деятельности, в особенности тех ее видов, которые традиционно считались интеллектуальными, и (2) создание компьютерных моделей, имитирующих процессы решения человеком тех или иных интеллектуальных задач в целях объяснения сущности этих процессов.

Еще одной возможной целью, о которой, однако, часто забывают, является создание усилителя интеллекта (УИ). Методология УИнаправления не сильно, но все же отличается от методологии ИИнаправления. Но что отличается существеннее – это прогнозируемые социальные последствия.

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

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

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

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

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

Тем не менее, свое название научное направление «искусственный интеллект» получило не случайно. Ведь одной из первых работ в этом направлении была основополагающая статья А. Тьюринга «Вычислительные машины и интеллект», опубликованной в 1950 г. в журнале «Mind». И основной темой этой статьи был вопрос: «Может ли машина мыслить?» (собственно, в русском переводе название статьи звучало именно так). Само же название «искусственный интеллект»

распространилось в 1960-х годах (хотя появилось оно чуть раньше), и уже в 1969 году была проведена 1-я Международная объединенная конференция по искусственному интеллекту, которая официально и закрепила это название. Таким образом, видно, что ученые, определявшие лицо новой науки, все же в качестве конечной ее цели видели создание именно машинного разума.

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

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

Чтобы понять истинное значение этого теста, следует обратиться к социально-историческому контексту той статьи. В то время информация о принципах работы человеческого мозга (как на нейрофизиологическом, так и на психологическом уровне) была очень скудной. Высказывание:

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

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

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

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

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

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

К направлениям, выделяемым на основе решаемой задачи, относятся:

• машинный перевод;

• автоматическое реферирование и информационный поиск;

• системы речевого общения;

• игровой интеллект, доказательство теорем и автоматизация научных исследований;

• компьютерное зрение;

• извлечение данных;

• сочинение текстов и музыки и др.

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

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

Направления в ИИ, выделяемые по развиваемому в них инструментарию, включают:

• искусственные нейронные сети;

• эволюционные вычисления;

• распознавание образов;

• экспертные системы;

• эвристическое программирование;

• мультиагентный подход и т.д.

Сюда также можно отнести и ряд других направлений, включающих исследование более частных групп методов.

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

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

К направлениям третьего типа можно отнести:

• поиск в пространстве решений;

• представление знаний;

• машинное обучение.

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

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

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

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

Важно отметить, что проблема манипулирования знаниями является более узкой и более конкретной, чем проблема поиска вообще.

Однако по мере развития данного направления была выявлена другая проблема, а именно проблема автоматического приобретения знаний.

Более широко эта проблема была сформулирована как проблема машинного обучения. Хотя и раньше важность обучения понималась многими учеными, только после исследований в области представления знаний стало ясно, насколько большой объем информации получает человек в процессе обучения и насколько трудоемко закладывать эти знания в машинные системы вручную. Выделившись в самостоятельное направление, машинное обучение в 1980-е годы стало привлекать все большее внимание и в результате стало центральным в области ИИ.

Интеллект перестал пониматься как некий готовый продукт, который можно воспроизвести, или как фиксированная способность к решению задач или манипулированию знаниями.

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

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

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

На рис. 1 представлена схема, условно изображающая структуру базового уровня области искусственного интеллекта (той ее части, которая к настоящему времени является сравнительно устоявшейся).

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

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

на основе сенсорной информации ставит множество дополнительных проблем, решение которых еще предстоит искать в будущем. Вероятно, современное состояние в области ИИ можно охарактеризовать как этап синтеза, на котором происходит объединение методов, полученных ранее в рамках изолированных направлений исследований.

Выше выделены три базовых проблемы (и несколько производных от них), которые обуславливали развитие области ИИ до настоящего момента (хотя, возможно, их число больше). Таким образом, структуру области ИИ можно условно разделить на три уровня (см. рис. 2).

Подходы к реализации Предметные области Рис. 2. Общая структура области искусственного интеллекта 1. Что такое искусственный интеллект?

2. Какие цели ставят исследователи в области ИИ? Какие подходы выделяются по этим целям?

3. В чем заключается тест Тьюринга?

4. Что говорит гипотеза символьной физической системы?

5. В чем заключается парадокс китайской комнаты? Какие возражения можно предложить против этого парадокса?

6. Из каких разделов состоит область ИИ? Как в общем виде можно представить структуру этой области?

7. Какие наиболее существенные ограничения есть у существующих интеллектуальных систем? Какое возможно дальнейшее развитие данной области?

2. Основные понятия эвристического программирования Первым доминирующим направлением в области ИИ было направление, обычно обозначаемое термином «эвристическое программирование», в котором была принята метафора, что мышление – это поиск в пространстве решений. Данное направление тесно связано с лабиринтной гипотезой мышления в психологии и исследованиями формализации процесса доказательства теорем в математике.

Математика занимается исследованием формальных (символьных) систем. На основе некоторой системы аксиом, определяющей интересующий математика класс объектов, далее доказываются различные теоремы о свойствах этих объектов. Таким образом, из истинных утверждений дедуктивно выводятся другие истинные утверждения.

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

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

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

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

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

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

Эти наблюдения показали, что мыслительная деятельность возникает в ответ на проблемную ситуацию, для которой нет готового решения, и заключается в поиске ее решения. У низших животных этот поиск осуществляется непосредственно в физическом пространстве. У человека, напротив, поиск приобретает еще более сложную форму, чем у обезьян, благодаря развитию языка как символьной системы. Таким образом, поиск с использованием символьных представлений выглядел хорошим кандидатом на объяснение сути мышления, что было выражено в лабиринтной гипотезе мышления, название которой очевидным образом связано с лабиринтами, используемыми зоопсихологами для оценки интеллектуальных способностей животных. Однако здесь лабиринт не обязательно является физическим; это лабиринт возможных путей решения, в котором производится поиск пути, ведущего из исходной точки – условий задачи, к конечной точке – ее решению.

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

К примеру, со стороны критиков ИИ часто слышались утверждения, что компьютер никогда не сможет играть в шахматы лучше человека. Это говорит о том, что критика ИИ основывалась не на более глубоком понимании природы человеческого разума, а на субъективных предпочтениях.

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

Слово «эвристический» означает «способствующий открытию».

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

Работы в направлении эвристического программирования привели к формированию собственной терминологии и методов исследования.

Центральным понятием в эвристическом программировании является понятие дерева вариантов (пространства состояний), которое обычно принимает форму дерева игры либо дерева целей. Корень дерева представляет собой исходное состояние, из которого выходят ветви, соответствующие тому, как это состояние может быть изменено. Листьям дерева, не имеющим потомков, соответствуют состояния, для которых выполняется критерий окончания. В дереве целей корню, как правило, соответствует цель, а дочерним узлам – подцели, достижение которых необходимо или достаточно для достижения цели.

На рис. 3 и 4 приведены примеры фрагментов дерева игры и дерева целей соответственно.

Решение некоторой задачи сводится к нахождению удовлетворяющего условиям задачи листа и построению пути от корня дерева до этого листа.

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

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

Деревья игры и целей могут быть эксплицитными и имплицитными.

Эксплицитное дерево задается в явном виде путем указания всех его узлов и дуг, в то время как имплицитное дерево задается путем указания исходной позиции и правил формирования дерева (правил игры или допустимых операций по изменению текущего состояния).

Решение задачи поиска на эксплицитном дереве тривиально:

достаточно лишь из листьев дерева выбрать подходящее. Однако эксплицитные деревья в реальных задачах встречаются редко.

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

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

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

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

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

Рис. 5. Порядок обхода узлов дерева при поиске (а) в глубину; (б) в ширину Поскольку порядок обхода дерева вариантов при поиске в глубину и ширину различается, при наличии ограничения на число посещенных узлов с использованием этих двух стратегий поиска разные узлы останутся не посещенными.

Еще один часто используемый способ перебора – это порождение комбинаторных объектов в лексикографическом порядке, т.е. введение линейного порядка на множестве вариантов и перечисление всех вариантов в этом порядке. Этот способ удобен тем, что если дерево вариантов удается свести к одному из типов комбинаторных объектов, то это может существенно упростить процедуру поиска. Рассмотрим несколько типичных задач.

1) Перечисление всех бинарных строк длины N.

Пример перечисления в лексикографическом порядке для N=3:

2) Перечисление всех перестановок символов в строке длины N.

Пример перечисления в лексикографическом порядке для N=3.

3) Перечисление всех K-элементных подмножеств множества из N Пример для N=5, K=3.

00111, 01011, 01101, 01110, 10011, 10101, 10110, 11001, 11010, 11100.

Сами алгоритмы порождения комбинаторных объектов состоят из процедуры генерации первого объекта и процедуры перехода от n-го к (n+1)-му объекту.

Однако при порождении объектов в лексикографическом порядке проблематичным оказывается введение эвристик, отсекающих неперспективные ветви, поскольку эти объекты, как правило, соответствуют листьям на дереве вариантов, и процедура порождения переходит от листа к листу, минуя неконечные узлы на дереве (см. рис. 6).

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

Примером простейшей эвристики является использование симметрий:

позиции, получаемые в результате поворотов и отражений уже рассмотренных позиций рассматривать не нужно. Например, в крестикахноликах на поле 3х3 существует 3 разных первых хода (см. рис. 3).

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

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

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

1) Есть кучка из 2007 монеток. Два игрока по очереди берут из нее от одной до шести монеток. Выигрывает тот, кто делает последний ход. Какова выигрышная стратегия?

2) Можно ли замостить доску 8х8 клеток с двумя вырезанными уголками (A1 и H8), то есть доску из 62 клеток, костяшками Очевидно, обе задачи могут быть решены полным перебором, деревья вариантов для которых несложно построить. Однако для обеих задач есть беспереборные решения. В первой задаче в качестве инварианта может выступать остаток от деления числа монеток на 7, на чем и строится выигрышная стратегия. Во второй задаче нужно заметить, что при шахматной раскраске доска с вырезанными клетками имеет неравное число белых и черных клеток, а костяшка домина всегда занимает одну белую и одну черную клетку. Итак, не любую задачу, для которой можно построить дерево вариантов, следует решать перебором.

Однако задачи, решаемые в области ИИ, зачастую относятся к т.н. NPполным. Для таких задач не известно точное решение, которое не требовало бы обхода дерева вариантов, количество узлов в котором экспоненциально растет с глубиной. Этот эффект называется комбинаторным взрывом или проклятием размерности (почему это проклятие, понять несложно: именно невозможность полного перебора на экспоненциально растущем дереве вариантов лишает переборные алгоритмы интеллектуальности, а исследователей – легкого решения проблемы искусственного интеллекта). В связи с этим, для таких задач также не существует и оценивающих функций, которые бы позволяли на каждом шаге гарантированно выбирать лучший ход. В то же время, конечным позициям (листьям) оценивающая функция должна назначать правильные веса. Таким образом, оценивающая функция должна при приближении к листьям сходиться к «правильному ответу», однако эта сходимость может быть немонотонной.

Рассмотрим простой пример оценивающей функции: суммарную силу фигур в шахматах. Для начала отметим эвристичность этой функции: из правил игры в шахматы напрямую не следует, что большое количество фигур способствует выигрышу. Эта оценивающая функция, очевидно, немонотонна (вернее, не строго возрастает), что проявляется в двух фактах. Во-первых, веса двух ходов будут одинаковы, если эти ходы не приводят к изменению количества фигур, то есть с использованием данной оценивающей функции нельзя отдать предпочтение какому-либо ходу без съедения фигуры. Во-вторых, часто съедение какой-либо фигуры приводит к потере более значимой фигуры на следующем ходе, в результате чего значение данной оценивающей функции сначала увеличится, а затем уменьшится.

Уже на этом примере видно, что немонотонность оценивающей функции может быть компенсирована перебором, на основе которого и формируются рабочие оценки.

1. Чем отличается дерево игры от дерева целей?

2. По какой причине оказывается необходимым вводить понятие 3. Оцените примерные размеры полного дерева вариантов для игры «пять в ряд» (крестики-нолики) на поле 15х15.

4. Какие деревья вариантов бывают?

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

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

Другое ограничение подхода заключается в том, что задание релевантных признаков необходимо выполнять человеку.

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

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

Для узла, соответствующего ходу противника, напротив, рабочая оценка формируется как минимум среди рабочих оценок непосредственных потомков.

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

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

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

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

Однако улучшать можно не только оценивающую функцию.

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

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

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

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

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

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

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

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

Эта задача заключается в следующем. Дано N предметов, для каждого из которых определен вес wi и ценность vi, i=1,…,N. Необходимо выбрать такой набор предметов, который бы обладал максимальной суммарной ценностью, и при этом общий вес предметов не превосходил некоторого значения W. Данная задача решается перебором. Предметы обычно сортируются по удельной ценности vi/wi (это является очевидной для человека эвристикой, но ее нужно закладывать в алгоритм априорно).

Жадный алгоритм работает следующим образом: выбирается предмет максимальной ценности, который не нарушает ограничения по весу, после чего производится переход к выбору следующего предмета. Этот алгоритм не гарантирует нахождения оптимального решения, что хорошо видно на следующем примере: N=3, w1=5, v1=10, w2=4, v2=7, w3=4, v3=7, W=8. В данной ситуации сначала будет выбран первый предмет, после чего ни один предмет больше взят быть не может.

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

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

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

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

Исходно такие системы разрабатывались в рамках еще доминировавшей парадигмы эвристического программирования. Одна из первых и наиболее известных систем такого рода – это «Общий решатель задач» (GPS, General problem solver), первая версия которого была разработана Аланом Ньюэллом и Гербертом Саймоном (при участии Кристофера Шоу) в 1957 году (развитие и исследование программы осуществлялось до 1969 года) на основе ранее разработанной ими программы «Логик-теоретик».

Основной особенностью GPS является то, что помимо описания конкретной задачи этой программе также в явном виде задается описание и проблемной среды. GPS решает задачи следующего типа: поиск цепочки допустимых действий, приводящих заданную начальную ситуацию к желаемой конечной ситуации (цели). Каждая ситуация описывается как совокупность объектов, находящихся в определенных состояниях. То есть задача для GPS описывается как совокупность имеющихся и желаемых состояний набора объектов. Допустимые действия трактуются как операторы. Чтобы GPS был способным решать задачи такого рода, он должен обладать описанием проблемной среды, которая включает всю общую для задач определенного типа информацию, например, информацию о проблеме интегрирования.

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

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

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

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

Тем не менее, хотя GPS и другие аналогичные программы потерпели неудачу в качестве универсальных решателей задач, они позволили глубже понять проблему ИИ и послужили одним из факторов, приведших к смене парадигм. А именно, в них была выявлена необходимость исследования способов представления и манипуляции знаниями о предметной области.

1. В чем заключаются отличия процедуры формирования рабочих оценок от статической оценивающей функции?

2. Если для каждого хода в некоторой игре есть возможность выбора одного из 64 вариантов, то во сколько раз более глубокий поиск обеспечит процедура n-наилучшего направленного сокращения при n=4 по сравнению с процедурой неполного перебора на фиксированную глубину без отсечения ветвей?

3. Для каких целей используется неглубокий поиск?

4. Каково основное отличие алгоритма альфа-бета отсечения от процедуры n-наилучшего направленного сокращения?

5. Какой недостаток классических методов эвристического программирования был призван преодолеть Общий Решатель 6. Какие выводы для области искусственного интеллекта позволил сделать общий решатель задач?

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

Пусть дана доска MxN клеток. В каждой клетке указана некоторая стоимость ее посещения ci,j, i=1,…,M, j=1,…,N. Требуется найти такой путь из клетки с координатами (1,1) в клетку с координатами (M,N), стоимость которого была бы минимальной. Здесь путь – это такая последовательность клеток, что расстояние между последующей и предыдущей клеткой равно единице (т.е. клетки являются 4-связанными).

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

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

К счастью, поиск наилучшего пути и не требует полного перебора.

Существует следующий простой алгоритм:

1. Создать массив D размера MxN и присвоить его элементам di,j значения +.

2. Изменить значение элемента (1, 1) на c1,1.

3. Для каждого элемента (i, j), значение которого было изменено на предыдущем шаге алгоритма, просмотреть его соседей и сравнить величины di,j+ci±1,j±1 с соответствующими текущими значениями di±1,j±1. В случае если di±1,j±1> di,j+ci±1,j±1 заменить значение элемента (i±1, j±1) на di,j+ci±1,j±1. Обычно среди всех измененных элементов сначала рассматривают элементы с наименьшим значением di,j.

4. Повторять шаг 3 алгоритма до тех пор, пока значения каких-либо элементов массива D меняются.

5. Массив D будет содержать минимальные стоимости путей от точки (1, 1) до каждой из точек доски, откуда будет несложно восстановить и сам маршрут от начальной до конечной точки.

На рис. 7 представлено пояснение к алгоритму: исходные стоимости посещения клеток и изменение матрицы D при выполнении одного шага.

Рис. 7. Поиск кратчайшего пути: а) матрица стоимости посещения клеток;

б) матрица D после пяти итераций; в) матрица D после шести итераций.

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

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

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

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

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

Задачи поиска в непрерывном пространстве зачастую сводятся к поиску экстремума некоторой целевой функции (поиск наилучшего пути также можно свести к этой задаче).

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

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

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

Как известно, градиент некоторый функции f (x ) в некоторой точке показывает направление локального наискорейшего увеличения функции.

Этот факт используется в методах градиентного спуска (подъема).

Эти методы описываются следующей последовательностью действий:

1. Выбрать начальную точку x 0 = ( x1,0,...xn,0 ). Установить номер 2. Для текущей точки определить значение градиента:

В случае если градиент не может быть вычислен аналитически, его компоненты могут быть оценены численно:

3. Определить положение следующей точки:

где d – параметр, определяющий скорость спуска, и положить 4. Перейти к шагу 2, если не выполнен критерий останова.

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

Однако в этом случае можно проверять изменение за несколько итераций и Существует также возможность адаптивного выбора шага d. Для этого на каждой итерации осуществляется выбор такого значения из трех величин шага d 0 = d, d1 = d / w, d 2 = dw (где w – некоторый параметр, как правило w (1,2]), что значение функции в точке xi +1 = xi d j минимально. Таким образом, если при большом шаге d метод градиентного спуска «проскакивает» минимум, то d будет уменьшаться.

Уменьшение d ниже заданного порога также служит критерием остановка.

Напротив, на пологих участках значение d будет увеличиваться.

При условии существования глобального минимума функции f метод градиентного спуска обычно сходится (за исключением случаев, когда вдоль некоторого направления функция, монотонно убывая, стремится к некоторому конечному пределу при x ). Сходимость метода обеспечивается тем, что на каждой итерации выбирается такая точка xi, что f (xi ) < f (xi 1 ). Метод, однако, не гарантирует нахождения глобального минимума, поскольку при достижении любого локального минимума метод не в состоянии определить направление на более глубокий минимум (и вообще обнаружить его существование) и останавливается в соответствии с выбранным критерием останова.

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

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

Для решения этих проблем был предложен метод моделирования отжига. Этот метод предназначен для поиска глобального минимума некоторой функции f : S R, где S – некоторое пространство (необязательно непрерывное), элементы которого интерпретируются как состояния некоторой воображаемой физической системы, а значения самой функции – как энергия этой системы E=f(x) в состоянии x S.

В методе моделирования отжига система в каждый момент времени находится в некотором состоянии xi, а также обладает некоторой температурой T, которая является управляемым параметром.

На каждой итерации система случайным образом переходит в новое состояние xi xi +1. Механизм выбора нового состояния состоит из двух частей:

1. Сначала выбирается состояние xi +1 в соответствии с некоторой функцией распределения g ( xi+1, xi, T ). Как правило, эта функция зависит только от расстояния xi +1 xi, причем с увеличением этого расстояния вероятность перехода понижается.

2. После случайного выбора xi +1 проверяется вероятность перехода в это новое состояние h(E, T ), исходя из разности энергий показывает вероятность перехода в состояние с другой энергией.

Проверка производится следующим образом: выбрасывается случайное число из диапазона [0, 1]. Если это число оказывается меньше, чем значение вероятности h(E, T ), то новое состояние xi +1 принимается, в противном случае шаг 1 повторяется. Функция h(E, T ), как правило, стремится к 1 при E, стремящемся в минус бесконечность, и стремится к 0 при E, стремящемся в плюс бесконечность (то есть предпочтение в среднем отдается состояниям с меньшей энергией).

Поскольку метод моделирования отжига базируется на физических принципах, функции распределения вероятностей g ( xi+1, xi, T ) и h(E, T ) также часто заимствуются из физики. В частности, достаточно популярен больцмановский отжиг, в котором распределения задаются в форме где D – размерность пространства S;

Таким образом, температура T определяет, насколько в среднем может меняться текущее состояние xi, а также то, насколько в среднем может меняться энергия системы при переходе в новое состояние.

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

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

где номер итерации i > 0. Больцмановский отжиг гарантирует нахождение глобального минимума для широкого класса целевых функций. Закон (6) может, однако, потребовать большое число итераций, особенно при больших значениях начальной температуры T0 и высокой требуемой точности результата. В этом несложно убедиться: за 106 итераций происходит уменьшение температуры всего в 14 раз. В связи с этим зачастую используется закон более быстрого понижения температуры:

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

Начальная температура неявно задает область, в которой будет осуществляться поиск глобального минимума, а также определяет необходимое для сходимости число итераций.

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

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

1. Какая основная эвристика используется в методах поиска в непрерывных пространствах решений, которая позволяет существенно повысить эффективность этих методов?

программирования аналогичен градиентный спуск?

3. В чем преимущество адаптивного выбора шага в градиентном 4. Какие ограничения классического градиентного спуска позволяет преодолеть стохастических или иерархический градиентный спуск?

5. За сколько итераций при Больцмановском отжиге начальная температура уменьшится в 20 раз?

6. Если количество итераций в методе имитации отжига фиксировано, то на что влияет выбор начальной температуры?

7. В каких случаях метод имитации отжига предпочтительнее градиентного спуска?

Эволюционные вычисления – это совокупность подходов к решению проблемы поиска (оптимизации), в основе которых лежат идеи, почерпнутые из эволюции в живой природе. Для начала, установим связь между эволюцией и процессом поиска.

Существующие методы эволюционных вычислений берут за основу идеи Дарвина. Одна из этих идей гласит: выживает наиболее приспособленный. В действительности, это тавтология (хотя, возможно, не вполне очевидная применительно к природе), поскольку более приспособленный – это, по определению, тот, кто имеет больше шансов выжить. Однако в сочетании с другой идеей – идеей изменчивости видов, первая идея превращается в идею естественного отбора. То, что виды изменяются со временем, не самоочевидно и может быть установлено только из эмпирических данных, поскольку изменчивость должна обеспечиваться какими-то конкретными механизмами.

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

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

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

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

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

Таким образом, обычный градиентный спуск содержит все базовые элементы эволюции. С одной стороны, это еще раз подчеркивает сходство эволюции с поиском, но с другой стороны, ставит вопрос, что же исследователи ИИ нашли нового в эволюции?

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

Таким образом, не базовые идеи эволюции, а конкретные ее механизмы (не выводящиеся из этих идей) и представляли интерес для специалистов в области ИИ.

Эти механизмы являются основой нескольких направлений исследований в рамках эволюционных вычислений:

• генетические алгоритмы (ГА);

• эволюционные стратегии;

• эволюционное (генетическое) программирование.

Эти направления тесно связаны и во многом похожи, хотя возникли практически независимо. Концепция генетических алгоритмов была предложена Холландом в начале 1960-х годов (хотя широко известной она стала только с середины 1970-х годов). Идею эволюционных стратегий предложил Реченберг (а чуть позже Шефель) в середине 1970-х годов.

Концепция эволюционного программирования была предложена Фогелем, Оуэнсом и Уолшем в середине 1960-х годов.

Мы рассмотрим сначала генетические алгоритмы, а затем укажем сходство и различия других направлений с ГА.

ГА предназначены для нахождения экстремумов функций от произвольных объектов. Сами объекты трактуются как некоторые организмы, а оптимизируемая функция – как приспособленность организмов, или фитнесс-функция. Множество возможных объектов отображается (предпочтительно, взаимно однозначно) на некоторое подмножество множества битовых строк (обычно фиксированной длины).

Эти строки трактуются как хромосомы (или геномы).

Особенность генетических алгоритмов заключается в том, что они работают с битовыми строками, не опираясь на структуру исходных объектов, что позволяет применять ГА без модификации для любых объектов. Единственно, что требуется для такого применения, – это процедура перекодирования объектов в геномы.

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

1. Сгенерировать начальную популяцию (случайную совокупность 2. Выбрать родительские пары.

3. Для каждой родительской пары с использованием оператора скрещивания породить потомство.

4. В хромосомы порожденного потомства внести случайные искажения оператором мутации.

5. Произвести отбор особей из популяции по значению их фитнесс-функции, применив оператор редукции.

6. Повторять шаги 2-4, пока не выполнится критерий остановки.

Рассмотрим каждый из шагов чуть подробнее.

1. Генерация начальной популяции обычно производится равномерно по пространству генов (или по пространству описаний объектов). Размер популяции – установочный параметр.

2. Выбор родительских пар может осуществляться различными способами. Этот выбор осуществляется в два этапа: выбор первого родителя и формирование пары. При выборе одного родителя обычно используется один из следующих способов:

• с равной вероятностью выбирается любая особь из имеющейся • особь выбирается случайно с вероятностью, пропорциональной значению фитнесс-функции; то есть в этом случае значение фитнесс-функции сказывается не только на том, какие особи останутся в популяции в результате отбора, но и на то, сколько потомства они произведут.

Выбор второго родителя осуществляется по одному из следующих критериев:

• независимо от уже выбранного родителя (то есть второй родитель выбирается абсолютно так же, как и первый); этот вид отбора называется неселективным;

• на основе ближнего родства;

• на основе дальнего родства.

В последних двух случаях выбор одного родителя влияет на выбор другого родителя: с большей вероятностью формируются пары, состоящие из особей, которые больше похожи друг на друга (то есть ближе находятся в пространстве геномов или описаний объектов) в случае использования ближнего родства и меньше похожи – в случае дальнего родства. В генетических алгоритмах в качестве меры близости обычно используется расстояние Хемминга.

3. Оператор скрещивания – это оператор, который определяет, как из хромосом родителей формировать хромосомы их потомства. Часто применяется следующий оператор скрещивания: хромосомы делятся в некоторой случайной точке и обмениваются этими участками (то есть, все, что идет до этой точки, берется от одного родителя, а все, что после, – от другого). Это одноточечный кроссинговер. В многоточечном кроссинговере таких участков обмена больше.

При равномерном скрещивании каждый бит хромосомы берется от случайного родителя или родители случайным образом обмениваются некоторыми битами (рис. 8).

Рис. 8. Примеры работы оператора скрещивания: а) одноточечного;

б) многоточечного; в) обмена случайными битами 4. Мутации обычно осуществляются, как случайная замена одного бита хромосомы. Скорость мутаций определяется тем, как часто они происходят. Это управляемый параметр, который влияет на скорость сходимости и вероятность попадания в локальный экстремум.

5. Отбор особей в новую популяцию чаще всего осуществляется одной из двух стратегий:

• пропорциональный отбор, при котором вероятность того, что некая особь останется в следующей популяции, пропорциональна значению фитнесс-функции этой особи;

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

Формирование новой популяции может осуществляться как на основе потомков и родителей, так и на основе только потомков в зависимости от конкретной реализации.

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

Отличие эволюционных стратегий от ГА заключается в том, что в них не используются битовые представления. Вместо этого все генетические операторы реализуются в исходном пространстве объектов с учетом их структуры. Это ведет к потере универсальности, но повышению гибкости.

Рассмотрим особенности реализации генетических операторов в эволюционных стратегиях на примере объектов, описаниями которых являются двухкомпонентные векторы: (x,y).

1. Генерация начальной популяции может осуществляться путем выбора случайных векторов из области [x min, x max ] [ y min, y max ], где величины x min, x max, y min, y max задают ожидаемые минимальные и максимальные значения переменных x и y искомого положения экстремума фитнесс-функции. В случае генетических алгоритмов эта область задается неявно, и она зависит от способа отображения вектора (x,y) в битовую строку.

2. При выборе родителей особенность эволюционных стратегий выражается в способе задания меры родства. В данном случае мерой родства двух особей ( x1, y1 ) и ( x2, y 2 ) может служить евклидово расстояние: ( x2 x1 )2 + ( y 2 y1 )2, которое будет заметно отличаться от расстояния Хемминга, используемого в ГА.

3. Результатом скрещивания двух особей в рассматриваемом случае будет являться особь ((x1 + (1 ) x2, y1 + (1 ) y2 ) ), где [0,1] – случайная величина, что, опять же, отличается от результата скрещивания в пространстве геномов.

4. Результатом мутации для особи ( x, y ) будет являться особь ( x + x, y + y ), где x, y – случайные величины. Их распределение вероятностей может быть выбрано гауссовым или, для простоты программной реализации, равномерным в некотором интервале. Дисперсия этих величин определяет скорость мутаций.

5, 6. Операторы отбора и критерии останова в эволюционных стратегиях не имеют особых отличий от тех, которые используются в генетических алгоритмах.

Как видно, эволюционные стратегии допускают гораздо более гибкую настройку генетических операторов и позволяют учитывать особенности конкретных объектов, что позволяет повысить их эффективность по сравнению с ГА. Это, однако, происходит за счет потери универсальности:

реализация операторов в ГА не зависит от того, фитнесс-функцию от каких именно объектов необходимо оптимизировать, в то время как для эволюционных стратегий каждый тип объектов требует индивидуальной реализации операторов.

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

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

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

Зачастую этот язык не является алгоритмически полным. Популярным также является представление программ в виде нейронных сетей или в рамках других графовых представлений.

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

Схема работы генетического алгоритма (и других эволюционных методов) достаточно проста и понятна с точки зрения классических методов поиска. Естественная эволюция гораздо сложнее и содержит в себе многие эвристики поиска, которые еще не были перенесены в эволюционные вычисления.

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

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

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

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

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

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

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

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

1. Какие основные подходы существуют в области эволюционных 2. Какие типичные генетические операторы используются в генетических алгоритмах?

3. В чем основное отличие между генетическими алгоритмами и эволюционными стратегиями?

4. Какой генетический оператор влияет на возможность нахождения глобального экстремума, находящегося вне области, в которой задавалась начальная популяция?

5. Как скорость мутаций влияет на скорость сходимости генетического алгоритма?

6. При каком виде скрещивания скорость сходимости максимальна?

К генетическим алгоритмам, эволюционным стратегиям и эволюционному программированию примыкает направление исследований, получившее название «Искусственная жизнь» (artificial life, AL). Оно оформилось под таким названием в конце 1980-х годов, однако большое число работ, которые можно к нему отнести, были выполнены гораздо раньше.

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

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

или «Адаптивное поведение», в котором реализация эволюции является второстепенной задачей, напротив, искусственные существа достаточно часто реализуются в реальном мире или в виртуальной модели реального мира.

Основной целью исследований в направлении «искусственная жизнь»

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