МОСКОВСКИЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Факультет Кибернетики

Кафедра Интеллектуальных технологий и систем (ИТС)

Курсовая работа

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

Студенты:

Группа: АИ-1-91

Руководитель: Нечаев В. В.

Москва 1996 г.

Задание на курсовое проектирование по дисциплине «Основы теории творческой деятельности» студентам группы АИ-1-91.

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

2. Исходные данные:

   1. Теория концептуального метамоделирования.

   2. Методы решения системных задач.

   3. Список литературы.

   4. Методические указания к курсовому проектированию.

   5. Конспект лекций.

   6. Тема дипломного проекта.

3. Перечень вопросов, подлежащих разработке:

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

   2. Проведение анализа конкретной задачи, выносимой на курсовую работу.

   3. Выбор и обоснование метода решения задачи.

   4. Анализ и описание метода решения задачи.

   5. Описание решения задачи на основе выбранного метода.

4. Календарный план-график работы:

1. Получение задания 21.04.96.

2. Анализ задания, подбор и изучение литературы 25.04.96.

3. Разработка концептуальной метамодели объекта моделирования 09.05.96.

4. Оформление пояснительной записки и сдача проекта на проверку 21.05.96.

5. Защита курсового проекта 24.05.96.

Руководитель …………..(Нечаев В. В.)

^(подп.)

Исполнители

^(подп.)

Содержание

Введение

1. Постановка задачи

   1. Концептуальное метамодельное представление задачи

   2. Форма организации учебного процесса и базовые компоненты предметной области

      1. Аудиторный фонд

      2. Контингент учащихся

      3. Профессорско-преподавательский состав

      4. Комбинированный учебный план

      5. Расписание занятий

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

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

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

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

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

2.1.2.2 Структура БАС

2.2. Методы формирования решения

2.2.1 Алгоритмы навигации на БАС

2.2.2. Маршруты на БАС

2.2.3 Оценка результатов решения задачи на БАС

3. Реализация БАС на ОО системе в проекте «Учебное расписание»

3.1. Структура класса

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

3.3. Фрагмент решения задачи «Формирование учебного расписания»

3.3.1.Класс «Учебный блок»

3.3.2. Класс «Блок занятия»

3.3.3. Класс «Блоки занятий»

Список литературы

4

5

8

8

8

9

10

11

13

13

14

16

16

21

22

22

23

26

27

27

29

31

31

35

38

40

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

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

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

1) выбор методологии решения задачи на основе искусственного

интеллекта;

2) определение алгоритма реализации метода;

3) разработка пакета программ, реализующих алгоритм.

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

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

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

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

Экономическая эффективность решения задачи будет оценена на основе методов функционально-стоимостного анализа

1. Постановка задачи

1.1. Концептуальное метамодельное представление задачи

Концептуальное метамодельное (КММ) представление задачи определим в виде кортежа:

где;

 - проблемная ситуация, являющаяся исходным посылом для построения КММ задачной системы;

Z - определяет цели "неудовлетворенной потребности", в ре­зультате которой порождается проблемная ситуация;

С - определяет условия достижения цели;

I - определяет исходную информацию, в зависимости от кото­рой цель порождает различные решения (R).

В качестве условий определим следующий необходимый и доста­точный набор компонент:

- метод решения (М);

- алгоритм (А);

- программу (Р);

- оценку адекватности, релевантности (_ад).

Кортеж целей тогда запишется в следующем виде:

Z = < М, А, Р, _ад>. (1.2)

Исходная информация включает в себя данные (D), необходимые для решения задачи, и знания (К) о предметной области задачи:

I = , K> (1.3)

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

I^* = Z, I^M, I^A, I^P, I^>. (1.4)

Адекватность решения задачи представим как совокупность пока­зателей качества и эффективности:

_ад = Г (Qw, Ef). (1.5)

Развитие задачи (Тр) связано с заполнением задачной оболочки в форме КММ конкретными сведениями, определяемыми решением зада­чи.

Как известно, возможны следующие постановки задач:

1) Рутинная задача, когда кортеж (1.1) и (1.2) заданы пол­ностью (Т_P-Р_R).

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

3) Творческая задача уровня алгоритма (Т_Р-Р_А), т.е. неизвес­тен алгоритм (А) и его программная реализация.

4) Творческая задача уровня метода решения (Тр-Рм), когда не­известны метод, алгоритм и программа.

