Тема 6. Алгоритмічні основи прийняття рішень в інтелектуальних системах

Характер пошуку необхідних знань в базі знань, спосіб організації виведення рішень визначається стратегією управління ІС.

Стратегія управління являє собою засіб, що використовує судження і здійснює висновки про знання, які є в базі знань. Стратегії управління забезпечують управління ІС в рамках прийнятої для даної системи схеми механізму виведення.

Існують такі механізми виведення:

- за зразками;

- на основі дошки оголошень;

- методами перебору: (пошук в глибину, пошук в ширину, на основі вартості дуг, пошук з поверненням (бектрекінг));

- еврістичні методи.

Методи пошуку за зразками

Зразки – це формати, що визначають умови активізації різних структурованих знань.

На кожній ітерації відбувається аналіз і співставлення поточної ситуації і зразків з метою знаходження блоків, для яких виконуються умови активізації для даної ситуації.

Процедури співставлення зі зразками і визначення правил, що відповідають поточному стану об´єкта визначені самою логікою роботи інтерпретатора правил. Весь процес реалізації стратегії виведення проходить через чотири основних стадії: вибір співставлення, розв´язання конфліктів та виконання. На стадії вибору вибираються модулі БЗ та дані з робочої пам´яті.

Пошук рішень неформалізованих задач (НФЗ) в просторі стану відображується за допомогою семантичного графа, названого деревом варіантів рішень.

Процедура пошуку рішення НФЗ в просторі станів може бути сформульована таким чином. Задана трійка (S₀, F, S₁), де S₀ - множина початкових станів (умови задачі); F - множина операторів задачі, що перетворюють одні стани в інші; S₁- множина кінцевих (цільових) станів (рішень задачі). В цій постановці вирішити НФЗ -значить визначити таку послідовність операторів, яка перетворить початкові стани в кінцеві. Процедуру розв'язання можна представити у виді графа G=(X,Y), де G = {x₀, x₁, …} -множина (в загальному випадку нескінченна) вершин графа, кожна з яких відображує один із станів; Y -множина дуг, інцидентних парі вершин (x_i, x_j); x_i, x_j X.

Множина дуг, що витікають з вершини x_і , відображує множину операторів, які можуть бути застосовані до стану, що відображається вершиною x_і . В множині вершин Х виділяють підмножину вершин Х₀ Х, відображувало множину початкових станів (S₀), і підмножину вершин Х₁ Х, що відображує множину кінцевих (цільових) станів (S₁). Множина Х₁, може бути задана як явно, так і неявно, топто через властивості, якими повинні володіти цільові стани.

Очевидно, що рішеня НФЗ методом пошуку в просторі станів зводиться до процедури пошуку шляху L в графі G. Шлях з х₀ Є Х₀, до х₁ Є Х₁., називають вирішальним (цільовим). Часто зручно приписувати дугам графа певну вагу, яка рівна вартості застосування відповідних операторів. Для позначення ваги «с» дуги, направленої з x_i в x_j, використовують запис: з (x_i, x_j). Вартість шляху між двома вершинами визначається як сума вартостей всіх дуг даної колії. У ряді додатків виникає задача знаходження шляхів (шляху), мають мінімальну вартість, між будь-якими елементами з множини Х₀ і будь-якими елементами з множини Х₁. Відзначимо, що граф G може бути заданий як в явному вигляді (експлицітно), так і в неявному (імплицітно). Неявне завдання графа G полягає у визначенні множини Х₀ і множини операторів, які, будучи застосовні до деякої вершини i рафа, породжують всі її вершини-нащадки.

Отже, граф G відображував простір станів, тобто простір, в якому відбувається пошук рішення НФЗ. Побудова простору здійснюється за допомогою наступної операції. До деякої вершини з х₀ Є Х₀ застосовують всі можливі оператори, всі її вершини-нащадки, що породжують. Породження всіх вершин-нащадків для деякої вершини х_і називають операцією розкриття вершин. Якщо отримана цільова вершина, то вона не розкривається. Операція побудови простору станів закінчується, коли всі нерозкриті вершини є цільовими, або термінальними (тобто вершинами, до яких не можна застосувати ніяких операторів). Оскільки простір станів може містити нескінченне число вершин, операцію породження простору станів oбмежують або часом, або об'ємом пам'ять ЕОМ.

