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

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

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

УДК 681.3

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

Спеціальність 01.05.02 - математичне моделювання та

обчислювальні методи

Автореферат

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

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

КОЗАЧКО ОЛЕКСІЙ МИКОЛАЙОВИЧ

Вінниця - 2006

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

Робота виконана у Вінницькому національному технічному університеті Міністерства освіти і науки України

Науковий керівник: кандидат технічних наук, доцент Штовба Сергій Дмитрович, Вінницький національний технічний університет, докторант кафедри комп'ютерних систем управління

Офіційні опоненти: доктор технічних наук, професор, заслужений діяч науки і техніки України, Герасимов Борис Михайлович, Військовий інститут Київського національного університета ім. Тараса Шевченка, професор кафедри математичного та програмного забезпечення автоматизованих систем управління

доктор технічних наук, професор Квєтний Роман Наумович, Вінницький національний технічний університет, завідувач кафедри автоматики та інформаційно-вимірювальної техніки

Провідна установа: Національний університет “Львівська політехніка”, кафедра програмного забезпечення, Міністерство освіти і науки України, м. Львів.

Захист відбудеться “ 26 ” ___05_____ 2006 р. о ___9³⁰___ годині на засіданні спеціалізованої вченої ради Д 05.052.01 у Вінницькому національному технічному університеті за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

З дисертацією можна ознайомитись у бібліотеці ВНТУ за адресою: 21021, м. Вінниця, Хмельницьке шосе, 95.

Автореферат розісланий “_25__”___04_____ 2006 р.

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

спеціалізованої вченої радиЗахарченко С.М.

багатовимірний алгоритмічний градієнтний

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

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

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

В дисертаційній роботі розглядаються так звані багатовимірні АП, тобто процеси при виконанні яких вносяться, виявляються та усуваються помилки різних типів. Помилки різних типів пов'язані з неправильним виконанням людиною або технікою деякого фрагменту алгоритму. Для оцінювання багатовимірних АП О.П. Ротштейн запропонував матричні моделі надійності. Обмеженням цих моделей є неможливість їх застосування в реальних умовах проектування АП, коли початкові дані задаються експертними оцінками. Для забезпечення надійності багатовимірних АП О.П. Ротштейн та С.Д. Штовба запропонували модель оптимізації на базі типового генетичного алгоритму. Недоліком цієї моделі є низька швидкість пошуку оптимуму. Таким чином, недостатність теоретичних досліджень і, відповідно, відсутність програмних засобів для математичного обґрунтування проектних рішень для багатовимірних АП вимагає розробки нового методу моделювання надійності АП. Це і обумовлює актуальність дисертаційної роботи.

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

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

Аналіз методів оцінювання та оптимізації надійності багатовимірних АП (розділ 1);

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

Розробка моделей оцінювання надійності багатовимірних АП по нечітким початковим даним (розділ 3);

Розробка програмного забезпечення автоматизованої системи моделювання та оптимізації надійності багатовимірних АП (розділ 4).

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

Предметом дослідження є моделі оцінювання та забезпечення основних показників надійності АП.

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

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

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

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

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

Практичне значення одержаних результатів. На основі теоретичних результатів розроблено програмне забезпечення автоматизованої системи моделювання та забезпечення надійності багатовимірних АП. Практичні результати дисертації впроваджені компанією “Банк'c Cофт Системс” (Москва) та банком “УКРІНБАНК” (Вінниця). Теоретичні результати впроваджено у навчальний процес кафедри комп'ютерних систем управління ВНТУ.

Особистий внесок здобувача. Усі наукові результати, що виносяться на захист, отримані здобувачем самостійно. В роботах, опублікованих у співавторстві, здобувачу належить: швидкі градієнтні та генетичні моделі оптимізації надійності багатовимірних АП [2-5, 7, 9, 11-15], нечіткі моделі надійності типових багатовимірних алгоритмічних структур [1, 6, 8, 10], програмне забезпечення автоматизованої системи [16, 17].