Схему решения задачи в общем виде представлена на рис. 1.1, а логическая схема решения задачи в виде схемы алгоритма на рис. 1.2.

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

- генерации решений;

- анализ полученных решений;

- формирование парадигмы решений;

- упорядочение альтернативных решений ;

- выбор удовлетворительного результата;

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

R = F:{(Z_R/C  (R/I_R)}, (1.6)

т. е. решение определяется, исходя из заданных целей и условий достижения целей.

Системная задача Р

P_M

P_A

P_P

P_R

Р

Исходная задача

Задача метода

Задача алгоритма

Задача программы

Задача результата

нет

нет

нет

нет

нет

нет

нет

нет

да

да

да

да

да

да

да

да

ис. 1.1 Схема решения системной задачи

Рис. 1.2 Логическая схема (алгоритм) решения системной задачи

1.2. Форма организации учебного процесса и базовые компоненты предметной области

В соответствии с принятой системой правил организации учебно­го процесса каждый факультет (кафедра) ВУЗа самостоятельно форми­рует себе расписание занятий, согласовывая с другими факультетами (кафедрами) вопросы совместного использования аудиторного фонда и труда профессорско-преподавательского состава.

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

1.2.1. Аудиторный фонд

Аудиторный фонд (АФ) - каталог помещений ВУЗа, в которых пла­нируется проведение занятий.

Каждое помещение (аудитория) характеризуется двумя основными параметрами:

АФ = <ФНА, ЕВ>, (1.7)

где ;

ФНА - определяет функциональное (занятийное) назначение ау­дитории;

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

По своему функциональному назначению различают три типа поме­щений:

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

- аудитории для проведения практических занятий (семинаров);

- аудитории для проведения лабораторных занятий.

1.2.2. Контингент учащихся

Контингент учащихся (КУ) - иерархическая древовидная структу­ра организации учебных формирований (УФ) (рис. 1.3). В целях ми­нимизировать возможность потери общности данных о КУ определим следующие базовые единицы:

- курс;

- поток;

- временный поток;

- учебная группа.

Курс - условное обозначение вершины дерева, в которое включа­ются всё учебные группы, сформированные в определенный год.

Поток - объединение одной или нескольких учебных групп одного года формирования.

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

Учебная группа - самостоятельная неделимая учебная формация.

Курс

Поток 1

Поток 1.1

Учебная группа I.I.I

Поток 1.2

Учебная группа 1.2.1

Учебная группа 1.2.2

…………………………………

Рис. 1.3. Организация КУ

1.2.3 Профессорско-преподавательский состав и дисциплины

Профессорско-преподавательский состав (ППС) объединяет людей (преподавателей), ответственных за проведение занятий.

Преподавателя характеризуют две составляющие:

ППС = <З, ТНД>, (1.8)

где

З - определяет звание (должность) преподавателя;

ТНД - определяет тематическую направленность дисциплины (Д), которую "читает" преподаватель:

Д <=> <ТНД>, (1.9)

Должность преподавателя определяет формальную систему приори­тетов:

- профессор;

- старший преподаватель;

- преподаватель;

- совместитель;

- аспирант.

ТНД может иметь также и сложную структуру, объединяя в себе набор дисциплин с разными тематиками:

ТНД*= {ТНД₁, ... , ТНД_N}. (1.10)

1.2.4. Комбинированный учебный план

Комбинированный учебный план (КУП) - таблица, в которой каж­дому учебному формированию поставлены в соответствие определенные дисциплины с указанием учебной нагрузки, выраженной в академических часах в неделю для каждого вида занятия, и преподавателя, ответственного за проведение занятия.

КУП формируется из двух составляющих:

КУП =<УП, ПН> (1.11)

где

УП – учебный план кафедры;

ПН – план нагрузки преподавателей кафедры,

или

КУП = <УФ, С, Д, КЧЛК, КЧЛР, КЧПР>, (1.12)

где

УФ - учебное формирование;

С - семестр;

Д - дисциплина;

КЧЛК - количественный показатель, определяющий академические

часы в неделю для лекций;

КЧЛР - количественный показатель, определяющий академические

часы в неделю для лабораторных занятий;

КЧПР - количественный показатель, определяющий академические

часы в неделю для практических занятий.

Семестр характеризуется количеством недель:

С=<КН>. (1.13)

По значению ТНД дисциплины выбирается преподаватель. Параметры КЧЛК, КЧЛР, КЧПР формируют абстрактное понятие ко­личество часов нагрузки (КЧН).

1.2.5. Расписание занятий

Расписание занятий (РЭ) - таблица, в которой указаны место и время проведения занятий.

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

Формальная постановка задачи составления расписания представ­лена на рис. 1.4.

На рис. 1.5. отображена система отношений между объектами проекта "Учебное расписание".

Учебные формирования

Кафедра

П

Р

Е

П

О

Д

А

В

А

Т

Е

Л

И

Д

И

С

Ц

И

П

Л

И

Н

Ы

Комбинированный учебный план

План нагрузки

Учебный план

Расписание

Рис 1.4 Постановка исходной задачи составления расписания

Рис. 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~^О), который будем называть ре­шением. При этом существует несколько показателей (атрибутов), характеризующих объект:

П = (П₁,...,П_,... ,П_N) (2.4)

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

П=(^₁, …, ^_j, …, ^_I),

или (2.5)

А=(^₁, …, ^_j, …, ^_I)

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

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

R <=> (А₁ ... А ... А_N). (2.6)

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

А₁ = (₁₁, …, _1j, …, _1m1)

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

А = (_1, …, _j, …, _m) (2.7)

……………………………

A_N = (_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.

ФБА

Вход Выход

Рис. 2.4. Инкапсуляция БА и ФВА в класс объектов-альтернатив

^БА₁

^БА_N

^БА_

Рис. 2.5. Последовательная разомкнутая БАС

^БА₁

^БА_N

^БА_

Блок обратной связи

Рис.2.6. Последовательная замкнутая БАС

2.2. Методы формирования решения

2.2.1. Алгоритмы навигации на БАС

При работе с БАС возможны следующие варианты навигации:

- последовательная;

- параллельная;

- смешанная.

Для последовательной сети последовательный алгоритм навигации может быть реализован двумя базовыми способами.

1. Прохождение сети реализуется последовательно, начиная с первого a₁ и кончая последним а_N блоками. Алгоритм обращается к блоку a₁, просматривает его содержимое и через транзитные вершины передает результат. Далее переходит к следующему блоку. В итоге образуется некоторый вершинный маршрут R₁=(₁j,... ,_j,.. ,_Nj), который и представляет данные о результате решения. Если частные решения совместны, то они оцениваются по критериям -адекватнос­ти. Если какое-то решение несовместно, то выявляется причина не­совместимости и ищется новое решение.

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

2.2.2. Маршруты на БАС

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

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

Следует отметить, что в элементарном блоке имеет место три вида вершин:

а) вершины первого ранга: вход и выход;

б) вершины второго ранга: значения атрибутов;

в) вспомогательные вершины: рекурсия и транзит.

В зависимости от содержания маршрута и метода его формирова­ния будем различать ациклические и циклические маршруты.

Ациклический маршрут (АМ¹) формируется как последовательность

вершин совместно с отношением между вершинами:

AMⁱ : (Aⁱ r_ij u_ij), (2.8)

где

Аⁱ - атрибут;

r_ij - определяет отношение между атрибутом и вершиной-значе­нием ij;

_ij - значение атрибута Аⁱ.

Полное представление внутриблокового маршрута по схеме ис­ток-сток будет представлять собой объединение:

AMⁱ : (Аⁱ r_ij _ij) U (_ij r_ji A*_i), (2.9)

или в общем виде для вершин-альтернатив получим вершинный ацикли­ческий маршрут:

AM¹: (Аⁱ, _ij, A*_i). (2.10)

Аналогично для маршрута, проходящего через транзитную верши­ну:

АMⁱ_T: (Aⁱ, r_T, A*_i), (2.11)

что эквивалентно записи

AMⁱ_T: (Aⁱ, T, A*_i). (2.12)

В циклическом маршруте (ЦМⁱ) использует вершина с индексом R:

ЦМⁱ_*: (Aⁱ, _ij, A*_I)  R_q, q = 1,2, …, Q (2.13)

где  - определяет повтор маршрутов.

Для циклических маршрутов возможно несколько вариантов реали­зации:

- поиск одной единственной альтернативы;

- использование двух альтернатив вместе;

- поиск с множеством альтернатив.

В первом случае может реализоваться q-кратное прохождение по внутриблоковому маршруту, причем значение q определяется коли­чеством циклов, при котором находится требуемое значение оси,

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

ЦМⁱ_**: (Aⁱ, (_ij, _q1), A*_I)  R_q, q = 1,2, …, Q (2.14)

