68256

УЗАГАЛЬНЕНИЙ ІТЕРАЦІЙНИЙ АЛГОРИТМ ІНДУКТИВНОГО МОДЕЛЮВАННЯ З ЗАСТОСУВАННЯМ МЕРЕЖЕВИХ ТЕХНОЛОГІЙ

Автореферат

Информатика, кибернетика и программирование

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

Украинкский

2014-09-20

842.5 KB

6 чел.

Національна академія             Міністерство  освіти

наук  України                                                      і науки України

МІЖНАРОДНИЙ НАУКОВО-НАВЧАЛЬНИЙ ЦЕНТР

ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ТА СИСТЕМ

 

БУЛГАКОВА ОЛЕКСАНДРА СЕРГІЇВНА

УДК 681.5.015

УЗАГАЛЬНЕНИЙ ІТЕРАЦІЙНИЙ АЛГОРИТМ ІНДУКТИВНОГО МОДЕЛЮВАННЯ З ЗАСТОСУВАННЯМ МЕРЕЖЕВИХ ТЕХНОЛОГІЙ

05.13.06 – інформаційні технології

 

Автореферат

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

Київ - 2011


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

Робота виконана у Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН та МОН України

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

- доктор технічних наук, професор

Степашко Володимир Семенович,

Міжнародний науково-навчальний центр інформаційних технологій та систем НАН та МОН України,

завідувач відділу

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

- доктор технічних наук, професор

Литвинов Віталій Васильович,

Інститут проблем математичних машин і систем НАН України, завідувач відділу

- кандидат технічних наук

Осипенко Володимир Васильович

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

та робототехнічних систем

 

Захист відбудеться 15 червня 2011 року о 1200 годині на засіданні Спеціалізованої вченої ради Д 26.171.01 в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН та МОН України за адресою: 03680, Київ-680, проспект акад. Глушкова, 40.

З дисертацією можна ознайомитись у бібліотеці Міжнародного науково-навчального центру інформаційних технологій та систем НАН та МОН України: 03680, Київ, проспект акад. Глушкова, 40.

Автореферат розіслано  «13»    травня     2011 р.

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

Спеціалізованої вченої ради      О.В.Бабак

    


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

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

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

Вагомий внесок у формування теорії та практики індуктивного моделювання зробили перш за все академік О.Г.Івахненко, а також П.І.Бідюк, Є.В.Бодянський, В.М.Висоцький, Ю.П.Зайченко, Т.Кондо, П.Кордік, В.А.Крисілов, Н.М.Куссуль, Ф.Лемке, В.В.Різник, В.С.Степашко, Ю.В.Юрачковський та інші українські й закордонні вчені. Серед різноманітних методів моделювання вирізняється метод групового урахування аргументів (МГУА), який дозволяє будувати моделі безпосередньо за вибіркою даних, без залучення додаткової апріорної інформації.

МГУА успішно застосовується в задачах аналізу даних і виявлення закономірностей, прогнозування і моделювання, кластеризації та розпізнавання образів. Він дає можливість автоматично знаходити взаємозалежності в даних, обирати оптимальну складність моделі. Станом на сьогодні розроблено і досліджено багато різновидів алгоритмів МГУА перебірного та ітераційного типу. Перебірні алгоритми ефективні як засіб структурної ідентифікації, але лише за обмеженого числа аргументів. Ітераційні алгоритми працездатні за великої кількості аргументів, але специфіка їхньої архітектури не гарантує побудови моделі істинної структури. Досі ці два класи алгоритмів розвивались без поєднання їх сильних сторін.

Найбільш поширеним нині є класичний багаторядний ітераційний алгоритм МГУА, проте він має свої істотні недоліки: можливість втрати інформативних та/або включення неінформативних аргументів, експоненційне зростання степеня полінома. Для подолання цих недоліків раніше були запропоновані та реалізовані окремі модифікації, проте вони не вирішували всі проблеми в комплексі. Крім того, з розвитком Інтернет-технологій з’явилася можливість використання веб-інтерфейсу як засобу забезпечення комфортної та ефективної роботи користувача.

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