Апробація результатів дисертації. Основні положення і результати дисертаційної роботи доповідались та були представлені на: Міжнародній науковій конференції з індуктивного моделювання (Львів, 2002 р.); IV-й Міжнародній молодіжній науковій конференції “Людина і космос” (Дніпропетровськ, 2002 р.); ІІ-й та ІІІ-й Міжнародних конференціях “Photonics-ODS” (Вінниця, 2002, 2005 рр.); ІХ-й та ХІ-й Міжнародних конференціях з управління “Автоматика-2002” (Донецьк, 2002 р.) та “Автоматика-2004” (Київ, 2004 р.); VIІ-й та VIІI-й Міжнародній НТК “Контроль і управління в складних системах” (Вінниця, 2003, 2005 рр.); Науково-практичній конференції “Стан та перспективи розвитку новітніх науково-освітніх комп'ютерних технологій” (Миколаїв, 2003 р.); Міжнародній науково-практичній конференції “Інтелектуальні системи прийняття рішень та інформаційні технології” (Чернівці, 2004 р.); Міжнародній науковій конференції “Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій” ISDMIT'2005 (Євпаторія, 2005 р.), VII-й Міжнародній НТК “Системний аналіз та інформаційні технології” (Київ, 2005 р.), а також на щорічних науково-методичних конференціях ВНТУ.

Публікації. Результати дисертації опубліковано в 20 роботах, серед яких: 7 статей в журналах з переліку ВАК України, 2 статті в збірках матеріалів конференцій та 11 тез доповідей. Основний зміст дисертації викладено в 17 роботах.

Структура та обсяг дисертації. Робота складається із вступу, 4 розділів, висновків, списку використаних джерел і додатків. Основний зміст викладено на 148 сторінках друкованого тексту. Дисертація містить 48 рисунків, 39 таблиць, 123 літературних джерела, 6 додатків. Повний обсяг дисертації - 202 сторінки.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

Постановка задачі. Оптимізація АП полягає у визначенні структури процесу, що забезпечує необхідні рівні ймовірнісно-часових показників надійності функціонування. На практиці найбільш поширеними задачами оптимізації надійності АП є розподіл контрольних точок та вибір кратностей контролів. В цих задачах АП представляє собою послідовне виконання n робочих операторів A₁, A₂, …, A_n. При виконанні робочих операторів в АП можуть бути внесені помилки різних типів. Якість виконання робочого оператора A_i перевіряється контролем _i x_i -раз. Для задачі розподілу контрольних точок x_i {0, 1}, а для задачі вибору кратностей контролів x_i {0, 1, 2, …}, i=1,n. Операція доробки U_i виправляє помилки, які виявлені контролем _i. Оптимізація надійності АП полягає в знаходженні такого вектора Х=(x₁, x₂, …, x_ni), що забезпечує:

пряма постановка:

(1)

зворотна постановка:

(2)

де C(Х) - вартість виконання АП, який задано вектором X; p¹(Х) -ймовірність правильного виконання АП; p^0j(X) - ймовірність помилки j-го типу на виході АП; Р^* - мінімально допустима ймовірність безпомилкового виконання АП; q_j(Х) - максимально допустима ймовірність наявності помилки j-го типу на виході АП; С^* - максимально допустимі витрати на виконання АП; m - кількість різних типів помилок.

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

(3)

,(4)

де і

- характеристики надійності операторів A_i і U_i: p^0j_Ai - ймовірність внесення оператором A_i помилки j-го типу; p¹_Ai - ймовірність безпомилкового виконання оператора A_i; н^1j_Ui(н^0j_Ui) -ймовірність усунення (не усунення) помилки j-го типу, j=1,m;

 і -

характеристики надійності контролю _i: k¹¹_i(k¹⁰_i) - ймовірність того, що відсутність помилок ідентифіковано правильно (неправильно); k^01j_i(k^00j_i) - ймовірність пропуску (виявлення) помилки j-го типу, j=1,m; c_Ai, c_i та c_Ui - вартість виконання робочого оператора A_i, контролю _i і доробки U_i, відповідно, i=1,n.

Формули (3)-(4) отримані x_i- кратним застосуванням моделі надійності структури “робота-контроль-доробка”, яку запропонував проф. О.П. Ротштейн.

Для перевірки моделей оптимізації розроблено бібліотеку тестових задач (www.ksu.vstu.vinnica.ua/shtovba/benchmark). Вона складається з 4-х множин задач: А_4_1, А_4_2, В_4_1 і В_4_2. Множини задач А_4_1 і А_4_2 використовуються для тестування задачі (1), а В_4_1 і В_4_2 - для задачі (2). В кожній задачі розглядаються АП з 4 різними типами помилок з кількістю робочих операторів n=20, 40, 60, 80, 100, 120. Для задач А_4_1 і В_4_1 ймовірність появи одного типу помилки має бути на порядок нижче за інших. Для задач А_4_2 і В_4_2 всі типи помилок мають приблизно однакову важливість.

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

,(5)

