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

Размещено на http://www.allbest.ru/

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ ПРОБЛЕМ МАТЕМАТИЧНИХ МАШИН І СИСТЕМ

УДК 004.896

05.13.06 - Автоматизовані системи управління та прогресивні інформаційні технології

АВТОРЕФЕРАТ

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

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

Панченко Максим Валерійович

Київ - 2004



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

Роботу виконано на кафедрі математичних методів еколого-економічних досліджень факультету кібернетики Київського національного університету імені Тараса Шевченка

Науковий керівник: доктор технічних наук, професор Волошин Олексій Федорович, кафедра математичних методів еколого-економічних досліджень факультету кібернетики Київського національного університету імені Тараса Шевченка

Офіційні опоненти: доктор технічних наук, професор Гладун Віктор Полікарпович, Інститут кібернетики НАН України кандидат фізико-математичних наук, доцент Івохін Євген Вікторович, кафедра системного аналізу і теорії прийняття рішень факультету кібернетики Київського національного університету імені Тараса Шевченка

Провідна установа: Інститут прикладного системного аналізу Міністерства вищої освіти та науки України і Національної академії наук України, м. Київ

Захист відбудеться 02.02.2005 року о 14 годині на засіданні спеціалізованої вченої ради Д 26.204.01 в Інституті проблем математичних машин і систем НАН України за адресою: 03187, Київ 187, пр. академіка Глушкова, 42.

З дисертацією можна ознайомитися у науковій бібліотеці Інституту проблем математичних машин і систем НАН України за адресою: 03187, Київ 187, пр. академіка Глушкова, 42.

Автореферат розісланий 29.12.2004 року

Вчений секретар спеціалізованої вченої ради, кандидат технічних наук Ходак В.І.



Загальна характеристика роботи

проблемний прогнозування поведінка економічний

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

Особливості проблем, які виникають при спробі аналізу нестабільних процесів методами “якісного прогнозування”, зазначені в роботах Бергера Г., Звіскі Ф., Згуровського М.З. та ін.

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

При використанні цих методів виникає проблема інтерпретації нечіткої експертної інформації, розв'язку якої присвячені роботи Белмана Р., Заде Л., Борисова А.Н., Поспєлова Д.А., Орловського С.А. та ін.

Одним з основних методів, які адекватно описують процес прийняття рішень і яким, зокрема, присвячені роботи Гладуна В.П., Рабіновіча З.Л. та ін., є сценарний метод, що базується на методі дерева рішень. Але перепоною для його ефективного використання є проблема великої розмірності. Методи обробки інформації, які дозволяють її подолати, поділяються на такі групи:

алгоритми, розроблені на основі методу вектора спаду, запропонованого Сергієнком І.В., та розвинутого у роботах Гуляницького Л.Ф. та ін.;

методи, які базуються на методології послідовного аналізу варіантів, запропоновані Міхалєвічем В.С., Шором Н.З. та розвинуті у роботах Волковича В.Л., Волошина О.Ф., Мащенка С.О., Кукси А.І. та ін.;

методи, які використовують декомпозиційну схему. Їх розробці присвячені роботи Лесдона Л.С., Валяха Є.П., Цуркова В.І. та ін.

На основі зазначених методів розроблені системи підтримки прийняття рішень, які описуються у роботах Бідюка П.І., Ларічева О.П., Морозова А.О., Згуровського М.С., Мельника В.С., Панкратової Н.Д. та ін.

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

існуючі на даний момент якісні методи не можуть бути застосовані в повній мірі для розв'язання наближених до реальності задач;

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана на кафедрі математичних методів еколого-економічних досліджень факультету кібернетики Київського національного університету ім. Т.Г. Шевченка і є частиною досліджень наукової держбюджетної теми “Математичне моделювання та алгоритми розязання задач оптимізації еколого-економічних систем” (номер держреєстрації - б/т 97067, ДР0197U003334).

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