Зв’язок роботи з науковими програмами, планами, темами. Робота виконувалась відповідно до планів наукових досліджень відділу Інформаційних технологій індуктивного моделювання Міжнародного науково-навчального центру інформаційних технологій та систем НАН і МОН України. Головні результати дисертації отримано в рамках досліджень за такими темами відділу:

  1.  «Дослідження і розробка нових інформаційних технологій аналізу та виявлення закономірностей нестаціонарних динамічних процесів в умовах невизначеності та неповноти інформації» (№ держреєстрації 0107U003270, 2007-2011 рр.);
  2.  «Розроблення та дослідження інтелектуальних інформаційних технологій індуктивного моделювання складних процесів і систем» (№ держреєстрації 0107U000568, 2007-2011 рр.).

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

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

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

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

Предметом дослідження є підвищення ефективності алгоритмів МГУА на основі узагальнення їхніх типових структур.

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

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

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

Практичне значення одержаних результатів:

  •  розроблені в роботі комплексна методика аналізу ефективності ітераційних алгоритмів МГУА та відповідний програмний інструментарій дозволяють виконувати порівняльні дослідження алгоритмів моделювання та ефективно розв'язувати задачі побудови моделей за вибірками даних;
  •  реалізована комп’ютерна онлайн-технологія автоматизованого розв’язання задач моделювання на основі розроблених узагальнених алгоритмів МГУА дозволяє виконувати розрахунки через Інтернет, в межах локальної комп'ютерної мережі або в навчальному процесі при виконанні лабораторних робіт;
  •  прикладну ефективність розроблених інструментальних засобів продемонстровано на прикладі розв'язання реальних задач: моделювання впливу токсиканта біхромат калію на життєдіяльність клітин зелених водоростей; моделювання впливу забруднення Чорного моря (бухти Севастопольська, Південна та  Карантинна) на загальне число видів донних організмів; побудова моделі залежності ВВП України від показників, що описують стан інвестиційної сфери;

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

  •     в Інституті біології південних морів імені О.О.Ковалевського НАН України впроваджено моделі, що описують вплив антропогенного забруднення морських бухт Севастополя на загальне число видів донних організмів. У процесі моделювання виявлено існування однорідних зон забруднення різних бухт, що дозволили побудувати лише три інформативні моделі без втрати їх точності.
  •     в навчальному процесі Миколаївського національного університету імені В.О.Сухомлинського впроваджено розроблений комп'ютерний комплекс для використання його студентами 4-го курсу на заняттях з дисципліни «Моделювання економічних, біологічних та соціальних процесів».
  •     в Чеському технічному університеті в Празі впроваджено підсистему для комбінаторної оптимізації структури нейромережі МГУА у складі програмного комплексу «Повністю автоматизоване виявлення знань на основі еволюції груп адаптивних моделей» FAKE GAME.

Особистий внесок здобувача у працях зі співавторами. В працях, написаних у співавторстві, автору дисертації належать: порівняння результатів моделювання впливу альгінової кислоти на життєдіяльність клітин водоростей за допомогою МГУА та нейромереж зі зворотним поширенням помилки [1], гібридні алгоритми самоорганізації моделей [2], опис структурних компонентів та модулів програмного комплексу на основі узагальненого ітераційного алгоритму МГУА [3],  вивчення на чисельних експериментах впливу ключового параметра МГУА – свободи вибору кращих рішень – на ефективність алгоритмів [4], дослідження застосування МГУА та нейромереж для побудови моделей економічних процесів [5], побудова математичних моделей для розрахунку впливу сполук хрому на фотосинтетичну активність і рухливість клітин зелених водоростей [6], застосування нейромереж та МГУА для моделювання впливу токсиканта на концентрацію хлорофілу у водоростях [7],  впровадження підсистеми для комбінаторної оптимізації структури нейромережі МГУА у складі програмного комплексу FAKE GAME [8], аналіз застосування гібридного алгоритму МГУА для селекції ефективної моделі на реальних даних [9], чисельне дослідження ефективності застосування гібридних алгоритмів МГУА для побудови моделей на тестових даних [10].  

Апробація наукових результатів. Основні результати роботи оприлюднені та обговорювалися на Другому Міжнародному семінарі з індуктивного моделювання IWIM-2007 – Прага, 16-19 вересня 2007 р., Міжнародній науковій конференції «Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту» ISDMCI’2008 – Євпаторія, 18-22 травня 2008 р., Другій міжнародній конференції з індуктивного моделювання ICIM-2008 – Київ, 16-19 вересня 2008 р., Міжнародній науковій конференції «Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту (ISDMCI’2009)», Євпаторія, 19-23 травня 2009 р. Третьому міжнародному семінарі з індуктивного моделювання IWIM-2009 – Криниця, Польща,14-19 вересня 2009 р., Третій міжнародній конференції з індуктивного моделювання ICIM-2010 – Євпаторія, 17-23 травня 2010 р.