де B_i=K¹_i+K⁰_i P_Ui- ймовірність переходу на доробку; Pz - матриця надійності оператора оновлення, в якій перший стовпчик є одиничним, а решта m стовпчиків є нульовими; І - одинична матриця; - ліве домноження матриці.

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

Занулити початковий вектор X^<0>:=(x₁^<0>, x₂^<0>, …, x_n^<0>) ;

Розрахувати показники надійності АП за формулою (3); N:=0;

While Не виконуються обмеження задачі оптимізації

Обчислити _i^<N>, для всіх і таких, що x_i^<N>:=0;

Визначити контроль з максимальним градієнтом ;

Встановити x_l^<N>:=1; N:=N+1; X^<N>:=X^<N-1>;

Обчислити показники надійності АП;

End | Кінець першої ітеративної ділянки

While Виконуються обмеження задачі оптимізації

Встановити N:=N+1; X^<N>:=X^<N-1>;

Ініціалізувати множину надлишкових контролів L:=;

For i=1…n | для всіх робочих операторів

If x_i^<N>:=1

Встановити x_i^<N>:=0 та обчислити показники надійності АП;

Присвоїти L:={L, i}, якщо виконуються обмеження задачі;

Встановити x_i^<N>:=1; | End of If

End

Знайти контроль lL, для якого вартість АП мінімальна;

Встановити x_l^<N>:=0;

Обчислити показники надійності АП;

End. | Кінець другої ітеративної ділянки

Реалізація моделі оптимізації розподілу контрольних точок для задачі (2) співпадає з реалізацією моделі оптимізації розподілу контрольних точок для задачі (1), за винятком кроків 9, 10, 12, 13 та 14, які необхідно виконати так:

If x_l^<N>:=0

Встановити x_i^<N>:=1 та обчислити показники надійності АП ;

Встановити x_i^<N>:=0; | End of If

Знайти контроль lL, для якого p¹(X) максимальна;

Встановити x_l^<N>:=1.

Реалізація моделі оптимізації вибору кратностей контролів для задачі (1) складається з таких двох ітеративних ділянок:

Занулити початковий вектор X^<0>:=(x₁^<0>, x₂^<0>, …, x_n^<0>);

Розрахувати показники надійності АП за формулою (3); N:=0;

While Не виконуються обмеження задачі оптимізації

Обчислити градієнти контролів_i^<N>, i=1,n за формулою (5) ;

Визначити контроль з максимальним градієнтом ;

Встановити x_l^<N>:=x_l^<N>+1; N:=N+1; X^<N>:=X^<N-1>;

Обчислити показники надійності АП;

End | Кінець першої ітеративної ділянки

While Виконуються обмеження задачі оптимізації

Встановити N:=N+1; X^<N>:=X^<N-1>;

Ініціалізувати множину надлишкових контролів L:= ;

For i=1…n | для всіх робочих операторів

Встановити x_i^<N>:=x_i^<N>-1, якщо x_i^<N>>0;

Обчислити показники надійності АП;

Присвоїти L:={L, i}, якщо виконуються обмеження задачі;

Встановити x_i^<N>:=x_i^<N>+1;

End

Знайти контроль lL, для якого вартість АП мінімальна;

Встановити x_l^<N>:=x_l^<N>-1;

Обчислити показники надійності АП;

End. | Кінець другої ітеративної ділянки

Реалізація моделі оптимізації вибору кратностей контролів для задачі (2) співпадає з реалізацією моделі оптимізації вибору кратностей контролів для задачі (1), за винятком кроків 9, 12, 13 та 14, які необхідно виконати так:

Встановити x_i^<N>:=x_i^<N>+1;

Встановити x_i^<N>:=x_i^<N>-1;

Знайти контроль lL, для якого p¹(X) максимальна;

Встановити x_l^<N>:=x_l^<N>+1.

Генетичні моделі. Для розв'язання задач оптимізації (1) і (2) генетичним пошуком необхідно обрати: а) способи кодування; б) процедури ініціалізації початкової популяції; в) схрещування і мутацію; г) селекцію; д) модель фітнес-функції. Реалізація цих компонентів така.

Кодування хромосом. Варіант АП закодуємо хромосомою з n генів Х=(x₁, x₂, …, x_ni), де кожен ген відповідає одній керованій змінні.

Процедури ініціалізації. Для задачі розподілу контрольних точок значення гену x_i пропонується генерувати за такою моделлю

, _i=f(_i)/g(_i), i=1,n,(6)

