Разработка методов принятий решений в экспертной системе идентификации виновников загрязнения рек тема автореферата и диссертации по математике, 01.01.01 ВАК РФ

1 г МІШСТЕРСТВО ОСВІТИ УКРАЇНИ

ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

Білогурова Ганна Вікторівна

УДК 007.681.518.2:628.3

РОЗРОБКА МЕТОДІВ ПРИЙНЯТТЯ РІШЕНЬ В ЕКСПЕРТНІЙ СИСТЕМІ ІДЕНТИФІКАЦІЇ ВИНУВАТЦЮ ЗАБРУДНЕННЯ

РІЧОК

01.0^.0^- Системний аналіз і теорія оптимальних рішень

Автореферат дисертації на здобуття наукового ступеня кандидата технічних наук

Харків -1998

Дисертацією є рукопис.

Робота виконана в Харківському державному технічному університеті радіоелектроніки '

Науковий керівник:

доктор технічних наук, професор Шостак Володимір Федорович, зав. каф. технічної кібернетики ХТУРЕ.

Офіційні опоненти:

- доктор технічних наук, професор Сіроджа Ігор Борисович, зав. каф. інформатики та програмного забезпечення автоматизованих систем Харківського авіаційного інституту;

- кандидат технічних наук, доцент Пономаренко Євген Георгійович, доцент каф. інженерної екології міст Харківської державної академії міського господарства.

Провідна установа:

Український науково-дослідний інститут екологічних проблем (УкрНДІЕП).

Захист відбудеться «¡¿<» к^7ійЯ 1998 р. о /3_ годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському державному технічному університеті радіоелектроніки за адресою: 310726, м. Харків, пр. Леніна, 14, fax: (0572) 40-91-13.

З дисертацією можна ознайомитися в бібліотеці університету за адресою: 310726, м. Харків, пр. Леніна, 14.

Автореферат розісланий « /2 » 1998 р.

Вчений секретар -

спеціалізованої вчено"

професор

Левикін В. М.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Однією з найважливіших проблем охорони вод є виявлення винуватців забруднення, тобто визначення того з безлічі можливих джерел забруднення, дії якого призвели до порушення водоохоронних норм. При встановленні факту екстремально високого забруднення (ЕВЗ) ця проблема звичайно вирішується шляхом інспекторського обстеження ряду джерел забруднення та виявлення тих, що порушили встановлені для них норми і правила. При такому підході виявити винуватців вдається лише тоді, коли поява ЕВЗ викликана аварією, приховати яку неможливо. У разі неаварійних залпових скидів звичайні інспекторські засоби рідко призводять до мети, бо вони не використовують знання, методи та моделі, які накопичені наукою та відомі висококваліфікованим ек-спертам-спеціалістам з безлічі різноманитних ЕВЗ.

Зараз відомі математичні методи рішення задачі ідентифікації винуватців забруднення річок на основі традиційного алгоритмічного підходу, однак ці методи не знайшли широкого застосування тому, що вони не орієнтовані на врахування суттєвої невизначеності інформації. Проте методи штучного інтелекту (ШІ) дозволяють врахувати невизначеність інформації завдяки використанню процедур нечіткого виведення на знаннях. Однак ці методи та експертні системи (ЕС) для рішення задачі ідентифікації винуватців забруднення річок ще не використовувались. ,

Викладене підтверджує, що тема дисертаційної роботи є новою і актуальною.

Зв’язок роботи з науковими програмами, планами, темами. Тема дисертаційної роботи відповідає проблематиці бюджетної науково-дослідної роботи, що проводиться на кафедрі технічної кібернетики Харківського державного технічного університету радіоелектроники під керівництвом завідуючого кафедрою проф., д.т.н В.Ф. Шостака по темі 465-1 «Розробка теоретичних основ і засобів управління складними об’єктами в інтелектуальних дискретних системах реального часу з використанням баз знань і експертних систем».

Метою роботи є розробка методів прийняття рішень в експертній системі ідентифікації винуватців забруднення річок в умовах невизначеності інформації.

Задачі дослідження:

•математична постановка задачі ідентифікації винуватців забруднення річок;

•розробка продукційної моделі предметної області, обгрунтування вибору натурного об'єкта для тестування методів прийняття рішень;

•розробка методу нечіткого виведення на знаннях, що базується на відомих процедурах врахування невизначеносте інформації приєднаного типу але орієнтований на особливості задачі ідентифікації винуватців забруднення річок;

•розробка методу нечіткого виведення на знаннях, що належить до класу механізмів неприєднаного типу та дозволяє знаходити одного чи декілька винуватців забруднення, виявляти протиріччя у вхідній інформації та визначати умо-

ви, коли отриманої інформації недостатньо для прийняття рішення щодо винуватців забруднення.

•розробка алгоритмів і -програмна реалізація запропонованих методів рішення задачі ідентифікації винуватців забруднення річок;

•експериментальні дослідження працездатності розроблених методів і алгоритмів на натурних даних;