Публікації. Результати дисертації викладені у 10 наукових публікаціях, у тому числі в 4 статтях у журналах та збірниках наукових праць з переліку фахових видань ВАК України, 6 доповідей у матеріалах конференцій.

Структура і обсяг дисертаційної роботи. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел (104 бібліографічних посилань) та 3 додатків. Повний обсяг дисертації становить 174 сторінки друкованого тексту, з них 143 сторінки основного тексту, 60 рисунків та 26 таблиць.

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

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

У першому розділі роботи проаналізовано методи та технології розв’язання задач моделювання, їх переваги та недоліки. Проаналізовано особливості наявних алгоритмів МГУА та їх модифікацій, сучасний розвиток МГУА-подібних систем. Обґрунтована необхідність розробки більш ефективного алгоритму самоорганізації оптимальних моделей на основі узагальнення структур відомих алгоритмів МГУА.

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

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

     (1)

у класі лінійних за параметрами функцій типу полінома Колмогорова-Габора:

та пошуку оптимальної моделі з цієї множини як розв’язок задачі дискретної оптимізації за умовою мінімуму зовнішнього критерію селекції :

     (2)

де оцінки параметрів для кожної  fΦ є розв’язком задачі неперервної оптимізації

     (3)

де  – критерій якості задачі оцінювання параметрів моделі, згенерованої в процесі структурної ідентифікації, sf  – її складність (число параметрів).

В ролі критерію  в МГУА можуть застосуватись, наприклад, зовнішні критерії регулярності або незміщеності, що ґрунтуються на розбитті вибірки.

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

    (4)

Критерій незміщеності рішень (міра близькості оцінок, отриманих на різних частинах вибірки):

  (5)

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

   (6)

В комбінаторних алгоритмах МГУА організується повний перебір всіх можливих структур моделей, тому вони обмежені в своєму застосуванні часом та розмірністю задач. Багаторядні алгоритми дозволяють розв’язувати задачі великої розмірності за прийнятний час завдяки скороченому перебору моделей.

В класичному багаторядному ітераційному алгоритмі БІА МГУА кожна частинна модель формується як деяка функція  від пари аргументів ,  (; i j) на початковому ряді та комбінація моделей, отриманих на попередньому ряді, починаючи з другого, з такими можливими варіантами лінійних, білінійних чи квадратичних частинних описів:  

      

    (7)

      

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

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

Пропозиції щодо усунення окремих недоліків раніше застосовувались у кількох окремих алгоритмах, зокрема, пропонувалось: додавати початкові аргументи на кожному ряді в перелік аргументів: багаторядний алгоритм зі збереженням базису (Б.К.Свєтальський, П.І.Ковальчук, 1979; Ю.П.Юрачковський, 1981); спрощений багаторядний алгоритм (О.І.Шелудько, 1974); застосовувати повний перебір варіантів частинної моделі (Н.О.Івахненко, А.А.Марчев, 1978); формувати «активні нейрони» (О.Г.Івахненко, 1994), коли кожен нейрон мережі МГУА є теж алгоритмом МГУА, що самоорганізує свою структуру.

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

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

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

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

Структуру класичного багаторядного алгоритму БІА МГУА описано вище. Інший базовий алгоритм, у якому пари формуються з проміжних та початкових аргументів, називається «релаксаційний ітераційний алгоритм», або РІА МГУА:

 

          (8)

 

Алгоритм, що об’єднує архітектуру двох попередніх, можна назвати «Комбінованим ітераційним алгоритмом» КІА МГУА.

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

,    (9)

де  – елементи двійкового структурного вектора  d , що приймають значення 1 або 0 (включення чи невключення відповідного аргументу): ,. Схема перебору тоді має вигляд:

,

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

Таким чином, алгоритм із запропонованою архітектурою є узагальненням усіх шести згаданих вище алгоритмів, тому його природно назвати «Узагальнений ітераційний алгоритм МГУА» УІА МГУА (рис.1).  

Рис. 1. Схема роботи узагальненого ітераційного алгоритму МГУА

