Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Под ошибкой второго рода будем понимать такую ошибку распознавания,когда траектория нештатного поведения реально входит в наблюдаемую траекторию, ноне распознается алгоритмом распознавания. Неверная классификация траекториинештатного поведения так же относится к ошибкам второго рода.Эта задача относится к классу задач распознавания образов. Для решения такогорода задач используется большое число методов, таких как: нейронные сети, алгоритм kближайших соседей, алгоритмы на основе SSA и др.

Однако, их применение для даннойзадачи осложнено наличием искажений траекторий нештатного поведения, как по длине,так и по времени. Чтобы учесть данные особенности задачи, было разработанопараметрическое семейство алгоритмов распознавания и метод обучения на основегенетического алгоритма.Параметрическое семейство алгоритмов распознаванияРазработанное семейство алгоритмов распознавания основано на аксиоматическомподходе.Основойаксиоматическогоподходаявляетсяразметкаанализируемойтраектории аксиомами и анализ траектории по полученному ряду разметки.Элементарное условие ec  ec( xt* , t , p) – это бинарная функция, определенная наотчете t и некоторой его окрестности xt* на траектории X, зависящая от наборапараметров p.

Пример элементарного условия:true, если i  [t  k , t  j ], i  N :ec( x , t , p)  xi 1  xi  xi 1 , f ( x * , i )  xi    0 false, иначе*t1где: f ( x * , i )  ( xi 1  xi 1 ) , p  {k , j ,} .267Аксиомаa  a( xt* , t ) – это бинарная функция, определенная в точке t и некоторойее окрестности xt* на траектории X. Аксиома представляет собой булеву формулу надмножеством элементарных условий. Точка траектории размечается аксиомой, если вданной точке условия аксиомы выполняются. Траектория размечается набором аксиом,если каждая точка траектории размечается некоторой аксиомой из данного набора.Определение 1: Набор аксиом as  {a1 , a2 ,..., am } будем называть системой аксиом,если он удовлетворяет следующим ограничениям:Условие полноты.

Это условие означает, что для любой точки допустимойтраектории найдется аксиома из набора аксиом её размечающая.Условие однозначности. Это условие заключается в том, что любая точкадопустимой траектории может быть размечена лишь одной аксиомой из набора.X  ( x1 , x2 ,..., xn ) , полученной при помощи системыРазметкой траекторииаксиом as, является последовательность J  ( j1 , j 2 ,..., j n ) , где ji – номер аксиомы изнабора as, которая размечает отсчет xi .В рамках аксиоматического подхода распознавание нештатного поведения в работенаблюдаемой системы происходит следующим образом:1) Размечаются эталонные траектории { X Anom } , соответствующие различным классамнештатного поведения.2) Размечается наблюдаемая траектория X и формируется ряд разметки J.3) ВрядуразметкиJищутсяподпоследовательностиномероваксиомсоответствующие разметкам эталонных траекторий.Таким образом, определение нештатного поведения в работе наблюдаемой системыведется не путем поиска эталонных траекторий { X Anom } в наблюдаемой траектории X, апутем поиска разметок эталонных траекторий в ряду разметки J.Решение рассматриваемой задачи распознавания будем искать среди множестваалгоритмов S, каждый из которых включает в себя:алгоритм разметки и система аксиом,алгоритм поиска разметок эталонных траекторий в разметке наблюдаемойтраектории.Для поиска разметок эталонных траекторий можно использовать следующиеалгоритмы: алгоритмы на основе метрики Минковского, и DTW (Dynamic Time Warping) ,алгоритмы на основе нейросетей.68Задача построения алгоритма распознаванияПусть задан набор прецедентов TS в виде экземпляров траекторий X, полученных вразличных условиях работы системы.

Траектории X из набора TS содержат как участкинештатного поведения, так и участки нормального поведения. Для каждой из траекторийX указаны:Отсчеты начала и окончания участка участков нештатного поведения;Для каждомго участка нештатного поведения указан тип нештатной ситуации измножества W = l 1  0 .LВесь набор TS разделим на обучающую TS и контрольную TS выборку:TS = TS  TS TS  TS = Пусть определена целевая функция  (e1 , e2 ) , где e1 и e2 - число ошибокраспознавания первого и второго рода, которая отвечает следующим требованиям:Функция  (e1 , e2 ) определена для любых неотрицательных целых значенийаргументов e1 и e2 .Функция  (e1 , e2 ) монотонно неубывает по каждому из аргументов.Число ошибок распознавания первого рода e1 (второго рода e2 ) определяется длянекоторого алгоритма распознавания Al на некоторой траектории X . Под числомошибок распознавания на выборке TS будем понимать сумму ошибок распознавания навсех траекториях данной выборки.