Досягнення мети роботи пов'язано з розробкою методів обробки експертної інформації, в тому числі і нечіткої, та алгоритмів аналізу цієї інформації, що вимагає розв'язання таких задач:

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

створення алгоритмів побудови дерева рішень на основі методу попарних порівнянь;

створення методів обробки дерева рішень, в тому числі з векторно заданими “довжинами” дуг;

розв'язання проблеми великої розмірності, яка виникає при обробці дерева значних об'ємів.

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

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

Наукова новизна. Розроблено метод, який дозволяє знаходити “найімовірніші” шляхи у дереві рішень (тобто такі шляхи, сума довжин дуг яких найбільша) із скалярно заданими довжинами дуг в умовах великої розмірності (з сотнями вершин).

Запропоновано методи, що дозволяють знаходити “найімовірніші” шляхи у дереві рішень із векторно заданими довжинами дуг, що базуються, зокрема, на застосуванні згорток та дозволяють обробляти дерева із сотнями вершин.

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

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

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

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

Апробація результатів дисертації. Викладені у дисертаційній роботі результати доповідались на: міжнародній конференції “Знання - діалог - рішення”, 13 - 18 вересня 1999 р. (KDS - 99), м. Кацівелі; міжнародних науково - практичних конференціях: “Проблеми впровадження інформаційних технологій в економіці та бізнесі”, травень 2000 р., м. Ірпінь; “Ризикологія в економіці та підприємництві”, 27-28 березня 2001 р., м. Київ; “Моделювання та оптимізація складних систем” (МООС-2001), 25-28 січня 2001 р., м. Київ; “Знание - диалог -решение”, 15 - 20 червня 2001 р. (KDS - 2001), Росія, м. Санкт-Петербург; 16 - 26 червня 2003 р. (KDS - 2003), Болгарія, м. Варна; міжнародній школі-семінарі “Теорія прийняття рішень”, 7 - 12 жовтня 2002 р., м. Ужгород.

Публікації. По темі дисертаційної роботи опубліковано 10 наукових праць. З них - 4 статті у фахових наукових виданнях, 3 - у працях міжнародних наукових конференцій, 1 - у міжнародному журналі, 2 - тези виступів на конференціях.

Структура та обсяг роботи. Дисертаційна робота складається зі вступу, чотирьох основних розділів та списку використаних джерел із 75 найменувань. Повний обсяг роботи становить 145 сторінок, з них 140 сторінок основного змісту та 5 сторінок використаних джерел.



Основний зміст роботи

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

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

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

Також, з'ясована необхідність створення системи підтримки прийняття рішень, яка полягала б у послідовному застосуванні методів якісного та кількісного характеру для аналізу розвитку досліджуваного явища. В основі системи, що пропонується, лежить метод дерева рішень, причому експертна інформація використовується як для побудови самого дерева, так і для оцінки його дуг, для чого використовується метод попарних порівнянь. Експертна інформація може задаватися як в детермінованому вигляді, так і в нечіткій формі. При обробці експертної інформації для знаходження “колективних” оцінок використовується алгебраїчний метод, в якому застосовується метрика Хемінга та міра неспівпадання рангів об'єктів.

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

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

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

Якщо експерт висловлюється чітко (або проводиться числова інтерпретація його нечіткої оцінки), то .

Якщо ж експерт висловлюється нечітко, тобто оцінює перевагу однієї альтернативи над іншою вербально - “так”, “ні”, “можливо” тощо, то в цьому випадку . Тут , де - кількість елементів вектора .

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

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

Для її знаходження застосовуються статистичні та алгебраїчні методи. При їх використанні, у випадку задання відношення переваги нечітко сформульовано та доведено ряд тверджень.

Твердження 2.1 Побудовані таким чином ваги є нормованими:

(

- це вектор одиниць розмірності m),

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

;

;

.

- це елементи матриці . Вони є векторами розмірності m, елементи яких є дійсні числа від до , причому (тут - одиничний вектор розмірності m) та ( - вектор нулів розмірністю m).

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

