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

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2013
Hauptverfasser:	Порплиця, Н.П., Дивак, М.П.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2013
Schriftenreihe:	Індуктивне моделювання складних систем
Schlagworte:	Наукові статті
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/83679
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії / Н.П. Порплиця, М.П. Дивак // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 256-269. — Бібліогр.: 15 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-83679
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-836792025-02-09T11:30:48Z Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії Порплиця, Н.П. Дивак, М.П. Наукові статті У статті розглянуто актуальну задачу структурної ідентифікації математичної моделі об’єкту з розподіленими параметрами у вигляді різницевого оператора. Показано, що зазначена задача є задачею дискретної оптимізації. Запропоновано підхід до синтезу моделі у вигляді інтервального різницевого оператора, що ґрунтується на принципах роєвого інтелекту, який притаманний бджолиній колонії. This paper deals with the actual problem of structure identification of mathematical model distributed parameters object in the form of difference operator, it is shown that these problem are discrete optimization problem; an approach to the synthesis of the model in the form of interval difference operator was proposed. The approach based on the principles of swarm intelligence that is inherent for bee colony. В статье рассмотрена актуальная задача структурной идентификации математической модели объекта с распределенными параметрами в виде разностного оператора; показано, что указанная задача является задачей дискретной оптимизации; предложен подход к синтезу модели в виде интервального разностного оператора, основанный на принципах роевого интеллекта, который присущ пчелиной колонии. 2013 Article Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії / Н.П. Порплиця, М.П. Дивак // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 256-269. — Бібліогр.: 15 назв. — укр. XXXX-0044 https://nasplib.isofts.kiev.ua/handle/123456789/83679 519.876.5 uk Індуктивне моделювання складних систем application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Наукові статті Наукові статті
spellingShingle	Наукові статті Наукові статті Порплиця, Н.П. Дивак, М.П. Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії Індуктивне моделювання складних систем
description	У статті розглянуто актуальну задачу структурної ідентифікації математичної моделі об’єкту з розподіленими параметрами у вигляді різницевого оператора. Показано, що зазначена задача є задачею дискретної оптимізації. Запропоновано підхід до синтезу моделі у вигляді інтервального різницевого оператора, що ґрунтується на принципах роєвого інтелекту, який притаманний бджолиній колонії.
format	Article
author	Порплиця, Н.П. Дивак, М.П.
author_facet	Порплиця, Н.П. Дивак, М.П.
author_sort	Порплиця, Н.П.
title	Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії
title_short	Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії
title_full	Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії
title_fullStr	Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії
title_full_unstemmed	Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії
title_sort	синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate	2013
topic_facet	Наукові статті
url	https://nasplib.isofts.kiev.ua/handle/123456789/83679
citation_txt	Синтез структури інтервального різницевого оператора з використанням алгоритму бджолиної колонії / Н.П. Порплиця, М.П. Дивак // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2013. — Вип. 5. — С. 256-269. — Бібліогр.: 15 назв. — укр.
series	Індуктивне моделювання складних систем
work_keys_str_mv	AT porplicânp sintezstrukturiíntervalʹnogoríznicevogooperatorazvikoristannâmalgoritmubdžolinoíkoloníí AT divakmp sintezstrukturiíntervalʹnogoríznicevogooperatorazvikoristannâmalgoritmubdžolinoíkoloníí
first_indexed	2025-11-25T21:34:39Z
last_indexed	2025-11-25T21:34:39Z
_version_	1849799722428006400
fulltext	Синтез структури інтервального різницевого оператора УДК 519.876.5 СИНТЕЗ СТРУКТУРИ ІНТЕРВАЛЬНОГО РІЗНИЦЕВОГО ОПЕРАТОРА З ВИКОРИСТАННЯМ АЛГОРИТМУ БДЖОЛИНОЇ КОЛОНІЇ Н.П. Порплиця, М.П. Дивак Тернопільський національний економічний університет ocheretnyuk.n@gmail.com,2mdy@tneu.edu.ua У статті розглянуто актуальну задачу структурної ідентифікації математичної моделі об’єкту з розподіленими параметрами у вигляді різницевого оператора. Показано, що зазначена задача є задачею дискретної оптимізації. Запропоновано підхід до синтезу моделі у вигляді інтервального різницевого оператора, що ґрунтується на принципах роєвого інтелекту, який притаманний бджолиній колонії. Ключові слова: аналіз інтервальних даних, інтервальний різницевий оператор, структурна ідентифікація, алгоритм бджолиної колонії. This paper deals with the actual problem of structure identification of mathematical model distributed parameters object in the form of difference operator, it is shown that these problem are discrete optimization problem; an approach to the synthesis of the model in the form of interval difference operator was proposed. The approach based on the principles of swarm intelligence that is inherent for bee colony. Keywords: analysis of interval data, interval difference operator, structure identification, artificial bee colony algorithm. В статье рассмотрена актуальная задача структурной идентификации математической модели объекта с распределенными параметрами в виде разностного оператора; показано, что указанная задача является задачей дискретной оптимизации; предложен подход к синтезу модели в виде интервального разностного оператора, основанный на принципах роевого интеллекта, который присущ пчелиной колонии. Ключевые слова: анализ интервальных данных, интервальный разностный оператор, структурная идентификация, алгоритм пчелиной колонии. Вступ У теорії систем одними із найскладніших об’єктів моделювання є об’єкти з розподіленими параметрами. До зазначеного класу об’єктів відносять моделі процесів тепло- та масоперенесення, зокрема модель процесу сушіння гіпсокартону [1] чи поширення забруднень шкідливих викидів автотранспорту в атмосфері [2]. Математичною основою для моделювання об’єктів з розподіленими параметрами слугують диференціальні рівняння в частинних похідних або їх дискретні аналоги у вигляді різницевих операторів. Переважно для побудови таких моделей використовують дедуктивний підхід, коли, виходячи з фізичних міркувань, визначають загальний вигляд диференціального рівняння, потім його дискретизують і розв’язують методом скінченних різниць. Такий підхід вимагає детального вивчення фізики процесу, Індуктивне моделювання складних систем, випуск 5, 2013 256 Порплиця Н.П., Дивак М.П. визначення коефіцієнтів дифузії чи тепло- та масоперенесення, що суттєвим чином ускладнює задачу математичного моделювання. На противагу дедуктивному підходу застосовують методи індуктивного моделювання [1-6]. У цьому випадку математичну модель процесу синтезують у вигляді різницевої схеми (різницевого оператора) в процесі аналізу даних експерименту. Варто зазначити, що задача теоретичного чи формального обґрунтування загального вигляду математичної моделі є задачею структурної ідентифікації [7]. Зазначена задача суттєво ускладнюється, коли результати експерименту представляють в інтервальному вигляді, тобто допускають, що можливі значення модельованої характеристики гарантовано належать до експериментально встановленого числового інтервалу. Розв’язуванню задачі структурної ідентифікації математичної моделі у вигляді різницевого оператора на основі інтервальних даних присвячено ряд публікацій [2, 3]. Однак наведені авторами цих статей підходи ґрунтуються на генетичних алгоритмах, які, як відомо, є евристичними, вимагають налаштування цілого ряду параметрів, але малоефективні, коли недостатньо вивчена фізика процесу. Іншим недоліком зазначених алгоритмів є необхідність використання нестандартних операторів схрещування (кросоверів) та операторів мутації. У цілому практика застосування зазначених алгоритмів показала, що з їх допомогою важко «обходити» локальні мінімуми складної цільової функції задачі дискретної оптимізації, якою є задача структурної ідентифікації. Останнім часом для розв’язування задач дискретної оптимізації застосовують методи та алгоритми, які ґрунтуються на основі децентралізації та самоорганізації мультиагентних систем. До таких алгоритмів відносять алгоритми бджолиної колонії (АБК), які базуються на принципах роєвого інтелекту. Тому метою даної праці є розробка методу структурної ідентифікації інтервального різницевого оператора із застосуванням принципів роєвого інтелекту та порівняння його ефективності з відомими методами та алгоритмами їх реалізації. 1. Постановка задачі Розглянемо задачу структурної ідентифікації лінійного різницевого оператора (РО) у такому загальному вигляді: ,...,,...,,,...,( 0,0,1,00,0,0,10,1,0,00,0,0,0,,, −−−= jih T khji vvvvfv r ,),...,, ,,,0,,,1,1,1,1 guuv khjihjikhji rrr ⋅−−−− Ii ,...,1= , Jj ,...,1= , Hh ,...,1= , Kk ,...,1= , (1) Індуктивне моделювання складних систем, випуск 5, 2013 257 Синтез структури інтервального різницевого оператора де )(•Tf r - вектор невідомих базисних функцій, що визначає структуру різницевого оператора; – модельована характеристика у точці з дискретно заданими просторовими координатами khjiv ,,, Ii ,...,1= , Jj ,...,1= , Hh ,...,1= та на часовій дискреті Kk ,...,1= ; khjihji uu ,,,0,,, ,..., rr - вектори вхідних змінних (управлінь); gr – вектор невідомих параметрів різницевого оператора. Слід зазначити, що загальний вигляд РО (1) отримуватимемо на основі аналізу експериментальних даних, які представлено в інтервальному вигляді та отримано для обмеженої кількості часових дискрет за умов різних значень чинників впливу. При цьому вектор оцінок g )r параметрів gr та вектор базисних функцій у різницевому операторі (1) отримуватимемо із умов забезпечення заданої точності моделі: )(•Tf r ];[][ ,,,,,,,,, +−∈ khjikhjikhji zzv) , Ii ,...,1= , Jj ,...,1= , Hh ,...,1= , (2) Kk ,...,1= де ]- інтервал можливих значень модельованої характеристики в точці з дискретними координатами i,j,h в k-тий момент часу. ;[ ,,,,,, +− khjikhji zz У виразі (2) ][ ,,, khjiv) означає інтервальні оцінки прогнозованої характеристики, які обчислюватимемо на основі такого різницевого оператора: ],...,[],...,[],...,([];[][ 0,0,1,00,0,0,10,0,0,0,,,,,,,,, −− +− == ji T khjikhjikhji vvvfvvv )))r))) ,),...,],[ ,,,0,,,1,1,1,1 guuv khjihjikhji )rrr) ⋅−−−− (3) Ii ,...,1= , Jj ,...,1= , Hh ,...,1= Kk ,...,1= . Взявши до уваги те, що всі обчислення у різницевому операторі (3) необхідно проводити із застосуванням правил інтервальної арифметики, РО (3) будемо називати інтервальним різницевим оператором (ІРО) [8]. Складність задачі налаштування ІРО (3) полягає в тому, що невідомими є не лише параметри, а і його загальний вигляд, тобто структура. Для початку введемо ряд позначень, які необхідні для розкриття суті формальної постановки задачі. Позначимо за sλ поточну структуру ІРО: Λ⊂⋅•⋅•⋅•= })(;;)(;)({ 2211 s I s I ssss s ss gfgfgf ) K ))λ (4) де набір структурних елементів, що задає поточну Ffff s I ss s ⊂••• )}(;);();({ 21 K s -ту структуру ІРО. Індуктивне моделювання складних систем, випуск 5, 2013 258 Порплиця Н.П., Дивак М.П. Далі введемо наступні умовні позначення: ];[ maxmin III s ∈ – кількість елементів у поточній структурі sλ ; F – множина усіх структурних елементів, )},(;);,(;);,({ ,,,,,,,,,,,,,,,,,,1 khjikhjiLkhjikhjilkhjikhji uvfuvfuvfF rr K rr K rr = , де LF = (потужність множини F); sg )r – вектор відомих значень параметрів, оцінений для поточної структури ІРО на основі методів параметричної ідентифікації, які ґрунтуються на процедурах випадкового пошуку [1]; – множина усіх можливих структур ІРО. Λ Задача структурної ідентифікації полягає у пошуку структури sλ ІРО у вигляді (3), що задовольняє умови (2), що забезпечують належність інтервальних оцінок прогнозованого значення модельованої характеристики до інтервалів допустимих значень модельованої характеристики на множині усіх дискрет. Варто зазначити, що параметрична ідентифікація в даному випадку є етапом структурної ідентифікації. Як відомо, у випадку, коли дані задано в інтервальному вигляді, цей етап полягає у формуванні деякого вектора базисних функцій (поточної структури sλ ІРО) і знаходженні оцінок параметрів ІРО шляхом розв’язування інтервальної системи нелінійних алгебричних рівнянь (ІСНАР) [2]. Якість поточної структури ІРО оцінюватимемо за значенням показника )( sλδ , який кількісно визначає наближеність поточної структури до задовільної в сенсі забезпечення умов (2). Значення показника )( sλδ обчислюватимемо за допомогою виразів, отриманих у праці [9]: ,],[],[],...,([({max)( 0,0,0,10,1,0,00,0,0,0 ,...,1,,...,1,,...,1,,...,1 K )))r −− ==== = ih Ts KkHhJjIi s vvvfmidλδ )),...,],[],...,[ ,,,0,,,1,1,1,10,0,1,1 s khjihjikhjij guuvv )rrr)) ⋅−−−−− – }])([ ,,, khjizmid , (5) якщо ∩][ ,,, khjiv) ∅=][ ,,, khjiz ∃ Ii ,...,1= , ∃ Jj ,...,1= , ∃ Hh ,...,1= , ∃ Kk ,...,1= ; ],...,[],[],...,([({max)( 0,0,0,10,1,0,00,0,0,0 ,...,1,,...,1,,...,1,,...,1 −− ==== = ih Ts KkHhJjIi s vvvfwid )))r λδ )),...,],[],...,[ ,,,0,,,1,1,1,10,0,1,1 s khjihjikhjij guuvv )rrr)) ⋅−−−−− ],...[],[],...,([(( 0,0,0,10,1,0,00,0,0,0 −−− ih Ts vvvfwid )))r (6) )),...,],[],...,[ ,,,0,,,1,1,1,10,0,1,1 s khjihjikhjij guuvv )rrr)) ⋅−−−−− ])}[) ,,, khjiz∩ , якщо ∩][ ,,, khjiv) ∅≠][ ,,, khjiz ∀ Ii ,...,1= , ∀ Jj ,...,1= , ∀ Hh ,...,1= , ∀ Kk ,...,1= ; де - операції визначення центру та ширини інтервалів, відповідно. ( ) ( )•• widmid , Індуктивне моделювання складних систем, випуск 5, 2013 259 Синтез структури інтервального різницевого оператора Вираз (5) описує «наближеність» поточної структури до задовільної на початкових ітераціях, тим часом як вираз (6) у випадку )( sλδ =0 забезпечує виконання умови (2). Тепер задачу структурної ідентифікації ІРО запишемо формально у вигляді задачі знаходження мінімуму функції )( sλδ : ( ) ];[min,)( maxmin , III s fg s ss ∈⎯⎯⎯ →⎯ • r)r λδ , ( ) Ff s ∈• r (7) Чим менше значення )( sλδ , тим «краща» поточна структура ІРО. Якщо 0)( =sλδ , то поточна структура ІРО дає можливість побудувати адекватну модель, для якої інтервальні оцінки прогнозованої характеристики належать до інтервалів можливих значень модельованої характеристики. 2. Основні засади алгоритму бджолиної колонії та його біологічне підґрунтя Як видно із вищесказаного, основною науковою задачею є синтез структури ІРО на основі аналізу даних, представлених в інтервальному вигляді. Зазначена задача (7) – задача дискретної оптимізації, а алгоритми її розв’язування є NP-складними. Для розв’язання задачі структурної ідентифікації у даній праці запропоновано використати АБК [10]. АБК – це метаеврестичний алгоритм, що ґрунтується на принципах роєвого інтелекту. Вперше, основні засади АБК (Artificial Bee Colony algorithm) були сформульовані турецьким вченим Д. Карабога у 2005 році для розв’язку задачі оптимізації із складними цільовими функціями багатьох змінних [10]. Основна ідея АБК полягає у моделюванні поведінки колонії медоносних бджіл у процесі пошуку нектару. У пошуках їжі в залежності від рельєфу місцевості медоносна бджола може долати відстань до 14 км. У бджолиній колонії кожній бджолі відведена своя роль: одні будують воскові стільники, збирають нектар, переробляють його у мед, а пилок в пергу, інші годують матку, охороняють гніздо, регулюють процес природного роїння тощо. Однак пошуками їжі у сім’ї медоносних бджіл займаються лише «дорослі» робочі бджоли (найчастіше починаючи із 15–18- денного віку) [11]. У живій природі із вулика спочатку вилітає у випадковому напрямку певна кількість бджіл-розвідників для пошуку нових джерел нектару. Знайшовши «якісне» джерело їжі, бджоли повинні зафіксувати своє місцезнаходження стосовно вулика та подолати зворотній шлях. У вулику ці бджоли за допомогою так званих «бджолиних танців» [11] повідомляють решті про напрямок та відстань до джерела їжі, а також про кількість знайденого нектару. Варто зазначити, що у вулику бджоли «танцюють» лише в тому випадку, якщо виявлене ними джерело їжі відрізняється високими ціннісними якостями, в протилежному ж бджола обирає одну з двох альтернатив: Індуктивне моделювання складних систем, випуск 5, 2013 260 Порплиця Н.П., Дивак М.П. залишитися у вулику та чекати на інформацію від інших особин чи продовжити випадковий пошук джерел нектару в якості бджоли-розвідника. Бджоли визначають цінність джерел нектару за відстанню від вулика і за якістю їжі в порівнянні з їжею з інших джерел. Чим далі знаходиться їжа від вулика, тим солодшою вона повинна бути, щоб змусити бджолу ділитися інформацією, тобто «танцювати», таким чином мобілізуючи інших особин для пошуку їжі у певному напрямку. Після «бджолиного танцю» в окіл кращих джерел їжі відправляються бджоли із вулика, при чому чим якісніше джерело їжі, тим більше туди летить бджіл [11]. Важливо зазначити, що мобілізовані бджоли на основі інформації отриманої, із «танцю», дістаються саме в окіл джерела їжі (точку, віддалену від знайденого джерела нектару в радіусі 5-6 метрів), а далі бджоли переходять на інший спосіб пошуку – за кольором та запахом, про що свідчать результати експериментів, описані у статті [12]. Ділянки, на яких джерело нектару вичерпалося, медоносні бджоли покидають. Бджоли-розвідники знову відлітають для пошуку нових джерел їжі, після чого процес повторюється. Для реалізації АБК усіх бджіл колонії, котрі займаються пошуком джерел їжі, умовно поділяють на три типи [13]: робочі бджоли (проводять пошук їжі в околі уже відомих джерел нектару та інформують бджіл-дослідників про якість досліджуваних джерел нектару); бджоли-дослідники (знаходяться у вулику, де отримують інформацію від робочих бджіл, після чого відправляються на пошуки нектару в окіл знайдених робочими бджолами джерел нектару); бджоли-розвідники (здійснюють випадковий пошук нових джерел нектару). Загальна схема АБК формулюється наступним чином [13]: Крок 1. Ініціалізація. Крок 2. Фаза активності робочих бджіл. Крок 3. Фаза активності бджіл-дослідників. Крок 4. Фаза активності бджіл-розвідників. Крок 5. Запам’ятовування кращого джерела нектару. Повернення на крок 2 поки не буде досягнуто критерію зупинки. Важливо зазначити, що у класичному формулюванні АБК [13] вхідними параметрами алгоритму є: кількість джерел нектару, що дорівнює кількості робочих бджіл S, максимальна кількість ітерацій алгоритму MCN, «критерій вичерпаності» [13] LIMIT (задає максимальну можливу кількість ітерацій «незмінності» координат джерела нектару, тобто якщо координати джерела нектару незмінні уже LIMIT разів, то таке джерело нектару вважається вичерпаним). Крім того, розподіл типів бджіл у популяції відбувається наступним чином [13]: робочі бджоли – 50% популяції; бджоли-дослідники – 50% популяції. 3. Теоретичні основи застосування принципів роєвого інтелекту до задачі структурної ідентифікації ІРО У контексті задачі структурної ідентифікації ІРО поведінка бджоли при виборі місцезнаходження джерела нектару безпосередньо реалізує сам Індуктивне моделювання складних систем, випуск 5, 2013 261 Синтез структури інтервального різницевого оператора алгоритм синтезу поточної структури ІРО; область пошуку нектару – множина допустимих розв’язків задачі структурної ідентифікації ІРО, тобто множина усіх можливих структур ІРО із відомими оцінками компонентів вектора параметрів g )r ; окіл джерела нектару – множина структур ІРО, що можуть бути згенеровані на основі поточної структури ІРО шляхом часткової заміни її структурних елементів; координати джерела нектару – поточна структура ІРО; якість джерела нектару представляється обчисленим значенням функції ( s )λδ , що задає точність моделі, побудованої на основі поточної структури. Згідно з виразом (7), для розв’язування задачі структурної ідентифікації за допомогою АБК до вхідних параметрів додаються: множина структурних елементів F з потужністю L; значення меж інтервалу , що задають відповідно мінімальну та максимальну кількість структурних елементів у поточній структурі ІРО ];[ maxmin II sλ . Множина структурних елементів F повинна гарантовано включати всі елементи оптимальної структури ІРО, тому базисні функції та порядок ІРО задаються дослідником емпірично, виходячи з природи розв’язуваної задачі. Припущення щодо наявності у множині F структурних елементів, які формуватимуть шукану структуру хоча і є досить жорстким, проте у випадку його виконання забезпечується збіжність алгоритму. Варто зазначити, що у випадку малої потужності L множини структурних елементів часто неможливо отримати оптимальну структуру оλ ІРО. Однак суттєве збільшення потужності L множини структурних елементів підвищить обчислювальну складність розв’язування задачі структурної ідентифікації. Розв’язком задачі структурної ідентифікації є конкретна структура ІРО sλ із відомим вектором параметрів sgr . Рис. 1. Простір пошуку розв’язків задачі структурної ідентифікації ІРО для L=3 Індуктивне моделювання складних систем, випуск 5, 2013 262 Порплиця Н.П., Дивак М.П. На Рис. 1 показано приклад простору пошуку розв’язків для трьохвимірного випадку, де множина структурних елементів F складається лише з трьох елементів { )(),(),( 321 }••• fff , а поточна структура ІРО являє собою точку із координатами, що задають оцінене значення параметра для кожного структурного елемента із простору пошуку розв’язків. Наприклад, структура 3λ , яка зображена на Рис. 1 матиме вигляд: )},();();({ 3 3 32 3 21 3 13 •⋅•⋅•⋅= fgfgfg )))λ тобто якщо відома структура 3λ , то однозначно можемо записати вигляд різницевого оператора: ).()()( 3 3 32 3 21 3 1,,, •⋅+•⋅+•⋅= fgfgfgv khji ))) 3. Метод та алгоритм структурної ідентифікації ІРО на основі АБК У контексті задачі структурної ідентифікації фаза ініціалізації АБК означає: Крок 1. Ініціалізація. Дослідником задаються значення вхідних параметрів алгоритму: MCN, LIMIT, S, та множина структурних елементів F. Далі відбувається формування випадковим чином множини структур ІРО потужності S, де кожна структура ІРО задає координати джерела нектару. Ініціалізація лічильника ітерацій алгоритму mcn=0. Для кожної із сформованих структур обчислюється значення показника якості ];[ maxmin II mcnΛ ( )sλδ та ініціалізація лічильника «критерію вичерпаності» limits=0, де mcns Λ∈λ , .1 Ss K= Якщо знайдено хоча б одну структуру, для якої ( ) 0=sλδ , то переходимо на крок «STOP». Фаза активності робочих бджіл означає наступне: Крок 2. Синтез поточних структур ІРО: ),,(1 FnP smcnmcn Λ=Λ + , (8) де оператор означає перетворення множини структур ),,( FnP smcnΛ mcnΛ , згенерованих на ітерації алгоритму , у множину структур ІРО mcn 1+Λmcn способом заміни випадковим чином елементів кожної структури елементами із множини структурних елементів F. Кількість елементів, що потрібно замінити, обчислюємо за формулою (9): sn Індуктивне моделювання складних систем, випуск 5, 2013 263 Синтез структури інтервального різницевого оператора ( ) ( ) ( ){ }( ) ( ) ( ) ( ){ } ( ) ({ )} ⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ + − −⋅− = 1 ,,min,,max 2,,minint 11 max 1 SS sSs s In λδλδλδλδ λδλδλδ KK K , (9) де Ss K1= ; – кількість елементів у структурі із найбільшим значенням max sI ( )sλδ . Варто зазначити, що Smcnmcn =Λ=Λ +1 . Із формули (9) випливає наступна залежність: чим нижча «якість» структури ІРО, тим більшу кількість її структурних елементів потрібно замінити. Крок 3. Попарна селекція структур ІРО та формування множини найкращих структур з елементів: ⎩ ⎨ ⎧ ′>′ ′≤ = )),()((, )),()((, sss sss s IF IF λδλδλ λδλδλ λ (10) де mcns Λ∈λ , 1+Λ∈′ mcnsλ , .1 Ss K= Крім того, інкрементуємо лічильник mcn=mcn+1; у випадку виконання умови )()( ss λδλδ ′≤ інкрементуємо лічильник: Limits=Limits+1 , де Ss K1= ; а у випадку виконання умови )()( ss λδλδ ′> обнуляємо значення лічильника . 0=sLimit Якщо знайдено хоча б одну, структуру для якої ( ) 0=sλδ , то переходимо на крок «STOP». Фаза активності бджіл-дослідників означає наступне: Крок 4. Синтез множини поточних структур ІРО з урахуванням «якості» структур: ),,,,(1 ssmcnmcn RFnP Λ=Λ + δ (11) де оператор означає перетворення множини структур , згенерованих на ітерації алгоритму , у множину структур ІРО способом заміни випадковим чином елементів, елементами із множини структурних елементів F, однак лише для тих структур ),,,( ssmcn pFnP Λδ mcnΛ mcn 1+Λmcn sn mcns Λ∈λ , для яких . У формулі (11): 0>sR Індуктивне моделювання складних систем, випуск 5, 2013 264 Порплиця Н.П., Дивак М.П. ( ) ( ){ } ( ) ( )( ) ( ) ( ){ } ( ) , ),,(max ,,max2int 1 1 1 11 ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ − − −−⋅⋅ = − = − ∑ sS s sS ssS s RSR λδλδλδ λδλδλδλδ K K (12) де ,01 =R Ss K2= ; – означає кількість структур, які будуть згенеровані на базі sR s -ї структури із множини mcnΛ , де елементи множини упорядковані відповідно до спадання значення показника якості mcnΛ )( sλδ . Такий принцип розподілу структур у групах ґрунтується на припущенні, що кількість бджіл- дослідників, що полетить в окіл джерела нектару, про яке повідомила конкретна робоча бджола, прямо пропорційна якості знайденого нею джерела нектару. Насправді, біологічні механізми, на основі яких бджола-дослідник приймає рішення летіти за тою чи іншою робочою бджолою, досліджені не достатньо, однак вважається, що кількість «завербованих» бджіл-дослідників з математичної точки зору завжди є функцією якості джерела нектару [14]. Варто зазначити, що загальна кількість згенерованих структур – S , де Smcnmcn =Λ=Λ +1 . Це також означає, що для структур sλ із множини mcnΛ , для яких , не буде згенеровано жодної структури у множині . 0=sR 1+Λmcn Крок 5. Погрупова селекція поточних структур ІРО та формування множини найкращих структур з елементів: ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ =Λ′∈∃ ≠∧> =Λ′∈∀ ≠∧≤ = = ,1, )),0())()(((, ,1, )),0())()(((, ),0(, ssr srs s r ssr srss ss s Rr RIF Rr RIF RIF K K λ λδλδλ λ λδλδλ λ λ (13) { },,1 211 SsmcnSs Λ′∪Λ′∪Λ′∪Λ′=Λ= + KKKK де – підмножина структур сформованих на основі sΛ′ sλ структури із множини . Слід зауважити, що якщо для поточної структури mcnΛ sλ : , то 0=sR ∅=Λ′s . Крім того, у випадку виконання умови: або інкрементуємо лічильник Limit 0=sR ))0())()((( ≠∧≤ srs Rλδλδ s=Limits+1 , де Ss K1= ; у випадку ж виконання умови: обнуляємо значення лічильника . ))0())()((( ≠∧> srs Rλδλδ 0=sLimit Індуктивне моделювання складних систем, випуск 5, 2013 265 Синтез структури інтервального різницевого оператора Якщо знайдено хоча б одну структуру, для якої ( ) 0=sλδ , то переходимо на крок «STOP». Фаза активності бджіл-розвідників означає наступне: Крок 6. Перевірка «критерію відмови» (бджоли покидають вичерпані джерела нектару) Якщо = LIMIT, тоді sLimit ),,( maxmin IIFPNs =λ і одночасно: =0, sLimit .1 Ss K= Оператор означає синтез структури ),,( maxmin IIFPN sλ випадковим чином із множини усіх структурних елементів F , де кількість структурних елементів – Для кожної зі сформованих структур ].;[ maxmin III s ∈ sλ обчислюємо значення показника якості ( )sλδ . Якщо знайдено структуру, для якої ( ) 0=sλδ , то переходимо на крок «STOP», в іншому випадку переходимо на крок 2. У класичній інтерпретації АБК крок «STOP» відсутній, проте у реалізації АБК для розв’язку задачі структурної ідентифікації ІРО є необхідним. Крок 7. «STOP». Виведення структури ІРО, для якої показник якості дорівнює нулю. 4. Приклад застосування АБК для моделювання процесу розподілу вологості на поверхні листа гіпсокартону на стадії сушіння Розглянемо процес виробництва листів гіпсокартону стандартних розмірів, де товщина – 9,5мм, довжина – 2500мм та ширина – 1200мм. Відомо, що прилади для вимірювання вологості відзначаються точністю в межах 5% [1]. Тому в процесі ідентифікації моделі необхідним є виконання умови, щоб інтервальні оцінки прогнозованого значення відносної вологості були в межах цієї похибки. Крім того, значення відносної вологості на поверхні листів гіпсокартону для забезпечення виробництва якісної продукції повинні належати інтервалу від 0,6% до 0,9%, а в протилежному випадку продукція бракується. Для реалізації алгоритму бджолиної колоній для структурної ідентифікації моделі розподілу вологості на поверхні листа гіпсокартону на стадії сушіння було згенеровано множину структурних елементів F з потужністю L=188. У результаті отримано таблицю 1 – упорядковану множину структурних елементів. Множина структурних елементів містить поліноміальні функції не вищі другого степеня для різницевого оператора, не вищого другого порядку. Індуктивне моделювання складних систем, випуск 5, 2013 266 Порплиця Н.П., Дивак М.П. Таблиця 1. Множина структурних елементів моделі розподілу вологості на поверхні листа гіпсокартону на стадії сушіння № пп Структурний елемент № пп Структурний елемент № пп Структурний елемент 1 )/( ,10,2,20,1,,1 kkkji uuuuv ⋅⋅⋅− 73 2 ,,1 kjiv − 125 )( 0,20,1,,1,1, uuvv kjikji ⋅⋅⋅ −− 2 )/( ,10,2,20,1,1, kkkji uuuuv ⋅⋅⋅− 74 2 ,1, kjiv − 126 )( 0,20,1,2,,1, uuvv kjikji ⋅⋅⋅ −− … … … … … … 37 kjikji vv ,,1,1, −− ⋅ 81 )/( 0,20,1,,1 uuv kji ⋅− 153 )/( ,2,1,,1 kkkji uuv ⋅− 38 kjikji vv ,2,,1, −− ⋅ 82 )/( 0,20,1,1, uuv kji ⋅− 154 )/( ,2,1,1, kkkji uuv ⋅− … … … … … … 65 kjiv ,,1− 117 )( 0,20,1,,1 uuv kji ⋅⋅− 161 )/( ,2,1,,1,1, kkkjikji uuvv ⋅⋅ −− 66 kjiv ,1, − 118 )( 0,20,1,1, uuv kji ⋅⋅− … … … … … … 188 )/( ,2,1,2,2,1,2 kkkjikji uuvv ⋅⋅ −−−− Вхідні параметри алгоритму задаємо наступним чином: MCN=100, Limit=4, S=10, =[4; 10]. Далі, згідно з алгоритмом структурної ідентифікації, на основі таблиці 1 випадковим чином згенеровано початкову множину структур ІРО та для кожної з них обчислено значення показника якості ];[ maxmin II mcnΛ ( s )λδ . У процесі досліджень на другій ітерації алгоритму бджолиної колонії для структурної ідентифікації макромоделі процесу розподілу вологості на листі гіпсокартону на стадії сушіння отримано ІРО у вигляді: +⋅⋅⋅+= + − − − + − − − +− ];[];[)/(];[ ,,1,,1,1,,1,20,20,11,,,, kjikjikjikjikjikji vvvvguugvv )))))))) (14) ],;[];[];[];[ ,1,1,1,1,1,2,1,24,2,2,2,2,1,,1,3 + −− − −− + −− − −− + −− − −− + − − − ⋅⋅+⋅⋅ kjikjikjikjikjikjikjikji vvvvgvvvvg )))))))))) де =⊂⋅⋅⋅= + = − = + = − = +− ];[];[)/(];[ 0,,0,,0,,0,,,10,2,20,1,,,, kjikjikjikjikkkjikji zzvvuuuuvv )))) ]01,0;01,0[ 0,,0,,0,,0,, ⋅+⋅− ==== kjikjikjikji zzzz , {i=0, j=0,…,7} {i=0,…,3, j=0,…,1} – задані початкові умови; ∨ де 1g) = 0.57; 2g) =0.0017; 3g) =-0.15; 4g) = -0.4 – оцінки значень параметрів ІРО; - температури у сушильній камері при заданих для тестового набору даних та при прогнозуванні для kuu ,10,1 , k -го її значення відповідно; швидкості переміщення листа у сушильній камері при заданих для тестового набору даних та при прогнозуванні для kuu ,20,2 , - k -го її значення відповідно. Слід зазначити, що в отриманій моделі відсутні співвідношення між швидкістю переміщення листа та температурою у сушильній камері для їх k -х значень при прогнозуванні, на відміну від моделі, отриманої у праці [1], а для Індуктивне моделювання складних систем, випуск 5, 2013 267 Синтез структури інтервального різницевого оператора забезпечення працездатності моделі достатньо задати ці співвідношення як початкові умови, що суттєвим чином спрощує структуру моделі. Як витікає з виразів (5) та (6) найскладнішою процедурою в алгоритмі структурної ідентифікації є процедура обчислення показника якості структури ( s )λδ . У праці [15] висвітлено результати досліджень, які показують, що ефективність алгоритмів структурної ідентифікації можна визначити за кількістю обчислень значень показника ( )sλδ , який визначає цільову функцію у задачі структурної ідентифікації у виразі (7). У праці проведено порівняльний аналіз часової складності відомого методу, що ґрунтується на генетичному алгоритмі (ГА), та методу структурної ідентифікації ІРО на основі АБК. У результаті аналізу встановлено, що значення показника часової складності алгоритму структурної ідентифікації ІРО на основі АБК на 36% менше, ніж на основі ГА. У подальшому доцільно дослідити вплив кількості генерованих структур на поточній ітерації на обчислювальну складність запропонованого методу та на його збіжність. 5. Висновки Розглянуто задачу структурної ідентифікації інтервального різницевого оператора як моделі об’єкту з розподіленими параметрами. Показано, що зазначена задача – задача дискретної оптимізації, а алгоритм її розв’язування є NP-повним. Для розв’язування задачі запропоновано використовувати алгоритм бджолиної колонії. Встановлено основні аналогії функціонування бджолиної колонії стосовно алгоритму розв’язування задачі структурної ідентифікації ІРО та розроблено теоретичні основи застосування принципів роєвого інтелекту для розв’язування задачі структурної ідентифікації ІРО і на цій основі побудовано метод та алгоритм структурної ідентифікації. Література 1. Дивак Т. М. Параметрична ідентифікація інтервального різницевого оператора на прикладі макромоделі розподілу вологості у листі гіпсокартону в процесі його сушіння / Т. М. Дивак // Інформаційні технології та комп`ютерна інженерія : міжнар. наук.–техн. журнал. – 2012. – Вип. 3. – С. 79–85. 2. Войтюк І. Ф., Метод та генетичний алгоритм структурної ідентифікації інтервальних різницевих операторів в задачах екологічного моніторингу / І. Ф. Войтюк, М. П. Дивак, В. М. Неміш// Збірник наукових праць Донецького національного технічного університету серії „Інформатика, кібернетика та обчислювальна техніка“. – 2011. - Вип. 14 (188). - С. 8-17. 3. Войтюк. І. Ф. Особливості оптимізації структури інтервального різницевого оператора / Войтюк. І. Ф., Манжула В. І., Дивак Т. М. // Прогресивні інформаційні технології в науці, освіті та економіці. Збірка наукових праць учасників міжнародної науково-практичної конференції Індуктивне моделювання складних систем, випуск 5, 2013 268 Порплиця Н.П., Дивак М.П. „Трансформаційні реформи та антикризовий потенціал економіки в постсоціалістичних країнах“. – Вінниця, 2009. – С. 146-154. 4. Ивахненко А . Г . Численное исследование помехоустойчивости многокритериальной селекции моделей / А . Г . Ивахненко, B. C. Степашко // Автоматика. –1982. – № 4. – С . 26-36. 5. Степашко В.С. Елементи теорії індуктивного моделювання. – Стан та перспективи розвитку інформатики в Україні: монографія / Кол. авторів. – Київ: Наукова думка, 2010. – С. 481-496. 6. Ивахненко А.Г. Индуктивный метод самоорганизации моделей сложных систем / А.Г. Ивахненко - Киев: - Наукова думка, 1981.- 296 с. 7. Льюнг Л. Идентификация систем. Теория для пользователя. М.: Наука, 1991. – 432 с. 8. Алефельд Г. Введение в интервальные вычисления / Г. Алефельд, Ю. Херцбергер – М. : – Мир, 1987. – 360 с. 9. Дивак М. П. Особливості побудови інтервальної системи алгебричних рівнянь та методу її розв’язку в задачах ідентифікації лінійного інтервального різницевого оператора / М. П. Дивак, Т. М. Дивак // Індуктивне моделювання складних систем. Збірник наукових праць / відпов. редактор В.С.Степашко. – Київ : МННЦ ІТС, 2009. – Вип. 1. – 236 с. – С. 35–43. 10. Karaboga D. An idea based on honey bee swarm for numerical optimization: Techn. rep. — TR06. —Erciyes: Erciyes Univ. Press, 2005. — 10 p. 11. Фриш К. Из жизни пчёл / Халифман И. А. (отв.ред.). — Москва: Мир, 1980. — 216 с. 12. Riley J.R., The flight paths of honeybees recruited by the waggle dance / J. R. Riley , U. Greggers, A. D. Smith, D. R. Reynolds R. Menzel // NATURE: International weekly journal of science– 2005.–Vol. 435. – pp. 205-207. 13. Karaboga D., “Artificial bee colony algorithm”, scholarpedia.org, March 23,2010.[online].Available:http://www.scholarpedia.org/article/Artificial_bee_colony _algorithm. [Accessed: Oct. 3, 2013]. 14. Camazine S. , Sneyd J. A model of collective nectar source by honey bees: Self-organization through simple rules // J. Theoret. Biol. — 1991. — N 149. — pp. 547–571. 15. Дивак М. П. Кількісні характеристики оцінки якості структури моделі у вигляді інтервального різницевого оператора / М. П. Дивак, Т. М. Дивак, І. Ф. Войтюк // Відбір і обробка інформації : міжвід. зб. наук. пр. – Вип. 34 (110). – 2011. – C. 86–94. Індуктивне моделювання складних систем, випуск 5, 2013 269 http://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%BB%D0%B8%D1%84%D0%BC%D0%B0%D0%BD,_%D0%98%D0%BE%D1%81%D0%B8%D1%84_%D0%90%D1%80%D0%BE%D0%BD%D0%BE%D0%B2%D0%B8%D1%87 http://www.scholarpedia.org/article/Artificial_bee_colony_algorithm http://www.scholarpedia.org/ http://www.scholarpedia.org/article/Artificial_bee_colony_algorithm http://www.scholarpedia.org/article/Artificial_bee_colony_algorithm

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

Institution

Ähnliche Einträge