Для характеристики структури алгоритмів було запроваджене впорядковане кодування ітераційних алгоритмів в ієрархічній структурі УІА.

Узагальнений ітераційний алгоритм – це множина ітераційних та ітераційно-комбінаторних алгоритмів, що визначається компонентами вектора трьох індексних множин: DM (Dialogue Mode), ІC (Iterative-Combinatorial), MR (Multilayered- Relaxative), тобто будь-який ітераційний алгоритм визначається як певний окремий випадок узагальненого УIA = {DM, ІС, MR}. При цьому DM приймає три значення: 1 – стандартний автоматичний режим; 2 – планований автоматичний режим; 3 – інтерактивний режим; ІC приймає два значення: 1 – ітераційний та 2 – ітераційно-комбінаторний алгоритми; MR приймає три значення: 1 – класичний ітераційний, 2 – релаксаційний, 3 – комбінований алгоритми. Тоді вектор з трьох елементів повністю визначає собою той чи інший алгоритм. Наприклад, при DM=1 маємо три стандартні/базові варіанти ітераційних алгоритмів: БІА= УІА (1,1,1); РІА= УІА (1,1,2) та КІА= УІА (1,1,3), а також три ітераційно-комбінаторних: БІКА= УІА (1,2,1); РІКА= УIA (1,2,2) та КІКА= УIA (1,2,3). Зрозуміло, що при DM рівному 2 чи 3 сформуються нові варіанти цих алгоритмів, що генеруватимуть інші моделі.

Сконструйована таким чином ієрархічна структура узагальненого ітераційного алгоритму зображена на рис.2.

Рис.2. Ієрархія розробленої архітектури ітераційних алгоритмів МГУА

(світлі блоки – відомі алгоритми, сірі – розроблені нові структури)

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

Вхідні параметри ітераційних алгоритмів: число початкових аргументів m; число точок у вибірці n; критерій селекції моделей; свобода вибору моделей F.  

Проміжні показники: графік зміни мінімальних та максимальних значень критерію по рядах; зміна складу аргументів у кращій моделі по рядах.

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

Методика чисельного дослідження впливу управляючих параметрів на ефективність алгоритмів містить такі основні етапи: згенерувати матрицю аргументів Х із випадкових чисел за певним розподілом; задати конкретний вид залежності виходу не від усіх, а лише від певної частини аргументів; обчислити значення вектора  у та сформувати вибірку  W=(X y) ; побудувати оптимальні моделі за кожним з алгоритмів при різних значеннях F чи інших вхідних параметрів.

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

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

Основний показник ефективності – відновлення структури істинної моделі

Порівняння ефективності виконувалось для чотирьох ітераційних алгоритмів – багаторядного, релаксаційного, комбінованого та узагальненого. У тестовому прикладі істинна модель залежала лише від 10 аргументів з усіх 200, що були у вибірці. Експеримент показав, що істинну лінійну залежність відтворюють усі алгоритми, крім класичного багаторядного, в якому були втрачені три істинні аргументи, причому в УІА значення критерію AR найменше. Важливо зазначити, що для знаходження лінійної залежності в узагальненому алгоритмі використовувалися квадратичні частинні описи, проте завдяки комбінаторній оптимізації структури частинних моделей була знайдена істинна лінійна залежність.

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

Мета проведення експерименту – порівняти здатність різних алгоритмів МГУА відновити структуру істинної нелінійної моделі, закладеної в даних.

Параметри даних: m = 200, n = 243, nA = 163, nB = 70 (штучні дані, випадкові числа в діапазоні [0, 5]), свобода вибору F = 40.

Порівнювані алгоритми: 1) багаторядний (БІА); 2) релаксаційний (РІА); 3) комбінований ітераційний (КІА); 4) багаторядно-комбінаторний (БІКА); 5) релаксаційно-комбінаторний (РІКА); 6) узагальнений ітераційний (УІА); Квадратична залежність (196 зайвих аргументів) представлена такою формулою:

   (11)

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

Таблиця 1 – Порівняння ефективності різних ітераційних алгоритмів

у разі квадратичної залежності

Алго-ритми

AR(В)

Модель

1

11,309

2

3,031

3

3,011

4

0,462

5

4*10-7

6

3*10-8

  1.  Дослідження ефективності алгоритмів в умовах зашумлених даних.

