Литература:
1. «Искусственный интеллект», Нильсон; Слейгл; Хант; Уинстон; Поспелов Д.А.(Ситуационное управление-детище Поспелова!!!).
2. Каширин И.Ю. «ПСИИ» (РГРТА) 2000г.
3. «Полиморфическое представление знаний в Semantic Web» Каширин, Пылькин, 2010г.
Интеллектуальные решатели задач(ИРЗ)
ИРЗ - это программные системы, моделирующие мыслительную деятельность человека при решении сложных задач, в которых существует большое поле вариантов выбора, планов решений.
Условия, при которых необходимо применение ИРЗ:
1. Наличие задачи с возможностью выбора на каждом из этапов её решения множества альтернативных действий.
2. Использование в предметных областях, где присутствие человека в силу ряда причин невозможно.
3. Для которых еще не найдено готовых математических методов решения задач.
4. Для исследования структуры естественного интеллекта человека.
Классически ИРЗ используют методы эвристического программирования.
Эвристическое программирование
Эврика – открыл, озарение, интуитивное открытие. Существует два определения эвристических программных систем:
1. Программные системы, использующие переборные алгоритмы с сокращением перебора на основе заложенных знаний человека – эксперт.
2. Любые программные системы, в которых сложные и точные математические вычисления заменены на упрощенные готовые решения, взятые из априорного опыта человека.
Деревья вариантов
Теоретической основой эвристического программирования является понятие дерево вариантов(ДВ). ДВ – это дерево, вершины которого соответствует ситуациям в предметной области для рассмотрения возможного изменения этих ситуаций, для приближения текущей ситуации к целевой.
Целевая ситуация – программная модель ситуации предметной области, которая должна быть достигнута для решения интеллектуальной задачи.
ДВ принято делить на эксплицитные и имплицитные.
Эксплицитным является дерево, все вершины которого заранее известны.
Имплицитным называется ДВ с известной начальной ситуацией и известной процедурой определения целевой ситуации. Предполагается так же, что известна порождающая процедура.
Порождающая процедура – это алгоритм порождения дочерней вершины в дереве вариантов (выполнение хода).
В зависимости от числа активных объектов в предметной области, ДВ подразделяют на однородные(1 активный объект) и неоднородные(с двумя и более активными объектами).
Пространство задач и пространство состояний
В зависимости от представления задачи и способов её решения различают деревья поисков(ДВ) в пространстве состояний и деревья поисков в пространстве задач. При поиске в пространстве состояний вершины дерева соответствуют ситуациям предметной области. При поиске в пространстве задач вершины соответствуют подзадачам, решение которых необходимо для решения задач более верхнего уровня.
Для поиска в пространстве подзадач характерно применения и\или - деревьев. Они состоят из двух типов вершин: И - вершины соответствуют задачи, для решения которой необходимо найти решения всех её подзадач; ИЛИ – вершина соответствуют задаче, для решения которой необходимо решение хотя бы одной из подзадач.
Поиск на деревьях
Поиск в глубину, алгоритм основан на последовательном переборе вариантов, изменении начальной ситуации, начиная каждый раз с самого левого потомка вершин. При этом исследуются дочерние вершины до обнаружения решения (целевой ситуации) или тупика. В случае обнаружения тупика алгоритм реализует возврат к отцовской порождающей вершине и осуществляет попытку рассмотрения очередного варианта. Алгоритм заканчивается при отыскании любой из целевых вершин или при обнаружении ситуации, в которой начальная вершина является тупиковой. Тупиковой, называется вершина относимая к тупиковым соответствующей логической подпрограммы, или вершина, все потомки которой так же тупиковые вершины.
Поиск в ширину, алгоритм основан на переборе вариантов параллельно во всех возможных направлениях на дереве вариантов. Этот алгоритм исследует вершины уровня 1, затем уровня 2 и т.д., пока не будет найдено ближайшее решение или все тупиковые вершины.
Оценочные функции
Более мощные алгоритмы поиска используют априорные знания человека – эксперта об особенностях решения задач в заданной предметной области. В эвристических программах эти знания реализуются с помощью оценочных функций. Оценочной функцией называется функция от n аргументов, представляющие собой некоторые числовые (или приведенные к числовым) параметры предметной области и вычисляющая меру близости любой из текущих ситуаций к целевой. Можно представить значения оценочной функции как точки N – мерного пространства.
Стратегии поиска с оценочными функциями
Метод наискорейшего подъема (поиск по градиенту)
Алгоритм заключается в использовании правила максимизации с опорой на поиск в глубину. При этом, возможные ходы выбираются не случайным образом, а в соответствии со значениями оценочной функцией. То есть сначала выбирается наилучший ход, а потом другой, оцененный ранее как менее предпочтительный.
Поиск от наилучшего частичного пути
Этот алгоритм является модификацией предыдущего. Но оценка производится с помощью перебора в ширину не на один ход вперед, а сразу на несколько (n ходов вперед). Далее выбирается лучший из ходов последнего уровня и делается попытка рассмотрения вариантов еще на m ходов в глубину. Если, оценочного функция лучшего из этих ходов уточняется в не худшую сторону поиск можно продолжить в этом же направлении. В противном случае реализуется возврат на один шаг назад и делается попытка рассмотрения вариантов оцененных ранее как, менее предпочтительнее.
Стратегия ветвей и границ
Практически все задачи искусственного интеллекта можно рассматривать как задачи с затратами на выполнение хода, где каждый ход имеет определенную стоимость (трудоемкость) и нужно найти наименее затратное решение. В простейшем случае каждый ход может иметь затраты равные единице. В этом случае функция может рассматриваться как вычисляющая затраты на выполнение хода. Стратегия ветвей и границ заключается в расчете затрат одного уровня дерева вариантов и последующем расчете суммарных оценок следующих уровней. При поиске выбирается ветвь с наименьшей оценкой суммарного частичного пути, что позволяет сократить число рассматриваемых вариантов.
Оценку пути C и Е не имеет смысл производить на втором уровне, поскольку суммарные затраты на путь А в Б в Д равные 4 меньше, чем затраты на один ход А в С, равным 5.
А
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