•розробка рекомендацій щодо практичного використання запропонованих методів і алгоритмів в експертній системі ідентифікації винуватців забруднення річок.

Наукова новизна одержаних результатів полягає у тому, що:

1) сформульовано і розв'язано задачу ідентифікації винуватців забруднення річок, для якої засоби штучного інтелекту раніше не застосовувались;

2) вперше розроблено продукційну модель предметної області, яка забезпечує можливість вирішення задачі ідентифікації винуватців забруднення річок в умовах невизначеності інформації, в тому числі і при її навмисному викривленні;

3) розроблено метод нечіткого виведення на знаннях, який є модифікацією відомих методів MYCÍN та PROSPECTOR, але зоріентован на особливості задачі ідентифікації винуватців забруднення річок;

4) дістав подальшого розвитку напрямок «логічне виведення на знаннях» з теорії штучного інтелекту, завдяки тому що розроблено новий метод прийняття рішень з класу приєднаних механізмів нечіткого виведення на знаннях, який відрізняється від відомих тим, що дозволяє:

• вибирати найбільш пріоритетні свідчення по критерію, який враховує вартість отримання інформації та силу впливу свідчення на міру невизначеності усіх гіпотез;

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

•приймати будь-який тип рішення з повного їх набору: знайдено одного винуватця; винними є декілька винуватців забруднення водночас; знайдено протиріччя у вхідніх даних; рішення приймати не можна через нестачу інформації.

Практичне значення одержаних результатів полягає в тому, що розроблені алгоритми можна безпосередньо застосовувати в інспекторській практиці для виявлення винуватців забруднення річок на рівні обласних управлінь Держеко-безпекм. Розроблені методи і алгоритми можуть також стати основою для розробки технічної документац ії системи екологічного моніторингу (СЕМ) України.

Особистий внесок автора. Всі результати дисертаційної роботи отримані особисто автором. У праці [1], написаній у співавторстві, дисертантові належить математична постановка задачі ідентифікації винуватців забруднення річок.

Реалізація результатів роботи. Результати наукових досліджень знайшли практичне застосування при виконанні завдання Мінекобезпеки України

з

№ 470/008/13 «Розробка єдиного міжвідомчого керівництва по організації та здійсненню державного моніторингу вод» і в проекті № КЗ-487 (7-1, 2/96) «Розробка базових рішень по організаційно-методичному і інформаційному забезпеченню відомчого блоку екомоніторингу Мінекобезпекн України».

Апробація результатів дисертації. Основні результати дисертаційної роботи доповідалися і обговорювалися на Міжнародній конференції “Теорія і техніка передачі, прийому і обробки інформації” (Туапсе, 18-21 вересня 1995 p.), на 3-й Українській конференції з автоматичного керування «Автоматика-96» (Севастополь, 9-14 вересня 1996 p.), на першій міській науково-практичній конференції «Актуальні проблеми сучасної науки у дослідженнях молодих вчених м. Харкова» (Харків, 19 грудня 1997 p.), на 15-му Всесвітньому конгресі IMACS «Scientific Computation, Modeling and Applied Mathematics» (Будапешт, 14-17 липня 1997 p.).

Публікації. Матеріали дисертації достатньо повно викладено в 5 друкованих роботах (4 статтях, 1 тези доповіді).

Структу ра і обсяг роботи. Дисертація складається з вступу, п'яти розділів, висновків, переліку використаних джерел і додатків. Матеріал дисертації включає 149 сторінок тексту, 4 малюнки, 7 таблиць, бібліографію з 109 найменувань і 4 додатки. ■

ЗМІСТ РОБОТИ

У вступі обгрунтовано актуальність проблеми, розглянутої в роботі, сформульовані мета та завдання дослідження, наведені відомості щодо наукової новизни, практичної цінності і впровадження результатів роботи, публікацій автора, апробації роботи, структури і обсягу дисертації.

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

В результаті аналізу можливостей експертних систем (EC) показано, що проблема виявлення винуватців забруднення річок задовольняє умовам Д.Уотермена, при яких розробка EC є можливою, виправданою і доцільною. Обгрунтовано доцільність використання подання знань у вигляді правил продукції та розробки методів прийняття рішень із напрямку «логічне виведення на знаннях» теорії штучного інтелекту (ШІ) з процедурами врахування невизначеності інформації. Цікавими є обидва типи мєтодіе нечіткого виведення на знаннях:

1) приєднані - з процедурами врахування невизначеності, що підпорядковані схемі виведення та начебто супроводжують процес виведення;

2) непрєднані - зі схемою виведення, спеціально орієнтованою на обраний засіб врахування невизначеності.

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

при виявленні ЕВЗ по і-й забруднюючий речовині (ЗР) в j-му річковому створі:

j:Cy[k]>NES , (1)

деСц[к] - концентрація і-ї речовини в j-му створі в момент k; NESl- гранична величина концентрації і-ї ЗР, перевищення якої визначає виникнення ЕВЗ,

отримавши результати спостережень за якістю води С-[к], і є І, j є J і за

