Казаков П.В., Шкаберин В.А. Основы искусственного интеллекта

Подождите немного. Документ загружается.

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

словаря. Однако для обработки сложного разговорного текста необ-

ходимы алгоритмы анализа его смысла, создание которых очень тру-

доемкая и пока нерешенная задача. Поэтому в настоящее время дос-

тупны системы, обеспечивающие диалог между человеком и компью-

тером на упрощенном, урезанном естественном языке, программы

электронного перевода эффективные преимущественно при работе с

односложным текстом, а также функции ассоциативного контекстно-

го поиска в электронных словарях.

Разработка интеллектуальных систем на основе принципов

обучения, самоорганизации и эволюции. Моделирование этих

принципов ориентировано на исследование возможностей решения

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

биологическим системам. Процесс обучения связан со способностью

системы накапливать информацию и рационально корректировать в

соответствии с ней свое поведение. Самоорганизация подразумевает

способность системы обобщать накопленную информацию, например

для поиска в ней закономерностей. Использование принципов эволю-

ции позволяет системе приобретать новые качества и свойства для

наиболее оптимального функционирования.

Распознавание образов. Является одним из ранних направле-

ний искусственного интеллекта. Оно связано с моделированием осо-

бенностей восприятия внешнего мира, узнавания объектов. В основе

этого лежит тот факт, что все объекты могут быть проклассифициро-

ваны по определенным признакам и, следовательно, умение разли-

чать их проявление и позволяет идентифицировать соответствующий

объект.

Игры и машинное творчество. Машинное творчество охваты-

вает сочинение компьютерной музыки, стихов, автоматизацию изо-

бретения новых объектов. Компьютерные игры являются той сферой

искусственного интеллекта, которая наиболее знакома большинству

пользователей. Уровень реализации ИИ в игре во многом определяет

ее интересность, поэтому разработчики компьютерных игр постоянно

совершенствуют их интеллектуальную составляющую.

Программное обеспечение систем искусственного

интеллекта. Инструментальные средства для разработки интеллек-

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

представления знаний, среды создания систем ИИ, а также оболочки

экспертных систем.

Интеллектуальные роботы. Их создание связано с объедине-

нием технологий искусственного интеллекта и методов кибернетики,

робототехники. В настоящее время их производство ограничивается

манипуляторами с жесткой схемой управления, а также роботами

развлекательного и бытового назначения с узкой областью примене-

ния и ограниченными функциями. Сдерживающим фактором при

разработке более совершенных кибернетических систем являются не-

решенные проблемы в области машинного зрения, адаптивного пове-

дения, накопления и обработки трехмерной визуальной информации.

Уровень теоретических исследований по искусственному интел-

лекту в России не уступает мировому. Началом становления этого

научного направления в нашей стране следует считать 1954 г., когда в

МГУ начал свою работу семинар «Автоматы и мышление» под руко-

водством академика Ляпунова А.А. Впоследствии стали активно раз-

виваться направления, связанные с представлением и обработкой

знаний, ситуационным управлением, моделированием рассуждений,

распознаванием образов, обработкой естественного языка [3].

Развитие искусственного интеллекта в современной России свя-

зано с образованием в 1988 г. Ассоциации искусственного интеллек-

та, объединившей научные школы, исследователей по различным на-

правлениям ИИ. Под ее эгидой проводятся различные исследования,

организуются семинары для специалистов, устраиваются конферен-

ции, издается научный журнал.

В то же время проведение прикладных исследований, внедрение

их результатов в коммерческие разработки происходит гораздо мед-

леннее, чем за рубежом. Во многом это объясняется консервативно-

стью потенциальных потребителей новых информационных техноло-

гий, а также настороженным отношением к возможностям искусст-

венного интеллекта.

Далее рассматриваются основные методы научного направления

«Искусственный интеллект», особенности их реализации, а также за-

дачи, для которых их применение наиболее эффективно.

Контрольные вопросы

1. Какой смысл вкладывается в понятие «искусственный

интеллект»?

2. Решением каких задач занимается научное направление ис-

кусственный интеллект?

3. Какие существуют подходы к исследованиям в области ис-

кусственного интеллекта?

4. Что такое интеллектуальная система?

5. В каких областях применение интеллектуальных систем

наиболее эффективно?

6. Какие существуют основные направления исследований в

области искусственного интеллекта?

7. Подготовьте реферат, посвященный истории развития искус-

ственного интеллекта в России и за рубежом.

2. МЕТОДЫ ЭВРИСТИЧЕСКОГО

ПРОГРАММИРОВАНИЯ

Эвристическое программирование – разработка стратегий дей-

ствий на основе заранее заданных эвристик (теоретически необосно-

ванных правил). Эвристический метод - метод решения задачи, осно-

