Решение задачи повышения надежности резервирования
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
µрвирования;
0, в противном случае; .
Важным ограничением является фиксированное среднее время безотказной работы системы (наработка до отказа).
Было показано, что среднее время безотказной работы элемента, резервируемого по схеме 1оо2, составляет 3/2 от среднего времени работы нерезервируемого элемента, а среднее время безотказной работы элемента по схеме 2оо3 соответственно равно 5/6 от среднего времени работы 1oo1.
Исходя из того, что , наработку до отказа всей системы Tс можно представить в виде где Tj - наработка до отказа j-го элемента.
Тогда первое ограничение имеет вид:
,
где Tj - cреднее время наработки на отказ j-го элемента системы без резервирования.
Поскольку каждому элементу назначается ровно один метод резервирования, вторая группа ограничений задачи имеет вид:
, ,
В качестве критериев оптимизации могут рассматриваться общая стоимость системы и величина вероятности безотказной работы всех ее компонентов.
Стоимость элемента, резервируемого по схеме 1оо2 в два раза выше стоимости элемента без резервирования, а стоимость элемента, резервируемого по схеме 2оо3, как показано выше, в четыре раза выше стоимости нерезервируемого элемента. Однако, схема 1оо2 не всегда реализуема, так как для нее необходим абсолютно надежный блок переключения на резерв, который для некоторых резервируемых элементов может отсутствовать. Если же такой блок присутствует, его стоимость может увеличивать общую стоимость данного варианта резервирования.
Поэтому первая целевая функция имеет вид:
Здесь - стоимость j-го элемента резервирования, Gj ?1 - коэффициент, увеличивающий стоимость схемы 1оо2 в случае, если для данного резервируемого элемента существует надежный блок переключения на резерв; и Gj=S в случае, если такой блок отсутствует (S - максимально возможная суммарная стоимость резервируемых элементов, выполняет роль штрафного коэффициента). Заметим, что если стоимости резервируемых элементов примерно равны, то этот критерий можно интерпретировать как минимизацию общего количества элементов системы (а, следовательно, и ее габариты).
В качестве второго критерия оптимизации может рассматриваться величина вероятности безотказной работы всех компонентов системы.
Пусть pj - вероятность безотказной работы j-го элемента без резервирования. Тогда в схеме 1оо2 вероятность безотказной работы имеет вид , а в схеме 2оо3 эта вероятность равна . Таким образом, вторая целевая функция имеет вид:
В итоге, модель выбора вариантов резервирования компонентов стендовой информационно-управляющей системы принимает вид:
, ,
.
4. Генетические алгоритмы
4.1 Общая схема генетического алгоритма
Задача формализуется таким образом, чтобы её решение могло быть закодировано в виде вектора (генотипа) генов, где каждый ген может быть битом, числом или неким другим объектом. В классических реализациях генетического алгоритма (ГА) предполагается, что генотип имеет фиксированную длину. Однако существуют вариации ГА, свободные от этого ограничения.
Некоторым, обычно случайным, образом создаётся множество генотипов начальной популяции. Они оцениваются с использованием функции приспособленности, в результате чего с каждым генотипом ассоциируется определённое значение (приспособленность), которое определяет, насколько хорошо фенотип им описываемый решает поставленную задачу.
Из полученного множества решений (поколения) с учётом значения приспособленности выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются генетические операторы (в большинстве случаев скрещивание и мутация), результатом чего является получение новых решений. Для них также вычисляется значение приспособленности, и затем производится отбор (селекция) лучших решений в следующее поколение.
Этот набор действий повторяется итеративно, так моделируется эволюционный процесс, продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий останова алгоритма. Таким критерием может быть:
нахождение глобального, либо субоптимального решения;
исчерпание числа поколений, отпущенных на эволюцию;
исчерпание времени, отпущенного на эволюцию.
Таким образом, можно выделить следующие этапы генетического алгоритма:
Создание начальной популяции
начало цикла
Отбор (селекция).
Скрещивание (кроссовер).
Мутация.
Формирование новой популяции.
Если условие останова не выполняется, то начало цикла, иначе конец цикла.
4.2 Создание начальной популяции
Один из вариантов задания начальной популяции - взятие случайных особей. Они могут быть очень плохими в смысле приспосабливаемости, однако в результате алгоритма они будут эволюционировать, тем самым в итоге давая хорошие показатели приспосабливаемости.
Другой вариант - взятие начальной популяции из предположительной области оптимума, что может несколько ускорить работу алгоритма.
Обозначим начальную популяцию через , где - i-ая особь (i=1,…, n), n - количество особей в популяции.
4.3 Отбор (селекция)
На каждой итерации с помощью вероятностного оператора отбора выбираются два решения-родителя для их последующ?/p>