Практично при розв'язанні НФЗ необхідно забезпечити повноту пошуку, тобто організувати пошук так, щоб всі цільові вершини були знайдені, якщо вони існують. Надійним способом забезпеченні повноти є повний впорядкований перебір всіх вершин графа. Для кожної операції впорядкованого перебору необхідно визначити порядок, в якому будуть перебиратися вершини графа. Звичайно виділяють два основні способи перебору вершин: пошук «в глибину» (або «одностороннім обходом») і пошук «в ширину» (або «полним (фронтом»).

При пошуку «в глибину» спочатку розкривається та вершина, яка була побудована самою останньою. Глибина вершини в графі визначається таким чином: 1) глибина вершини-кореня рівна нулю; 2) глибина проміжної вершини рівна одиниці плюс глибина найбільш близької вершини-предка. При практичній реалізації пошук «в глубину» в деякому напрямі завершується в наступних випадках: 1) досягши цільової вершини; 2) досягши термінальної вершини; 3) при побудові в ході пошуку вершини, глибина якої перевищує деяку граничну глибину.

При пошуку «в ширину» вершини розкриваються в тому ж порядку, в якому породжуються. Якщо в просторі станів ввести оператори, що переводять стан S_і, в попередній стан S_і-1, то пошук можна здійснювати як у напрямі від початкового стану (від початкових даних) до цільового, так і у зворотному напрямі. Стратегію пошуку «від початкових даних до цілі» називають «прямим пошуком», а стратегію пошуку «від цілі до данних» - «зворотнім пошуком». Більш того, можна організувати пошук в обох напрямах одночасно. Таку стратегію називають двонаправленою.

На рис.6.1 для графа типу «АБО» приведений приклад пошуку рішення задачі способом «в глибину» (рис.6.1, а) і «в ширину» (рис.6.1, б). Вершини пронумеровані в тому порядку, в якому вони розкриваються; цільові вершини помічені заштрихованими квадратами, термінальні - білими квадратами. При використанні кожного із способів можуть бути знайдені всі рішення НФЗ. При переборі всього простору обидва способи будуть аналізувати однакове число вершин, проте спосіб пошуку «в ширину» буде вимагати істотно більше пам'яті, оскільки він ураховує всі шляху пошуку (а не один, як при пошуку «в глибину»).

Для пошуку ріщень НФЗ на «ТА/АБО» графі, як і для пошуку в просторі станів, можна застосовувати пошук «в глибину» і пошук «в ширину» як в «прямому», так і в «зворотньому» напрямі.

На рис.6. 2. наведений приклад пошуку «в ширину» і «в глибину». Всі вершини пронумеровані в тому порядку, в якому вони розкриваються; кінцеві вершини позначені подвійними заштрихованими кружками, вирішувані вершини зачорнені, дуги вирішального графа виділенi подвійними лініями.

Пошук «в глубину» і «ширину» називають рутинним, або сліпим пошуком, оскільки при цьому порядок розкриття вершин передбачуваним і не залежить від розташування ланцюга. При збільшенні простору пошуку способи сліпого пошуку вимагають надмірних витрат часу ТА/АБО пам'яті ЕОМ.

Рис.6.1. Процедура пошуку на дереві варіантів рішень способом «в глибину» (а) і «в ширину» (б)

Для скорочення часу пошуку застосовують евристичні методи пошуку, тобто методи, що використовують деяку інформацію про предметну галузь для розгляду не всього простору пошуку, а таких раціональних шляхів в ньому, які з щонайбільшою вірогідністю приводять до цілі. Один із способів скорочення перебору полягає у виборі більш «ипформованого оператора, який не породжує так багато вершин, що не відносяться до розв'язання НФ3.

Рис.6.2. Процедура пошуку розв'язання неформалізованої задачі з використанням принципу декомпозиції задачі на підзадачі способом «в ширину» (а) і «в глибину» (б)