Нехай - множина усіх нестрогих ранжувань n об'єктів. Тоді результуюча оцінка знаходиться за однією з формул:

( медіана Кемені - Снела);

( середнє значення);

(компроміс);

- відстань між ранжуваннями.

Ранжування задаються матрицями, як і у попередній методиці. В якості відстані між ранжуваннями застосовується метрика Хемінга

або міра неспівпадання рангів об'єктів

,

де - ранг (місце) -го об'єкта в ранжуванні, що задається відповідними матрицями та .

З'ясовано основні переваги та недоліки застосування алгебраїчних методів обробки експертної інформації для знаходження результуючої оцінки.

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

Твердження 2.2. Застосування алгебраїчного методу знаходження загального ранжування вимагає здійснення операцій порівняння.

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

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

Нехай

-

оціночних функціоналів для альтернативи (шляху) , - кількість дуг, які входять у шлях , - кількість вершин у дереві рішень, - початкова вершина, - кінцева вершина.

Тут , якщо та в іншому випадку, - множина усіх можливих шляхів (тобто множина всіх можливих комбінацій вершин дерева рішень).

Тоді задача обробки дерева рішень має вигляд:

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

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

або необхідно знайти таку множину , що для виконується умова: ,, де -кількість елементів у векторі , що (якщо необхідно знайти найкоротші шляхи).

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

Алгоритм пошуку найдовшого (найімовірнішого) шляху. Потрібно знайти найдовший шлях із вершини у вершину . Кожній вершині відповідає оцінка . Кожна вершина може бути пофарбована та розфарбована.

Крок 1. Фарбуємо вершину s. Покладаємо .

Крок 2. Для всіх вершин перераховуємо:

,

де відповідає довжині дуги, яка з'єднує вершини та . Якщо ж така дуга відсутня, то .

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

Крок 3. Якщо для всіх непофарбованих вершин та вершина пофарбована, то найдовший шлях знайдено, закінчити роботу алгоритму.

Для цього методу сформульовано та доведено твердження:

Твердження 3.1. Алгоритм знаходження найдовшого шляху вимагає виконання операцій порівняння, де - кількість вершин у дереві.

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

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

-вага відповідного елемента вектора,

або значення, обчислене за методом Ходжа - Лемана:

;

- елементи вектора; - їх ваги; - коефіцієнт “колективної обережності”; .

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

Твердження 3.2. Якщо , то , де та

;; - елементи вектора; - їх ваги; - коефіцієнт “колективної обережності”; .

Також для лінійної згортки сформульовано та доведено теорему.

Теорема 3.1. Не існує шляху довшого за шлях, який був знайдений у дереві за допомогою методу згорток із застосуванням алгоритму знаходження найдовшого шляху.

Тобто, якщо був знайдений шлях , довжина якого , де , то не існує шляху з довжиною , де , для якого , або і, відповідно, .

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

Модифікований алгоритм пошуку найдовшого шляху. Треба знайти найдовший шлях із вершини у вершину . Дуги графа задані нечітко, за допомогою векторів. Кожній вершині відповідає вектор оцінок . Кожну вершину можна фарбувати та розфарбовувати.

Крок 1. та для всіх , .

Крок 2. Для кожної непофарбованої вершини наступним чином перерахувати величину :

.

де вектор відповідає довжині дуги, яка з'єднує вершини та , і розглядається поелементно. Якщо ж така дуга відсутня, то . Очевидно, що можливий випадок, коли вектори та неможливо порівняти. Тоді

, та , .

Це означає, що в цю вершину є два можливі шляхи.

Якщо ж вектори можливо порівняти, то

та .

Отже маємо для вершин такі характеристики:

.

- це вектор, що визначає довжину одного з можливих шляхів до вершини .

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

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

Крок 3. Якщо всі вершини, для яких пофарбовані, та після виконання кроку 2 жодне не збільшилось, завершити процедуру. Інакше перейти до кроку 2.

