РОЗДІЛ 2
МОДЕЛІ ОПТИМІЗАЦІІ НАДІЙНОСТІ БАГАТОВИМІРНИХ
АЛГОРИТМІЧНИХ ПРОЦЕСІВ
В розділі пропонуються градієнтні та генетичні моделі оптимізації надійності
багатовимірних АП. Проводиться порівняльний аналіз запропонованих градієнтних
та генетичних моделей оптимізації за теоретичною складністю, практичною
швидкодією та якістю знайденого розв’язку.
2.1. Постановки задач оптимізації надійності багатовимірних алгоритмічних
процесів
Позначимо через Х – структуру АП. В загальному випадку задачу оптимізації
багатовимірних АП можна поставити у вигляді такої задачі векторної
оптимізації:
знайти такий вектор Х, щоб
(2.1)
де – витрати, які пов’язані з функціонуванням АП, який задано вектором Х;
– ймовірність правильного виконання АП, який задано вектором Х;
– ймовірність помилки j-го типу на виході АП, який задано вектором Х;
m – кількість різних типів помилок.
Для розв’язання задачі векторної оптимізації (2.1) можна використовувати ідеї
оптимальності за Парето [5, 24 ,27, 98] або методи математичного програмування
[19, 20, 38, 52, 54, 56]. В останньому випадку, задачу векторної оптимізації
спочатку необхідно перетворити в задачу скалярної оптимізації (умовної або
безумовної). Задачі оптимізації АП, які виникли на практиці, породжують
Парето-множину великої потужності, тому доцільним буде використання ідеї
скаляризації.
Скалярну задачу оптимізації АП можна сформулювати як задачу мінімізації
середніх сумарних витрат [64]
(2.2)
де – витрати на виконання АП, який задано вектором Х;
– експлуатаційні витрати, що пов’язані з помилками різних типів на виході АП,
який задано вектором Х.
З [64] відомо, що середні витрати на експлуатацію пов’язані з ймовірностями
помилок на виході АП таким чином
, (2.3)
де f – деяка функція.
Для практичних задач ідентифікувати залежність (2.3) дуже важко, а в деяких
випадках і неможливо. В таких випадках можна використовувати лінійну
апроксимацію і представити залежність (2.3) як функцію ризику. Тоді задача
(2.2) перетвориться до вигляду [70]
, (2.4)
де – витрати на експлуатацію, які пов’язанні з наявністю помилки j-го типу на
виході АП ().
При відсутності достовірних даних про значення параметрів функції ризику (що
часто буває на етапі проектування АП) задачу мінімізації (2.4) зручно поставити
у вигляді наступних прямої і зворотної задач умовної оптимізації
Пряма постановка задачі: знайти Х, щоб [70]
(2.5)
де Р* – мінімально допустима ймовірність безпомилкового виконання АП;
– максимально допустима ймовірність помилки j-го типу на виході АП (), який
задано вектором Х.
Зворотна постановка задачі: знайти Х, щоб [70]
(2.6)
де – максимально допустимі витрати на виконання АП.
Існують різні можливості управління надійністю АП: вибір способів реалізації
алгоритмічних операцій [64, 77], розподіл контрольних точок [8, 28, 43, 64],
вибір кратностей контролів [62, 64] тощо. В дисертації пропонуються моделі
оптимізації найбільш важливих в практичному плані надійнісних задач оптимізації
алгоритмів –розподіл контрольних точок (РКТ) та вибір кратностей контролів
(ВКК).
2.1.1. Постановки задачі розподілу контрольних точок.
Розглядається АП, що складається з n потенційно-контрольованих робочих
операторів . Потенційно-контрольований оператор записується так [64]:
, (2.7)
де – робочий оператор, під час виконання якого в АП можуть бути внесені
помилки різних типів, ;
– контроль правильності виконання робочого оператора , причому , якщо виконана
без помилок (з помилками), ;
– оператор доробки, який усуває помилки, які виявлені контролем , ;
Е – тотожній оператор, який використовується для фіксації результату виконання
робочого оператора;
– умова переходу на контроль після виконання робочого оператора : , якщо
виконується з контролем (без контролю), .
Оператор (2.7) може бути виконаний з контролем та доробкою або без них, .
Показники надійності потенційно-контрольованого робочого оператора
розраховуються так [64]:
; (2.8)
, (2.9)
де – матриці ймовірнісних показників надійності операторів та логічних умов,
які описані в додатку А;
, та – вартість виконання робочого оператора , контролю і доробки ,
відповідно, .
Запишемо в матричній формі характеристики надійності та середню вартість
багатовимірного АП так [64]:
; (2.10)
, (2.11)
де – вектор керованих змінних, в якому координата вказує на наявність () або
відсутність () контролю з доробкою після і-го робочого оператора , ;
– характеристики надійності багатовимірного АП: – ймовірність безпомилкового
виконання; –ймовірність наявності помилки j-го типу, .
– середня вартість виконання АП.
Використовуючи співвідношення (2.8) – (2.11) задачі оптимізації (2.5) та (2.6),
перепишемо таким чином:
Пряма постановка: знайти , щоб [85]
(2.12)
Зворотна постановка: знайти , щоб [85]
. (2.13)
2.1.2. Постановки задачі вибору кратностей контролів.
Розглядається АП, що складається з n робочих операторів, які виконуються з
багаторазовим контролем та доробкою . Такі робочі оператори записуються так
[64]
(2.14)
де – кратність виконання контролю з доробкою після робочого оператора , .
Оператор (2.14) є робочий оператор , після якого разів виконується контроль та
доробка (якщо виявлені помилки), .
Якщо припустити, що для оператора характеристики всіх контролів та операторів
доробки є однаковими, то показники надійності розраховуються за такою
ітеративною схемою [86]:
; (2.15)
, (2.16)
де – ймовірність переходу на доробку Uі після -кратного контролю.
Якщо не враховувати помилку першого роду при контролі (), то формули (2.15) та
(2.16) перетворяться у такі співвідношення [86]:
- Киев+380960830922