При дальнейшем увеличении количества описании альтернатив gjлучим циклический маршрут с множеством альтернатив:

ЦМⁱ_**: (Aⁱ, {_ij}, A*_I)  R_q, q = 1,2, …, Q (2.15)

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

М_N ~ MN_, = U MБi, (2.16)

где

MN_ - сетевой маршрут;

MБi - внутриблоковый маршрут.

При таком алгоритме навигации путем склеивания будет получен маршрут:

MN_ = R <=> (R_1,, …, R_i, …, R_N), (2.17)

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

В другом случае имеет место следущая картина, представленная на рис. 2.8.

Для каждого блока альтернатив определяется свой алгоритм вы­бора альтернативы. Алгоритм параллельной навигации, в свою оче­редь, реализует функции координации, которые взаимодействуют с каждым блоковым алгоритмом. Работа осуществляется параллельно. Алгоритм координации передает исходные данные (I^O) в локальные алгоритмы и запускает их в работу. Каждый ив локальных алгоритмов формирует внутриблоковый маршрут и соответствующий результат (R). Далее формируется последовательность (R¹₁, ..., Rⁱ₁, ..., R^N₁)=R_l несвязанных между собой решений. После этого решается задача склеивания частных решений в общее. Данная процедура может проте­кать по двум направлениям:

1)формирование общего решения на уровне координирующего ал­горитма; анализ, оценка, принятие решения для дальнейших дейс­твий;

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

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

2.2.3. Оценка результатов решения задачи на БАС

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

N_R = (m x n) => П{R} (2.18)

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

АНПС

R₁ R_i R_N

БА₁

БА_i

БА_N

Рис. 2.7. Формирование сетевого маршрута с помощью последовательного алгоритма навигации на сети

Алгоритм параллельной навигации

АБ₁

АБ_i

АБ_N

БА₁

БА_i

БА_N

I^O₁ R¹₁ I^O_i Rⁱ₁ I^O_N R^N₁

Рис. 2.8. Формирование сетевого маршрута с помощью параллельного алгоритма навигации на сети

Если этот показатель задан, то он непосредственно используется при анализе и оценке решения, если нет, то для каждого конкретного случая оформляется своя за­дача определения показателя.

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

3. Реализация БАС на 00 системе в проекте "Учебное расписание"

3.1. Структура класса

Учитывая специфику решаемой задачи и методы, используемые для достижения результатов, определим класс для проекта "Учебное рас­писание" как поименованную структуру, которая включает в себя:

К = <А, Ф>,

и соответственно

А = <О_А, З_А, С_А> и Ф = <Оф, Зф, Сф>.

Общедоступная интерфейсная часть описания атрибутов класса включает в себя декларацию признаков объекта, универсально и од­нозначно характеризующих данную абстракцию:

О_А = { а_оi }, (3.1)

где А_Оi – атрибут объекта-экземпляра класса.

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

класса:

с_а = <А_С1, ... , а_сi, ... А_Cn, ФБП>, (3.2)

где

а_сi, - скрытый элемент данных класса;

ФБП - файл базы правил генерации объектов-альтернатив.

Общедоступная интерфейсная часть декларации функций (методов) управления объектами класса представляется следующим образом:

О_Ф = <ФК, ФД, Ф₀₁, ..., Фoi, ...., Фоn, ФОБП>, (3.3)

где

ФК - функция-конструктор класса, определяющая механизм выделения оперативной памяти для хранения объекта-альтернативы (результата);

ФД – функция-деструктор класса, определяющая механизм освобождения оперативной памяти, выделенной конструктором;

Фоi - общедоступный метод управления объектом класса;

ФОБП - набор функций, предназначенных для обработки базы

правил (знаний).

Как минимум кортеж ФОБП включает в себя:

ФОБП = <ФВА, ФДП, ФУП, ФРП>, (3.4)

где:

ФВА - функция выбора альтернативы;

ФДП - метод для добавления правила в базу знаний;

ФУП - метод для удаления правила из базы знаний;

ФРП – метод для редактирования правила в базе знаний.

Функция выбора альтернативы определяет механизмы построения синтаксиса правила, выборки из множества и оценки результатов на основе критериев -адекватности.

Функции добавления/удаления/редактирования правил содержат в своем теле два основных блока: блок добавления/удаления/редактирования правила и блок добавления/удаления/редактирования альтернативы.

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

Правила, представленные в ФБП делятся на две основные группы:

декларативные и продукционные.