Для цього методу сформульоване й доведене таке твердження:

Твердження 3.3. Модифікований алгоритм знаходження найдовшого шляху вимагає виконання операцій, де - кількість вершин у дереві, а - кількість елементів у векторах, якими задаються переходи у дереві.

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

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

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

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

На основі обчислених ваг вершин дерева можна здійснювати прогноз щодо оцінки ймовірності досягнення досліджуваним процесом певних станів.

Для “матричного” методу сформульовано та доведено таке твердження.

Твердження 3.4. Кількість операцій порівняння, при застосуванні даного алгоритму, становить , де - кількість дуг у дереві, а - кількість елементів векторів, за допомогою яких задаються переходи у дереві рішень.

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

Модифікований метод вектора спаду. Необхідно знайти найдовший шлях із вершини у вершину . Відомий деякий початковий шлях , який з'єднує ці вершини. Визначаємо певний окіл (глибину пошуку).

Крок 1. .

Крок 2. За допомогою описаних методів знаходимо найдовший шлях із в . Замінюємо відповідний сегмент у шляху ; .

Крок 3. Якщо , то перейти до кроку 2. Якщо ж , то знаходимо найдовший шлях з в . Замінюємо відповідний сегмент у шляху . Закінчуємо роботу алгоритму.

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

Твердження 3.5. Застосування модифікованого алгоритму вектора спаду вимагає виконання операцій порівняння, де - глибина пошуку, - довжина початкового шляху.

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

Нехай , - -ий рівень дерева; - вершини цього рівня. На кожному рівні вершин, , - “верхні” вершини цього рівня (тобто такі вершини, на які посилаються лише вершини вищого рівня), , - “нижні” вершини цього рівня (тобто такі вершини, які посилаються лише на вершини нищого рівня).

Потрібно знайти найдовший шлях із вершини у вершину .

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

Крок 2. . Знаходимо найдовші шляхи з верхніх вершин (вершин, на які посилаються нижні вершини вищого рівня) поточного рівня до нижніх. Виділяємо пару вершин, з'єднаних найдовшим шляхом.

Крок 3. Якщо поточний рівень містить вершину і вона відноситься до верхніх вершин, то перейти до кроку 4. Якщо поточний рівень містить вершину і вона не відноситься до верхніх вершин, то знайти найдовші шляхи з верхніх вершин поточного рівня у вершину . Знайти ту з верхніх верши, шлях із якої до найдовший. Перейти до кроку 4. Якщо поточний рівень не містить вершину , то перейти до кроку 2.

Крок 4. “Зклеюємо” шляхи сусідніх рівнів таким чином: спочатку намагаємося знайти найдовший шлях з останньої вершини шляху верхнього рівня до першої вершини шляху нижчого рівня. Якщо ці вершини взагалі неможливо з'єднати, то відкидаємо останню вершину шляху з вищого рівня та знаходимо найдовший шлях з останньої вершини вищого рівня до першої вершини нижчого рівня. Якщо ж і ці вершини неможливо з'єднати, то відкидаємо першу вершину шляху нижчого рівня і т.д.

У найгіршому випадку доведеться шукати найдовший шлях між першою вершиною вищого рівня та останньою вершиною нижчого рівня. Включаємо знайдені вершини у загальний шлях. Якщо ж з'єднати таким чином вершини двох рівнів не вдалося, то в даному дереві неможливо з'єднати вершини та .

Загалом можна сформулювати наступне твердження.

Твердження 3.6. Кількість операцій порівняння, якої вимагає робота декомпозиційного алгоритму, в найгіршому випадку становить

або .

Алгоритм послідовного аналізу варіантів. Застосовується у випадку, коли дерево рішень розбивається на певні рівні та можливий контроль особи, яка приймає рішення, за процесом “зклеювання” шляхів сусідніх рівнів.

Необхідно знайти найдовший шлях із вершини у вершину .

Крок 1. . Визначаємо рівні, до яких належать вершини та .