Експерименти, виконані в дисертації, показують, що при накладанні на вихідну змінну рівномірного шуму з відношенням шум/сигнал 10% та 30%  кращим алгоритмом, що відтворює істинну структуру моделі, залишається узагальнений.

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

Параметри вибірки: m=3 аргументи та n=100 точок, поділ на підвибірки  nA=65, nВ=35. Досліджувався вплив свободи вибору моделей  F, як основного з перелічених вище управляючих параметрів, на показники ефективності алгоритмів.

Істинна модель має вигляд такої нелінійної функції від трьох аргументів:

  (12)

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

З рис. 3 видно, що достатньою свободою вибору для всіх алгоритмів є F = 20.

Рис. 3 Зміна значень критерію селекції при збільшенні

свободи вибору моделей

На рис. 4 показано залежність значень критерію селекції від номера ряду при різних свободах вибору для узагальненого алгоритму УІА. Видно, що при F=3 та F=5 мінімум досягається на 9-му ряді, а при   F=10 та F=20 – на 10-му, тобто при збільшенні F кількість рядів, необхідних для досягнення мінімуму критерію, зростає, а саме значення мінімуму зменшується, доки точка мінімуму та мінімальне значення не стабілізуються, що свідчить про знаходження істинної моделі.

Рис.4 Зміна значень критерію селекції по рядах алгоритму УІА

при різних свободах вибору (логарифмічна шкала)

  1.  Дослідження внутрішньої збіжності ітераційних алгоритмів МГУА.

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

Ітераційний алгоритм має внутрішню збіжність, якщо в результаті ітераційного процесу з критерієм селекції CR=RSS, де RSSзалишкова сума квадратів на всій вибірці W (без розбиття), оцінки параметрів оптимальної моделі збігаються до оцінок параметрів моделі істинної структури, отриманих за МНК. 

Розбиття вибірки на навчальну та перевірочну підвибірки не застосовується (m=10, n=50). Досліджується внутрішня збіжність трьох ітераційних алгоритмів МГУА: класичного БІА, комбінованого КІА та узагальненого УІА.

Істинна модель має вигляд лінійної функції від десяти аргументів:

 (13)

На рис.6 показана зміна значень RSS по рядах цих алгоритмів при F = 20.

Рис.6 Зміна значення RSS по рядах для трьох ітераційних

алгоритмів МГУА при F = 20 (логарифмічна шкала)

     (14)

 (15)

(16)

Два перші  рівняння (14) (15) загалом підтверджують внутрішню збіжність двох ітераційних алгоритмів, оскільки значення оцінених параметрів близькі до істинних, див. (13). Видно, що узагальнений алгоритм досягає мінімуму на 9-му ряді, а комбінований – на 12-му, тобто швидкість збіжності УІА значно вища, ніж КІА. Точність отриманих моделей теж відрізняється на користь узагальненого: для УІА RSS=0.001, для КІА RSS=0.006. Це демонструє ефективність використання оптимізації частинних моделей.  В багаторядному ж алгоритмі спостерігається збіжність за критерієм, але відсутня внутрішня збіжність за структурою і параметрами, оскільки, як видно з (16), були втрачені істинні аргументи х1 та х7.

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

У третьому розділі розглядається структура програмного комплексу, який реалізує узагальнений алгоритм МГУА з можливістю мультидоступу через Інтернет або локальну мережу. Для розв’язання задач моделювання складних систем розроблено спеціальне програмне забезпечення, виконане у вигляді самостійної програми з можливістю керування через веб-інтефейс.

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

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

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

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

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

Серверна частина додатку виконана на мові Perl, як і основний код.

Клієнтська частина представляє собою одну єдину сторінку index.htm. Запити до сервера надсилаються без перезавантаження сторінки, отримані відповіді змінюють зовнішній вигляд сторінки.

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

Метою першої задачі було моделювання впливу K2Cr2O7 на фотосинтетичну активність та рухомість клітин зелених водоростей за даними Київського національного університету імені Т.Г.Шевченка. Побудовані моделі дозволили описати процес розвитку водоростей при додаванні різних концентрацій токсиканта, який може служити індикатором посиленого антропогенного забруднення водних об’єктів. Помилка отриманих моделей склала 6-10%.

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

Точність (за величиною коефіцієнта детермінації) загальної моделі, побудованої за об’єднаною вибіркою даних усіх станцій, виявилась незадовільно низькою як загалом, так і по окремих станціях (до 30%). З іншого боку, моделі, побудовані за даними кожної станції окремо, показали достатню для практичних задач точність (70-90%), але використання такої кількості моделей знижує їх прикладну цінність.

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