ванный на интуиции решающего лица. Этот метод часто не имеет

формального доказательства того, что он приводит к цели.

В основе методов эвристического программирования лежит по-

нятие эвристики, которое может рассматриваться, с одной стороны,

как информация, отражающая специфику задачи, с другой – как не-

которое предположение о способе разрешения проблемы на основе

имеющегося опыта решения подобных задач. Сам процесс эвристиче-

ского программирования можно рассматривать как построение неко-

торого плана действий (планирование решения) с применением эври-

стик. Часто эвристическое программирование используется в задачах

большой размерности, где решение в принципе может быть найдено

перебором.

2.1. Направления эвристического программирования

Эвристическое программирование имеет двоякую цель:

- выяснение сущности естественного интеллекта;

- использование машинного интеллекта для решения сложных

задач.

Эвристическое программирование охватывает несколько на-

правлений, связанных с планированием решения задач ИИ (рис. 2.1)

Все задачи, связанные с построением плана действий, можно

разбить на два типа [11]:

- планирование в пространстве состояний;

- планирование в пространстве задач.

Эвристическое программирование

Эвристический поиск в

пространстве состояний

Эвристический поиск в

пространстве задач

Игровые модели

искусственного интеллекта

Общий решатель задач (GPS)

Планирование решения задач в

системах искусственного интеллекта

Автоматизация инженерного творчества

(поисковое конструирование)

Прикладная

область

Рис. 2.1. Направления эвристического программирования

В первом случае считается заданным некоторое пространство

ситуаций (состояний), требуется найти путь, ведущий из начального

состояний в одно из конечных.

Второй тип задач состоит в поиске декомпозиции исходной за-

дачи на подзадачи посредством введения между ними отношений

«часть-целое», «задача-подзадача», «общее-частное» и т.п., что в ре-

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

В основе решения перечисленных типов задач лежит тот или

иной метод эвристического поиска.

2.2. Эвристический поиск в пространстве состояний

Типичным представителем класса задач, для которых подходит

представление (формализация) в пространстве состояний, является

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

пятнадцать пронумерованных (начиная с 1) подвижных фишек, рас-

положенных в клетках квадрата 4x4. Одна клетка этого квадрата ос-

тается всегда пустой. Передвигая соседние с ней фишки необходимо

добиться упорядоченного расположения их номеров. На рис. 2.2 изо-

бражены две конфигурации фишек для игры в пятнадцать (а) и для ее

упрощенного варианта - квадрата 3x3 и восьми фишек (б). Рассмот-

рим задачу перевода начальной (первой) конфигурации в целевую

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

последовательность сдвигов фишек, например: «передвинуть фишку

8 вверх, фишку 6 влево и т.д.».

Рис. 2.2. Пример перехода между состояниями игры

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

жит рассмотренная головоломка, является наличие в каждой задаче

точно определенной начальной ситуации и точно определенной цели.

Имеется также некоторое множество операций или ходов, переводя-

щих одну ситуацию в другую. Именно из таких ходов состоит иско-

мое решение задачи, которое можно получить (теоретически) мето-

дом проб и ошибок. Действительно, отправляясь от начальной ситуа-

ции, можно построить все промежуточные конфигурации, возникаю-

щие в результате выполнения каждого из возможных ходов, затем

построить множество конфигураций после применения следующего

хода и так далее – пока не будет достигнута целевая конфигурация.

2.2.1. Представление задачи в виде пространства состояний

Ключевым понятием при формализации задачи в пространстве

состояний является понятие состояния, характеризующего некоторый

момент решения задачи. Так, для игры в пятнадцать состояние – это

просто некоторая конкретная конфигурация фишек. Среди всех со-

стояний выделяются начальное состояние и целевое состояние (целе-

вая конфигурация), в совокупности определяющие задачу, которую

надо решить.

Другим важным понятием для рассматриваемого представления

является понятие оператора, или допустимого хода в задаче. Опера-

тор преобразует одно состояние в другое, являясь, по сути, функцией,

определенной на множестве состояний и принимающей значения из

этого множества. Для рассматриваемой игры удобнее выделить четы-

ре оператора, соответствующие перемещениям пустой клетки влево,

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

неприменимым к какому-то состоянию: например, операторы вправо

и вниз неприменимы, если пустая клетка расположена в правом ниж-

нем углу (соответствующая функция является частично определен-

ной).

В терминах состояний и операторов решение задачи есть опре-

деленная последовательность операторов, преобразующая начальное

состояние в целевое. Решение задачи ищется в пространстве состоя-

ний – множестве состояний, достижимых из начального состояния

при помощи операторов. В игре в пятнадцать пространство состояний

состоит из всех конфигураций фишек, которые могут быть образова-

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

Таким образом задача эвристического поиска содержательно

