Содержание к диссертации
Введение
ГЛАВА 1. Анализ математических методов моделирования и численных методов оптимизации в задачах оптимизации систем прогнозирования граничных состояний сложного объекта 16
1.1. Анализ задач моделирования при оптимизации систем прогнозирования достижения граничных состояний сложного объекта 16
1.2. Основные проблемы математического моделирования и численных методов оптимизации в задачах прогнозирования риска достижения граничных состояний 24
1.3. Основные проблемы математического моделирования и численных методов оптимизации в задачах отбора и формирования прогностических признаков 31
1.4. Основные проблемы математического моделирования и численных методов оптимизации при разработке методов планирования процесса натурного эксперимента для систем прогнозирования граничных состояний. 41
1.5. Структура дуальной вычислительной среды для решения задачи оптимизации систем прогнозирования граничных состояний сложного объекта 49
Выводы первой главы 53
ГЛАВА 2. Разработка математических моделей прогнозирования риска достижения объектом граничного состояния 55
2.1. Моделирование риска потери управляемости сложной системы с помощью d-оценок 55
2.2. Исследование свойств оценок риска для некоторых базовых классов плановых траекторий 64
2.3. Прогнозирование изменения параметров системы с помощью
комитета нейроэкспертов для получения оценок будущего риска 72
Выводы второй главы 82
ГЛАВА 3. Формирование и исследование оптимизационных моделей и численных методов минимизации избыточности систем прогнозирования достижения граничных состояний 83
3.1. Построение оптимизационных моделей и формирование эквивалентных задач оптимизации 83
3.2. Разработка алгоритмов решения задач минимизации избыточности систем прогнозирования достижения граничных состояний 98
3.3. Минимизация избыточности систем прогнозирования с использованием репликативных нейронных сетей 130
Выводы третьей главы 130
ГЛАВА 4. Разработка и исследование моделей и алгоритмов оптимизации надежности систем прогнозирования граничных состояний . 138
4.1. Оптимизационная модель задачи повышения надежности системы прогнозирования граничных состояний при многовариантном резервировании ее компонентов 138
4.2. Метод ветвей и границ для решения задачи повышения надежности системы прогнозирования граничных состояний при многовариантном резервировании ее компонентов 145
4.3. Генетический алгоритм для решения задачи повышения надежности системы прогнозирования граничных состояний при многовариантном резервировании ее компонентов 158
4.4. Формирование процедур нейросетевого резервирования при решении задачи повышения надежности системы прогнозирования граничных состояний 167
Выводы четвертой главы 169
ГЛАВА 5. Построение и исследование моделей и алгоритмических процедур оптимизации процессов восстановления исходного состояния сложного объекта 171
5.1. Решение задачи оптимизации восстановления исходного состояния сложного объекта в нечеткой многокритериальной постановке 171
5.2. Применение растущей нейронной сети для решения задачи оптимизации восстановления исходного состояния сложного объекта
в квадратичной постановке 193
Выводы пятой главы 200
ГЛАВА 6. Анализ эффективности разработанных процедур математического моделирования и численной оптимизации по результатам вычислительного эксперимента и использования при проведении испытаний ЖРД. 201
6.1. Анализ эффективности решения задачи прогнозирования риска достижения граничных состояний с помощью нейросетевых комитетов. 201
6.2. Анализ эффективности разработанных процедур минимизации избыточности систем прогнозирования граничных состояний. 205
6.3. Анализ эффективности алгоритмов оптимизации надежности систем прогнозирования граничных состояний. 217
6.4. Анализ эффективности алгоритмических процедур оптимизации процессов восстановления исходного состояния сложного объекта 229
6.5. Анализ эффективности разработанных алгоритмов при использовании их в задачах разработки диагностических процедур и управления наземными огневыми испытаниями ЖРД 237
Выводы шестой главы 246
Заключение 249
Список использованной литературы 251
- Основные проблемы математического моделирования и численных методов оптимизации в задачах прогнозирования риска достижения граничных состояний
- Исследование свойств оценок риска для некоторых базовых классов плановых траекторий
- Разработка алгоритмов решения задач минимизации избыточности систем прогнозирования достижения граничных состояний
- Метод ветвей и границ для решения задачи повышения надежности системы прогнозирования граничных состояний при многовариантном резервировании ее компонентов
Введение к работе
Актуальность темы
Задача прогнозирования достижения граничных состояний имеет широкий круг приложений. Прежде всего, она возникает при разработке систем технической диагностики как задача прогнозирования аварийных состояний технических объектов. В экологических системах – это задача прогнозирования неблагоприятного развития экологической ситуации. В инвестиционном анализе – это задача прогнозирования риска неполучения запланированной прибыли. В автоматизированных системах медицинской диагностики – это прогнозирование прогресса заболевания, перехода его в новую форму.
В общем случае, задача прогнозирования достижения граничных состояний возникает при разработке систем автоматического контроля функционирования любых сложных объектов и используется для распознавания критических ситуаций, связанных с неадекватной нормальному функционированию динамикой объекта контроля. Цель решения задачи оптимизации прогнозирования достижения граничных состояний – повышение надежности сложных систем.
Задачи прогнозирования достижения граничных состояний составляют особый класс задач. В отличие от методов непосредственного прогнозирования состояния сложных объектов, которые, по сути, дают точечные прогнозные оценки, методы прогнозирования достижения граничных состояний должны дать ответ на вопрос – останется ли объект через некоторое время в заданных границах или выйдет за их рамки, что ближе уже к интервальному оцениванию.
Предсказать, попадет ли некоторый параметр в заданный интервал, всегда можно с большей уверенностью, чем определить само значение этого параметра, поэтому методы прогнозирования достижения граничных состояний могут (и должны) обеспечивать более высокую точность прогнозов, чем классические методы прогнозирования. Однако для разработки таких методов нужно применять математический аппарат, максимально учитывающий специфику таких задач. Представляется, что таким аппаратом может стать дуальная вычислительная среда, включающая методы нейросетевого и оптимизационного моделирования. Оптимизационные модели обеспечат точность, наглядность и обоснованность методов, а нейронные сети позволят проводить адаптивную настройку параметров таких моделей. Дуальная вычислительная среда даст возможность более эффективно соединять формализуемые знания (оптимизационные модели) и плохо формализуемые (нейронные сети).
Задача исследования процесса достижения граничных состояний рассматривалась в работах И. А. Биргера, Л.Н. Александровской, А.Н. Абрамова, В.И. Круглова, Ю.К. Беляева, Л.Г. Евланова, И.В. Павлова, Т.А Голинкеви-ча, В.И. Городецкого, А.Г. Кузнецова, В.П. Назарова и других, и, в основном, эти исследования проводились на базе статистических методов. В процессе решения задачи прогнозирования достижения граничных состояний можно выделить несколько основных этапов.
На первом этапе решается задача определения набора прогностических
признаков (предикторов), обладающего низкой избыточностью и высокой информативностью. Математически задача построения минимального подмножества прогностических признаков сводится к оптимизации комбинаторной задачи о минимальном покрытии, методы точного и приближенного решения которой представлены в трудах А.А. Корбута, Ю.Ю. Финкельштейна, А.В. Еремеева. Но, поскольку задача о покрытии относится к NP- сложным, а задача оптимального построения минимальной системы предикторов имеет высокую размерность, в существующих системах прогнозирования достижения граничных состояний применяются только простые приближенные методы решения задачи о покрытии либо традиционные статистические методы. Поэтому требует решения проблема построения эффективных точных и приближенных алгоритмов для комбинаторного класса задач минимального покрытия, а также проблема предварительного формирования значимых обобщенных прогностических признаков, представляющих собой нелинейные комбинации исходных признаков.
На этапе разработки прогностических процедур осуществляется математическое моделирование оценок риска достижения граничных состояний, связанных с вероятностями выхода за эти границы. В литературе подобная задача решается с привлечением существенных гипотез и допущений о вероятностных свойствах прогнозируемого процесса. На практике такие сведения редко бывают заданными. На этом этапе требует решения задача получения оценок риска достижения граничных состояний, не опирающихся на знание полных вероятностных характеристик прогнозируемого процесса, а также проблема прогнозирования контролируемых параметров процесса для вычисления оценок будущего риска.
При решении задачи прогнозирования достижения граничных состояний огромное значение имеет этап проведения натурного эксперимента, при этом его стоимость и длительность, как правило, становятся определяющими в общих затратах и сроках, необходимых для создания сложной системы. На данном этапе нерешенной остается проблема разработки точных и приближенных алгоритмов отыскания решения многокритериальной задачи повышения надежности аппаратных и программных средств для проведения натурных экспериментов, а также проблема построения моделей виртуальных резервных элементов.
Вместе с тем сроки исследований поведения объекта в состояниях, близких к граничному, тесно связаны с решением задач оптимизации процесса последующего восстановления исходного состояния объекта. Данная задача может быть отнесена к широко известному классу задач о назначении. Однако ее решение осложняется тем, что она может иметь многокритериальную постановку с нечеткими коэффициентами целевых функций или постановку с квадратичной целевой функцией. Возможность точного решения таких задач ограничена размерностью 20-25 элементов, при этом в литературе для них практически отсутствуют эффективные приближенные алгоритмы.
Таким образом, актуальность темы определяется необходимостью комплексного исследования, связанного с недостаточной разработанностью мето-2
дов математического моделирования, численной оптимизации и концептуальных основ их интеграции для эффективного решения фундаментальных и прикладных задач оптимизации прогнозирования достижения граничных состояний сложных объектов.
Работа выполнена в соответствии с основным научным направлением ВГУ «Математическое моделирование, программное и информационное обеспечение, методы вычислительной и прикладной математики и их применение к фундаментальным исследованиям в естественных науках».
Целью диссертации является разработка численных методов, алгоритмических процедур и программных средств математического моделирования для концептуального решения задач оптимизации прогнозирования достижения граничных состояний сложных объектов в дуальной вычислительной среде.
В соответствии с указанной целью определены следующие задачи, которые необходимо решить для достижения поставленной цели:
проанализировать классы математических методов моделирования и численных методов оптимизации прогнозирования достижения граничных состояний и определить пути повышения их эффективности в дуальной вычислительной среде;
разработать математические модели прогнозирования риска достижения объектом граничных состояний на основе оптимизационного и нейросете-вого подходов;
сформировать оптимизационные модели и исследовать численные методы минимизации избыточности систем прогнозирования достижения граничных состояний на основе рандомизированных схем решения задач о минимальном покрытии и репликативной нейронной сети;
разработать оптимизационную модель и алгоритмические схемы численной оптимизации надежности системы прогнозирования достижения граничных состояний на основе метода ветвей и границ, генетического алгоритма и виртуального нейросетевого резервирования;
сформировать модели оптимизации восстановления исходного состояния объекта в виде многокритериальных задач о назначениях в квадратичной и нечеткой постановках и разработать для их решения генетический алгоритм и алгоритм на основе растущей нейронной сети;
провести анализ эффективности разработанных методов математического моделирования и численной оптимизации с применением вычислительного и натурного экспериментов.
Методы исследования. Для решения поставленных задач использовались основные положения теории математического моделирования, системного анализа, теории вероятностей и математической статистики, теории эффективности и надежности сложных систем, методы нейросетевого моделирования, дискретной и непрерывной оптимизации, интеллектуального анализа данных, эволюционного моделирования.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18: п.3 «Разработка, обоснование и тестирование эффективных
вычислительных методов с применением современных компьютерных технологий», п.5. «Комплексные исследования научных и технических проблем с применением современной технологии математического моделирования и вычислительного эксперимента», п. 8 «Разработка систем компьютерного и имитационного моделирования»
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
-
способ математической формализации задач прогнозирования достижения граничных состояний, отличающийся схемой классификации их содержательных постановок инвариантного и проблемно- ориентированного типов, которая обеспечивает возможность адекватного описания с использованием нейросетевых и оптимизационных моделей;
-
концепция интеграции оптимизационного и нейросетевого моделирования в дуальную вычислительную среду, отличающиеся способом выбора нейронных сетей специального вида или их комитета (ансамбля) для включения в структуру поиска численного решения задач оптимизации систем прогнозирования достижения граничных состояний;
-
методы математического моделирования прогнозных оценок риска достижения объектом граничного состояния, отличающиеся формой трансформации трактовки риска из проективной метрики на плоскости в d-оценки и геометрической интерпретацией процесса изменения наблюдаемого параметра системы в виде определенных классов траекторий с использованием методов нейросетевого прогнозирования;
-
комплекс оптимизационных моделей и алгоритмов минимизации избыточности систем прогнозирования достижения граничных состояний, отличающихся проблемной ориентированностью критериев оценивания информативности признаков, использованием новых эквивалентных способов математической формализации исходных задач, позволяющих применять для изначально комбинаторных постановок методы непрерывной оптимизации, разрабатывать вероятностные аналоги методов покоординатного спуска и вероятностные аналоги двойственных субградиентных процедур в сочетании с нейросе-тевым подходом;
-
математическая модель и алгоритмические схемы точной и приближенной численной оптимизации надежности системы прогнозирования достижения граничных состояний, отличающиеся способом формализованного представления критериев и ограничений на множестве булевых переменных и выбором реализации локальных этапов в процедурах многокритериального поиска компромиссного решения на основе результатов вычислительных экспериментов, а также введением нейросетевого резервирования;
6) оптимизационные модели и алгоритмические процедуры численной
оптимизации процесса восстановления исходного состояния сложного объекта,
отличающиеся формализацией исходной постановки в виде многокритериаль
ной задачи о назначениях с нечеткими целевыми коэффициентами и квадра
тичной задачи о назначениях, а также моделью генетического алгоритма, учи
тывающего нечеткие коэффициенты целевой функции, и использованием по-
4
исковой схемы на основе растущей нейронной сети;
7) структура и реализация комплекса программных средств вычислительного и натурного (испытания жидкостных ракетных двигателей) эксперимента, отличающаяся возможностью использования экспериментальных результатов для проведения сравнительного анализа эффективности численных процедур моделирования и оптимизации в задачах прогнозирования достижения граничных состояний, получаемых при варьировании алгоритмическими схемами и параметрами.
Практическая значимость работы и внедрение результатов работы
Разработанные модели и оптимизационные процедуры позволяют:
эффективно организовать последовательность взаимосвязанных этапов прогнозирования достижения граничных состояний и объединить методы решения задач на разных этапах в дуальную вычислительную среду;
минимизировать избыточность систем прогнозирования достижения граничных состояний за счет выбора набора наиболее информативных первичных и формирования вторичных прогностических признаков;
осуществлять оперативный допусковый контроль и прогнозирование риска достижения граничных состояний сложных объектов;
находить компромиссное решение по критериям надежность-стоимость при моделировании систем прогнозирования достижения граничных состояний;
оптимизировать маршрут восстановительных работ по результатам натурных экспериментов;
- использовать их в составе разработанного программного комплекса,
универсальность которого допускает рассмотрение достаточно широких клас
сов сложных систем.
Часть исследований, проведенных автором в работе, были выполнены в рамках ФЦП «Научные и научно-педагогические кадры инновационной России»: 2010-1.2.1-400-027 «Разработка поисковой среды интеллектуальной поддержки проектно-производственного процесса освоения инвестиций в создании жидкостных ракетных двигателей» (2010-2012гг.), 2012-1.4-12-000-4005 «Оптимизация управления испытаниями жидкостных ракетных двигателей на основе нейросетевых технологий и адаптивных методов принятия решений» (2012г.)».
Основные теоретические и практические результаты внедрены в практическую деятельность ОАО КБХА (в испытательный и научно-технический комплекс), ООО «Инвестиционная палата» (г. Воронеж), а также используются в учебном процессе ФГБОУ ВПО «Воронежский государственный университет» и АНОО ВПО «Воронежский институт высоких технологий», и подтверждены актами внедрения.
Апробация результатов исследования
Результаты, полученные в рамках диссертационной работы, докладывались и обсуждались на Международной конференции «Interactive Sytems. The Problems of Human-Computer Interaction» (Ульяновск, 2001), X Международном симпозиуме «Математика. Экономика. Образование» (Новороссийск, 2002),
Международной конференции «Современные сложные системы управления
(СССУ-HTCS 2003)» (Санкт-Петербург, 2003), Международной школе-
семинаре «Современные проблемы механики и прикладной математики» (Во
ронеж, 2004), Всероссийской научно-технической конференции «Информаци
онные технологии» (Воронеж, 2005), 4-й Международной научно-практической
конференции «Экономическое прогнозирование: модели и методы» (Воронеж,
2008), Международной конференции «Актуальные проблемы прикладной ма
тематики, информатики и механики» (Воронеж, 2009), Международной кон
ференции «Актуальные проблемы прикладной математики, информатики и ме
ханики» (Воронеж, 2010) ; X Международной конференции «Системы проекти
рования, технологической подготовки производства и управления этапами жиз
ненного цикла промышленного продукта (CAD/CAM/PDM-2010)» (Москва,
2010); Всероссийской научной школе «Управление, информация и оптимиза
ция» (Воронеж, 2011), Всероссийской научной школа «Информационно- теле
коммуникационные системы и управление» (Воронеж, 2011), Международной
школе-семинаре «Интеллектуальные компьютерные обучающие системы»,
(Воронеж, 2011), Международной конференции «Актуальные проблемы при
кладной математики, информатики и механики» (Воронеж, 2012), Междуна
родной молодежной научной школе «Теория сложности вычислений» (Воро
неж, 2012), 36 Международной научной школе-семинаре «Системное модели
рование социально-экономических процессов» (Воронеж, 2013), а также на
ежегодных научно-практических конференциях профессорско-
преподавательского состава ВГУ.
Публикации результатов работы. По теме диссертации опубликовано 56 научных работ, в том числе 17 - в изданиях, рекомендованных ВАК РФ, 1 – свидетельство на программу для электронных вычислительных машин, базу данных, топологию интегральных микросхем. В опубликованных в соавторстве работах автором лично разработаны модели и алгоритмы, представленные в пунктах научной новизны.
Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, списка литературы, содержащего 205 наименований, приложения. Основная часть диссертации изложена на 270 страницах, содержит 48 рисунков, 26 таблиц.
Основные проблемы математического моделирования и численных методов оптимизации в задачах прогнозирования риска достижения граничных состояний
В настоящее время моделирование является неотъемлемым элементом процесса создания любой сложной системы. В сложных системах роль моделирования при оценке параметров исследуемых процессов особенно высока. Это объясняется особенностями исследуемых объектов, вытекающими из сложности функциональных связей между параметрами системы, изменяющимися условиями внешней среды и оцениваемыми показателями. Как правило, при моделировании сложных систем возникает ситуация, когда исследуемые процессы в системе и условия внешней среды имеют вероятностный характер, число факторов, влияющих на исследуемые параметры, значительно и оценки этих параметров нужно получить для широкого диапазона изменений функционирования системы.
Исследование методом моделирования начинается обычно со сбора априорной информации об объекте, выбора вида модели, разработки базовой модели, предназначенной для конкретных исследований. Затем уже производится экспериментирование на данной модели с последующим уточнением ее вида и самих результатов моделирования. Во многих случаях моделирование заканчивается серией натурных испытаний системы с целью подтверждения достоверности полученных результатов. С помощью моделирования можно контролировать работу систем, оптимизировать их характеристики, осуществлять краткосрочный или долгосрочный прогноз. Основное назначение моделирования – выбор оптимальной стратегии поиска наилучшего из возможных вариантов. В данной работе с помощью методов математического моделирования решается задача оптимизации процесса прогнозирования достижения граничных состояний сложного объекта.
Задача прогнозирования достижения граничных состояний имеет широкий круг приложений. Прежде всего, она возникает при разработке систем технической диагностики как задача прогнозирования аварийных состояний технических объектов. В экологических системах – это, например, задача прогнозирования неблагоприятного развития экологической ситуации. В инвестиционном анализе – это может быть задача прогнозирования риска неполучения запланированной прибыли. В автоматизированных системах медицинской диагностики – это прогнозирование прогресса заболевания, перехода его в новую форму.
В целом можно сказать, что задача прогнозирования достижения граничных состояний возникает при разработке систем автоматического контроля функционирования любых сложных объектов и используется для распознавания критических ситуаций, связанных с неадекватной нормальному функционированию динамикой объекта контроля.
Важно отметить, что рассматриваемые при этом сложные системы не обязательно являются техническими, но обязательно такими, состояние которых меняется в динамике и для которых существует проблема возможного выхода значений некоторых контролируемых параметров за установленные границы, что приведет к нарушению нормального функционирования системы. Задачи прогнозирования достижения граничных состояний составляют особый класс задач прогнозирования. В отличие от методов непосредственного прогнозирования состояния сложных объектов, которые, по сути, дают точечные прогнозные оценки, методы прогнозирования достижения граничных состояний должны дать ответ на вопрос – останется ли объект через некоторое время в заданных границах или выйдет за их рамки, что ближе уже к интервальному оцениванию. Предсказать, попадет ли некоторый параметр в заданный интервал, всегда можно с большей уверенностью, чем определить само значение этого параметра, поэтому методы прогнозирования достижения граничных состояний могут (и должны) обеспечивать более высокую точность прогнозов, чем классические методы прогнозирования.
Процесс разработки системы прогнозирования достижения граничных состояний в общем случае состоит из ряда этапов, необходимых для осуществления прогностических мероприятий. Последовательность этих этапов может быть представлена в виде, который изображен на рис. 1.1. На схеме приведены только основные этапы, позволяющие получить математические модели процессов, реализуемых на этом этапе.
Впоследствии эта модель может уточняться на основе данных, полученных в процессе натурных экспериментов.
Этап планирования натурных экспериментов ставит своей задачей построение модели, позволяющей при минимальном количестве экспериментов получить данные, с максимальной достоверностью характеризующие исследуемые свойства объекта.
На этапе проведения экспериментов собираются экспериментальные данные, характеризующие граничные состояния объектов. Одной из задач на этом этапе является оперативное принятие решений по завершению или продолжению натурных экспериментов, в случае достижения объектом граничного состояния и формирование мероприятий по коррекции условий и задач экспериментов. Еще одной задачей этого этапа является предоставление исходных данных для оптимизации восстановительных работ после эксперимента.
После сбора экспериментальных данных осуществляется их обработка с целью систематизации полученных данных и исключении возможных погрешностей, возникших при сборе данных. Для этого, как правило, используют специализированные статистические методы. По результатам систематизации данных на этом этапе формируются классы граничных состояний. Конкретный класс граничных состояний объединяет подмножество граничных состояний, каждое из которых характеризуется каким-либо набором первичных признаков.
Стоит отметить, что этап проведения экспериментов очень важен, поскольку реализуемые аналитические модели на практике уточняют по экспериментальным данным, которые в свою очередь используются для повышения точности моделирования. Использование аналитических методов построения математических моделей на разных этапах решения задачи прогнозирования достижения граничных состояний значительно сокращает объем экспериментальных исследований. Этим объясняется сочетание в одной вычислительной схеме элементов аналитической и экспериментальной моделей. По мере накопления экспериментальных данных точность моделирования повышается. В этом отношении возможности экспериментально-аналитических моделей очень высоки.
На следующем этапе необходимо оценить информативность измеряемых параметров (признаков) объекта с точки зрения раннего обнаружения и классификации граничных состояний и отобрать наиболее значимые из них для использования на следующих этапах прогнозирования. Под информативностью признаков понимают величину, количественно характеризующую пригодность отдельных признаков либо их наборов для прогнозирования достижения граничных состояний. На следующем этапе непосредственно разрабатываются прогностические процедуры. Состав этих процедур может быть очень разнообразным в зависимости от специфики и назначения конкретного объекта. Как минимум, эти процедуры включают два основных типа алгоритмов – алгоритмы, формирующие вторичные информативные обобщенные прогностические признаки по результатам обработки первичных признаков, и алгоритмы, предсказывающие достижение граничных состояний путем анализа признаков.
Исследование свойств оценок риска для некоторых базовых классов плановых траекторий
Функциональное понятие прогностического теста, а также математическая модель неадекватно функционирующей системы как функции неисправности позволяют в принципе решать задачи отыскания минимальных наборов прогностических тестов любых систем, для которых выработано логическое описание. Универсальный метод построения тестов до настоящего времени остаётся единственным, не связанным с определённым типом критических ситуаций. Однако, несмотря на универсальность такого подхода, он редко используется на практике. Причина в том, что комбинаторная задача о минимальном покрытии (а вместе с ней и сформулированная таким образом задача минимизации набора прогностических признаков) является чрезвычайно сложной. Сложность этой задачи связана с ее комбинаторным характером. Например, при наличии 20 различных прогностических признаков придется рассмотреть 220 их возможных комбинаций (более 1000000 вариантов). Решить комбинаторную задачу о минимальном покрытии такого размера классическими методами (такими, как метод ветвей и границ) уже невозможно. Поэтому появляется необходимость либо в разработке эффективных приближенных методов решения этой задачи, либо в привлечении других методов выделения минимального набора признаков, либо в привлечении дополнительной информации для сокращения перебора.
В частности, по результатам предварительного анализа могут быть сделаны предположения об информативности тех или иных наборов признаков. Информативность признаков – это величина, количественно характеризующая пригодность признаков или их набора для распознавания классов отказавших и не отказавших изделий.
Общая задача отбора информативных признаков может быть поставлена одним из следующих способов: 1) отобрать комбинацию признаков из исходного набора данных таким образом, чтобы при ней достигалось оптимальное значение заданного критерия оценивания информативности набора признаков; 2) выбрать из исходного набора признаков комбинацию, содержащую не более, чем заданное количество признаков, и обеспечивающую при этом оптимальное значение критерия оценивания информативности признакового набора; 3) найти набор признаков наименьшего размера, при котором достигается приемлемое значение критерия оценивания информативности.
В настоящее время существуют различные подходы к построению информативной системы признаков. Одним из самых распространенных является следующий эвристический подход [54]. Для получения «наилучшего» (по выбранному критерию) набора признаков используется следующее правило. Из всех n признаков выбирается один наиболее информативный («ценный»); далее, к первому признаку добавляется такой признак из n-1 оставшихся, чтобы информативность пары признаков для прогнозирования была наибольшей; затем к полученной паре признаков добавляется наилучшим образом новый признак и так далее. Процесс заканчивается тогда, когда информативность некоторой совокупности признаков незначительно превосходит информативность совокупности, полученной на предыдущем шаге, или когда достигнут требуемый уровень информативности (или требуемый уровень точности прогнозирования критической ситуации). Процедура такого отбора признаков называется алгоритмом сокращенного перебора с добавлением признаков.
Очевидно, что данный подход может быть переформулирован как самый известный «жадный» эвристический алгоритм решения упомянутой выше задачи о минимальном покрытии, в котором на каждом этапе выбирается подмножество, покрывающее максимальное (по количеству или весу) число ещё не покрытых элементов. Но, как известно [95], этот алгоритм не является эффективным, поскольку найденное им решение может отличаться от оптимального в сколь угодно большое число раз. Для наглядности рассмотрим пример (рис.1.5). Пусть исходный набор подмножеств состоит из попарно не пересекающихся подмножеств мощности которых 2,4,8,... ,2 соответственно. Так же имеются два непересекающихся множества їо,7і каждое из которых содержит половину элементов из каждого . На таком наборе эвристический алгоритм выбирает для покрытия поочередно все подмножества тогда как оптимальным решением является выбор всего двух подмножеств Зои її.
Справедливости ради надо отметить, что в [60] представлен результат, из которого следует, что для задачи о минимальном покрытии в принципе не может существовать приближенных алгоритмов, для которых порядок оценки точности (отношения приближенного и точного значения целевой функции) будет лучше, чем In п. При этом среднее количество итераций всех точных алгоритмов имеет порядок 2п. Это побуждает к конструированию новых точных и приближенных алгоритмов решения этой задачи так как, хотя в целом улучшить эти оценки нельзя, при решении конкретной задачи результаты могут существенно различаться. Особенно если алгоритмы будут построены с учетом особенностей некоторого конкретного класса задач (например, таких как высокая или, наоборот, низкая разреженность матрицы покрытий)
Однако, одной только минимизации набора прогностических тестов недостаточно для решения задачи оптимизации признакового пространства, и, как следствие, задачи минимизации избыточности систем прогнозирования достижения граничных состояний.
С помощью задачи о минимальном покрытии можно выбрать минимальный набор прогностических тестов, но она не поможет при выявлении связей между прогностическими параметрами и формировании на их основе значимых обобщенных прогностических признаков. А возможностей для формирования такого рода признаков даже при не очень существенном числе измеряемых параметров очень много.
Так, например, измеряемыми параметрами, используемыми для формирования прогностических признаков, на практике могут служить: - значение некоторого обобщенного параметра или функция двух и более таких обобщенных параметров; - отклонения измеренного или прогнозируемого значения параметра от некоторого значения; - отклонение вниз/вверх измеренного или прогнозируемого значения параметра от экстремального достигнутого за время контроля; - тренд (смещение среднего уровня) измеренного или прогнозируемого значения параметра и его направление; - дрейф (скорость смещения среднего уровня) измеренного или прогнозируемого значения параметра и его направление - временная последовательность достижения некоторых пороговых значений прогностическими признаками. При этом пороги, в сравнении с которыми формируются прогностические признаки могут быть: - постоянными, - переменными, изменяющимися во времени, - переменными, изменяющимися в зависимости от текущего, прошлых или прогнозируемых значений контролируемого параметра, - переменными, изменяющимися в зависимости от текущего, прошлых или прогнозируемых значений другого параметра, функционально связанного с контролируемым. При этом, как правило, причинно-следственные связи между измеренными параметрами прогнозируемого процесса и значимыми обобщенными прогностическими признаками в функциональном виде неизвестны.
Разработка алгоритмов решения задач минимизации избыточности систем прогнозирования достижения граничных состояний
Самым очевидным подходом к организации комитета является введение «специализации» экспертов. Для этого проводится предварительная кластеризация всей обучающей выборки, то есть исходное множество данных разбивается на несколько (2-5) кластеров, состоящих из схожих входных наборов. Такое разбиение позволяет снизить возможную противоречивость данных в обучающей выборке, так как в каждом кластере будут находиться только «похожие» образы. Каждый нейро-эксперт обучается только на данных одного из кластеров (число нейро-экспертов совпадает с числом кластеров). В процессе функционирования комитета каждый входной образ вначале анализируется, чтобы определить, к какому из кластеров он относится. Результирующий прогноз комитета вырабатывается тем экспертом, специализацией которого является данный кластер. Для проведения предварительной кластеризации обучающего множества может быть использована самоорганизующаяся нейронная сеть (карта Кохонена).
В дальнейшем, когда комитет начнет функционировать, входной образ сначала будет анализироваться картой Кохонена, чтобы определить, к какому из имеющихся входных кластеров он относится. Итоговый прогноз будет вырабатывается экспертом, специализацией которого является этот кластер.
Архитектура модели прогнозирования комитета с руководителем. В этом случае обучается еще одна нейронная сеть («руководитель комитета»), входами которой будут прогнозы всех нейро-экспертов, а выходом – итоговый прогноз комитета (рис. 2.6). Модификация такого подхода может заключаться в том, что на вход «руководителя» будут поступать не только прогнозы нейро-экспертов, но и элементы исходного временного ряда. 3) Комитет выбора наилучшего эксперта
В качестве ответа комитета используется прогноз той из P имеющихся в распоряжении сетей, которая в данный момент t является наилучшей в том смысле, что для нее экспоненциально сглаженная сумма квадратов ошибок прогнозов за k периодов, предшествующих данному, минимальна:
Здесь - прогноз сети с номером i в момент времени t-s; истинное значение параметра в этот момент. Величины и k (k 1) задают скорость забывания предыстории. 4) Комитет, использующий метод наименьших квадратов.
В этом случае прогноз комитета вычисляется как линейная комбинация прогнозов сетей-экспертов: Здесь P- общее число сетей комитета, - прогноз сети с номером i в момент времени t, y (t) - прогноз комитета, - весовые коэффициенты, которые находятся с помощью решения следующей вспомогательной задачи: Здесь на каждом шаге t ищется набор весовых коэффициентов , такой, что экспоненциально сглаженная сумма квадратов ошибок прогнозов комитета за k периодов, предшествующих данному, минимальна с учетом регуляризации. При этом - это прогноз комитета в момент (t-s), y(t-s) - значение прогнозируемого параметра в момент (t-s), - весовые коэффициенты сетей, найденные на предыдущем этапе, - параметр сглаживания (забывания предыстории), параметр регуляризации, позволяющий найти компромисс между точностью прогнозов и устойчивостью весовых коэффициентов во времени.
Недостатком этого метода является необходимость решать на каждом этапе задачу квадратичного программирования. Конечно, это требует дополнительных временных затрат. Однако, отметим, что целевая функция вспомогательной задачи является выпуклой, поэтому ее решение не представляет большой сложности. 5) Комитет компетентности на кластерах
Этот подход к формированию комитета нейро-экспертов предполагает начальную кластеризацию всех входных данных обучающей выборки, как и в комитете специализации. Далее для всех нейро-экспертов определяются их коэффициенты компетентности на каждом из кластеров. Когда комитет начнет функционировать, эти коэффициенты будут корректироваться в соответствии с величиной ошибок прогноза нейро-эксперта на данных этого кластера. Выработка согласованного решения комитета производится с весами, соответствующими коэффициентам компетентности нейро-экспертов того кластера, в котором находится анализируемый входной вектор.
При прогнозировании класса надежности исследуемой системы нейросетевой комитет, по сути должен решить задачу классификации, а не регрессии. Поэтому далее рассмотрим методы формирования нейросетевых комитетов, осуществляющих классификацию входных данных на K непересекающихся классов.
Для наглядности сначала рассмотрим задачу классификации на два класса. Предположим, есть три сети-эксперта, каждая из которых решает задачу бинарной классификации с вероятностью p, независимо от остальных. Тогда при классификации очередного примера возможны 8 исходов, когда все классификаторы выдали верный ответ, либо два из трех не ошиблись (три варианта), либо не ошибся лишь один (еще три варианта), и, наконец, когда ошиблись все три сети одновременно. Вероятности этих комбинаций исходов равны p3, 3p2(1 -p), 3p(1 -p)2 и (1 -p)3.
Если из трех данных сетей образовать комитет большинства, принимающий решение путем простого голосования, то вероятность безошибочной классификации вычисляется по формуле:
Отметим, что в области 1 p 0.5 объединение сетей в комитет позволяет превысить точность отдельной сети, так как 3p2 - 2p3 p. Поэтому, теоритически, можно было бы неоднократно повышать точность путем построения комитетов из комитетов, затем комитетов из комитетов комитетов и т. д. В реальности, этого достигнуть не удается, так дает о себе знать проблема переобучения, возникающая в результате подгонки модели комитета под обучающее множество.
Однако точность комитета сетей можно улучшить, если повысить точность каждой отдельной модели и, одновременно, обеспечить статистическую независимость ошибок разных сетей комитета (например, за счет выбора разных сетевых архитектур). 7) Комитет пересчета коэффициентов компетентности.
Этот комитет осуществляет классификацию на K классов. Прогноз комитета вычисляется как номер класса, такой, что сумма коэффициентов компетентности сетей-экспертов, проголосовавших за данный класс, максимальна: где - номер класса, предсказанный i-той сетью. При этом коэффициенты компетентности пересчитываются согласно следующему алгоритму: 1) На начальном этапе все коэффициенты задаются равными: . Полагается t=0. 2) Строится прогноз комитета 3) Пересчитываются весовые коэффициенты: , где , если сеть под номером i дала верный прогноз (угадала номер класса), и А 0, если прогноз был неверным. 4) Пока t не достигло максимального возможного значения, полагается t=t +1 и осуществляется переход на шаг 2. 8) Комитет адаптивного пересчета коэффициентов компетентности В этом случае при пересчете весовых коэффициентов сетей мы будем учитывать не только то, ошиблась сеть на последнем примере или нет, но и то, сколько из сетей комитета допустили ошибку на этом примере. То есть если последнее значение все сети предсказали верно, то коэффициенты сетей меняться не будут, а если, например, верно предсказала только одна сеть, а остальные ошиблись, то изменение веса этой сети будет довольно существенным
Метод ветвей и границ для решения задачи повышения надежности системы прогнозирования граничных состояний при многовариантном резервировании ее компонентов
В рамках данной схемы можно получать не только достаточно широкий класс новых алгоритмов, но и адаптивные модификации большинства известных приближенных алгоритмов. Остановимся на возможностях, предоставляемых данной схемой для конструирования алгоритмов решения задач (3.1)-(3.5). Для этого рассмотрим ее этапы более подробно. Задание движени во множестве случайных величин . Рассматриваемые далее вероятностные алгоритмы базируются на итеративной 100 процедуре движения в пространстве случайных векторов . Здесь - случайный вектор, определяющий направление движения на -м шаге, такой что - булева случайная величина. Это движение может осуществляться в реализациях случайных величин или в их вероятностных характеристиках.
Отыскание неизвестных параметров движени на основе услови локального улучшени .
Условие локального улучшения, требующее "неухудшения" значения целевой функции на каждой последующей итерации, служит основой для отыскания неизвестных параметров движения. Этот этап можно выделить как основной, непосредственно формирующий структуру алгоритма. Так как УЛУ представляет собой одно неравенство с большим числом неизвестных, то можно предложить множество различных способов его решения. При этом наряду с непосредственным поиском каких - то частных решений, возможно приведение неравенства к виду, удобному для отыскания общих решений с перестройкой вектора вероятностей p в соответствии с текущей информацией. Именно на этом этапе большую роль играет выбранный способ постановки задачи.
Итеративный пересчет условных веро тностей. Формула для итеративного пересчета вероятностей может быть получена из приведенной выше формулы движения. Так как , то справедливо равенство = В предположении статистической независимости векторов XN, YN+1 от случайной величины данное равенство переписывается следующим образом: или 101 Однако заметим, что если при выполнении УЛУ вычислялись или оценивались условные математические ожидания, то с помощью найденных параметров движения на каждой итерации будут пересчитываться условные вероятности. В таком случае в алгоритме необходимо наличие этапа изменени безусловных веро тностей. На этом этапе возможно, например, использование формулы полной вероятности. Фиксирование допустимых точек в соответствии с полученным распределением. Фиксирование допустимых точек осуществляется, как правило, либо алгоритмически (в процессе выполнения условия локального улучшения), либо с помощью датчика случайных чисел, настроенного на полученное распределение вероятностей. Проверка на останов. Заметим, что выполнение условия локального улучшения на каждой итерации не гарантирует монотонную сходимость к глобальному оптимуму. Поэтому, кроме специфических для конкретного алгоритма остановов, рекомендуется предусмотреть останов по числу итераций. Рассмотрим далее несколько алгоритмов решения задач (3.1)-(3.5), построенных в рамках данной схемы. 3. Веро тностный аналог метода покоординатного спуска Воспользуемся описанной выше схемой для построения вероятностного аналога известного метода покоординатного спуска для решения задачи (3.1), записанной в виде (3.7), а далее переписанной в виде (3.13). Зададим движение на множестве случайных величин в виде Для определения неизвестных параметров УЛУ преобразуется к виду В рамках предположения о статистической независимости векторов , 102 от случайной величины УЛУ записывается следующим образом: (3.19) Введем обозначения: Тогда формулy движения в координатной форме в вероятностных характеристиках можно записать в виде
Для итеративного пересчета вероятностей по формуле (3.20) требуется определить неизвестные величины и , Параметр будет параметром алгоритма, его значение не влияет на выполнение неравенства (3.19) величины определятся из УЛУ, которое может быть записано в виде C целью решения последнего неравенства воспользуемся свойством линейности псевдо-булевой функции по каждой переменной : В таком случае С учетом полученного представления УЛУ переписывается в виде 103 Рассмотрим следующий вариант выполнения этого неравенства. Положим для (т.е. ). Тогда УЛУ преобразуется к виду В предположении независимости случайных векторов X и Y, а также попарной независимости случайных величин УЛУ может быть переписано следующим образом Здесь, как и ранее если Обозначим через величину, равную Тогда для решения последнего неравенства достаточно положить, например, , если , и , если
Разные способы выбора номера k на каждом шаге алгоритма порождают различные алгоритмические версии. Так, например, если номер меняется последовательно в соответствии с начальной зафиксированной перестановкой, то в итоге получим вероятностный аналог покоординатного спуска. Если номер ищется как ,то получается вероятностный аналог "жадного" минимаксного алгоритма. При формировании алгоритмов типа покоординатного спуска целесообразно взять и предусмотреть возможность фиксирования значения k-й координаты на каждом шаге алгоритма, так как при этом появляется возможность сокращения размеров исходной матрицы A путем вычеркивания k-го столбца, а в случае и тех строк, где (выполнившиеся ограничения). УЛУ в этом случае на шаге (после фиксирования s координат) имеет вид Здесь I- множество номеров невыполненных ограничений, J- множество индексов незафиксированных координат. Фиксирование реализации случайной величины после решения неравенства и пересчета вероятностей можно осуществить, например, следующим образом: , т.е. единица появится при уменьшении вероятности на данном шаге, ноль при её увеличении. В этом случае можно гарантировать, что все получаемые в ходе работы алгоритма точки будут допустимыми. Это утверждение следует из того факта, что после сокращения размерности в матрице А не появляется нулевых строк. Действительно, такая ситуация могла бы возникнуть лишь в том случае, если бы существовала строка, в которой
Другим способом фиксирования реализаций случайной величины X, является использование датчика случайных чисел, настроенного на соответствующее распределение. В этом случае на каждой итерации алгоритма необходимо осуществлять приведение исходной матрицы (т.е. в частности, вычеркивание столбцов, имеющих в какой-то строке ровно одну единицу и фиксирование для соответствующей переменной значения, равного 1).