Розроблену методику зонування було апробовано в Інституті біології південних морів ім. О.О. Ковалевського НАН України. Виділено три істотних групи станцій, що відповідають таким зонам бухт: станції на серединній лінії (фарватері) Севастопольської бухти, тобто глибоководна зона; станції поблизу берегів бухт, тобто мілководна зона; станції в невеликих затоках бухт, або локальна зона.

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

Третя задача полягала у моделювання залежності ВВП від 10-ти інвестиційних макроекономічних показників за даними Держкомстату України. Мета моделювання – визначити інформативні інвестиційні показники, що найбільше впливають на динаміку ВВП. Найкраща модель була знайдена за допомогою узагальненого алгоритму. Отримана модель має високу точність і свідчить про те, що з усіх 10-ти інвестиційних показників істотний вплив на  ВВП мають лише 4. Помилка отриманої моделі склала 1%.

В трьох додатках містяться таблиці даних, опис експериментів по оптимізації структури нейромережі МГУА в FAKE GAME   та документи про впровадження.

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

У дисертаційній роботі отримали подальший розвиток технології індуктивного моделювання на основі ітераційних алгоритмів МГУА.

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

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

  1.  В результаті виконаного порівняльного аналізу переваг та недоліків наявних алгоритмів і засобів індуктивного моделювання виявлено можливості та шляхи підвищення ефективності розв’язання задач побудови моделей на основі узагальнення типових структур алгоритмів МГУА.
  2.  Розроблений узагальнений ітераційний алгоритм МГУА, окремими випадками якого є як відомі, так і нові різновиди багаторядних, релаксаційних та ітераційно-комбінаторних алгоритмів, забезпечує широкі можливості для порівняльного дослідження ефективності різних алгоритмів та для розв’язання реальних задач моделювання.
  3.  Комплексна методика аналізу ефективності ітераційних алгоритмів МГУА за допомогою обчислювальних експериментів дозволяє всебічно вивчати вплив ключових параметрів порівнюваних алгоритмів на основні показники якості результатів моделювання. Зокрема, для узагальненого ітераційного алгоритму вперше в результаті експериментів встановлено факт збіжності до істинної поліноміальної моделі як за структурою, так і за параметрами.
  4.  Розроблені програмні засоби із застосуванням мережевих технологій дають можливість використання узагальненого ітераційного алгоритму МГУА та його окремих випадків як у режимі онлайн-доступу через Інтернет, так і в локальній мережі, в тому числі для роботи груп користувачів.
  5.  Розроблена технологія автоматизованого розв’язання задач моделювання на основі МГУА дозволяє будувати моделі у трьох основних режимах: двох автоматичних – стандартному та планованому, а також інтерактивному, коли процес самоорганізації моделі можна коригувати чи зупиняти на будь-якому етапі зі збереженням проміжних результатів та продовжувати його в інший момент часу.
  6.  Ефективність розробленої технології побудови моделей продемонстровано на трьох прикладах розв’язання реальних задач моделювання: вплив токсиканта біхромат калію на життєдіяльність клітин зелених водоростей; вплив забруднення бухт Севастополя на загальне число видів донних організмів; залежність ВВП України від показників стану інвестиційної сфери.
  7.  У задачі моделювання екологічних наслідків забруднення Чорного моря запропонована методика зонування акваторії морських бухт у Севастополі на основі аналізу структур побудованих моделей, що описують залежність біорозмаїття донних організмів від рівня локального забруднення, яка дозволила звести число інформативних моделей до трьох відповідно до виявленої кількості екологічно однорідних зон.

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

  1.  Булгакова О.С.  Застосування МГУА та нейромереж для моделювання життєвих функцій зелених водоростей під впливом токсикантів / Булгакова О.С.,  Степашко В.С., Паршикова Т.В., Новікова І.П. // Моделювання та керування станом еколого-економічних систем регіону. Збірник праць, випуск 3. – Київ: МННЦ ІТС, 2008. – С. 30–39.
  2.  Степашко В.С. Гібридні алгоритми самоорганізації моделей для прогнозування складних процесів / Степашко В.С., Булгакова О.С., Зосімов В.В. // Індуктивне моделювання складних систем. Збірник праць, випуск 2. – Київ: МННЦ ІТС, 2010. - С. 236-246.
  3.  Зосимов В.В. Проектирование программного модуля для исследования работы алгоритмов поисковых систем / Зосимов В.В., Булгакова А.С. // Проблеми Моделювання. Збірник наукових праць. Випуск 56. – Київ: Інститут проблем моделювання в енергетиці, 2010. - С. 112-118.
  4.  Булгакова О.С. Порівняльний аналіз ефективності ітераційних алгоритмів МГУА за допомогою обчислювальних експериментів. / Булгакова О.С., Степашко В.С. // Вісник ЧДТУ. – №1. – Черкаси: Вид-во ЧДТУ, 2011. – С. 41-44.
  5.  Bulgakova Oleksandra. Comparing NN and GMDH methods for prediction of socio-economic processes / Bulgakova Oleksandra, Samoylenko Oleksandr // – Proceedings of the II International Workshop on Inductive Modelling IWIM-2007, 19-23 September 2007, Prague, Czech Republic. – Prague: Czech Technical University, 2007. – P. 217-220. – ISBN 978-80-01-03881-9.
  6.  Булгакова О.С. Моделювання впливу токсиканта біхромат калію на життєдіяльність клітин зелених водоростей з використанням інтелектуальних обчислень / Булгакова О.С., Степашко В.С.,  Паршикова Т.В., Новикова І.П.  //  Матеріали міжнародної конференції „Інтелектуальні системи прийняття рішень та проблеми обчислювального інтелекту”, Євпаторія, 19-23 травня 2008 р.: в 3-х т. – Херсон: Вид-во ХНТУ, 2008. – Том 3, Частина 1. – С. 64-67.
  7.  Bulgakova O. GMDH and Neural Network Application for Modelling Vital Functions of Green Algae under Toxic Impact / Bulgakova O., Stepashko V., Parshikova T, and Novikova I. // Proceedings of the II International Conference on Inductive Modelling ICIM-2008, 15-19 September 2008, Kyiv, Ukraine. – Kyiv: IRTC ITS NANU, 2008. – P. 281-285.
  8.  Bulgakova O. Compare GMDH and FAKE GAME Methods on Artificial Data Set for Investigation of Their Properties / O. Bulgakova, P. Kordik. // Матеріали міжнародної конференції „Інтелектуальні системи прийняття рішень та проблеми обчислювального інтелекту”, Євпаторія, 18-22 травня 2009 р.: в 3-х т. – Херсон: Вид-во ХНТУ, 2009. – Том 2. – С. 157-160.
  9.  Bulgakova O. Methods of true data mining model selection – with experimental results / Oleksandra Bulgakova, Pavel Kordik //  Proceedings of 3rd International Workshop on Inductive Modelling IWIM-2009, 14-19 September 2009, Krynica, Poland. – Prague: Czech Technical University, 2009. – P. 23-27.
  10.  Stepashko V. Modified multilayered GMDH algorithm with combinatorial optimization of partial descriptions complexity / Volodymyr Stepashko, Oleksandra Bulgakova, Viacheslav Zosimov // Proceedings of 3rd International Conference on Inductive Modelling ICIM-2010, 16-19 May 2010, Yevpatoria, Ukraine. – Kherson: KNTU, 2010. – P. 24-30.