Крок 2. Знаходимо найдовші шляхи з вершини до всіх найнижчих вершин її рівня (тобто до вершин, які посилаються лише на вершини наступного рівня), .

Крок 3. Якщо поточний рівень містить вершину і вона відноситься до верхніх вершин, то перейти до кроку 4. Якщо поточний рівень містить вершину і вона не відноситься до верхніх вершин, то знайти найдовші шляхи з верхніх вершин поточного рівня у вершину . Знайти ту з верхніх вершин, шлях із якої до найдовший. Перейти до кроку 4. Якщо поточний рівень не містить вершину , то перейти до кроку 2.

Крок 4. “Зклеюємо” шляхи сусідніх рівнів та таким чином: задаються коефіцієнти та . Для шляху , який буде проходити через вершини цих двох рівнів, повинно виконуватися: , де - найдовші шляхи рівнів та . Так само задається глибина пошуку . Знаходимо найдовший шлях з останньої вершини шляху верхнього рівня до першої вершини шляху нижчого рівня. Якщо , то процедура зклювання завершена. Інакше відкидаємо вершини зі шляхів поточних рівнів (дозволяється відкидати не більш ніж вершин) та повторюємо процедуру “зклеювання”. Якщо не вдалося з'єднати два рівні, то понижуємо значення і повторюємо все спочатку.

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

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

Наведений опис інтерфейсу системи та основні його процедури у вигляді текстів мовою С.

Для обробки дерева рішень запрограмовані такі методи:

- метод пошуку найдовшого шляху;

- матричний метод;

- метод Дейкстри;

- модифікований метод вектора спаду.

Для цих методів приведені блок-схеми та тексти мовою С.

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

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

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

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

- складання розкладів руху громадського транспорту.

Ефективне застосування даної програмної системи підтверджено відповідними актами впровадження.



Висновки

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

Основні теоретичні й практичні результати, представлені в дисертації:

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

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

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

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

4. Для обробки дерев, довжини дуг яких задані нечітко, створені наступні методи:

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

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

5. Для подолання проблеми великої розмірностіяка, яка виникає при застосуванні методу дерева рішень для обробки значної кількості експертної інформації, розроблені наступні оригінальні методи пошуку наближеного розв'язку:

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

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

- алгоритм послідовного аналізу варіантів.

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

7. За допомогою зазначеної системи було створено наступні СППР:

- СППР для діагностики епілептичних захворювань, яка успішно застосовувалась для розв'язання конкретних практичних задач, що підтверджено відповідним актом впровадження;

- СППР, яка дозволяє здійснювати діагностику кардіологічних захворювань. Вона успішно застосовувалась на практиці, що підтверджено відповідним актом впровадження;

- СППР складання розкладів руху громадського транспорту, про успішне застосування якої свідчить відповідний акт впровадження.



Список опублікованих робіт за темою дисертації

1. Волошин О.Ф., Панченко М.В. Використання експертного оцінювання для якісного прогнозування на основі багатопараметричних залежностей // Математичні машини та системи.-2002.-№2.- С. 83-90.

2. Волошин О.Ф., Панченко М.В., Піхотник Є.П. Експертна система підтримки прогнозування курсу гривні // Искусственный интеллект.-1999. - № 2. - С. 354 - 359.

3. Волошин О.Ф., Панченко М.В. Оцінка ризику на основі методу дерева рішень та експертних оцінок // Ризикологія в економіці та підприємництві: Збірник наукових праць за матеріалами міжнародної науково-практичної конференції.- 2001. - 27-28 березня. - С. 84 - 86.

4. Волошин О.Ф., Панченко М.В. Експертна система для прогнозування нестабільних процесів на основі методів дерева рішень та попарних порівнянь //Моделювання та оптимізація складних систем.-2001.-Т.3 - С. 79 - 81.

