• Курсова робота
  • Мал. 1.3. організація КУ


  • Дата конвертації25.03.2017
    Розмір117.36 Kb.
    Типреферат

    Скачати 117.36 Kb.

    Рішення творчих завдань методом блокових альтернативних мереж: об'єктно-орієнтовані уявлення

    МОСКОВСЬКИЙ ІНСТИТУТ радіотехніки, електроніки і АВТОМАТИКИ

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


    факультет кібернетики

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


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


    Тема: Рішення творчих завдань методом блокових альтернативних мереж: об'єктно-орієнтовані уявлення.


    студенти:

    Група: АІ-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 Оцінка результатів рішення задачі на БАС

    1. Реалізація БАС на ГО системі в проекті «Навчальний розклад»

    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 , С , 1 >, (1.1)


    де;

     - проблемна ситуація, яка є вихідним посилом для побудови КММ задачного системи;

    Z  - визначає цілі "незадоволених потреб", в результаті якої породжується проблемна ситуація;

    З  - визначає умови досягнення мети;

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

    В якості умов визначимо наступний необхідний і достатній набір компонент:

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

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

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

    - Оцінку адекватності, релевантності ( пекло).

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


    Z  = <М , А , Р ,  пекло ». (1.2)


    Вихідна інформація включає в себе дані (D ), необхідні для вирішення завдання, і знання (К ) про предметну область завдання:


    I  = (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

    Навчальна група III

    потік 1.2

    Навчальна група 1.2.1

    Навчальна група 1.2.2

    .......................................

    Мал. 1.3. організація КУ


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


    Професорсько-викладацький склад (ППС) об'єднує людей (викладачів), відповідальних за проведення занять.

    Викладача характеризують дві складові:

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

    де

    З - визначає звання (посаду) викладача;

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

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

    Посада викладача визначає формальну систему пріоритетів:

    - Професор;

    - Старший викладач;

    - Викладач;

    - Сумісник;

    - Аспірант.

    ТНД може мати також і складну структуру, об'єднуючи в собі набір дисциплін з різними тематиками:

    ТНД * = {ТНД 1,..., ТНД 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  О), который будем называть решением. При этом существует несколько показателей (атрибутов), характеризующих объект:

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

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

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

    или (2.5)

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

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

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

    R  <=>1 ...  А  ...  А N). (2.6)

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

    А 1 = (  11, …,  1 j, …,  1 m 1)

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

    А  = (  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. Инкапсуляция БА и ФВА в класс объектов-альтернатив









    БА 1

    БА N

    БА



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









    БА 1

    БА N

    БА




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




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


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


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


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

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

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

    - смешанная.

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

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


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


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


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

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

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

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

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

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

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

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

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


    AM i : (A i r ij u ij), (2.8)

    де

    А i - атрибут;

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

    ij - значение атрибута А i.

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


    AM i : (А i r ijij) U (  ij r ji A* i), (2.9)


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

    AM 1 : (А i,  ij, A* i). (2.10)


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


    АM i T : (A i, r T, A* i), (2.11)


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

    AM i T : (A i, T, A* i). (2.12)


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


    ЦМ i * : (A i,  ij, A* I)  R q, q = 1,2, …, Q (2.13)


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

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

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

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

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

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

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


    ЦМ i ** : (A i, (  ij,  q1), A* I)  R q, q = 1,2, …, Q (2.14)

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

    ЦМ i ** : (A i, {  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 1 1, ..., R i 1, ..., R N 1)=R l несвязанных между собой решений. После этого решается задача склеивания частных решений в общее. Данная процедура может протекать по двум направлениям:

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

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

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


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


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

    N R = (mxn) => П{R} (2.18)

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

    АНПС




    R 1 R i R N

    БА 1

    БА i

    БА N



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


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

    АБ 1

    АБ i

    АБ N

    БА 1

    БА i

    БА N



    I O 1 R 1 1 I O i R i 1 I O N R N 1


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


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

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

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

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

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


    К = <А, Ф>,

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

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

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

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

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

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

    класса:


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

    де

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

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

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

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

    де

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

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

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

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

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

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

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

    де:

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

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

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

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


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

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


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


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

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

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

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

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

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

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


    FOR = <В, Е, S, F(С, Ao 1, …, Ao i, …, Ao n), O>, (3.5)


    де

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

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

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

    F(С, Ao 1, …, 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.


    Головна сторінка


        Головна сторінка



    Рішення творчих завдань методом блокових альтернативних мереж: об'єктно-орієнтовані уявлення

    Скачати 117.36 Kb.