Содержание к диссертации
Введение
Глава 1. Постановка задачи выбора сбалансированного набора МОО для РВС 20
1.1. Содержательная постановка задачи выбора сбалансированного набора МОО для РВС 20
1.2. Основные понятия и обозначения 21
1.3. Оценка надёжности, стоимости РВС в целом 24
1.4. Формальная постановка задачи 26
1.5. NP-сложность задачи 27
1.6. Особенности задачи 28
1.7. Выводы 29
Глава 2. Математическая модель организации РВС с МОО 30
2.1. Виды борьбы с неисправностями и отказами 30
2.2. Методы обеспечения отказоустойчивости 33
2.3. Оценка надёжности модуля РВС при использовании МОО 61
2.4. Оценка стоимости модуля РВС при использовании МОО 65
2.5. Ограничения и допущения рассматриваемой модели 67
2.6. Выводы 68
Глава 3. Обзор методов решения задачи выбора сбалансированного набора МОО для РВС 69
3.1. Критерии включения статей в обзор 69
3.2. Классификация постановок задач оптимизации надёжности 71
3.3. Классификация методов решения задач оптимизации надёжности 84
3.4. Отбор алгоритмов для решения задачи выбора сбалансированного набора МОО для РВС 85
3.5. Выводы 88
Глава 4. Метод решения задачи выбора сбалансированного на бора МОО для РВС 89
4.1. Генетические и эволюционные алгоритмы 89
4.2. Адаптивный эволюционный алгоритм 95
4.3. Самообучающийся эволюционный алгоритм 103
4.4. Выводы 114
Глава 5. Описание программного средства 115
5.1. Программное средство RelOpt для решения задачи выбора сбалансированного набора модулей РВС и МОО 115
5.2. Интеграция программного средства RelOpt с системой моделирования ДИАНА 121
5.3. Выводы 125
Глава 6. Экспериментальное исследование разработанного метода 126
6.1. Цель экспериментального исследования 126
6.2. Методика проведения экспериментов 127
6.3. Описание экспериментальных вычислительной системы 129
6.4. Результаты экспериментов 133
6.5. Выводы 138
Заключение 140
Литература 142
- Оценка надёжности, стоимости РВС в целом
- Оценка стоимости модуля РВС при использовании МОО
- Классификация методов решения задач оптимизации надёжности
- Интеграция программного средства RelOpt с системой моделирования ДИАНА
Введение к работе
Актуальность работы.
Одной из краеугольных характеристик распределённой вычислительной системы (РВС) (термин РВС определён в работе) является её надёжность. Под надёжностью РВС будем понимать способность РВС сохранять свою работоспособность при определённых спецификацией условиях в течение заданного периода времени. Для количественной оценки надёжности вводят меру надёжности, как вероятность безотказной работы в течение интервала [0, ten(j\ при условии, что система находится в работоспособном состоянии в момент времени t=0.
Надёжность РВС можно повысить двумя основными способами:
-
Использование более надёжных отдельных модулей, из которых состоит система;
-
Использование одного или нескольких механизмов обеспечения отказоустойчивости (МОО) на уровне модулей РВС.
Оба этих подхода приводят к увеличению стоимости и/или уменьшению производительности РВС. Поэтому при проектировании РВС необходимо увеличивать надёжность сбалансированно, то есть необходимо выбрать набор МОО и версии аппаратных и программных компонентов модулей РВС так, чтобы обеспечить максимальную надёжность РВС в целом при ограничениях на стоимость. Данная задача в работе называется задачей выбора сбалансированного набора модулей и МОО для РВС или, более кратко, задача выбора сбалансированного набора МОО для РВС. Эта задача относится к задачам, которые в литературе называются задачами оптимизации надёжности вычислительной системы.
Надо сразу отметить, что задача, в которой максимизируется надёжность вычислительной системы при ограничении на стоимость системы рассматривалась разными исследователями начиная с 60-х годов прошлого века и было показано, что она является NP-трудной. В большинстве опубликованных работ в качестве МОО рассматривалось
1 Смелянский Р. Л. Модель функционирования распределённой вычислительной системы с време
нем // Программирование. — 2013. — № 5. — С. 22-34
2 Kuo W., Wan R. Recent advances in optimal reliability allocation //Computational intelligence in
reliability engineering. - Springer Berlin Heidelberg, 2007. - p. 1-36
3 Chern M. S. On the computational complexity of reliability redundancy allocation in a series system
//Operations research letters. - 1992. - T. 11. - N. 5. - p. 309-315
исключительно аппаратное резервирование и оценивалась надёжность отдельно для аппаратных или только для программных компонентов модуля РВС. В некоторых работах авторы допускают возможность использования набора МОО, но он не включал в себя все имеющиеся МОО. Для РВС рассмотрение аппаратной и программной составляющих РВС по отдельности не позволяет адекватно оценивать надёжность системы. Поэтому для оценки надёжности всей системы необходимо рассматривать надёжность аппаратуры и программ в комплексе.
Настоящая диссертация посвящена исследованию алгоритмов выбора сбалансированного набора модулей РВС и МОО для модулей РВС в следующей постановке. Пусть нам задана РВС в виде набора модулей и структуры связей между модулями РВС (то есть топология РВС). Каждый модуль может быть построен с помощью хотя бы одного аппаратного и программного компонентов. К каждому модулю может применяться один из заданных МОО. Каждый компонент может иметь несколько версий. Количество аппаратных и программных компонентов в модуле зависит от МОО, используемого для модуля. Тем самым возникает несколько вариантов построения РВС. Требуется выбрать сбалансированный набор вариантов модулей РВС, эффективный по определенным критериям на множестве возможных вариантов построения РВС.
Актуальность определяется широкой распространенностью РВС , использованием этого типа систем во всех критически важных технически сложных объектах , а также отсутствием в свободном доступе работ, которые в полной мере позволяют решать задачу оптимизации надёжности для РВС, использующих различные МОО для каждого модуля.
Цель работы. Целью диссертационной работы является разработка алгоритмов и исследование их свойств для решения задачи сбалансированного выбора модулей РВС и МОО, с учётом индивидуального набора МОО для каждого модуля РВС.
Для достижения поставленной цели необходимо решить следующие задачи:
Построить формальную модель организации РВС при наличии МОО. Данная модель должна позволять учитывать наборы МОО, используемые в модулях РВС и предоставлять способ расчёта надёжности и стоимости модуля РВС при наличии МОО, исходя из особенностей каждого модуля.
4 Радченко Г.И., Распределенные вычислительные системы. - Челябинск. - Фотохудожник, 2012. -
184 с.
5 Колесов Н.В., Толмачева М.В., Юхта П.В. Системы реального времени. Планирование, анализ,
диагностирование. - Санкт-Петербург: ОАО «Концерн «ЦНИИ «Электроприбор», 2014. - 180с.
Провести аналитический обзор постановок задачи оптимизации надёжности вычислительных систем и методов их решения для схожих задач и провести анализ возможности их применения для сформулированной задачи.
Разработать алгоритмы решения задачи выбора сбалансированного набора модулей и МОО для РВС, индивидуально для каждого модуля.
На основе разработанных алгоритмов реализовать прототип инструментальной системы и провести экспериментальное исследование предложенных алгоритмов.
Методы исследования. При получении основных результатов диссертации использовались методы теории надёжности, математической статистики и методы оптимизации.
Научная новизна. В диссертации сформулирована новая математическая постановка задачи выбора сбалансированного набора модулей и МОО для РВС. Новизна постановки заключается в возможности выбора своего МОО для каждого модуля РВС. Разработаны и исследованы алгоритмы решения этой задачи, в классе адаптивных эволюционных алгоритмов. Разработанные алгоритмы применимы для нескольких РВС с различными исходными данными без перенастройки параметров алгоритмов.
Теоретическая и практическая ценность. Теоретическая ценность работы состоит в постановке новой оптимизационной задачи, разработке математической модели организации РВС при наличии МОО и новых алгоритмов в классе адаптивных эволюционных алгоритмов, исследованию их свойств на тестовых и реальных данных.
Практическая значимость обусловлена тем, что разработанные алгоритмы и программные средства обеспечивают поддержку процесса разработки новых РВС и модернизации существующих.
Апробация работы. Результаты, представленные в работе, докладывались на научных семинарах лаборатории Вычислительных комплексов кафедры Автоматизации систем вычислительных комплексов факультета ВМК МГУ под руководством чл.-корр. РАН, профессора Р.Л. Смелянского, семинаре кафедры Автоматизации систем вычислительных комплексов имени чл.-корр. РАН, профессора Л.Н. Королёва, научно-практическом семинаре "Технологии разработки и анализа программ "под руководством профессора А.К. Петренко, а также на 19 конференциях, в том числе:
Третья европейская конференция по аэрокосмическим наукам (3rd European Conference
for Aerospace Sciences, EUCASS'2009) (Франция, Версаль, июль 2009 г.);
III Всероссийская научная конференция «Методы и средства обработки информации» (МСО-2009) (Россия, Москва, 6-8 октября 2009 г.)
Шестая международная конференция по надёжности компьютерных систем (Sixth International Conference on Dependability of Computer Systems, DepCos-RELCOMEX 2011) (Польша, Брюнов, 27 июня - 1 июля 2011 г.)
Четвёртая европейская конференция по аэрокосмическим наукам (4th EUCASS European Conference for Aero-Space Sciences, EUCASS'2011) (Россия, Санкт-Петербург, 4-8 июля 2011 г.)
Международная научно-практическая конференция «Имитационное и комплексное моделирование морской техники и морских транспортных систем» - «ИКМ МТМТС 2015». (Россия, Санкт-Петербург, 1 июля 2015 г.);
VIII Московская Международная конференция по исследованию операций (ORM-2016) (Россия, Москва, октябрь 2016 г.);
Диссертационная работа была выполнена в рамках проведения прикладных научных исследований, выполняемых по Соглашению с Министерством науки и образования о предоставлении субсидии №14.579.21.0010 от "05" июня 2014 года по теме "Технология и программное обеспечение распределенных и высокопроизводительных вычислительных систем. Хранение и обработка больших данных".
Личный вклад автора заключается в выполнении основного объема теоретических и экспериментальных исследований, изложенных в диссертационной работе, включая разработку алгоритмов и проведение экспериментальных исследований, формулировку и доказательство приведенных утверждений, анализ и оформление результатов в виде публикаций и научных докладов. В опубликованных совместных работах постановка и исследование задач осуществлялись совместными усилиями соавторов при непосредственном участии соискателя.
Публикации. По теме диссертации опубликовано 12 печатных работ, 3 из них опубликованы в журналах «Моделирование и анализ информационных систем», «Программирование», «Прикладная информатика», входящих в перечень ведущих научных журналов ВАК РФ, 2 работы индексируются системой Scopus. Список работ приводится в конце автореферата.
Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения и списка литературы. Объём работы — 161 страница. Список литературы содержит 145 наименований. Диссертация снабжена 18 рисунками и 14 таблицами.
Оценка надёжности, стоимости РВС в целом
В каждом модуле РВС выделяются точки доступа к услугам других модулей. Внешняя среда и человек-оператор РВС будут рассматриваться как специфичные модули РВС. Состоянием модуля назовем совокупность значений его элементов памяти (ячеек ОЗУ, ПЗУ, регистров и т.д.) доступных в точке предоставления услуг модуля. Состояния модуля в точках предоставления услуг этого модуля будем называть внешними, а остальные внутренним/и. То есть, если модуль состоит из нескольких модулей, то внешние состояния внутренних модулей являются внутренними состояниями для внешнего/объемлющего модуля. Действием модуля РВС будем называть смену состояния модуля. Поведением модуля РВС будем называть все последовательности действий модуля [61].
Услугой, предоставляемой модулем, будем называть поведение модуля, влияющее на состояния, а может быть, и на поведение других модулей РВС. Услуга является корректной, если внешние состояния модуля соответствуют функциональной спецификации системы. Услуга может быть распределённой, то есть складываться из внешних состояний нескольких модулей, но мы для простоты изложения не будем рассматривать этот случай.
Будем говорить об отказе услуги, если предоставляемая услуга некорректна. Если в модуле произошёл отказ хотя бы одной из услуг, то будем говорить об отказе модуля или просто отказе. Ошибка - это отклонение одной из частей внутреннего состояния от ожидаемого. Поскольку услуга -это последовательность состояний, то некоторые ошибки могут не изменять внешних состояний модуля и не приводить к отказу. Причину ошибки будем называть неисправностью.
Под надёжностью РВС будем понимать способность РВС сохранять корректность услуг, при определенных спецификацией условиях, в течение заданного периода времени. Для количественной оценки надёжности вводят меру надёжности, как вероятность безотказной работы (то есть отсутствие отказов услуг) в течении интервала [0, ten(j\ при условии, что система находится в работоспособном состоянии в момент времени t=0 [99].
Для обеспечения необходимого значения надёжности применяют МОО, предотвращающие отказ РВС при отказах её модулей. МОО работают на этапе эксплуатации РВС и предотвращают отказ при возникновении ошибки. Каждый МОО содержит в себе нескольких версий программных и аппаратных компонентов и дополнительных компонентов, обеспечивающих совместную работу выбранных аппаратных и программных компонентов. Дополнительные компоненты имеют свои характеристики надёжности и стоимости. Также их использование увеличивает время работы модуля. Набор дополнительных компонентов специфичен для каждого МОО. В разделе 2.2 проводится выбор МОО для РВС и приводится подробное описание выбранных МОО.
Для формального описания структуры РВС введём следующие обозначения: P. Hi г - мультимножество версий Hij, выбранных для аппаратного компонента модуля Uf S-г - мультимножество версий Sij, выбранных для программного компонента модуля Uf {Ні % Si % Fi} — конфигурация і-ого модуля; System = {{Нр, Sp, Fi}\i Є [1,W]} - конфигурация РВС; Systems — множество всех корректных конфигураций; ЩТ і СІГ — надёжность и стоимость j -ой версии аппаратного компонента модуля Uі] Щ7і 1Г — надёжность и стоимость j -ой версии программного компонента модуля Uf С " — стоимость дополнительных аппаратных компонентов к-го элемента множества доступных элементов MOO {FTi) для модуля Uf С-}? — стоимость дополнительных программных компонентов к-го элемента множества доступных элементов MOO {FT) для модуля Uf Xij, yij — количество основных экземпляров Hij и Sij в модуле Ui. Может принимать только значение 0 или 1;
Для оценки надёжности РВС, состоящей из модулей, которые в свою очередь состоя из компонент, надёжность которых известна в литературе рассматриваются различные методы расчёта показателей надёжности [42]. Прежде всего стоит выделить методы: параллельно-последовательного расчёта [39, 54]; марковского моделирования [10, 31]; деревьев отказов [46, 52]; логико-вероятностные методы расчёта надёжности [32, 36].
В данной работе, как было указано ранее, одним из условий сохранения работоспособности РВС является функционирование всех модулей РВС в течении всего интервала работы системы. Таким образом структура системы с точки зрения надёжности является последовательной, а значит для оценки надёжности применим метод параллельно-последовательного расчёта. В соответствии с этим методом будем оценивать:
Оценка стоимости модуля РВС при использовании МОО
Традиционным методом обеспечения отказоустойчивости вычислительных систем на уровне аппаратных средств является их резервирование, то есть внесение в систему аппаратной избыточности за счет добавления в неё дополнительных функционально идентичных аппаратных компонентов. По составу резервирование можно разделить на два типа: 1. резервирование с использованием различных компонентов; 2. резервирование без использования различных компонентов. Резервирование с использованием различных компонентов - основано на проектном разнообразии аппаратных компонентов. Для резервирования используются функционально идентичные аппаратные компоненты, но имеющие разных производителей, разные технические характеристики, разную стоимость, срок службы, использующие разные технологии и конструкторские решения.
Резервирование без использования различных компонентов, заключается в том, что для резервирования используются одинаковые аппаратные компоненты.
При резервировании на уровне системы к существующей системе добавляется еще одна, функционально идентичная первой. Во втором случае в систему добавляются дополнительные модули, функционально эквивалентные некоторым модулям в ней. При резервировании на уровне компонентов в отдельные модули добавляются дополнительные компоненты и связи.
Общая схема работы. При активном резервировании в вычислительной системе параллельно работают два или более функционально идентичных аппаратных компонентов, выполняющих одинаковые задачи. Выходные данные Аппаратный компонент 1 Аппаратный компонент 2 Аппаратный компонент N Пример использования активного резервирования компонентов обрабатываются специальным дополнительным простым компонентом, который принимает решение о правильности работы компонентов по принципу большинства. Он называется модулем принятия решения. На рисунке 2.3 приведен пример использования активного резерва (или его иногда называют N-модульной избыточностью). Аппаратный компонент (устройство) системы дублируется (N-1) раз.
Достоинства метода. Метод достаточно простой и эффективный. Значительных изменений в структуру вычислительной системы и алгоритмы активное резервирование не вносит. Все компоненты являются активными.
Недостатки метода. Использование в системе дополнительных (N-1) функционально идентичных аппаратных компонента приводит к существенному увеличению энергопотребления системы и её габаритов.
Применимость в РВС. Использование активного резервирования в вычислительной системе для некоторого аппаратного компонента стоимостью Cost приводит к увеличению стоимости системы на (N-l) Cost. Однако при N=3 данный МОО будет удовлетворять выбранному критерию на стоимость его в РВС. Таким образом, активное резервирование при N=3 удовлетворяет всем критериям отбора.
Резервирование с замещением
Общая схема работы. При резервировании с замещением в вычислительной системе функционирует один из компонентов (основной), резервный компонент находится в отключенном состоянии и подключается только в случае отказа основного.
Достоинства метода. По сравнению с методом активного резервирования главное достоинство данного метода заключается в том, что его использование не приводит к увеличению энергопотребления системы, поскольку в работе всегда находится только один аппаратный компонент. Метод прост и эффективен. Не вносит существенных изменений в структуру и алгоритмы функционирования.
Недостатки метода. Сложность резервирования с замещением заключается в том, что в момент замещения резервный аппаратный компонент должен иметь внутренние состояния, идентичные состоянию основного. Для решения этой проблемы системе могут потребоваться дополнительные временные и вычислительные затраты. В свою очередь в системах с активным резервированием большинство внутренних состояний компонентов идентичны, поскольку они работают одновременно с одними и теми же входными данными и исполняют одну и ту же программу. Данный метод имеет и недостаток, связанный с увеличением габаритов системы. Стоимость вычислительной системы возрастает так же как и при активном резервировании. Применимость в РВС. Резервирование с замещением не удовлетворяет критерию активности всех компонентов в системе, поэтому не может быть включено в множество доступных МОО для РВС.
В данном подразделе рассматриваются различные МОО программной составляющей вычислительных систем.
Программные МОО необходимы для того, чтобы придать системе устойчивость к программным ошибкам, которые остаются в системе после их разработки. Обычно программные методы отказоустойчивости разрабатываются одновременно с разработкой основного программного обеспечения вычислительной системы.
Классификация методов решения задач оптимизации надёжности
Общая схема работы. Впервые метод N-самоконтролируемого программирования был разработан Лаприе в 1987-1988 годах [100]. Самоконтролирующиеся программы используют программную избыточность, чтобы контролировать собственное поведение во время выполнения.
Пример использования метода N-самоконтролируемого программирования при N=4 приведен на рисунке 2.9.
С точки зрения аппаратной составляющей требуется четыре аппаратных компонента, сгруппированных по парам. На каждом аппаратном компоненте выполняется одна версия программы. С точки зрения программной составляющей, для каждой пары аппаратных компонентов необходимо либо две версии программы и алгоритм сравнения, либо одна версия программы и контрольный тест. На рисунке 2.9 изображён первый случай.
Принцип работы метода заключается в следующем. Параллельно запускаются на выполнение все четыре версии программы, разбитые на две пары. Затем результаты внутри каждой пары сравниваются между собой. В том случае, если результаты не совпали, то выдается сообщение об ошибке для данной пары. Если результаты в паре совпали, то этот результат сравнивается с результатом другой пары. Если результаты пар совпали, то программа выполнена успешно. В том случае, если одна из пар выдает сообщение об ошибке, а вторая нет, то в качестве итогового принимается результат
В общем случае, для метода N-самоконтролируемого программирования необходимо N версий программы, выполняющихся на N/2 парах аппаратных компонентов. Если N - нечетное число, то используется дополнительная копия одной из версий программы.
Данный метод сочетает в себе достоинства и недостатки аппаратного метода активного резервирования и программного метода N-версионного программирования.
Достоинства метода. За счёт аппаратного резервирования и использования нескольких версий программы, работающих на разных аппаратных ком понентах, увеличивается вероятность получения правильного результата и, соответственно, надежность функционирования системы.
Недостатки метода. Метод имеет сложный принцип работы. Применение данного метода значительно увеличивает стоимость по сравнению с вышеперечисленными методами, поскольку требует не только N-версий программы, но и N/2 аппаратных компонентов. Применимость в РВС. Ввиду указанных недостатков данный метод не проходит по критериям для использования в РВС. Метод переконфигурирования системы Общая схема работы. Идея метода переконфигурирования системы заключается в том, что при отказе какого-либо компонента системы все данные с этого компонента перераспределяются между другими компонентами без остановки работы системы. Этот метод часто применяют в системах реального времени, так как он позволяет продолжить работу системы без существенных задержек по времени. Общая схема работы метода переконфигурирования представлена на рисунке 2.10.
Достоинства метода. Данный метод является эффективным в случае, если память и время являются важными, а также, если возникает ошибка наподобие потери данных. Существенных затрат при использовании данного МОО в вычислительной системе не требуется.
Недостатки метода. Метод требует получения информации об ошибках. Возможны временные задержки при перераспределении данных с отказавше Вычислитель 1
Общая схема работы метода переконфигурирования го компонента между другими компонентами системы. Использование данного метода связано с изменением структуры отказавшего компонента и далеко не всегда задачи, выполняющиеся на одном аппаратном компоненте, могут выполняться на других, поэтому переконфигурирование системы применимо не всегда.
Применимость в РВС. Данный механизм не может быть выбран, поскольку приводит к изменению структуры вычислительной системы и имеет ограниченную область применения.
Активное резервирование и N-версионное программирование Общая схема работы. Данный МОО основан на совместном использовании активного резервирования аппаратных компонентов и методе N-версион-ного программирования для программных компонентов, сочетает в себе их достоинства и недостатки, и имеет простую идею: на каждом из N аппаратных компонентов выполняется по одной версии программы. Достоинства метода. Данный метод прост, эффективен и достаточно часто применяется на практике. Все компоненты являются активными. Существенных изменений в структуру системы и алгоритмы данный механизм отказоустойчивости не вносит.
Недостатки метода. Достаточно высокая стоимость метода: стоимость N экземпляров аппаратного компонента и N версий программ.
Применимость в РВС. При N=3 данный метод будет удовлетворять критерию использования МОО для РВС. При N=1, данный механизм совпадает с методом активного резервирования. Активное резервирование и метод восстановления блоками
Общая схема работы. Данный МОО был предложен в [138] и основан на совместном использовании активного резервирования аппаратных компонентов и метода восстановления блоками для программных компонентов, но сложность его организации ниже метода восстановления блоками в оригинальном варианте. Для метода требуется N версий программ, М одинаковых аппаратных компонентов и контрольный тест. По N версий программы устанавливается на каждом из аппаратных компонентов. При инициализации этого модуля системы запускаются на выполнение первые версии на каждом из аппаратных компонентов. Если по принципу большинства удается установить правильное решение, то работа метода заканчивается, в противном случае запускаются вторые версии программы и так далее.
Интеграция программного средства RelOpt с системой моделирования ДИАНА
Утверждение 4.1. Предложенный алгоритм A3 А обладает свойствами корректности и полноты.
Доказательство. 1) Докажем корректность алгоритма. Алгоритм является корректным, если в ходе его работы не могут появиться некорректные решения. Назовем ген некорректным, если он задает несуществующую конфигурацию соответствующего модуля. Пусть, например, для модуля і доступно три варианта аппаратного компонента, тогда ген (5,3,0), задающий конфигурацию модуля і, является некорректным. Решение является корректным тогда и только тогда, когда все его гены корректны. A) Операция генерации начальной популяции устроена так, что все ре шения начальной популяции корректны. Новые решения могут появиться в результате выполнения операций скрещивания и мутации. Б) В ходе скрещивания новых генов не образуется, решение-потомок лишь наследует гены родительских решений. Поэтому из корректности родительских решений следует корректность решения-потомка. B) В ходе мутации некорректных генов получиться не может. Это следует из самого определения данной операции в разделе 4.2. Следовательно, не может получиться и некорректных решений. Из пунктов А), Б) и В) следует, что в ходе работы алгоритма некорректные решения не могут появиться в популяции. Корректность доказана.
2) Докажем полноту алгоритма. Алгоритм является полным, если в ходе его работы может быть получено любое корректное решение. Так как при формировании начальной популяции каждый ген каждого решения генерируется случайным образом, то в популяцию с равной вероятностью может попасть любое корректное решение. Из определения операции мутации в разделе 4.2 следует, что с равной вероятностью может мутировать любой ген решения. При этом с равной вероятностью может быть получен любой вариант этого гена. Отметим также, что вероятность попадания корректного решения в следующую популяцию никогда не равна нулю. Таким образом, любое корректное решение может быть получено в ходе работы алгоритма. Полнота доказана.
Для сравнения предложенного метода и существующих алгоритмов было проведено экспериментальное исследование, результаты которого приведены в главе 6.
Так же, как и в АЭА, идея СЭА заключается в изменении параметров мутации и скрещивания решений. Для этого вводятся индивидуальные параметры вероятности мутации и скрещивания для каждого решения из популяции, которые меняются после каждой итерации в зависимости от того, насколько удачным или неудачным оказалось применение конкретной операции к решению. Индивидуальные вероятности мутации и скрещивания хранятся в векторах Mmut и Мсгоаа соответственно, где i-ый элемент является значением соответствующего параметра для і-го элемента популяции.
Схема предлагаемого метода решения задачи, поставленной в разделе (1.4) представлена на рисунке 4.2. Начальное и конечное состояние алгоритма СЭА выделено жёлтым цветом. Голубым выделены шаги, которые присутствуют в КГА, а зелёным шаги, которые являются специфичными для 103 Рассмотрим шаги алгоритма СЭА более подробно: 1. Кодирование решения. Аналогично АЭА каждое решение задачи выбора сбалансированного набора МОО кодируется в виде строки. Строка состоит из блоков, которые соответствуют модулям РВС. Каждый блок (ген) представляет собой тройку вида Н, S, F . Н - это номер конфигурации аппаратной составляющей модуля, S - это номер конфигурации программной составляющей, a F - это порядковый номер МОО из множества FTavau, используемого в данном модуле. По каждой строке может быть вычислена целевая функция - надёжность системы Rsystemi которая характеризует качество решения, и однозначно восстановлена соответствующая конфигурация РВС. пит - число особей в начальной популяции (параметр алгоритма). 2. Подготовка популяции решений. Генерация случайным образом популяции решений Systerrik,k Є [1,raim], для первой итерации алгоритма берётся популяция с предыдущей итерации алгоритма. 3. Начальная оценка популяции. На этом этапе происходит вычисление целевой функции Rgystem и проверка ограничений стоимости С system Cistern- ЕСЛИ рЄНІЄНИЄ НЄ уДОВЛЄТВОрЯЄТ Ограничениям, ТО ОНО штрафуется. Подробнее использование штрафных функций описано в п. 10 (оценка популяции). 4. Выполнение операции селекции. В данном алгоритме использует ся пропорциональная схема селекции [9]. Популяция сортируется, от бираются лучшие Х% (изменяемый параметр) особей, наилучших по значению целевой функции, которые затем участвуют в операции скре щивания.