5. Волошин О.Ф., Панченко М.В. Система розробки СППР на основі методу дерева рішень // Тези міжнародної науково-практичної конференції “Проблеми впровадження інформаційних технологій”. - Ірпінь.-2000.- Травень.- С. 290 - 291.

6. Волошин О.Ф., Панченко М.В. Прогнозування нестабільних процесів на основі методу дерева рішень з використанням для аналізу експертної інформації методу попарних порівнянь // Вісник КНУ. Кібернетика.-2001.-Вип. 2. - С. 15 - 18.

7. Волошин О.Ф., Панченко М.В. Система розробки СППР на основі методу дерева рішень // Праці міжнародної школи-семінару “Теорія прийняття рішень”. - Ужгород: УжНУ.- 2002. - С. 22-23.

8. Панченко М.В. Пошук оптимальних шляхів у дереві рішень // Математичні машини та системи.- 2004.- №1. - С. 122-133.

9. Voloshin O.F., Panchenko M.V. The Forecasting of Stable Processes by a Tree Solution Using A Pairwise Comparison Method for Analysis of Expert Information // Труды научно-практической конференции KDS-2001.-2001.- Т. 1. - С. 50 - 54.

10. Voloshin O.F., Panchenko M.V. The System of Quality Prediction on the Basis of a Fuzzy Data and Psychography of the Experts // International Journal “Information & Application”.-2003.-№3. - P. 261-265.



Анотація

Панченко М.В. Розробка математичного, алгоритмічного та програмного забезпечення для прийняття рішень в різних предметних областях на основі методу дерева рішень. - Рукопис.

Дисертація на здобуття ступеня кандидата технічних наук із спеціальності 05.13.06. - автоматизовані системи управління та прогресивні інформаційні технології. - Інститут проблем математичних машин і систем НАН України, Київ, 2004.

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

Ця система використовує експертні дані для збору яких використовуються відомі методи, такі, як:

- метод попарних порівнянь;

- алгебраїчні методи обробки експертної інформації;

- порогові методи.

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

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

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

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

метод згорток. Дозволяє за рахунок застосування різноманітних згорток обробляти дерево з нечітко заданими дугами;

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

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

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

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

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

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

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

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

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



Аннотация

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

Диссертация на соискание степени кандидата технических наук по специальности 05.13.06. - автоматизированные системы управления и современные информационные технологии. - Институт проблем математических машин и систем НАН Украины, Киев, 2004.

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

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

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

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

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

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

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



Summary

Panchenko М.V. The creation of mathematical, algorithmic and software for acceptance of the decisions in different subject domains on the basis of a method of a tree of the decisions. - Manuscript.

The dissertation on gaining the candidate degree of technical science in speciality 05.13.06. - automated control systems and progressive information technologies. Institute of Mathimatical Machines and System of NAS of the Ukraine, Kyiv, 2004.

The dessertation work is devoted to creation of system of support of acceptance of the decisions, as theoretical development and software, which can be effective used for realization of forecasting of such astable processes, as change of a rate of national currency, other valuable papers, change of the prices in the market of resources, change of demand on the certain goods, development of illness of the patient, change of a condition of an environment in a consequence of action of chemical substances etc.

The received expert data are represented as a tree of the decisions, which permits to select group more qualified experts. It raises accuracy of the forecast and enables to investigate the phenomena, in which development the fast revolutionary changes are inherent.

The methods and algorithms are offered which allow to calculate weight of the experts, to make the tax and preliminary processing of the expert information and on its basis to construct a tree of the decisions.

The original methods of search in a tree of the decisions are offered which allow to find optimum ways, including at the indistinct task of arches of a tree.

The original algorithms and methods of search in a tree of the decisions are offered which allow to solve a problem of the large dimension, which arises at significant volume і of the data.

In the dissertation the program system created on a basis приведеных теоретическиз of development, used for diagnostics эпелептических and кардиологических of diseases is submitted.

Key words: the expert, indistinct expert information, system of support of acceptance of the decisions, algorithms of search on the columns.

Размещено на Allbest.ru