зовнішніми факторами е єЕ за період Т = |k-n,k - n + l,...,k],

маючи апріорні дані відносно множин джерел забруднення Gj, що впливають на якість води в j-му створі по і-й забруднюючий речовині, причин ЕВЗ - D, параметрів джерел забруднення - О, зовнішніх факторів -Е, невизначеностей - W, математичних моделей - М, нормагивів - N.

визначити таку множину рішень S=((g,d)*}, елементами якої є пари «винуватець, причина забруднення» \g,d)* такі, що мають f = 1:

io, при !iZag(<g,d>, o,e,w,m,n,j) -ACjbs

H / , л ’ <2>

[ 1, при|jZag((g,d)*,o,e,w,m,n,j)-ACj|^є

де ACj- вектор виміряних відхилень концентрації по всіх і-х ЗР в j-му створі, що визначені за результатами вимірів Cij: в момент k виявлення £ВЗ і до цього моменту; Zag«g,d),o,e,w,m!n,j) - вектор-функція розрахункових відхилень концентрації по всіх і-х речовинах (і єі) в j-му створі, які викликані g-м джерелом (geGj) з d-ою причиною (d єD) при відповідних характеристиках джерел забруднення о є О, зовнішніх факторах е є Е, невизначеностях w є W, математичних моделях m є М, нормативах п є N; є - допустима похибка рішення задачі.

В такій постановці вектор-функція Zag має об’єднувати сукупність складних багатокомпонентних моделей та водночас враховувати суттєву невизначеність інформації. Але наданий час про існування такої складної фунції не відомо. Тому задача (2) може бути вирішена традиційними (алгоритмічними) методами тільки у спрощеному вигляді в деяких окремих випадках.

