The 23 reference contexts in paper V. Terskov A., D. Sheenok A., I. Kartsan N., В. Терсков А., Д. Шеенок А., И. Карцан Н. (2016) “ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ОПТИМИЗАЦИИ АРХИТЕКТУРЫ БОРТОВОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ // GENETIC ALGORITHM FOR OPTIMIZATION OF ONBOARD SOFTWARE ARCHITECTURE” / spz:neicon:sustain:y:2014:i:4:p:102-121

  1. Start
    830
    Prefix
    Ключевые слова: генетический алгоритм, бортовое программное обеспечение, программная избыточность, надежность программного обеспечения. Бортовое программное обеспечение (БПО) автоматизированных систем управления спутниковыми системами связи исполняется на различных типах ЭВМ, характеристики которых определяются назначением систем
    Exact
    [1]
    Suffix
    . Эти факторы влияют на рациональный уровень автоматизации проектирования, на трудоемкость и длительность создания программного обеспечения и т.д. Однако принципы и методы проектирования ПО при этом меняются относительно мало.
    (check this in PDF content)

  2. Start
    1156
    Prefix
    Эти факторы влияют на рациональный уровень автоматизации проектирования, на трудоемкость и длительность создания программного обеспечения и т.д. Однако принципы и методы проектирования ПО при этом меняются относительно мало. БПО, использующееся в АСУ спутниковыми системами связи, обладает всеми свойствами сложных систем
    Exact
    [2]
    Suffix
    . Оно содержит большое количество модулей, тесно взаимодействующих в процессе решения общей целевой задачи. БПО имеет единую цель функционирования – обработку информации и принятие решений для управления объектами, вплоть до формирования соответствующих управляющих воздействий [3].
    (check this in PDF content)

  3. Start
    1436
    Prefix
    Оно содержит большое количество модулей, тесно взаимодействующих в процессе решения общей целевой задачи. БПО имеет единую цель функционирования – обработку информации и принятие решений для управления объектами, вплоть до формирования соответствующих управляющих воздействий
    Exact
    [3]
    Suffix
    . Для обеспечения взаимодействия модулей в едином комплексе широко используются иерархические структуры с несколькими уровнями группирования и подчиненности модулей. Каждый модуль имеет свою целевую задачу и специфический частный критерий качества, как правило, не совпадающий с критерием эффективности всего комплекса программ.
    (check this in PDF content)

  4. Start
    2961
    Prefix
    В компонент программной архитектуры, функционирование которого особо критично по надёжности, может быть введена программная избыточность методом N-версионного программирования или блока восстановления. Очевидно, что надёжность компонентов с программной избыточностью прямо пропорциональна глубине избыточности (или количеству различных его версий)
    Exact
    [4]
    Suffix
    и надёжностью среды исполнения версий (алгоритма голосования или приемочного теста). Надёжность мультиверсионного компонента i на архитектурном уровне j, построенного из K версий методом мультиверсионного программирования для любого K равна [5]: , где pijv – вероятность безотказной работы алгоритма голосования, pijk – вероятность безотказной работы версии k∈Zij.
    (check this in PDF content)

  5. Start
    3205
    Prefix
    Очевидно, что надёжность компонентов с программной избыточностью прямо пропорциональна глубине избыточности (или количеству различных его версий) [4] и надёжностью среды исполнения версий (алгоритма голосования или приемочного теста). Надёжность мультиверсионного компонента i на архитектурном уровне j, построенного из K версий методом мультиверсионного программирования для любого K равна
    Exact
    [5]
    Suffix
    : , где pijv – вероятность безотказной работы алгоритма голосования, pijk – вероятность безотказной работы версии k∈Zij. Надёжность мультиверсионного компонента i на архитектурном уровне j, построенного из K версий методом блока восстановления для любого K равна [5]: , где pijAT – вероятность безотказной работы приемочного теста для компонента i, i=1, .
    (check this in PDF content)

  6. Start
    3466
    Prefix
    компонента i на архитектурном уровне j, построенного из K версий методом мультиверсионного программирования для любого K равна [5]: , где pijv – вероятность безотказной работы алгоритма голосования, pijk – вероятность безотказной работы версии k∈Zij. Надёжность мультиверсионного компонента i на архитектурном уровне j, построенного из K версий методом блока восстановления для любого K равна
    Exact
    [5]
    Suffix
    : , где pijAT – вероятность безотказной работы приемочного теста для компонента i, i=1, .., N на уровне j, j=1,..,M; pijk – вероятность безотказной работы версии k∈Zij. Вероятность сбоя компонента i на уровне j равна: PFij = 1 – Rij.
    (check this in PDF content)

  7. Start
    4019
    Prefix
    При расчете трудоемкости разработки компонентов с программной избыточностью должны учитываться затраты на реализацию среды исполнения версий модуля (NVXij) и затраты на реализацию каждой версии i-го компонента на уровне j ()
    Exact
    [6]
    Suffix
    . Трудоемкость разработки всей системы Ts рассчитывается следующим образом: , где NVXij – трудоемкость разработки среды исполнения версий (приемочного теста для RB или алгоритма голосования для NVP) (N-version execute environment); Bij – бинарная переменная, принимающая значение 1 (тогда NVPij=0, RBij=0), если в программном компоненте не используется программная избыточность, иначе равна 0; N
    (check this in PDF content)

  8. Start
    6381
    Prefix
    в одно и тоже время с компонентом i на уровне j; Nteij – число сбойных компонентов на всех уровнях архитектуры, в которых происходит устранение сбоев во время устранения сбоя в компоненте i на уровне j; Ntuij – число компонентов на всех уровнях архитектуры, используемых в одно и тоже время с компонентом i на уровне j. Далее представлены обозначения параметров модели архитектуры БПО
    Exact
    [7]
    Suffix
    : М – количество архитектурных уровней в программной архитектуре; Nj – количество компонентов на уровне j, j∈ {1,...M}; Dij – множество индексов компонентов, зависимых от компонента i на уровне j, i ∈ {1,.
    (check this in PDF content)

  9. Start
    10541
    Prefix
    среднее время, в течение которого программное обеспечение не может выполнять свои функции; MTTF – среднее время возникновения сбоя в системе, которое определяется как среднее время, в течение которого сбоев в программном обеспечении не возникает; S – коэффициент готовности программной системы; Ts – общая трудоемкость реализации программной системы. Среднее время сбоя в программной системе равно
    Exact
    [8]
    Suffix
    : . Среднее время простоя программной системы равно [8]: . Коэффициент готовности программной системы равен: . Трудозатраты на разработку системы равны: . Для компонентов, в которых возможно введение программной избыточности, могут быть изменены следующие характеристики [9].
    (check this in PDF content)

  10. Start
    10681
    Prefix
    не может выполнять свои функции; MTTF – среднее время возникновения сбоя в системе, которое определяется как среднее время, в течение которого сбоев в программном обеспечении не возникает; S – коэффициент готовности программной системы; Ts – общая трудоемкость реализации программной системы. Среднее время сбоя в программной системе равно [8]: . Среднее время простоя программной системы равно
    Exact
    [8]
    Suffix
    : . Коэффициент готовности программной системы равен: . Трудозатраты на разработку системы равны: . Для компонентов, в которых возможно введение программной избыточности, могут быть изменены следующие характеристики [9].
    (check this in PDF content)

  11. Start
    10895
    Prefix
    Коэффициент готовности программной системы равен: . Трудозатраты на разработку системы равны: . Для компонентов, в которых возможно введение программной избыточности, могут быть изменены следующие характеристики
    Exact
    [9]
    Suffix
    . Метод реализации программной избыточности: мультиверсионное программирование (NVPij=1, RBij=0) или блок восстановления (NVPij=0, RBij=1). Если выбран метод NVP, то устанавливается значение гена равное 0, если RB, то равное 1.
    (check this in PDF content)

  12. Start
    12247
    Prefix
    Для компонентов, в которых не предусматривается введение программной избыточности, изменяется только вариант Var вероятности сбоя компонента и соответствующей трудоемкости для достижения этой вероятности сбоя (1 ≤ Var ≤ Кол-во вариантов для данного компонента). Таким образом, фенотип особи (решения) формируется из переменных характеристик программных компонентов
    Exact
    [10]
    Suffix
    . В таблице 1 представлен общий вид фенотипа с примером аллелей. Таблица 1. Фенотип особи Группа компонентов, с возможностью программной избыточности Группа компонентов, без возможности программной избыточности Компонент 1 .
    (check this in PDF content)

  13. Start
    13520
    Prefix
    Филипченко, было доказано, что наряду с «основным» геном, определяющим признак, существует ряд генов-модификаторов этого признака. Подобный тип наследования встречается часто. Таким образом, фенотип, как правило, представляет собой результат сложного взаимодействия генов
    Exact
    [11]
    Suffix
    . Таким образом, введем понятие «связанные гены». Связанные гены – это гены, взаимная комбинация которых осуществляет влияние на определенный признак особи. Надёжность и трудозатраты для компонентов с возможной программной избыточностью определяются взаимодействующими генами версий и метода избыточности.
    (check this in PDF content)

  14. Start
    15109
    Prefix
    Выбор любой альтернативы «вероятность сбоя/трудоемкость» равновероятен. 2. Выбор любого варианта «вероятность сбоя/трудоемкость» происходит вероятностью распределенной по закону нормального распределения вероятностей для дискретной случайной величины
    Exact
    [12]
    Suffix
    . При этом выбор текущего значения варианта невозможен. При мутации генов версий программных компонентов, для которых возможно значение 0 (отсутствие версии), такое значение добавляется как дополнительное возможное значение.
    (check this in PDF content)

  15. Start
    15937
    Prefix
    Распределение вероятностей выбора варианта Отсутствие версии Вар. 1Вар. 2Вар. 3 Вар. 4 (текущий) Вар. 5Вар. 6Вар. 7 0.0156250.093750.2343750.312500.2343750.093750.015625 Генетический алгоритм основан на идеях метода с независимой селекцией Шаффера при многокритериальной оптимизации VEGA (Vector Evaluated Genetic Algorithm)
    Exact
    [13]
    Suffix
    . Селекция происходит с вероятностью, пропорциональной значению критерия. Вероятность индивида быть отобранным по критерию S рассчитывается по формуле [14]: где fi – пригодность индивида i; – средняя пригодность популяции; N – размер популяции; .
    (check this in PDF content)

  16. Start
    16091
    Prefix
    . 4 (текущий) Вар. 5Вар. 6Вар. 7 0.0156250.093750.2343750.312500.2343750.093750.015625 Генетический алгоритм основан на идеях метода с независимой селекцией Шаффера при многокритериальной оптимизации VEGA (Vector Evaluated Genetic Algorithm) [13]. Селекция происходит с вероятностью, пропорциональной значению критерия. Вероятность индивида быть отобранным по критерию S рассчитывается по формуле
    Exact
    [14]
    Suffix
    : где fi – пригодность индивида i; – средняя пригодность популяции; N – размер популяции; . Вероятность индивида быть отобранным по минимизируемому критерию Ts рассчитывается по формуле [15]: где fi – пригодность индивида i; C – константа, определяющая минимальную пригодность популяции; ; N – размер популяции; .
    (check this in PDF content)

  17. Start
    16281
    Prefix
    Вероятность индивида быть отобранным по критерию S рассчитывается по формуле [14]: где fi – пригодность индивида i; – средняя пригодность популяции; N – размер популяции; . Вероятность индивида быть отобранным по минимизируемому критерию Ts рассчитывается по формуле
    Exact
    [15]
    Suffix
    : где fi – пригодность индивида i; C – константа, определяющая минимальную пригодность популяции; ; N – размер популяции; . В рассматриваемом алгоритме константа C равна максимальной пригодности особи в популяции.
    (check this in PDF content)

  18. Start
    16865
    Prefix
    При определении пригодности особи значения S и Ts рассчитываются по алгоритму, изображенном на рис. 1. Каждая особь с рассчитанными критериями записывается в массив. Перед тем как рассчитывать критерии для следующей особи происходит поиск аналогичной уже рассчитанной ранее особи
    Exact
    [10]
    Suffix
    . Это действие целесообразно и позволяет сэкономить время работы алгоритма, т.к. расчет критериев значительно дольше поиска идентичной особи в массиве решений. Для решения многокритериальной задачи условной оптимизации необходимо использовать подход, основанный на сведении условной задачи к безусловной.
    (check this in PDF content)

  19. Start
    17480
    Prefix
    Решения задачи с ограничениями должны не только принадлежать множеству Парето, но и находиться в допустимой области. Поэтому к предложенному алгоритму дополнительно вводится процедура, позволяющая стягивать решения в допустимую область
    Exact
    [14]
    Suffix
    . Чтобы стало возможным решение задачи условной оптимизации, каждое ограничение рассматривается как отдельная целевая функция, и поэтому изначально условная задача с несколькими целевыми функциями сводится к безусловной многокритериальной задаче оптимизации.
    (check this in PDF content)

  20. Start
    17834
    Prefix
    Чтобы стало возможным решение задачи условной оптимизации, каждое ограничение рассматривается как отдельная целевая функция, и поэтому изначально условная задача с несколькими целевыми функциями сводится к безусловной многокритериальной задаче оптимизации. Преобразование исходной задачи условной многокритериальной оптимизации имеет следующий вид
    Exact
    [14]
    Suffix
    : Целевые функции исходной задачи – F(X) → opt, ограничения исходной задачи – G(X)≤ B. Целевые функции преобразованной задачи – F(X) → opt, ограничения преобразованной задачи – |G(X) – B|→ opt. В первую очередь несколько итераций алгоритма решается исходная условная задача, но без учета ограничений.
    (check this in PDF content)

  21. Start
    18585
    Prefix
    Затем, чтобы получить большее число решений, принадлежащих допустимой области, поиск продолжается уже без учета целевых функций исходной задачи, а только по ограничениям. Таким образом, поиск решений производится только по функциям-ограничениям, что приводит большую часть популяции в допустимую область, но с потерей качества решений по критериям оптимизации
    Exact
    [14]
    Suffix
    . Генетический алгоритм многокритериальной условной оптимизации программной архитектуры [16] также основан на идеях метода VEGA (Vector Evaluated Genetic Algorithm) с независимой селекцией Шаффера при многокритериальной оптимизации.
    (check this in PDF content)

  22. Start
    18677
    Prefix
    Таким образом, поиск решений производится только по функциям-ограничениям, что приводит большую часть популяции в допустимую область, но с потерей качества решений по критериям оптимизации [14]. Генетический алгоритм многокритериальной условной оптимизации программной архитектуры
    Exact
    [16]
    Suffix
    также основан на идеях метода VEGA (Vector Evaluated Genetic Algorithm) с независимой селекцией Шаффера при многокритериальной оптимизации. Отличие алгоритма от ГА безусловной оптимизации состоит в том, что в нем каждое ограничение рассматривается как дополнительный критерий оптимизации.
    (check this in PDF content)

  23. Start
    22144
    Prefix
    Недоминируемые решения, полученные на каждой итерации, отбираются в множество Парето. Решения множества Парето не могут быть предпочтены друг другу, поэтому после его формирования задача может считаться математически решенной
    Exact
    [17]
    Suffix
    . Разработанный генетический алгоритм был протестирован на специально подготовленных задачах, а также был использован при разработке программного обеспечения корпоративных систем управления, и БПО. С помощью разработанного ГА все задачи были решены, а также найдены эффективные архитектурные решения.
    (check this in PDF content)