АнотаціЯ

Булгакова О.С. Узагальнений ітераційний алгоритм індуктивного моделювання з застосуванням мережевих технологій. – Рукопис.

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

Дисертаційна робота присвячена підвищенню ефективності алгоритмів МГУА в задачах моделювання складних систем на основі гібридизації алгоритмів ітераційного і комбінаторного типів та застосування онлайн-технологій.

Вперше розроблено архітектуру узагальненого ітераційного алгоритму МГУА для побудови моделей складних систем у класі поліномів.

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

Реалізована комп’ютерна онлайн-технологія для автоматизованого розв’язання задач моделювання на основі узагальненого алгоритму МГУА дозволяє виконувати розрахунки через Інтернет в автоматичному та інтерактивному режимах.

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

Ключові слова: вибірка даних, індуктивне моделювання, МГУА, ітераційні алгоритми, гібридний алгоритм.

АННОТАЦИЯ

Булгакова О.С. Обобщенный итерационный алгоритм индуктивного моделирования с применением сетевых технологий. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 – информационные технологии. – Международный научно-учебный центр информационных технологий и систем НАН и МОН Украины, Киев, 2011.

Диссертационная работа посвящена повышению эффективности алгоритмов МГУА в задачах моделирования сложных систем на основе гибридизации итерационного и комбинаторного алгоритмов и применения онлайн-технологий.