У загальному випадку задачу ідентифікації пропонується вирішувати за допомогою інтегрованої ЕС, яка спочатку традіційними методами визначає можливі гіпотези, а потім виявляє найбільш імовірного винуватця методами ШІ. ЕВЗ (1) обумовлює: підмножину забруднюючих речовин IES (Ies с і)> підмножину створів JES (JES с J), яка визначає забруднену ділянку річки, підмножину GES (GescGj) можливих джерел забруднення та підмножену причин DES (Des cD) цього забруднення. Д;ш отримання множин IES, JES, GES, DES використовуються традиційні методи на базі відомих моделей М та параметрів О джерел забруднення. Множину гіпотез Н, відповідних цій ЕВЗ, формують з усіх можливих пар (g,d\ g є GES, d sDES. Пошук імовірних виуватців забруднення далі реалізується серед елементів множини Н методами нечіткого виведення на знаннях продукдійного типу.

Продукційну модель предметної області з урахуванням невизначеності даних і знань, запишемо в наступному вигляді:

r. Wr;W(A), А=>В, W(B); U, (3)

де г - назва продукції ( г є R ); R - множина продукцій; А - антецедент, а В - консе-квент правила продукції; А => В - ядро продукції; U - посгумова продукції (описує дії і процедури, які необхідно виконати після реалізації В); Wr, W(A), W(B) - міри невизначеності правила продукції, антецедента А і консеквента В відповідно. В загальному випадку А є множиною декількох елементів - компонентів антецедента: А = {alsa2,...,an}. Кожний з них може бути консеквентом будь-якого правила і відповідно »має свою міру невизначеності X = [х1,х2,...,хп|.

Множину фактів F, яка обробляється в задачі, подамо як F = Е w H u V, де Н - множина кінцевих фактів (гіпотез); V - множина проміжних висновків, які визначаються методом рішення задачі; Е - множина вхідних фактів (свідчень, кожне з яких є парою <питання про наявність факту та відповідь на нього>). Свідчення описують дану ситуацію ЕВЗ та пов’язані з гіпотезами через правила продукції.

Наведена формалізація дозволяє конкретизувати мету роботи: розробка методів прийняття рішень полягає у тому, щоб вибрати міри невизначеності Wr, W(A), W(B), визначити методи їх перерахування залежно від вхідних фактів та запропонувати постумови продукції U, що задають послідовність аналізу правші, критерії завершення процесу та вироблення висновку.

Тестування розроблених методів пропонується проводити на натурному тест-об’єкті, який повинен відображати основні характерні особливості предметної області, але мати мінімально можливу вимірність, щоб забезпечити перевірку повноти та вірністі рішень засобами вичерпного пошуку. Цим вимогам відповідає ділянка річки Сіверський Донець від міста Рубіжне до кордону з Росією та реаль-

ний факт ЕВЗ, коли забруднення річкової води фенолами викликало скаргу адміністрації Ростовської області на Україну. Для натурного тест-об'єкга визначено множини гіпотез В та свідчень Е. Продукційна модель натурного тест-об'єкта подана у вигляді множини правил продукції R, як таблиця відповідностей між множинами гіпотез Н і свідчень Е, а також у вигляді графа І/АБО/КОМБ.

Третій розділ присвячено застосуванню відомих методів нечіткого виведення на знаннях з використанням процедур урахування невизначеності інформації приєднаного типу до нової задачі - ідентифікації винуватців забруднення річок. Особлівостям цієї задачи найбільш відповідає метод, який об’єднує комбінований ланцюжок виведення системи PROSPECTOR з функціями розрахунку невизначеності системи MYCIN. Розроблений метод названо MYCIN-подібним. Він харак-терізуєгься такими основними рисами:

1.Орієнтація на базу знань продукційного типу з використанням трьох типів логічного зв’язку «І», «АБО», «КОМБ». Зв’язок типу «КОМБ» дозволяє врахувати вплив декількох непов’язаних між собою джерел інформації, які підтверджують (або спростовують) окрему гіпотезу.

2.Подання міри невизначеності у вигляді скаляра W, W є [0,1]. Міру невизне-ченості (далі вагу) мають факти (свідчення, гіпотези) та знання, що наведені у вигляді правил.

3.Реалізація трьох функцій перерахування мір невизначеності, які дозволяють обрахувати: f - вагу антецедента по вагах його компонентів, h - вагу консек-вента по вагах антецедента та правила, g - вагу гіпотези по вагах джерел інформації, що зв’язані по «КОМБ». Функції f та h відповідають відомим правилам теорії нечіткої логіки, а функція g, яка запропонована у системі MYCIN, має вигляд:

1, коли W(B!) = 1 або W(B2) = 1 W(B1) + W(B2)-W(B1)-W(B2),

коли 0<W(Bi)<l, 0<W(B2)<1 W(B,) + W(B2), коли W(B,)-W(B2)<0,

W(B,)*±1 та W(B2)*±1 ’

W(BI) + W(B2) + W(B,)-W(B2), коли -1<W(B,)<0 та -1<W(B2)<0,

-1, коли W(B,) = -1 або W(B2) = -1.

де W(B0)- вага гіпотези В0, виведеної з консеквентів В, та В2; W(Bi), W(B2)- ваги консеквентів B¡ та В2 відповідно.

Процес розв’язання задачі розробленим методом являє собою ітераційний цикл, що складається з чотирьох етапів:

W(B°) = g(W(B1),W(B2)) =

- вибір чергової гіпотези спочатку (коли гіпотези мають нульові ваги) здійснюється по пріоритету, якій оцінює можливу вину джерел забруднення в залежності від характеристик окремого ЕВЗ, далі пріоритет надається гіпотезі з найбільшою вагою;

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

- перерахування ваг антецедентів, консеквентів правил та відповідних гіпотез здійснюєтся з використанням функцій £ Ь по прямому ланцюжкжу виведення, при цьому усі оброблені правила разподіляются на «вже виконані» та «взагалі нездійснимі»;

- вироблення рішення здійснюється коли всі правила разподілені на «вже виконані» та «взагалі нездійснимі». Винними вважаюгся ті джерела забруднення, відповідні гіпотези яких мають ваги більші ніж нуль. Міра їх вини оцінюється вагами відповідних гіпотез. Остаточне рішення щодо дій (вважати винним, проводити подальше обстеження і таке інше) виробляє користувач.

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

Четвертий розділ присвячено розробці нового методу нечіткого виведення на знаннях, який належить до типу неприєднаних (засіб урахування невизначеності впливає на схему логічного виведення). Цей метод названо методом з динамічною схемою виведення (ДС-методом), оскільки він оперативно зменшує коло пошуку та змінює його приоритетні напрямки в залежності від поточного стану ЕС та вхідної інформації. Він має дві характерні риси, що засновані на відомих методах.

1. Міра невизначеності є скаляр [0,1], що має фізичний зміст імовірності. Міри невизначеності надаються свідченням та гіпотезам. їх перерахування базується на теоремі Байєса. Кріс Нейлор запропонував відображати наявність впливу деякого свідчення на певну гіпотезу парою умовних імовірностей: р+=Р(Е|Н) при істинності гіпотези Н та р~=Р(Е|Н) при її хибності. Тоді ймовірність гіпотези можливо одержати по формулах:

Р(Н|Е) =----------------, коли свідчення Е підтверджує гіпотезу Н, (5)

р+р + р (1-р)

Ґ\ — Лг\

Р(Н|Е) =-----------—-——-------, коли свідчення Е спростовує гіпотезу Н, (б)

1-р+р-р (1-р)

де р=Р(Н) - апріорна ймовірність гіпотези Н, Р(Н'Е) - умовна ймовірність гіпотези Н при тому, що свідчення Е підтвердилось, Р(Н|Е) - умовна ймовірність гіпотези Н при тому, що свідчення Е не підтвердилось.

При наведеному формалізмі продукційну модель знань пропонуємо подати у вигляді таблиці 1. Якщо якесь свідчення не впливає на якусь гіпотезу, у відповідній клітині таблиці 1 ставлять пропуск, якщо впливає - пару умовних імовірностей. Обробка такої бази знань полягає у тому, щоб на кожній ітерації (тобто після отримання чергового свідчення) перерахувати усі можливі ймовірності гіпотез, приймаючи замість апріорних імовірності, що отримані на попередній ітерації.

Таблиця 1. Подання бази знань у ДС-методі.

~~~~ Гіпотези Свідчення ■— Н! Ні Нп

Еі ВДІЦ) Р(Е,|Н) РОчй) ВДР) - ВДІНі)