Декларативные правила (ДП) определяют в базе знаний множество фактов. Факт в данном случае однозначно отождествляется с конк­ретным объектом-альтернативой абстрактного типа данных. Факт в зависимости от количества атрибутов объекта класса может иметь простую или сложную (составную) структуру.

Продукционные правила (правила ЕСЛИ-ТО) позволяют явным обра­зом задавать критерии необходимости и достаточности количества входных параметров для идентификации объекта-альтернативы. Также в теле правил данного типа могут содержаться записи математичес­ких законов описания множества объектов.

Вне зависимости от типа, правила имеют два вида представле­ния: текстовый и двоичный. Возможные связи между текстовым и дво­ичным представлением правил в базе знаний представлены на рис. 3.1.

Одинарной линией на рис. 3.1. показана связь типа «один к одному», а двойной – связь типа «один к многим».

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

FOR = <В, Е, S, F(С, Ao₁, …, Ao_i, …, Ao_n), O>, (3.5)

где

В - определяет начальное значение счетчика;

Е - определяет конечное значение счетчика;

S - определяет шаг приращения значения счетчика;

F(С, Ao₁, …, Ao_i, …, Ao_n) - определяет математическую ба­зу для генерирования объекта-альтернативы;

С - текущее значение счетчика;

Ao_i - атрибут объекта;

О – определяет режим отображения объекта класса: О=base – отображение в файл БД, О=memory – отображение в оперативную память.

Текстовое представление

ИМЯ_КЛАССА.КВА

Двоичное представление

ИМЯ_КЛАССА.DBF

Декларативное правило 1

Объект-альтернатива 1

Продукционное правило 2

Продукционное правило 3

………………………

Объект-альтернатива 2

Объект-альтернатива 3.1

Объект-альтернатива 3.2

………………………………

Объект-альтернатива 3.i

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

Объект-альтернатива 3.n

Рис. 3.1. Связи между текстовым и двоичным представлением правил

При 0=base объемы-альтернативы собираются в файл базы данных (DBF-файл), где хранится в упакованной виде. Для файлов подобного типа определяются стандартные операции индексирования и фильтра­ции записей, что упрощает и убыстряет механизм поиска и выборки информации из БД.

3.3. Фрагмент решения задачи "Формирование учебного расписания"

Формальное представление алгоритма решения задачи формирова­ния расписания отображено на рио.З.2.

Из рисунка видно, что базовым элементом в системе составления расписания является учебный блок занятий (класс "Учебный блок" на рис. 1.4.).

3.3.1. Класс "Учебный блок"

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

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

Учебный блок составляют две компоненты:

- количество часов в блоке (КЧБ) определяет количество часов, которое блок занимает в сетке расписания одного учебного дня (од­на строка матрицы соответствует двум часам занятий);

• деление блока (Д) распределяет занятие по неделям семестра.

Значения КЧБ и Д рассчитываются на основании данных, из комби­нированного учебного плана. Связующим звеном здесь являемся абс­тракция "Количество часов нагрузки" (КЧН), которая объединяет три класса:

• количество часов лекционных занятий в неделю (КЧЛК);

• количество часов лабораторных занятий в неделю (КЧЛР);

• количество часов практических занятий в неделю (КЧПР).

БАС формирования блоков

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

БАС сопоставления блоков количеству групп

Сочетания: количество групп –

блоки

Сочетания: поток - блоки

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

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

Сочетания: преподаватель - блоки

Расписание на учебной части

Преобразование в блочное представление

Правила компоновки блоков в расписание

Расписание занятий

Рис. 3.2 Общая схема решения задачи сопоставления расписания занятий методами БАС на ООС на основании продукционной модели

*

* * *

*

КЧБ

Д

Рис. 3.3. Структура блока занятий

Обозначим количество недель в семестре как КНС. Тогда, сум­марное количество часов занятий эа семестр (ч) определяется про­изведением КНС и КЧН:

ч = КНС*КЧН, (3.6)

или

ч = (КНС/Д)*КЧБ. (3.7)

Из чего следует:

КЧН = КЧБ/Д. (3.8)

Декларативные правила, входящие в классы КЧЛК, КЧЛР и КЧПР

описывают следующие наборы фактов:

КЧЛК = {0, 1.0, 1.5, 2.0}, (3.9)

КЧЛР = {0, 1.0, 2.0}, (3.10)

КЧПР = {О, 1.0, 2.0}, (3.11)

Объединяя множества в мета-класс, получим:

КЧН = {0, 1.0, 1.5, 2.03}. (3.12)

Используя формулу 3.8, определим область значений объек­тов-экземпляров класса КЧБ и класса Д:

КЧБ = {2, 4, 6}, (3.13)

Д = {2, 3, 4}, (3.14)

Класс «Учебный блок» является наследником класса «Блок занятия».

3.3.2. Класс «Блок занятия»

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

Свободные доли описывают свободные часы занятий в неделю (КЧС).

Декларативное правило генерации параметра КЧС имеет вид:

ПРАВИЛО 1.

блок.КЧС = FOR (1, блок.Д-1, RETURN(C), base).

Объединяя КЧС с данными класса "Учебный блок", сформируем класс "Блок занятия".. Количество свободных (КСД) и занятых (КЗД) долей в блоке занятия определим через его параметры:

КСД = КЧС/КЧН. (3.15)

Используя формулу 3.8, получим;

КСД = Д * (КЧС / КЧБ). (3.16)

Очевидно, что:

КСД + КЗД = Д. (3.17)

Следовательно:

КЗД = Д * (1 - КЧС/КЧБ). (3.18)

На рис. 3.4. приведена структура БАС с алгоритмами навигации для класса "Блок занятий". В результате работы алгоритма, ФВА класса "Блок занятий" был получен набор решений, образующих блок альтернатив, представленный на рис. 3.5.

ФВА (учебный курс)

ФВА (блок занятий)

Рис. 3.4. Схема БАС формирования объекта «Блок занятий»

ФВА (выборка блоков)

Рис. 3.5. ВАС формирования объекта класса «Блоки занятий»

3.3.3. Класс «Блоки занятий».

Уравнения 3.16 и 3.18 необходимы для понятия совместимости блоков занятий.

Два блока Бi и Б2 совместимы, если:

KЧH1 = КЧН2, КЧБ1 = КЧБ2 и КЗД1 <= КСД2 (КЗД2 <= КСД1), (3.19)

Понятие совместимости блоков используется в правилах слияния нескольких блоков в один объект класса "Блоки занятий":

ПРАВИЛО 1.

ЕСЛИ стратегия.тип = общая

И блок(&А).КЧН = блок(&Б).КЧН

И блок (&A).КЧБ = блок (&Б).КЧБ

И блок(&А).КЗД <= блок (&Б).КОД ТО блок(&С) = блок(&А) U блок(&Б).

ПРАВИЛО 2.

ЕСЛИ стратегия.тип = общая

B блок(&А).КЧН == блок(&Б) .КЧН

И блок (&A). КЧБ = блок(&Б). КЧБ

И блок(&А). КCД >= блок(&Б). КЗД ТО блок(&C) = блок(&A) U блоков(&Б).

Класс "Блоки занятий" объединяет абстрактные потоки, которые характеризуются параметром "Количество групп в потоке" (КГ), и оптимальную совокупность блоков.

Схема алгоритма генерации объектов класса "Блоки занятий" отображена на рис. 3.6.

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

Ptr - указатель на текущий объект в описке альтернативных блоков занятий;

AltList - список блоков занятий, определяющих в совокупности одну альтернативу для текущего количества групп;

Len(AltList) - длина списка AltList.

Ptr=1

Взять блок по указателю; сохранить старое значение списка блоков в альтернативе Рассчитать КЧН_Б, КЗД; Сохранить КГ, КЧН_Б

Поместить блок в список блоков в альтернативе; КГ=КГ-КЗД

Включить альтернативу в список альтернатив для текущего КГ

ДА

Ptr+1

НЕТ

ДА

НЕТ

ДА

НЕТ

Ptr+1

Восстановить альтернативу

ДА

НЕТ

Рис 3.6. Схема алгоритма генерации объектов класса "Блоки занятий"

Список использованной литературы

Буч Г., Объектно-ориентированное проектирована. С примерами применения. М., Конкорт, 1992.

Анамия М., Танака Ю., Архитектура ЭВМ и искусственный интел­лект. М., Мир, 1993.

Лорьер Ж. Л., Системы искусственного интеллекта. М., Мир,

1991.

Искусственный интеллект. Применение в интегрированных произ­водственных системах. М., Машиностроение, 1991.

Малпас Дж., Реляционный язык Пролог и его применение. М., На­ука, 1990.

Рассохин Д., От С к C++. М., Эдель, 1993.

Нечаев В.В., Лекционные материалы по теории творческой дея­тельности. 1996.