Впервые разработана архитектура обобщенного итерационного алгоритма МГУА для построения моделей сложных систем в классе полиномов.

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

Реализованная компьютерная онлайн-технология для автоматизированного решения задач моделирования на основе обобщенного алгоритма МГУА позволяет выполнять расчеты через Интернет в автоматическом и интерактивном режимах.

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

Ключевые слова: выборка данных, математическая модель, индуктивное моделирование, МГУА, итерационный алгоритм, гибридный алгоритм.

ABSTRACT

Bulgakova O.S. Generalized iterative algorithm of inductive modeling with the use of network technologies. – Manuscript.

Thesis for a candidate degree in technical sciences by specialty 05.13.06 – information technologies. – International Research and Training Centre for Information Technologies and Systems of NAS and MES of Ukraine, Kyiv, 2011.

The thesis is devoted to enhancing the GMDH algorithms effectiveness in complex systems modeling tasks based on hybridization of iterative and combinatorial schemes and use of on-line technologies.

Architecture of generalized iterative GMDH algorithm is newly developed for building of complex system models in the polynomial class.

A technique is proposed for numerical analysis of iterative algorithms efficiency. Computing experiments with new algorithm was carried out and both efficiency and convergence was shown for the algorithm by structure and parameters to a true model

Implemented computational online-technology for automated solving the modeling tasks on the basis of the generalized GMDH algorithm makes it possible to carry out Internet-computations in automatic and interactive modes.

Solution results are given for tree applied modeling problems: impact of toxic bichromate potassium on the vital functions of green algae cells; impact of pollutions in Sevastopol bays on the total number of bottom-living organisms; modeling the Ukraine GDP as dependent from investment indicators.

Keywords: data sample, mathematical model, inductive modeling, GMDH, iteration algorithm, hybrid algorithm.


 

А также другие работы, которые могут Вас заинтересовать

69809. НАРОДЫ СИБИРИ НАКАНУНЕ ПРИСОЕДИНЕНИЯ К РУССКОМУ ГОСУДАРСТВУ. XIII - XVI вв 454.5 KB
  Так пророчески вдохновенно писал о Сибири во второй половине XVIII в. На юге Западной Сибири жили тюркские племена: енисейские киргизы томские чулымские кузнецкие татары предки шорцев алтайцев хакасов.Социальнохозяйственное развитие народов Сибири определялось прежде всего природными условиями.
69811. Национальный и конфессиональный состав населения России и ближнего зарубежья 39 KB
  На территории РФ проживают следующие языковые семьи: Индоевропейская: 129 млн.:1. Славянская (русские, украинцы, белорусы, поляки), Иранская (осетины), Германская (немцы), Романская (молдаване, румыны) группы. Алтайская семья: 11,9 млн.: Тюркская (татары, чуваши, башкиры, казахи, алтайцы, шорцы)...
69812. Национальная политика XIX (конец) - XX (начало). Русификаторская политика царизма XIX (конец) - XX (начало) 57.5 KB
  XIX век (вторая половина): Формально российское законодательство не знало правовых ограничений по национальному признаку. В законах были ограничены евреи (в некоторых правах, независимо от вероисповедания), с 1864 года поляки-католики.
69813. Национальная политика большевиков 29.5 KB
  Что общность не является нацией про которое во многом бытует и до настоящего времени и пришел к однозначному выводу о необходимости областной автономии в России для Польши Финляндии Украины Литвы Кавказа. Он стоял за создание как можно более крупных независимых государственных объединений...
69814. Национальная политика СССР (1964-1985) 25.5 KB
  Брежнев заявил что общество в СССР является развитым и однородным социалистическим обществом. На юбилее пятидесятилетия СССР в 1972 году Брежнев заявил что национальный вопрос в СССР окончательно решен.
69817. Национальный вопрос в программах и деятельности Большевиков и Эсеров 30.5 KB
  В Декрете о мире подчёркнуто право наций на самоопределение которое распространяется не только на народы воюющих государств но и на колонии и полуколонии. На Укр 7 ноя 1917 г издаётся третий универсал: создание Украинской нар республики в рамках России воспользовались...