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

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

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

УДК 681.3

Автореферат

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

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

КОЗАЧКО ОЛЕКСІЙ

МИКОЛАЙОВИЧ

Вінниця - 2006

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

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

Науковий керівник: кандидат технічних наук, доцент Штовба Сергій Дмитрович,

Вінницький національний технічний університет, докторант кафедри комп'ютерних систем управління

Офіційні опоненти: доктор технічних наук, професор, заслужений діяч науки і техніки України,

Герасимов Борис Михайлович,

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

доктор технічних наук, професор Квєтний Роман Наумович,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Постановка задачі. Оптимізація АП полягає у визначенні структури процесу, що забезпечує необхідні рівні ймовірнісно-часових показників надійності функціонування. На практиці найбільш поширеними задачами оптимізації надійності АП є розподіл контрольних точок та вибір кратностей контролів. В цих задачах АП представляє собою послідовне виконання n робочих операторів A1, A2, …, An. При виконанні робочих операторів в АП можуть бути внесені помилки різних типів. Якість виконання робочого оператора Ai перевіряється контролем i xi -раз. Для задачі розподілу контрольних точок xi {0, 1}, а для задачі вибору кратностей контролів xi {0, 1, 2, …}, i=1,n. Операція доробки Ui виправляє помилки, які виявлені контролем i. Оптимізація надійності АП полягає в знаходженні такого вектора Х=(x1, x2, …, xni), що забезпечує:

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

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

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

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

,

де і

- характеристики надійності операторів Ai і Ui: p0jAi - ймовірність внесення оператором Ai помилки j-го типу; p1Ai - ймовірність безпомилкового виконання оператора Ai; н1jUi(н0jUi) -ймовірність усунення (не усунення) помилки j-го типу, j=1,m;

і

- характеристики надійності контролю i: k11i(k10i) - ймовірність того, що відсутність помилок ідентифіковано правильно (неправильно); k01ji(k00ji) - ймовірність пропуску (виявлення) помилки j-го типу, j=1,m; cAi, ci та cUi - вартість виконання робочого оператора Ai, контролю i і доробки Ui, відповідно, i=1,n.

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

Для перевірки моделей оптимізації розроблено бібліотеку тестових задач. Вона складається з 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 показує відносну ефективність встановлення додаткового контролю після робочого оператора Ai. Для багатовимірних АП пропонується така модель градієнту контролю

,

де Bi=K1i+K0i PUi- ймовірність переходу на доробку; Pz - матриця надійності оператора оновлення, в якій перший стовпчик є одиничним, а решта m стовпчиків є нульовими; І - одинична матриця; - ліве домноження матриці.

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

Занулити початковий вектор X<0>:=(x1<0>, x2<0>, …, xn<0>) ;

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

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

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

End

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

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

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

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

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

If xl<N>:=0

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

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

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

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

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

Занулити початковий вектор X<0>:=(x1<0>, x2<0>, …, xn<0>);

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

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

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

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

End

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

для задачі:

,

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

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

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

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

де >0-коефіцієнт вагомості штрафів за порушення обмежень по ймовірностям помилок (q1, q2, …, qm); j(X)=max(0, p0j(X)-qj) - величина порушення хромосомою Х j-го обмеження; -якість поточної популяції, яка визначається максимальними порушеннями обмеження по qj, j=1,m.

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

для С(Х): (X)=100%(C*-C(X))/ C*; для p0j(X): (X)=100%(qj- p0j(X))/ qj, j=1,m.

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

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

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

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

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

,