Інший спосіб полягає в використанні еврістичної інформації для визначення на кожному кроці подальшого напрямку перебору. Для цього необхідно ввести міру «перспективності» вершини у вигляді деякої оцінночної функції. В деяких випадках вдається ввести таку оціночну функцію, що вона, скорочуючи перебір, не втрачає властивості повноти. Як правило, оціночні функції намагаються кількісно оцінити відстань від поточної вершини до кінцевої. Із двух вершин при однаковій глибині «перспективніша» та, від якої менша відстань до цілі. Необхідно відмітити, що застосування оціночних функцій не завжди підвищує ефективність процедури пошуку.

Існує два типових способи включення еврістичної інформації у пошукову структуру:

■ за допомогою еврістичної функції, яка "визначає вагу" тверджень конкретної задачі і визначає їх відносну значущість;

■ безпосередньо розмістивши еврістичну інформацію у правила інтелектуальної системи.

Є декілька варіантів використання еврістичної функції.

Одна із стратегій полягає у тому, що за допомогою такої функції вибирається найкращий крок і перевіряються у той же спосіб (вико­ристовуючи функцію) всі його наслідки, перед тим як здійснити інші кроки. У випадку тупика потрібно повернутися до найближчого розга­луження та спробувати здійснити інший найкращий крок. Тобто спо­чатку перевіряються всі наслідки одного вибору на всю можливу гли­бину, і тільки потім відбувається черговий вибір. Суттєвим недоліком такої стратегії є те, що для здійснення вибору використовується тільки локальна інформація.

Інший варіант еврістичного пошуку, що об'єднує у собі позитивні риси пошуку у глибину та ширину є пошук під назвою Кращий перший крок. На кожній стадії пошуку досліджується деяка кількість варіантів вибору, і оціночна функція обчислюється для їх кінцевого стану. У Кращому першому кроці пошук продовжується від досягнутого кінцевого стану, що має найкращу оціночну функцію уверх до цього місця. При такій стратегії часто відбуваються стрибки від кінця одного варіанту вибору до іншого, намагаючись завжди пра­цювати з тим, що є найбільш перспективним. Цей метод досить ефек­тивний, але тривалі обчислення і великий обсяг обліку (всі частинні варіанти вибору (шляхи) повинні постійно підтримуватися) приму­шують часто використовувати більш просту процедуру, яка швидко перевіряє багато розв'язків. Ефективна стратегія пошуку жорстко за­лежить від предметної області, ефективність евристичного пошуку ви­значається оціночною функцією, що використовується.

Вивід в умовах невизначеності

Для багатьох реальних задач потрібно провести оцінку гіпотез, для яких інформація є неповною або недостатньою. Експертні систе­ми, що призначені для розв'язування таких задач, повинні, незважаю­чи на невизначеність, приймати необхідні рішення.

Міркування, що базуються на невизначеності, використовуються у всіх EC медичної діагностики і консультацій по способам лікування. Те ж саме маємо і у системах спостереження за наявності одночасно декількох конкуруючих гіпотез та їх постійної переоцінки при надхо­дженні нових даних: у кінцевому підсумку визначається одна гіпотеза, яка дозволяє здійснити відповідний висновок. У системах розпізнання природної мови теж мають бути конкуруючі гіпотези, наприклад, про те, яке конкретне слово використовується у реченні.

Окрім того, багато програм, що використовують еврістики, теж повинні працювати в умовах невизначеності, так як евристика - на­ближений метод, що вказує напрям пошуку. Якщо існує тільки одна евристика, то проблем немає. А якщо два евристичних методи орієн­тують програму у двох різних напрямках? Або якщо дві евристики вказують один і той же напрямок пошуку, чи має це викликати більшу довіру, ніж би була тільки одна із них?

Тому при виводі в умовах невизначеності природним є викорис­тання понять теорії ймовірності: умовної ймовірності, правила Байєса, правила та/або, правила композиції, тощо.

[2,с.5-28;3,с.126-203;с.213-243;9,c.77-105]

Контрольні питання

1. Що таке стратегія управління?

2.Які існують механізми виведення?

3. В чому полягає метод пошуку за зразками?

4. В чому полягає метод пошуку “в ширину”?

5. В чому полягає метод пошуку “в глибину”?

6. Еврістичні алгоритм пошуку рішень.

Дата добавления: 2015-07-20