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

ПРОЕКТИРОВАНИЕ ИНТЕЛЛЕКТУАЛЬНЫХ РЕШАТЕЛЕЙ НА ОСНОВЕ ЭВРИСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ 1.1. Понятие эвристического программирования Интеллектуальные решатели задач были исторически одними из первых реальных программных систем, в которых использовались методы искусственного интеллекта. Первые реализации игровых программ, таких как рэндзю, шашки и шахматы, показали состоятельность теоретических концепций искусственного интеллекта и вызвали к жизни множество новых проектов, направленных на дальнейшее развитие интеллектуальных программных систем. Основой интеллектуальных решателей задач, которые проектировались для моделирования мыслительной деятельности человека, были различные алгоритмические стратегии поиска решения в сложных предметных областях, основанные на так называемых эвристиках. Само понятие эвристики ( в переводе с греческого означает способствование открытию ) характеризует разновидность однотипных программных процедур, не обладающих строгими свойствами алгоритма и направленными на поиск решения посредством проверки различных по степени обоснованности гипотез. Таким образом, эвристические процедуры всегда связаны с работой некоторого переборного механизма, предназначенного для исследования вариантов решения. Проектирование таких процедур получило название эвристического программирования. В последние годы, как это часто бывает с наиболее серьезными теоретическими концепциями, в понятие эвристического программирования или эвристических систем стали вкладывать более широкий смысл. Сейчас такими системами считаются программные комплексы, использующие неформализованные знания эксперта в какой-либо конкретной предметной области для решения интеллектуальных задач. Такое понимание эвристических систем иногда может быть оправдано, но, вместе с тем, следует отличать эти системы от экспертных систем, в которых основой являются не стратегии поиска решения, а собственно знания, представляемые в форме упорядоченного множества продукций (правил вида “если Х, то Y”) или каким-либо другим образом. Современное понимание эвристических систем может быть наиболее точно выражено с помощью понятия программной машины, как некоторого формального аппарата, позволяющего описать базовый программный или программно-технический инструментарий как формальную машину, в рамках которой можно проектировать различные по назначению, но одинаковые по методам реализации автоматизированные системы. Эвристические программные машины проектируются со следующими целями: • упрощение синтаксиса интеллектуальных языков программирования и получение новых более мощных инструментальных программных средств, • исследование структуры естественного интеллекта, • создание спецпроцессора на основе предварительной математически строгой разработки соответствующей программной машины. Эвристическое программирование применимо там, где невозможно использовать готовый математический аппарат, обладающей возможностью с заданной точностью, достоверностью и эффективностью решать определенного типа задачи с многовариантным полем шагов решения. Такое определение области применения эвристических методов в целом характерно и для других методов искусственного интеллекта, поскольку эти методы построены на подобии человеческим рассуждениям со свойственными им интуицией, ассоциативностью и нечеткостью. 1.2. Деревья вариантов Формальную основу методов эвристического программирования составляет понятие дерева вариантов. Дерево вариантов - дерево, вершины которого соответствуют статическим ситуациям, получаемым в математической модели предметной области при попытках рассмотрения вариантов изменения этих ситуаций для приближения их к целевой ситуации предметной области. Изменение ситуации соответствует некоторому действию человека, который хочет приблизить ситуацию к целевой. Такие изменения иногда называют “ходами”, которые оценивает эвристическая программа, после чего выбирает наилучшую комбинацию ходов из какого-либо множества вариантов. Целевая ситуация - математическая модель ситуации в ограниченной предметной области, которая должна быть достигнута для решения поставленной задачи. Примером целевой ситуации может быть, например, матовая ситуация в шахматах, равновесное состояние некоторого химического процесса, отсутствие аварийного ожидания, получение высокой прибыли предприятием и т.п. Деревья вариантов принято подразделять на эксплицитные и имплицитные. Эксплицитным называется дерево вариантов, все вершины которого заранее известны. Такое дерево, например, можно использовать при компьютерном моделировании игры в “крестики-нолики” на поле размером 3х3, поскольку в этом случае легко перечислить все возможные варианты ходов заранее. Для более сложных задач невозможно заранее определить всего множества ходов, и этот случай является наиболее частым. Имплицитным называется дерево вариантов с известной начальной ситуацией в предметной области и известными критериями определения целевой ситуации. Кроме того предполагается, что известна порождающая процедура. Порождающая процедура - алгоритм порождения дочерней вершины (на основе выполнения хода) в дереве вариантов. Таким образом имплицитное дерево строится программой в процессе поиска ею решения интеллектуальной задачи. Сделанные определения позволяют рассматривать деревья вариантов как множество вершин, связанным между собою ребрами. Каждая вершина соответствует некоторой воображаемой ситуации в предметной области, а выходящие из нее ребра представляют собой возможные шаги, изменяющие эту ситуацию, приближая ее к целевой или удаляя от цели. Предполагается, что изменение ситуации производится некоторым активным объектом (например, игроком) по определенным правилам, допускаемым природой предметной области. Ребра, выходящие из какой-либо вершины, можно называть ходами, возможными в конкретной ситуации предметной области, которой соответствует эта вершина. Дерево вариантов демонстрируется рисунком 1.1 . На этом рисунке вершина S0 соответствует начальной ситуации, заданной для решения какой-либо задачи в предметной области, например, начальная расстановка фигур в шахматах. SF соответствует целевой ситуации, например, ситуации в задаче поиска выхода из лабиринта “найден выход”. Остальные вершины являются либо промежуточными ситуациями при решении задачи, либо заключительными-тупиковыми (например, робот в лабиринте наткнулся на стенку или обнаружена ситуация полного проигрыша). При исследовании деревьев вариантов учитывают число активных объектов в предметной области, которые могут изменять в ней ситуацию, приближая ее к целевой или наоборот, удаляя от целевой. Каждый из активных объектов таким образом является “игроком”, делающим определенные правилами предметной области “ходы”. У игроков различные цели в игре, зачастую являющиеся противоположными целям других игроков. В зависимости от числа активных объектов деревья вариантов подразделяют на однородные, т.е. с одним активным объектом, и неоднородные, с двумя и более активными объектами. Графически такие деревья можно представить рисунком 1.1 для однородного дерева и рисунком 1.2 для неоднородного дерева вариантов. Каждая из вершин этого дерева должна быть как-либо идентифицирована с целью определения объекта, который повлиял на самое последнее изменение текущей ситуации. S0 ( Начальная ситуация ) (Промежуточная ситуация) (Тупиковые ситуации) SF (Целевая ситуация) Рис. 1.1. Пример дерева вариантов Так, например, дерево вариантов для игры в шахматы является неоднородным с двумя типами вершин, одни из которых соответствуют ходу черных, а другие - ходу белых. 1.3. Пространство задач и пространство состояний В зависимости от способа представления задачи и способов ее решения различают деревья поиска: • дерево поиска в пространстве состояний, • дерево поиска в пространстве задач. Дерево поиска в пространстве состояний - это дерево, вершинами которого являются состояния решающей машины (программы) (Рисунки 1.1, 1.2), т.е. текущая ситуация на используемой модели решения, а также текущее содержимое памяти компьютера для выбранной модели данных. Дерево поиска в пространстве задач - дерево, вершины которого являются подзадачами, решение которых необходимо для решения задач более верхнего уровня. S0 ( Игрок № 1 ) ( Игрок № 2 ) ( Игрок № 1 ) ( Игрок № 3 ) Рис. 1.2. Неоднородное дерево вариантов Для дерева поиска в пространстве задач, иногда называемого деревом целей, характерно использование И/ИЛИ-графов. Этот вид графов имеет два типа вершин: И-вершины, характеризующие задачу, для решения которой необходимо отыскать решения всех задач, которые соответствуют дочерним вершинам И-вершины, ИЛИ-вершины соответствуют задачам, для решения которых необходимо найти решение хотя бы одной из подзадач, которые соответствуют дочерним вершинам этой ИЛИ-вершины. Примером И/ИЛИ-деревьев служит представление задачи, приведенное на рисунке 1.3. Составить программу Составить алгоритм Составить текст И-вершины ИЛИ-вершины Использовать Использовать Использовать Использовать графику блок-схемы готовые фрагменты новый текст Рис.1.3. Пример И/ИЛИ-дерева Как следует из рисунка, начальной задачей является достижение цели“Составить программу”. Эта задача распадается на две подзадачи, решение которых нужно получить для решения главной задачи. Эти подзадачи определяются И-вершинами, т.е. должны быть решены вместе: “Составить алгоритм” и “Составить текст”. Для решения каждой из задач этого уровня необходимо найти решение хотя бы одной из подзадач: “Составить алгоритм, используя графический инструментарий” или “Составить алгоритм, используя ручное рисование блок-схем” - в первом случае, и “Написать текст, используя готовые фрагменты” или “Написать текст программы заново”. Если продолжить рисование И/ИЛИ-дерева, далее будет следовать уровень И-вершин, затем снова ИЛИ-вершины и т.д., т.е. чередование типов вершин по уровням является строгим. Эта строгость определяется элементарной математической логикой, следуя которой, два последовательных уровня И-вершин легко преобразуются в один уровень, также, как два уровня ИЛИ-вершин легко преобразовать в один. Методология И/ИЛИ деревьев часто используется в программных машинах языков программирования искусственного интеллекта, например в Прологе.