может быть представлена в следующем виде [11]. Заданы начальная

ситуация (объект, состояние), конечная ситуация и множество опера-

торов, преобразующих одну ситуацию в другую. Требуется найти та-

кую последовательность операторов, которая преобразует начальную

ситуацию в конечную наилучшим образом. Математически данная

задача описывается с помощью четырех множеств





TFSS ,,,

, где

S – множество состояний;



- множество начальных состояний;



- множество конечных состояний;

F – множество операторов.

Метод решения задачи





TFSS ,,,

называется методом эври-

стического поиска, если он на каждом шаге находит все возможные

применения операторов к данному текущему состоянию, а порядок

рассмотрения состояний и порядок применения операторов управля-

ется свойствами уже рассмотренных до этого шага состояний.

2.2.2. Представление пространства состояний

Пространство состояний можно представить в виде графа, вер-

шины которого соответствуют состояниям, а дуги – применяемым

операторам. Тогда решение задачи – это путь, ведущий от начального

состояния к целевому. На рис. 2.3 показана часть пространства со-

стояний для игры в пятнадцать, в каждой вершине помещена та кон-

фигурация фишек, которую она представляет. Пространства состоя-

ний могут быть большими и даже бесконечными, но в любом случае

предполагаются конечность множества допустимых операторов и ко-

нечность множества возможных состояний.

Итак, формализация задачи с использованием пространства со-

стояний включает выявление и определение следующих составляю-

щих:

- формы описания состояний и описание исходной задачи;

- множество операторов и их воздействий на описания состоя-

ний;

- указание свойств целевых состояний.

Эти составляющие задают (неявно) пространство, в котором

требуется провести поиск решения задачи.

Рис. 2.3. Фрагмент пространства состояний для игры в пятнадцать

Ясно, что решение задачи, представленной описанным спосо-

бом, можно в принципе обнаружить, осуществляя последовательный

поиск или перебор вершин в пространстве состояний. В начале этого

процесса к начальному состоянию применяется тот или иной опера-

тор. Затем на каждом шаге поиска к одному из уже полученных

(просмотренных) состояний применяется допустимый оператор и

строится новая вершина. Поиск заканчивается, когда построено целе-

вое состояние.

Математически пространство состояний может быть представ-

лено как граф G(X, E), где

},...,,{

110 



xxxX

- множество (в общем

случае бесконечное) вершин графа, каждая из которых отождествля-

ется с одним из состояний



;

)}(,,|),{(

ijjiji

xFxXxxxxE





- множество дуг или ребер графа

бесконечное, если бесконечно множество X. Все ребра в графе явля-

ются взвешенными, т.е. им присвоено некоторое значение (вес), по-

зволяющее оценить с помощью оценочной функции

)

(



переход от

одного состояния к другому;

F(x) – преобразование, порождающее все дочерние вершины

от x.

| F(x) | - количество дочерних вершин от x, т.е. вершин, соеди-

ненных с x дугой.

Структура графа пространства состояний представляется в виде

матрицы весов (значений оценочной функции) графа:

][

, ji

,...,





, в которой

соответствует значение веса ребра

(

xx ,

) или 0, если вершины

x ,

x не связаны ребром (

xx ,

Если граф пространства состояний не является простым, то он

должен быть преобразован в него посредством исключения всех пе-

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

ребром (ребром с наименьшим весом) из этого множества, каждое

неориентированное ребро заменяется парой ориентированных.

В множестве вершин X выделяют подмножество вершин



, соответствующее множеству начальных состояний



, соответствующих множеству конечных состояний



Определим путь в графе G как

)...,(

121 



xxxr

, где

Exx





),(

,...,





Если



, то решение задачи эвристического поиска

в пространстве состояний сводится к задаче поиска пути r на графе

G. Сумма всех ребер в пути называется весом или длиной пути.

Рассмотрим еще один пример представления задачи в простран-

стве состояний, а именно задачу о коммивояжере. В ней коммивоя-

жер, располагая картой дорог между несколькими городами, должен

выстроить кратчайший маршрут своей поездки так, чтобы побывать в

каждом городе, но не более одного раза. На рис. 2.4 показана карта

дорог между 7 городами.

Рис. 2.4. Пример задачи о коммивояжере

Для этой задачи фрагмент пространства состояний, представ-

ленного деревом, приведен на рис. 2.5.

Рис. 2.5. Фрагмент пространства состояний для задачи о коммивояжере

Таким образом, алгоритм поиска решения этой задачи заключа-

ется в построении дерева пространства состояний посредством пере-

бора его вершин до тех пор, пока не будет обнаружена целевая вер-

шина. При этом эффективность решение будет зависеть от такого

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

Вершины и указатели, построенные в процессе перебора, обра-

зуют поддерево всего неявно определенного пространства состояний.