де - випадкове число з діапазону [0, 1]; _i - градієнт і-го контролю;

f(_i)=min _j=1,n(_i)/_i - показник ефективності встановлення гена x_i в 1;

g(_i)=_i /max _j=1,n(_i) - показник ефективності встановлення гена x_i в 0;

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

х_i=ціла_частина((1- _і)х_і+_і х^?_і), i=1,n,(7)

де _i=ⁱ - число з діапазону [0, 1], яке визначає положення x_i на інтервалі [x_i, x^?_i] кратностей і-го контролю.

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

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

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

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

Фітнес-функція. Для оцінювання якості розв'язків пропонуються такі моделі фітнес-функцій:

для задачі (1):

,(8)

для задачі (2):

,(9)

де D(Х) - штрафна функція:

для задачі (1):

;

для задачі (2):

,

де >0-коефіцієнт вагомості штрафів за порушення обмежень по ймовірностям помилок (q₁, q₂, …, q_m); _j(X)=max(0, p^0j(X)-q_j) - величина порушення хромосомою Х j-го обмеження; -якість поточної популяції, яка визначається максимальними порушеннями обмеження по q_j, j=1,m.

Порівняння моделей. Градієнтні та генетичні моделі оптимізації протестовані на тестових задачах. Результати оптимального розподілу контрольних точок (РКТ) та вибору кратностей контролів (ВКК) для задачі (1) зведені в табл. 1, а для задачі (2) - в табл. 2. З цих таблиць видно, що генетичний пошук забезпечує кращі розв'язки, особливо для задач А_4_1. Для задач А_4_2 та В_4_2 результати генетичного та градієнтного пошуку є близькими. Для задач В_4_1 градієнтний пошук не завжди знаходить допустимий розв'язок.

На рис. 3 порівнюються як знайдені за градієнтними та генетичними моделями розв'язки задач В_4_1 задовольняють обмеженням (2). На цих рисунках осям ординат відповідає такий відносний показник:для С(Х): (X)=100%(C*-C(X))/ C*; для p^0j(X): (X)=100%(q_j- p^0j(X))/ q_j, j=1,m.

Від'ємне значення (Х) свідчить, що розв'язок Х не задовольняє обмеженням. Розв'язки оптимізації розподілу контрольних точок, що не задовольняють обмеженням знайдені при n=20, 40, 100 та 120, а для вибору кратностей контролів при n=20, 40 та 100.

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

Генетичний пошук є стохастичним, тому не можливо теоретично визначити скільки разів потрібно розраховувати цільову функцію, щоб досягти оптимуму. Тому швидкодія визначалася експериментально. На рис. 4 порівнюються час оптимізації генетичного та градієнтного вибору кратностей контролів на задачах А_4_1 та А_4_2. Час оптимізації генетичним пошуком розраховувався як середнє значення 100 обчислювальних експериментів. Рис. 4 свідчить, що для задач великої розмірності запропоновані генетичні моделі знаходять розв'язки навіть швидше, ніж градієнтні. Причому, оптимум найшвидше знаходять генетичні моделі з турнірною селекцією. Таким чином, градієнтні моделі доцільно використовувати при дефіциту часу, наприклад, для on-line адаптації АП. Генетичні моделі корисні на етапі проектування АП.

У третьому розділі отримані нечіткі аналоги (табл. 4) моделей надійності таких багатовимірних алгоритмічних структур як “послідовна”, “-диз'юнкція”, “-ітерація”, “робота-контроль-доробка”, “багаторазова робота” та “-доробка”. В табл. 4 наведені нижні та верхні межі -зрізів нечітких чисел. Розробка моделей здійснювалась за принципом нечіткого узагальнення.

Нечіткі моделі надійності застосовувалися для прогнозування часу проведення платіжних доручень через інтернетівську банківську систему. Обробку клієнтського запиту представимо АП такого виду

,(10)

де A₁ - ручне заповнення реквізиту форми документа; A₂ - заповнення реквізиту форми з довідника банка; A₃ - заповнення реквізиту форми з довідника клієнта; N₁, N₂, N₃ - кількість реквізитів в формі документа, що заповнюються вручну, з довідника банка та з довідника клієнта, відповідно; ₁ - контроль правильності заповнення реквізитів на стороні клієнта; U₁ - доробка документа при виявленні помилок контролем ₁; A₄ - електроно-цифрове підписування документу; A₅ -передача документа каналом зв'язку; ₂ - контроль реквізитів та підпису документа на стороні банка; U₂ -повідомлення клієнту про відмову виконання запиту; A₆ -завантаження документа в автоматизовану банківську систему; ₃ - контроль документа в автоматизованій банківській системі; B=U₂{₁U₁}A₄A₅ - позначення для спрощеного запису АП (10).