... — - - -

Еі щя) ЧЕ|И) щу») - рад Р(Е]!К1)

... — - - -

Е* РИЙ) ЯМ) ВД«|И) - «ЕУЧ.) РСЩН.

Апріорні ймовірності Р(Н,) ... Р(Н2) ... Р(Н„)

2. Врахування невизначеності відповіді користувача здійснюється таким чином. Для відображення міри непевності користувача в наявності факту, його відповідь надається в балах Я є[-5,+5], де -5 - означає «НІ», 5 - означає «ТАК», а

0 - «НЕ ЗНАЮ». Тоді ймовірність гіпотези Н при отриманні свідчення Е через значення Я запишемо

Р(НІЯ)= Р(Н|Е)-Р(Е[К) + Р(Н|Е)-Р(Е|К), (7)

де Р(Е|Я) (Р(ЕІТІ)) - ймовірність факту Е (Е) при відповіді Н.

Природньо, що Р(Н|Я) при К=5, Я = -5,11=0 дорівнює Р(Н|Е), Р(Н|Е), Р(Н) відповідно, де Р(Н) - попереднє значення ймовірності гіпотези Н. Після припущення про лінійну інтерполяцію залежності (7) між цими трьома точками маємо

рШ!Ю=Г(Н) + 0-2(Р(Н!Е)“Р(Н))к при о^її<;5,

1 [Р(Н) + 0.2(Р(Н) - Р(НІЕ))Я при - 5 < II < 0.

Запропоновано наступну схему логічного виведення ДС-методу:

- вибір наступного свідчення;

- перерахування ймовірностей;

- вилучення гіпотез;

- вироблення висновку.

Дія вибору наступного свідчення розроблено комплексний критерій , що враховує ціну свідчення (ЦС) та вартість отримання інформації (СИ), необхідної для аргументованої відповіді на питання ЕС. Формула для визначення ціни свідчення ЦС враховує вплив свідчення Е на всі гіпотези водночас:

ЦС(Е) = Х!Р(НІ|Е)-Р(НІ|Е^ (9)

і=!

де Нр і = 1,.2,...,п - гіпотези, що підлягають розгляду на наступній ітерації. Число п змінюється в міру вилучення гіпотез. Модуль під знаком суми забезпечує підсумовування відхилень як для тих гіпотез, які свідчення Е підтримує, так і для тих, які воно спростовує. Враховуючи (5) та (6), після деяких перетворень одержуємо вираз для ціни ^го свідчення:

ИГ = V |(р« ~Р«)ІРІ 4. V 1<РЇЇ-Ра»Рі пт

* і 2» * ,л *ч *2- **ч *

і=і РдО-Рц) и Ріі (1-Рц)

ІьІ+ -

де цсі - ціна і-го свідчення; ру = РуРі+р^(1-р;), а р" = рурі +рі(1 -р;);

] є І+ означає, що враховуються ті гіпотези, які підтримуються свідченням а

І є І' - ті гіпотези, які цим свідченням спростовуються.

Для визначення критерію пріоритетності (КП) пропонується використати підхід, прийнятий в комплексних критеріях типу «ефективність / вартість». При цьому величина ЦС виступає як ефективність. Це необхідно тому, що для охорони вод характерна дуже висока кратність змін вартості інформації (від часток гривні

для отримання простої довідки до сотень гривень за проведення

мікробіологічного аналізу). Ввівши позначку для вартості інформації поточної (СИ) і мінімальної (СИпгіп), а також ваговий коефіцієнт 5 для оптимізації співвідношення ефективності та вартості, з урахуванням вимог нормування критеріїв після ряду перетворень отримаємо

цс і

КП:=---------—-1

1 + 8(0^-СИтій

Першим завжди ставиться те питання, критерій пріоритетності (11) свідчення якого приймає найбільше значення.

Перерахування мір невизначеності полягає в тому, щоб після вибору свідчення Е по критерію (11) та одержання відповіді Я зробити перерахування Р(НР) згідно з формулою (7).

Вилучення гіпотез дозволяє зменшити коло пошуку на кожній ітерації процесу виведення. Вилучаємою вважається та гіпотеза (чи група гіпотез), максимально досяжна ймовірність якої стала меншою за мінімально досяжну ймовірність будь-якої гіпотези, окрім вилучаємо-!. Група гіпотез формується тоді, коли можливо виділити серед усіх якусь сукупність гіпотез, максимально досяжні ймовірності яких приблизно однакові та водночас відрізняються від інших. Максимально (мінімально) досяжною ймовірністюРшах(Н) (Ртіп(Н)) гіпотези Н є її ймовірність, якщо усі свідчення, на які ще не отримано відповідей, підтримують (спростують) гіпотезу Н. При звичайному припущенні про незалежність свідчень вирази для Ріпах (Н) та Ршіп(Н) згідно з (5), (6) приймають наступний вигляд:

Р П р(Еі!н)

Ршах(Н) =

Е;єЕ

р П Р(Е;!Н) + (1-р) П Р(^|Н)

ЕієЕ

І Н

ЕІ*ЕН

Ртіл (Н) =

Р П р(ЕіІН)

Е)ЄЕн

р п р^інжі-р) п р(ЕіІй)