Задача построения алгоритма распознаваниянештатных ситуаций в работе динамической системы состоит в следующем.Дано:Обучающая выборка TS и контрольная выборка TS ,Целевая функция  (e1 , e2 ) .ТребуетсяпостроитьалгоритмраспознаванияAl : Al  S ,которыйбудетудовлетворять следующему набору ограничений:1. Алгоритм Al не должен выдавать ошибок на обучающей выборке TS :e1 ( Al , TS ) = e2 ( Al , TS ) = 02. Алгоритм Al должен минимизировать значение целевой функции  (e1 , e2 ) наконтрольной выборке TS :Al = argmin ( (e1 ( Al , TS ), e2 ( Al , TS )))Al693.

Вычислительная сложность работы алгоритма распознавания  Al (m) напроизвольной траектории, длины не больше m , должна быть ограничена напередзаданной функцией  (m) , которая определяется характеристиками используемоговычислителя и скоростью развития процессов в анализируемой системе: Al (m)   (m)Данная задача построения алгоритма распознавания соответствует классическойпостановке задачи обучения по прецедентам.Генетический алгоритм построения системы аксиомОсобью в популяции Pl является система аксиом as :Pl = {as1 , as2 , , asn }Цель оптимизации состоит в получении системы аксиом as , минимизирующейцелевую функцию  (e1 , e2 ) на обучающей выборке TS . Далее будет подробно рассмотренкаждый их этапов генетического алгоритма построения системы аксиом.Для определения эталонных траекторий для каждого из классов нештатногоповедения разделим всю известную выборку TS на 3 части следующим образом:jTS = { X Anom}Lj=1  TS  TS ,jjTS  TS =  , { X Anom}Lj=1  TS =  , TS  { X Anom}Lj=1 = Из траекторий выборки TS случайным образом выделим по одному участкунештатного поведения от каждого класса нештатного поведения и поместим в множествоj{ X Anom}Lj=1 :jiij{ X Anom}Lj=1 : j  [1, L] ( I start, I end, j )   , X Anom TSгде: L - число классов нештатного поведения рассматриваемой технической системы.j}Lj=1 будем использовать как эталонныеТраектории из сформированного множества { X Anomтраектории для различных классов нештатного поведения.

После изъятия траекторийj{ X Anom}Lj=1 из выборки TS , разделим оставшуюся выборку в равной части междуобучающей TS и контрольной TS выборками. Теперь рассмотрим каждый их этаповгенетического алгоритма построения системы аксиом подробнее.Создание начальной популяции70Напервомэтапегенетическогоалгоритматребуетсясоздатьзаданноечислоразличных систем аксиом, которые будут составлять начальную популяцию Pl .Формирование каждой системы аксиом as в начальной популяции Pl происходит последующему алгоритму:1.

Выбирается число аксиом в системе as : N a = rand (1, N amax ) .Фу2. Создается N a аксиом, каждая из которых составляется следующим образом:a) Выбирается число элементарных условий в аксиоме: N ec = rand (1, N ecmax ) .b) Из множества элементарных условий {ec} , заданного в рамках шаблона S kвыбирается N ec условий. Их параметры определяются случайным образом.При этом типы условий среди выбранного набора могут повторяться.c) Выбранные N ec элементарных условий объединяются при помощи связок{,} . Тип связки, с которой элементарное условие добавляется в аксиомувыбирается случайно. При этом, с вероятностью 1/2 условие будет входить ваксиому с отрицанием, т.е.

в виде ec .Полученные таким образом наборы аксиом могут не удовлетворять условиямоднозначности и полноты. Для того, чтобы созданные системы аксиом удовлетворялиусловию однозначности вводится приоритет аксиом в системе. Все аксиомы в системепронумерованы:as = {a1 , a2 ,, a N }aБудем считать что, если аксиома с индексом i выполняется в некоторой точке траекторииX , то никакая аксиома с индексом j : j > i не может выполняться в данной точкетраектории. Чем меньше индекс аксиомы, тем больше ее приоритет в системе. Для любойсистемы аксиом с приоритетами условие однозначности выполняется.Для того, чтобы созданные системы аксиом удовлетворяли условию полноты вкаждую систему аксиом добавляется тождественная аксиома с наименьшим приоритетом:as = {a1 , a2 ,, a N , a }aТождественная аксиома a - это аксиома, которая выполняется в любой точке любойтраектории.

Характеристики

Список файлов лекций