При виконанні АП (10) можливі такі стани: помилки відсутні; форматна помилка; операційна помилка; помилка електроно-цифрового підпису.

Початкові дані про нечіткі ймовірнісно-часові характеристики операторів та логічних умов отримані опитуванням проектувальників системи. Для оцінювання ймовірнісно-часових характеристик використовувалися терми “Низький”, “Середній”, “Вище Середнього” і “Високий” з трикутними функціями належності. На рис. 5 наведені реальне ймовірнісне розподілення часу реакції системи “клієнт-банк” та прогнозована tЮY. Реальне розподілення отримано фірмою “Банкс Софт Системс” при навантаженому тестуванні системи протягом трьох місяців 2005 р. Нечіткий час tЮY практично збігається з експериментальними даними.

Аналіз чутливості часу обробки запиту tЮ_Y до лінгвістичного значення нечіткого часу передачі платіжного доручення каналом зв'язку наведено на рис. 6. При аналізі чутливості координату максимуму tЮ_A5 трикутної функції належності нечіткого числа tЮ_A5 змінювали в діапазоні [15, 150]. Цей діапазон відповідає зміні лінгвістичної оцінки від “низької” до “високої”. В результаті аналізу чутливості встановлено, що лінгвістична оцінка часу виконання алгоритму tЮ_Y змінюється від “Нижче Середнього” до “Вище Середнього”.

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

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

ВИСНОВКИ

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

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

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

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

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

4. На базі наукових результатів розроблено програмне забезпечення автоматизованої системи моделювання та оптимізації надійності багатовимірних АП. Система забезпечує автоматизацію найбільш трудомістких операцій проектування багатовимірних АП за критеріями надійності.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Ротштейн О.П., Штовба С.Д., Козачко О.М. Нечітке прогнозування надійності алгоритмів, що враховують помилки різних типів // Вісник Вінницького політехнічного інституту. - 2005. - №4. - С.77-85.

2. Штовба С.Д., Козачко О.М. Генетична мінімізація вартості контролів в технологічному процесі з урахуванням дефектів різних типів // Вісник Вінницького політехнічного інституту. - 2005. - №3. - С.74-79.

3. Ротштейн О.П., Штовба С.Д., Козачко О.М. Градієнтна оптимізація кратностей контролів технологічного процесу при обмежених ресурсах з урахуванням дефектів багатьох типів // Вісник Вінницького політехнічного інституту. - 2005. - №2. - С.54-62.

4. Ротштейн О.П., Штовба С.Д., Дубіненко С.Б., Козачко О.М. Евристична оптимізація розстановки контрольних точок в технологічних процесах при багатовимірному просторі типів дефектів // Вісник Вінницького політехнічного інституту. - 2004. - №1. - С.54-62.

5. Штовба С.Д., Козачко О.М. Генетична оптимізація кратностей контрольно-доробчих операцій в технологічних процесах з урахуванням дефектів багатьох типів // Вісник Житомирського державного технологічного університету. - 2004. - №4. - Том 2. - С.180-187.

6. Ротштейн А.П., Штовба С.Д., Козачко О.М. Нечеткие модели надежности алгоритмов, учитывающие ошибки различных типов // Вестник Севастопольского государственного технического университета. Сер. “Автоматизация процессов и управление”. -2004. -№58.-С. 175-187.

7. Shtovba S., Kozachko O., Dounias G. А fast genetic algorithm for optimising the checking - retrofit procedures in multidimensional technological processes // Штучний інтелект. - 2004.- №2.- C.225-230.

8. Штовба С.Д., Козачко О.М. Прогнозування часу обробки запиту в системі “клієнт-банк” за допомогою нечітких моделей надійності // Матеріали МНК “Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій”. - Херсон: ХМІ. - 2005. - Т.1 - C.171-174.

9. Ротштейн О.П., Штовба С.Д., Козачко О.М. Оптимизация расстановки контрольных точек в многомерном технологическом процессе на базе генетических алгоритмов // Праці Міжн. конференції з індуктивного моделювання. - Львів: НУЛП. - 2002. - Том 2. - С.4-7.

10. Штовба С.Д., Козачко О.М. Нечеткий анализ надежности алгоритмических процессов в многомерном пространстве типов ошибок // Матеріали НПК “Стан та перспективи розвитку новітніх науково-освітніх комп'ютерних технологій”. - Миколаїв: МДГУ. - 2003. - С.39-40.

11. Ротштейн А.П., Штовба С.Д., Козачко О.М. Сравнение генетического и градиентного алгоритмов расстановки контрольных точек в технологических процессах с дефектами многих типов // Тези доповідей Між. НПК “Інтелектуальні системи прийняття рішень та інформаційні технології”. - Чернівці: ЧФЮІ. - 2004.-С.56-57.

12. Ротштейн О.П., Штовба С.Д., Козачко О.М. Вплив якості початкової популяції на швидкість генетичної оптимізації надійності технологічних процесів // Тези доповідей VIІІ Міжн. НТК “Контроль і управління в складних системах”. - Вінниця: ВНТУ. - 2005.- С.98.

13. Штовба С.Д., Козачко О.М. Оптимальное проектирование алгоритмов SPAM- фильтрации // Материалы ХІ-ой Международной конференции по автоматическому управлению. - Киев: НУХТ. - 2004. - Том 4. - C.14-15.

14. Ротштейн О.П., Штовба С.Д., Козачко О.М. Оптимізація кратності контролю технологічних процесів з врахуванням різних типів дефектів // Тези доповідей VIІ Міжнародної НТК “Контроль і управління в складних системах”. - Вінниця: ВНТУ. - 2003.- С.38.

15. Козачко О.М. Проектування інформаційних процесів на базі генетичних алгоритмів // Тези доповідей ІІ-ї Міжнародної НТК “Оптоелектронні інформаційно-енергетичні технології”. - Вінниця: ВДТУ. - 2002. - С.30.

16. Штовба С.Д., Козачко О.М., Піскляров Д.С. Автоматизована система моделювання надійності алгоритму обробки запиту в системі “клієнт-банк” // Тези доповідей Міжн. НТК “Системний аналіз та інформаційні технології”. - Київ. - 2005.-С.127.

17. Ротштейн А.П., Штовба С.Д., Козачко О.М. Автоматизована система моделювання надійності алгоритмів, що виконуються з помилками багатьох типів // Тези доповідей ІІІ-ї Міжн. НТК “Оптоелектронні інформаційно-енергетичні технології”. - Вінниця: ВНТУ. - 2005.-С.30.

АНОТАЦІЯ

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

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

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

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

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

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

Розроблено програмне забезпечення автоматизованої системи моделювання та оптимізації надійності багатовимірних алгоритмічних процесів.

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

АННОТАЦИЯ

Козачко А.Н. Моделирование надежности алгоритмических процессов, выполняющихся с ошибками разных типов. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.02 - математическое моделирование и вычислительные методы - Винницкий национальный технический университет, Винница - 2006.

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

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

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

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

Разработано программное обеспечение автоматизированной системы моделирования и оптимизации надежности многомерных алгоритмических процессов. Система обеспечивает автоматизацию наиболее трудоемких операций надежностного проектирования многомерных АП.

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

ABSTRACT

Kozachko О.M. The reliability modeling of algorithmical process, performing with errors of diverse types. - Manuscript.

The thesis on competition of a scientific degree of the candidate of engineering science on a specialty 01.05.02 - mathematical modeling and computational methods - Vinnytsia National Technical University, Vinnytsia - 2006.

The thesis is devoted to the solution of reliability modeling task of multidimensional algorithmic processes, i.e. processes, when being performed, errors of different types are noted, detected and deleted.

The analyze of multidimensional algorithmic process patterns was carried out, estimation methods and providing of their reliability were analyzed, the principles of reliability modeling of such algorithmic process were proposed, research tasks were set.

The gradient and genetic optimization models of reliability multidimensional algorithmic process control were proposed. The comparative analysis of proposed optimization models by theoretical complexity, practical quick-action and solutions quality was realized.

Reliability multidimensional models of operators, logical conditions and such typical algorithmic structures for fuzzy data were generalized. Using of the models is illustrated by the example of algorithmic process of payment order realization reliability forecasting.

The software for modeling and optimizing the multidimensional algorithmic process reliability was described.

Keywords: algorithmic process, reliability, errors of different types, optimization, allocation of checking points, checking-retrofit multiplicity, fuzzy data.

Підписано до друку 12.04.2006 р. Формат 29.742 1/4

Наклад 100 прим. Зам. № 2006-092

Віддруковано в комп'ютерному інформаційно-видавничому центрі