Е]єЕн Е^н

(12)

(13)

де П р(Еі!н)

- добуток умовних імовірностей свідчень Ej та-

П Р(Еі|Н)

\Е^Ен

ких, що підтверджують (спростовують) гіпотезу Н.

Гіпотезу можна вилучити з подальшого розгляду, якщо для неї є справедливим наступний критерій:

^-Ртах(Ні)<Фір{Ршіп(Ні). і = 1. П}, і*)

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

Для групи гіпотез Нг максимально і мінімально досяжні ймовірності мають вигляд:

Ртах(Нг)= тах{Ртах(Нк), і = І7п }, Ршіп(Нг) = тіп{Ртіп(Нк), і = ї,п}, (15)

кєГ кєГ

де Нк - к-а гіпотеза групи.

Критерій (14) для групи гіпотез має вигляд:

у- Ртах(Нг)< тт{Ртіп(Нк), і = ГГп }. (16)

>*к кєГ

Перевірка гіпотез по критерію вилучення виконується послідовно. Спочатку до групи приймається одна гіпотеза, що має найменшу Ртах(Н). Якщо вона задовольняє умові (16), то вона вилучається з попереднього склад)' гіпотез та формується інша група, до якої входить гіпотеза з найменшою максимально досяжною ймовірністю серед інших. Якщо умову (16) не виконано, тоді до існуючої групи додається наступна гіпотеза з найменшою максимально досяжною ймовірністю та виконується перевірка згідно з умовою (16). Якщо гіпотеза (чи група) не задовільняють умові (16), процес вилучення закінчується. Вилучення гіпотез проводиться на кожній ітерації процесу прийняття рішень.

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

Введено визначення 1: суперечливим є теке поєднання фактів, яке не може підтвердити ані однієї будь-якої гіпотези. Це визначення справедливе в умовах відсутності невизначеності. В нашому випадку свідчення, що задовольняють визначенню 1, будуть суперечливими з деякою мірою невизначеності.

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

Процедура полягає в пошуку сукупності свідчень, що задовольняє визначенню 1. Факт наявності протиріч вважається встановленим, якщо виявлена хоча б одна тара (трійка, п-ка) свідчень, що задовольнє визначенню ]. При встанов-

ленні факту наявності протиріч приймається рішення «вхідні дані суперечливі». При цьому усі поєднання свідчень, що задовольняють визначенню 1, передаються користувачеві для уточнення.

Критерій прийняття рішень за відсутності протиріч у вхідних даних визначається наступним чином. Нехай число гіпотез у вхідній множині можливих винуватців дорівнювало п0, а після отримання всіх свідчень воно стало рівним П). Критерієм визначення рішень типу «винуватців декілька водночас» та «інформації для прийняття рішення недостатньо» будемо вважати число и, що може приймати значення на інтервалі [0,1]. При заданому и і при відсутності протиріч у вхідних даних правило прийняття рішень має вигляд: якщо Пі < и • п0, то приймається висновок «винуваті декілька джерел забруднення водночас» з переліком всіх гіпотез, не вилучених в процесі вибору, якщо ні - висновок «інформації для прийняття рішення недостатньо». На жаль, немає можливості математично вивести оптимальний критерій сутгєвості зменшення кількості гіпотез - він повинен визначатися, виходячи з умов рішення конкретної задачі. Однак очевидно: якщо підмножина вилучених гіпотез порожня, тоді рішенням може бути лише відповідь «інформації для прийняття рішення недостатньо».

