Xreferat.com » Рефераты по экономико-математическому моделированию » Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления

Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления

align="LEFT" hspace="13" />


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


2. Методология решения задачи


2.1 Модель представления знаний для проекта «Учебное расписание»


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

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

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

Наиболее часто используемые модели представления знаний для решения задач искусственного интеллекта (ИИ) приведены в табл. 1.1.

Таблица 1.1


Описательные формализмы Иерархия Наследование Модульность
Семантические сети + - -
Фреймовая модель + + -
Продукционная модель + - +
ОО модель + + +

Для проекта "Учебное расписание" был выбран объектно-ориенти­рованный (ОО) формализм представления знаний, который можно трак­товать как уточнение формализма фреймов (в формализме фреймов не делается различия между видом отношений класс/подкласс и видом отношений класс/конкретный экземпляр, в то время как в ОО форма­лизме эти два вида отношений являются ортогональными).

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

1. Идентификация классов и объектов данного уровня абстрак­ции;

2. Идентификация семантики классов и объектов;

3. Идентификация связей между классами и объектами;

4. Идентификация классов и объектов (программная реализация).


2.1.1. Объектно-ориентированная модель представления знаний


Концептуальной основой объектно-ориентированного стиля представления систем является подход, которому соответствуют четыре главных элемента:

- абстрагирование;

- ограничение доступа;

- модульность;

- иерархия.

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

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

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

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

- общедоступная;

- защищенная;

- обособленная (скрытая).

К = <А, Ф>, (2.1)


где

А – атрибуты класса;

Ф – функции (методы) класса.


В свою очередь:



А =<ОА, ЗА, СА>, (2.2),

а

Ф = <ОФ, ЗФ, ОФ>, (2.3)

где

О[А,Ф] - общедоступные элементы класса;

З[А,Ф] - защищенные элементы класса;

С[А,Ф] - скрытые элементы класса.

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

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

В обособленной части интерфейса класса декларируются опреде­ления, "скрытые" для объектов всех других классов.

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

Модульность является свойством системы, которое связано с возможностью декомпозиции ее на ряд тесно связанных модулей (об­ластей).

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

- наследование;

- использование;

- метаклассы.

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

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

Метакласс (абстрактный класс) является классом, объекты ко­торого сами являются классами.

2.1.2. Блочная альтернативная сеть

2.1.2.1. Элементарный блок альтернатив


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

Пусть существует объект R (R~О), который будем называть ре­шением. При этом существует несколько показателей (атрибутов), характеризующих объект:

П = (П1,...,П,... ,ПN) (2.4)

Каждый атрибут может принимать качественные и количественные значения, которые определяются как параметры (значения атрибута). Эти параметры могут быть постоянными и переменными во времени:

П=(1, …, j, …, I),

или (2.5)

А=(1, …, j, …, I)

Схема атрибутивного представления решения сложной задачи приведена на рис. 2.1.

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

R <=> (А1 ... А ... АN). (2.6)

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

А1 = (11, …, 1j, …, 1m1)

…………………………..

А = (1, …, j, …, m) (2.7)

……………………………

AN = (N1, …, Nj, …, NmN)


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

атрибут А и набор его альтернативных значений j, если сам ат­рибут и его значения заданы. Следует отметить, что значения j атрибута А могут иметь непрерывный или дискретный характер. Это могут быть числовые величины или некоторые понятия. Отношение ат­рибут-значение можно представить в виде первичного дерева иерар­хии (рис. 2.2).

Здесь атрибут А выступает в качестве корневой вершины, а значения j (j=l,... ,N) определяются как альтернативные, так как предполагается, что в любой момент времени атрибут А может при­нимать одно и только одно значение j.

Элементарный блок альтернатив (БА) можно представить как пои­менованную .структуру организации данных, т.е. класс, определяющий множество объектов-альтернатив (рис. 2.3).

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


Решение - R





1

о

m



Рис. 2.1 Атрибутивное представление решения сложной задачи



А




Рис. 2.2 Отношение атрибут-значение в виде первичного дерева иерархии


вход

А






R


T





якорь


выход



Рис. 2.3. Элементарный блок альтернатив


Инкапсулируя БА с ФБА, получим замкнутую систему работы с данными по поиску и выборке альтернатив (рис. 2.4).

Тогда входной массив данных Ах можно интерпретировать как набор входных аргументов для ФВА, а выходной массив Ау сопоста­вить с конкретным объектом-альтернативой, атрибутивным описанием которого является Ау.

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

Формально реализацию механизма эвристического поиска предста­вим в виде следующей последовательности:

Этап 1. Выбор из множества возможных действий некоторого действия:

1) с учетом соответствия цели:

- уменьшение некоторого нежелательного различия,

- непосредственное решение той или иной подзадачи;

2) с учетом опыта:

- повторение прошлого,

- обнаружение ключевого действия;

3) с учетом необходимых условий:

- решение, обусловленное анализом ситуации,

- исключение неосуществимого варианта;


4) с учетом фактора случайности:

  • предпочтение отдается разнообразию.

Этап 2. Осуществление выбранного действия и изменение текущей ситуации.

Этап 3. Оценка ситуации:

1) по аналогии:

- известна сама задача,

- известна подзадача;

2) по величине расстояния до цели:

-расстояние между двумя ситуациями,

-количество усилий, затрачиваемое на поиск;

3) по математическому критерию:

- составление перечня необходимых и/или достаточных для полу­чения данного решения характеристик,

- численная оценочная функция,

- верхние и нижние границы,

- сумма стоимостей, выбранных подходящим способом;

4) по ожидаемому выигрышу (критерий, связанный с прошлым опытом):

- простота ситуации,

- коэффициент расширения поиска,

- любой другой критерий (сложность задачи, затрачиваемое на

ее решение время и т.д.).

Этап 4. Исключение бесполезных ситуации.

Этап 5. Если достигнута конечная цель - конец, иначе выбор новой исходной ситуации и повторить поиск:

1) движение только вперед:

- систематическое развитие последней порожденной ситуации;

2) выполнение действий параллельно:

- поочередное выполнение всех действий;

3) выбор в качестве исходной самой многообещающей ситуации:

- в отношении оценочной функции,

- в отношении незначительного числа входящих в нее действий;

4) компромисс между:

- глубиной поиска,

- оценкой ситуации.


2.1.2.2. Структуры БАС

Блок, представленный на рис. 2.4., является базовым для пост­роения сетей, называемых блочными альтернативными сетями (БАС). Возможные структуры БАС определяются иерархией отношений между классами объектов-альтернатив.

Одной из возможных конфигураций может быть последовательная БАС. Пусть задан кортеж атрибутов {А: =1, N}, на основе которого формируется БАС с последовательной стратегией, вид которой предс­тавлен на рис. 2.5.

Замкнутый аналог последовательной БАС представлен на рис. 2.6.


ФБА

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: