close

Вход

Забыли?

вход по аккаунту

?

Решение задачи оптимизации надежности в дуальной вычислительной среде.

код для вставкиСкачать
УДК 519.72
РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НАДЕЖНОСТИ В ДУАЛЬНОЙ
ВЫЧИСЛИТЕЛЬНОЙ СРЕДЕ
И.Л. Каширина
В статье рассматривается математическая модель многокритериальной задачи оптимального резервирования.
Предлагаются метод ветвей и границ отыскания полной совокупности Парето-оптимальных решений данной задачи,
а также генетический алгоритм, позволяющий получить представительную аппроксимацию множества Парето
Ключевые слова: оптимальное резервирование, многокритериальная задача, множество Парето, метод ветвей и
границ, генетический алгоритм
Постановка задачи
Рассматривается сложная техническая система⋅, состоящая из n элементов. Универсальным
принципом обеспечения надёжности сложной системы является резервирование ее элементов, которое может быть аппаратным, информационным,
временным, программным. Наибольшее распространение получили две схемы резервирования: резервирование замещением «один из двух» (1оо2 – 1
outof 2) и резервирование по схеме мажоритарного
голосования «два из трех» (2оо3). Системы без резервирования обозначаются 1оо1.
Предположим, что каждый элемент исследуемой системы (а, значит, и система в целом) характеризуется тремя основными параметрами: вероятностью безотказной работы p j , стоимостью s j и
среднем
временем
безотказной
работы
tj ,
j ∈{1,2,..., n} .Зависимость стоимости, вероятности
безотказной работы и среднего времени работы до
отказа от способа резервирования представлена в
таблице.
Зависимость параметров системы от способа резервирования
Критерий
1оо1
1оо2
2оо3
p
2p-p2 3p2-2p3
Вероятность безотказной работы
S
2SG
4S
Стоимость
Среднее время раT
3T/2
5T/6
ботыдо отказа
Через G обозначен коэффициент, увеличивающий стоимость схемы 1оо2, если для данного
резервируемого элемента существует надежный
блок переключения на резерв.
Если такой блок
отсутствует, для элемента вводится запрет на возможность быть зарезервированным методом 1оо2.
Вводится ограничение на среднее время безотказной работы резервируемой системы: оно должно
быть не меньше заданного значения.
Задача состоит в выборе способа резервирования для каждого элемента системы, который позволил бы получать наибольшую возможную вероятность безотказной работы при наименьшей стоимости системы с учетом выполнения указанного ограничения. Математическая модель бикритериальной
задачи оптимального резервирования может быть
⋅
Каширина Ирина Леонидовна – ВГУ, канд. техн. наук,
доцент, тел. 8 903 653 92 93, e-mail: kash.irina@mail.ru
сформулирована в виде:
n
P = ∏( p j x1 j + (2 p j − p2j ) x2 j + (3 p2j − 2 p3j ) x3 j ) → max (1)
j =1
S=
n
∑ ( S j x1 j + 2S j G j x 2 j + 4S j x 3 j ) → min
(2)
j =1
x1 j + x2 j + x3 j = 1 , j = 1, n (3)
n
1
Tj
∑ ( x1 j +
j =1
2
6
1
x2 j +
x3 j ) ≤
3T j
5T j
Tc
(4)
Обозначения:
 1, если элементу j назначаетс я способ
x ij =  резервиров ания i ;
 0, иначе.
Здесь i ∈{1,2,3} - номер способа резервирования (соответственно, 1оо1, 1оо2, 2оо3). P – вероятность работы без отказа всей системы,
S– общая
стоимость системы. T c – минимальное среднее время работы до отказа всей системы. Ограничение (4)
имеет соответствующий вид потому, что среднее
время работы до отказа всей системы связано со
средним временем наработки до отказа ее элементов
следующим соотношением:
1
Tс
 n
=  ∑ T1
j
 j =1

.


Отметим, что с целью получения более простой однокритериальной модели задачи можно было
бы отказаться от целевой функции (2), добавив соответствующее ограничение на итоговую стоимость
системы. Однако, в данном случае существует несколько практических доводов в пользу рассмотрения именно бикритериальной модели. Во-первых,
стоимость сложной системы является довольно высокой и может варьироваться в достаточно широких
пределах. В связи с этим, имеет смысл отыскания
всего множества парето-оптимальных решений бикритериальной задачи (или хотя бы его представительной аппроксимации), чтобы получить представление о возможных диапазонах изменения стоимости и надежности и иметь возможность выбрать в
итоге компромиссный вариант. Во-вторых, задача
конструирования такого рода систем является технически сложной и содержит ряд трудно формализуемых требований. Поэтому получение не одного, а
сразу множества решений позволит выбрать из них
наиболее приемлемое с конструкторской точки зрения.
Методы решения
Для отыскания решения данной задачи в рабо-
те разработано и исследовано с помощью вычислительно эксперимента два метода: алгоритм ветвей и
границ, организованный таким образом, чтобы находить все множество Парето-оптимальных решений и генетический алгоритм, ориентированный на
получение некоторой представительной аппроксимации Парето-оптимального множества.
На рис. 1 приведена блок-схема метода ветвей
и границ.
Задание начальных рекордных оценок: нижней границы для вероятности
безотказной работы P 0 и верхней допустимой границы для стоимости S 0
да
Рассмотрены все координаты?
нет
Выбор индекса k, такого, что отношение sk/pkминимально среди всех непросмотренных координат
Ветвление : Ω k = Ω1k U Ω k2 U Ω 3k
Определение подмножеств, содержащих допустимые точки: I k ∈ {1,2,3}
Решение оценочных задач по двум критериям, вычисление пар оценок
( Pi k , S ik ), i ∈ I k . Если оценки доминируются какой-либо парой из рекордного
множества, то подмножество выбрасывается из рассмотрения
Возможное обновления множества рекордных решений, содержащего все
полученные к данному этапу недоминируемые точки, сокращение перебора
да
Остались перспективные
множества?
Выбор перспективного множества
для ветвления в соответствии со
стратегией
нет
Решение найдено
Рис. 1. Блок- схема метода ветвей и границ
Рассмотрим подробнее основные этапы этого
метода.
Ветвление.В данной задаче на каждом этапе
используется следующее правило ветвления:
Ω k = Ω1k U Ω 2k U Ω 3k , где Ω ik – это подмножество
множества допустимых решений, в котором для
резервирования элемента k
выбран способ i,
i=1,2,3. Если способ резервирования 1оо2 для соответствующего элемента невозможен, то полагается Ω k = Ω1k U Ω 3k .
Построение множества рекордных решений.Множество рекордных решений для данной задачи представляет собой совокупность точек, которые являются недоминируемыми в множестве всех
рассмотренных алгоритмом на данный момент вариантов. Процесс формирования такого множества
следующий. Пусть в какой-то момент работы алгоритма имеется некоторое множество рекордных ре-
шений Rec и получено новое допустимое решение
x new . Если ∃x ∈ Rec : x f x new , то решение x new в
рекордное множество не добавляется. Если же в
Rec нет решений, доминирующих x new , то x new
включается в множество R , причем из R исключаются все решения, которые являются доминируемыми решением x new . Следует отметить, что если
∃x ∈ Rec : x ~ x new и x ≠ x new , то x new также включается в множество R .
Оценка подмножеств допустимых решений и
сокращение дерева поиска.На этом этапе для каждого подмножества решаются по две специально построенные в работе оценочные задачи, а также определяется, содержит ли данное подмножество допустимые точки (те, в которых выполняется ограничение на среднее время безотказной работы). Если
допустимых точек нет, подмножество отбрасывается.
Стратегия построения и обхода дерева вариантов. Как показал вычислительный эксперимент,
наиболее существенное сокращение перебора дает
рассмотрение координат в порядке убывания значения отношения s j / p j . Предварительное упоря-
ность предложенного алгоритма, его практическое
использование ограничено для задач с размерностью более 30-40 резервируемых элементов. Поэтому для решения поставленной задачи в случае, если
она имеет большую размерность, с помощью численного эксперимента были разработаны и исследованы различные модификации приближенных генетических алгоритмов и выбран наиболее эффективный алгоритм для решения данной задачи, схема
которого представлена на рис. 2, позволяющий получать хорошую аппроксимацию множества Парето
за приемлемые временные затраты [1].
дочивание элементов по убыванию коэффициента
s j / p j и последующее ветвление дерева вариантов в
соответствии с полученной очередностью является
мощным способом увеличения скорости поиска решения задачи повышения надежности систем прогнозирования граничных состояний с помощью
предложенного метода ветвей и границ.
Несмотря на достаточно высокую эффективНачало
1
Создание случайной
начальной популяции
Скрещивание
Мутация
Вычисление вектора
целей
Случайное исправление
координат
Поиск недоминируемых вариантов
Выполняется
ограничение
Тср?
Ранжирование
Исключение недоминируемых вариантов
нет
да
Сохранение рекорда
нет
Все варианты
исключены ?
да
Оценка приспособленности
да
Есть изменения
рекорда за 100
поколений?
нет
Конец
Пропорциональный
отбор
1
Рис. 2. Блок-схема генетического алгоритма
Для этого алгоритма разработана специальная
методика назначения приспособленности, включающая следующие шаги.
1) Для каждого решения в популяции вычисляется вектор целей (S , P) .
2) Из текущей популяции выбирается множество недоминируемых внутри этой популяции решений, они запоминаются и временно исключаются
из рассмотрения.
3) Далее ищется множество недоминируемых
решений в полученном усеченном множестве, и они
тоже исключаются. Эта процедура проделывается
до тех пор, пока все решения не будут исключены из
популяции.
4) Затем все решения ранжируются: принадлежащие последнему исключённому множеству получают ранг 1, предпоследнему ранг 2. Решения, первыми исключенные из рассмотрения, получают максимальный ранг. Внутри каждого исключенного
множества решения имеют одинаковый ранг.
5) Далее, в отдельности для каждой группы
решений одного ранга, происходит назначение скалярных оценок приспособленности. Предположим,
ранг k имеет m решений. Тогда решение, сумма евклидовых расстояний от которого до остальных решений данного ранга максимальна, получит оценку
k+(m-1)/m. Решение со второй по величине суммой
расстояний получит оценку k+(m-2)/m. Решение с
минимальной суммой расстояний будет иметь оценку к.Такой подход к оцениванию экземпляров популяции настраивает алгоритм не только на поиск недоминируемых решений (любая недоминируемая
строка будет иметь оценку выше любой доминируемой), но и на поддержание разнообразия популяции (удаленные точки получают более высокие
оценки), что в результате обеспечивает лучшую аппроксимацию Парето-оптимального множества.
С целью дальнейшего повышения надежности системы предлагается использовать дуальную
вычислительную среду, в которую, кроме оптимизационной модели, включается модуль построения
нейросетевых моделей некоторых элементов этой
системы с целью осуществления дополнительного
резервирования в случае, если по результатам решения оптимизационной задачи для данного элемента
не предусмотрен резерв (например, элемент слишком дорогостоящий). То есть предлагается в качестве дополнительного резервного канала рассматривать вместо физической реализации некоторый виртуальный образ в виде нейросетевой модели, имитирующей преобразование входных воздействий от
других компонентов в выходные величины, поскольку именно нейросетевая модель способна решать слабо формализованные задачи, оперативно
аппроксимироватьпроизвольные непрерывные многопараметрические
зависимости,
обрабатывать
данные, представленные в разнотипных шкалах.
Вычислительный эксперимент
Результаты численных экспериментов подтвердили эффективность предлагаемых методов и
целесообразность их объединения в дуальную вычислительную среду.
В частности, для алгоритма метода ветвей и
границбыл организован численный эксперимент с
целью определения наилучшей стратегии обхода
дерева вариантов. Анализировались стратегии, основанные на упорядочивании резервируемых элементов по убыванию характеристик, вычисляемых
на основе значений параметров p j , s j и t j . Коэффициенты целевых функций определялись с помощью специальной рандомизированной процедуры.
Рассматривались системы, содержащие от 15 до 50
элементов с возможностью резервирования. Упорядочивание элементов по убыванию характеристик
s j / p j дало наилучшие результаты, при этом время
работы алгоритма сокращается в несколько раз.
Если бы решение задачи осуществлялось методом полного перебора, то, например, в каждой
задаче размерности 15 необходимо было рассмотреть 315 степени вариантов, то есть перебрать
14348907 решений. По результатам численного
эксперимента, метод ветвей и границ, не использующий стратегию упорядочивания элементов, для
этой размерности просматривает в среднем 40 000
решений, а алгоритм, использующий эту стратегию,
просматривает в среднем 8000 решений (что, примерно, в 1800 раз меньше, чем метод полного перебора), при этом средний объем Паретооптимального множества, составил 65 решений.
С помощью построенной многокритериальной
оптимизационной модели и разработанного для нее
алгоритма решена задача повышения надежности
управляющих трактов стендовой информационноуправляющей системы для диагностики и испытаний жидкостных ракетных двигателей(ЖРД).
Для элементов, зарезервированных по схеме
1оо2, в рамках дуальной вычислительной среды далее были построены нейросетевые модели и сформированы дополнительные виртуальные каналы
измерений, позволяющие при физическом резервировании по дублированной схеме 1оо2 использовать более наглядный метод мажоритарного контроля 2оо3[2-3]. Возможность использования нейросетевого резервирования в системах управления и
регулирования основных параметров ЖРД подтверждена на более чем 60-и огневых испытаниях в
ОАО КБХА.
Литература
1. Львович Я.Е. Генетический алгоритм решения
многокритериальной задачи повышения надежности резервирования/Я.Е.Львович, И.Л. Каширина, А.А. Тузиков//Информационные технологии, 2012.-№6- С.56-60.
2. Каширина, И.Л.Нейросетевая модель датчика
давления в камере сгорания для наземных огневых
испытаний ЖРД[Текст] / И.Л. Каширина, Я.Е Львович,
А.А. Тузиков // Вестник Воронежского государственного
технического университета. - 2010. - Т. 6. -№ 11. - С. 4-7.
3. Каширина И.Л. Нейросетевое резервирование
дублированных измерений параметров при наземных
огневых испытаниях ЖРД/ И.Л. Каширина, Я.Е. Львович,
А.А. Тузиков// Информационные технологии. 2011. № 9.
С. 74-78.
4. Львович, Я. Е. Оптимизация построения
решающих правил при управлении испытаниями [Текст] /
Я. Е.Львович, И. Л. Каширина, А. А. Шостак // Вестник
Воронежского
государственного
технического
университета. - 2012.-Т. 8. - № 5.-С. 22-24.
5. Подвальный,
С.Л.
Многоальтернативные
системы: обзор и классификация [Текст] / С.Л
Подвальный // Системы управления иинформационные
технологии. - 2012. - Т. 48. - № 2. - С. 4-13.
6. Фролов В.Н., Львович Я.Е., Повальный С.Л.
Проблема оптимального выбора в прикладных задачах.
Воронеж: ВГУ. 1980. – 140 с.
Воронежский государственный университет
SOLUTION OF THE TASK OF OPTIMIZATION OF RELIABILITY IN THE DUAL
COMPUTING ENVIRONMENT
I.L. Kashirina
In the article the mathematical model of a multicriteria problem of optimal reservation. Is offered the method of branches
and borders find a full set of Pareto-optimal solutions, as well as the genetic algorithm to obtain a representative approximation
of the Pareto set
Key words: optimal redundancy, multicriteria problem, Pareto set, the method of branches and borders, genetic algorithm
Документ
Категория
Без категории
Просмотров
8
Размер файла
133 Кб
Теги
среды, решение, надежности, оптимизация, вычислительной, дуальное, задачи
1/--страниц
Пожаловаться на содержимое документа