Коректність описаного ДС-методу обгрунтована з допомогою алгебраїчної конструкції II. Гаєха. Продукційна модель ЕС повинна являти собою кінцеву множину правил Я без циклів, для якої задані чотири функції перетворення ваг (мір невизначеності): >ШО(м') - вага заперечення, СОШ(\у, ,...,здк) - вага кон’юнкції, СТЩа, уу) - вага консеквента правила II, \ук) -

інтегральна вага послідовності правил з 51. Ці функції повинні задо-

вольняти умовам П. Гаєка. З (5)-(8), (12)-(16) можна отримати ці чотири функції. Для ДС-методу вони мають вид:

ЖО(\у)=1-\у (17)

СОМ.)(\¥1,...,«'к) = \у,х...,х\ук, (18)

€ТК(а.»,-|^ + а("~',»)- ПІШ -1<а5а (19)

\У! ©•••©тек, (20)

де операція Ф замкнена на інтервалі [0.1], асоціативна, комутативна і задовольняє умовам:

ДЛЯ\У?іО;

\уф0 = 0®\¥ = 0 для\у*1; (21)

1© 0 невизначено (протиріччя); з умови X < У витікає X © 2 < У © Т,.

Отримані результати дозволяють зробити два важливих висновки:

1) запропонований ДС-МЕТОД є коректним і, отже, може бути використаний для прийняття рішень;

2) ДС-метод відрізняється від методів, прийнятих в системах MYCIN і PROSPECTOR, не тільки зовні, але і на аксіоматичному рівні, оскільки вирази (17) - (21) відрізняються від відповідних виразів, отриманих П. Гаєком для систем, названих їм MYCIN-подібними.

На основі функціонального аналізу формул (5), (6) сформульовані умови коректності визначення апріорних імовірностей, необхідних для реалізації ДС-методу, і три властивості залежності апостеріорних імовірностей від апріорних, що дозволяють виявляти помилкові оцінки апріорних імовірностей.

В розділі 5 описані обчислювальні експерименти, основні результати яких можна викласти таким чином.

•Для обчислень за схемою «КОМБ» при ідентифікації винуватців забруднення річок метод системи MYCIN є більш прийнятним, ніж метод системи PROSPECTOR.

•MYCIN-подібний метод упевнено знаходить винуватців, якщо для нього достатньо вхідних даних.

•ДС-метод виявив правильність прийняття рішень та «інтелектуальність» вибору свідчень. Програма, що реалізує ДС-метод, вірно знаходить одного чи декількох винуватців відповідно до отриманих свідчень, виявляє протиріччя у відповідях користувача та при отриманні відповідей типу «НЕ ЗНАЮ» робить висновок «інформації для прийняття рішення недостатньо».

•Виявлено високу ефективність ДС-мегоду, який дозволяє зменшити кількість ітерацій на 42% та вартість отримання свідчень - на 36% (33% від зменшення кількості ітерацій та 3% за рахунок оптимизації вартості інформації по критерію КП без збільшення кількості ітерацій).

•Зміна значень апріорних та умовних імовірностей у ДС-методі впливає на процес прийнятгя рішень. При цьому ЕС продовжує знаходити правильні рішення, однак число необхідних ітерацій помітно змінюється.

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

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

ОСНОВНІ РЕЗУЛЬТАТИ ТА ВИСНОВКИ

1 .Показано, хцо проблема виявлення винуватців забруднення річок задоволь няє умовам Д. Уотермена, при яких розробка ЗС можлива, виправдана і доцільна.

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

3.Розроблена продукційна модель предметної області, яка відображена у ви гляді таблиці відповідності свідчень гіпотезам, множини правил продукції та гра фа І\АБО\КОМБ. Ця модель дозволяє вирішувати задачу ідентифікації викувати: забруднення річок в умовах невизначеності інформації двома розробленими ме тодами.

4.На базі методів MYCIN та PROSPECTOR розроблено метод нечіткого ви ведення на знаннях, який реалізує: зворотний ланцюжок виведення для ви бору потрібного свідчення, прямий ланцюжок виведення для перерахування мі] невизначеності проміжних змінних та гіпотез, отримання мір невизначеност свідчень за результами відповідей користувача, пріоритетний вибір гіпотез до подальшого розгляду, а також два типи рішень: знайдено одного винуватця за бруднення; знайдено декількох винуватців забруднення;

5.Розроблено метод з динамічною схемою виведення (ДС-метод), який вико ристовує неприєднані процедури врахування невизначеності інформації т відрізняється від відомих в ШІ тим, що включає нову процедуру вилученн гіпотез; при виборі свідчень враховує водночас інформативність свідчень т вартість їх отримання; при виробленні висновку передбачає можливість прийнят тя будь-якого типу рішення з повного їх набору («винуватець - найбільш імовірн гіпотеза», «вхідні дані суперечливі», «винуватців декілька водночас» т «інформації для прийняття рішення недостатньо»). Ці можливості забезпечуютьс завдяки тому, що:

•сформульовано умову, яка дозволяє обгрунтовано вилучати гіпотезу (чи ї групу) з подальшого розгляду в тих випадках, коли її ймовірність ні при яки комбінаціях свідчень, що залишилися, не може наблизитися (на інтервал, що за дасться введеним коефіцієнтом співідиошення ймовірностей) навіть до найменше з мінімально досяжних імовірностей для всіх інших гіпотез, що залишилися неви лученими; '

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

•введено визначення протиріччя свідчень, сформульовано критерій сутгєвості протиріч і запропоновано процедуру прийняття рішення типу «вхідні дані суперечливі»;

•визначено умову і критерій, що дозволять виробляти висновки типу «винуватців декілька водночас» і «інформації для прийняття рішення недостатньо».

Ці нови риси суттєво покращують техніко-економічні характеристики ДС-методу (підвищують оперативність та зменшують вартість прийняття рішень), а також дають підстави не приймати рішення, коли інформації недостатньо, або вхідні дані суперечливі.

б.Обгрунтовано коректність ДС-методу з допомогою алгебраїчної конструкції П. Гаєка, що дає теоретичні основи рекомендувати його для застосування в експертних системах.

7.Сформульовано умови коректності визначення апріорних імовірностей, необхідних для реалізації ДС-методу, і властивості залежності апостеріорної ймовірності від апріорних, що дозволяють виявляти помилки оцінок апріорних імовірностей.

8.Розроблено програми, що реалізують запропоновані методи рішення задачі ідентифікації винуватців забруднення річок, і проведено обчислювальні експерименти для реального водного об'єкта (ділянка річки Сіверський Донець від мм. Рубіжне, Сєверодонецьк до кордон}' з Росією) і тестового факт>' ЕВЗ (випадок забруднення річкової води фенолами, який призвів до скарги керівництва Ростовської області на Рубіжанське ПО «Барвник»), Ці експерименти показали високу ефективність ДС-злгоритму: він дозволяє суттєво (майже вдвічі) скоротити число ітерацій процедури виведення і дещо зменшити вартість отримання вхідної інформації, необхідної для прийняття рішень.

9.Розроблені методи і алгоритми пропонується застосовувати як складову ЕС в підсистемах кризового моніторингу Державної системи екологічного моніторингу (СЕМ) України, а також як основу самостійного програмного продукту в обласних Держуправліннях екобезпеки.

10.Практичне використання розроблених методів і алгоритмів повинно сприяти тому, що винуватці екстремально високого забруднення річок, як правило, будуть виявлені, в той час як зараз в багатьох випадках встановити і покарати винуватця ЕВЗ не вдасться. При цьому пошук винуватця буде організований найкращим засобом за критерієм мінімума вартості відбору і аналізу проб води, виїзду інспекторів на місця, проведення експериментів та інших робіт, необхідних цдя доказу його виші.

ПУБЛИКАЩЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Шостак В.Ф., Білогурова A.B. Застосування експертних систем для ідентифікації винуватців забруднення річок // Експрес-нозини: наука, техніка, виробництво. - Київ: УкрІНТЕІ. - 1996. - № 19, - C. 11-12.

2. Белогурова А.В. Идентификация виновников аварийного загрязнения воды I/ АСУ и приборы автоматики. - Харьков: ХТУРЭ. - 1997. - №105. - С. 112-116.

3. Белогурова A.B. Повышение эффективности механизма вывода путем переформулирования задачи // АСУ и приборы автоматики. - Харьков: ХТУРЭ. -1997.-№106.-С. 6-13.

4. Белогурова A.B. Методы учета неопределенности информации при идентификации виновников загрязнения рек // Актуальні проблеми сучасної науки у дослідженнях молодих вчених м.Харкова: Збірник доповідей Першої міської науково-практичної конференції. -Харків: АТ «Бізнес Інформ». - 1997. - С. 162164.

5. Белогурова A.B. Интеллектуализация управления в нештатных ситуациях // Тезисы докладов Междунар. конф. "Теория и техника передачи, приема и обработки информации". - Харьков: ХТУРЭ - 1995г. - С.260.

АНОТАЦІЯ

Білогурова Г.В. Розробка методів прийняття рішень в експертній системі ідентифікації винуватців забруднення річок. - Рукопис.

Дисертація на здобуття ступеню кандидата технічних наук за спеціальністю 01.05.04 - Системний аналіз и теорія оптимальних рішень. - Харківський державний технічний університет радіоелектроннім, Харків, 1998.

Запропоновано методи та алгоритми прийняття рішень при виявленні винуватців екстремально високого забруднення річок в умовах невизначеності інформації. Розроблені методи є розвитком механізмів нечіткого виведення на знаннях теорії штучного інтелекту. Наведено теоретичні обгрунтування та результати обчислювальних експериментів на натурному тест-об’екті.

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

АННОТАЦИЯ

Белогурова А.В. Разработка методов принятия решений в экспертной системе идентификации виновников загрязнения рек. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.04 - Системный анализ и теория оптимальных решений. -Харьковский государственный технический университет радиоэлектроники, Харьков, 1998.

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

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

ABSTRACT

Belogurova A.V. Elaboration of methods for decision making in ал expert system aimed at identification of river polluters. - Manuscript.

Dissertation for candidate degree of technical sciences on speciality 01.05.04 -Systems analysis and theory of optimal decisions. - Kharkov State Technical University of Radioelectronics, Kharkov, 1998.

Methods and algorithms for decision making under conditions of uncertainty of information when detecting culprits which brought about an extremely high pollution of river are offered. The designed methods are developing an knowledge-based uncertain inference of artificial intelligence theory. Theoretical substantiation and experimental computation’s results for a natural test-object are given.

Key words: artificial intelligence, expert systems, knowledge-based uncertain inference, uncertainty of information, detecting of river polluters, extremely high jollution.

Підп. до друку 12.02.98 Формат 60x84 1/1 б Папір друк.

Умов. друк. арк. 1,2 Облік вид. арк. 1,0 Тираж 100 прим.

Зам. № 302

Надруковано у видавництві ХТУРЕ 310726, Харків, просп. Леніна,14