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

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

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

При добавлениикаждое элементарное условие либо образует новый дизъюнкт в формулеаксиомы a , либо добавляется к одному из уже существующих дизъюнктов.Выбор способа вхождения в аксиому и выбор дизъюнкта осуществляетсяслучайным образом.Параметрами операции мутации на уровне аксиом являются: Pamut - вероятностьучастия аксиомы a в мутации; muta  [0,1] - параметр, который определяет степеньизменения аксиомы a в ходе мутации.Операция скрещивания.Для каждой пары аксиом [a, a] , выбранной в алгоритме скрещивания для систем аксиом,производится операция скрещивания на уровне аксиом.

Эта операция создает новуюаксиому на основе двух выбранных аксиом:[a  a]  a *Новая аксиома формируется путем объединения двух подформул от скрещиваемыхаксиом. Кроме того, происходит скрещивание элементарных условий одного типа,входящих в обе аксиомы. Операция скрещивания аксиом a и a работает последующему алгоритму:1. От аксиомы a выбираются дизъюнкты, которые будут входить в новуюаксиому. Вероятность выбора каждого дизъюнкта равна 1/2 . Множествовыбранных дизъюнктов обозначим E  .2.

От аксиомы a выбираются дизъюнкты, которые будут входить в новуюаксиому. Вероятность выбора каждого дизъюнкта равна 1/2 . Множествовыбранных дизъюнктов обозначим E  .78 . Число условий в3. Обозначим число элементарных условий в E  символом nec . Если (n  n) > N ecmax , то из каждого из множеств удаляетсяE  - символом necпо одному дизъюнкту до тех пор, пока данное условие не будет выполнено.4. Множество всех элементарных условий в дизъюнктах из множества E обозначим Eec . Множество всех элементарных условий в E  обозначим Eec .Для каждого элементарного условия eci в Eec выполняется:a) Случайным образом выбирается число r  [0,1] .b) Если r  Pecrc , то среди условий Eec случайным образом выбираетсяiэлементарное условие ecj того же типа, что и eci .c) Если была выбрана пара элементарных условий eci и ecj , топроисходит процедура их скрещивания на уровне элементарныхусловий.

Полученное в результате условиеec*заменяет eciвсоответствующем дизъюнкте в E  .5. Для каждого элементарного условия ecj в Eec выполняется:a) Случайным образом выбирается число r  [0,1] .b) Если r  Pecrc , то среди условий Eec случайным образом выбираетсяjэлементарное условие eci того же типа, что и ecj .c) Если была выбрана пара элементарных условий ecj и eci , топроисходит процедура их скрещивания на уровне элементарныхусловий. Полученное в результате условие ec*заменяет ecjвсоответствующем дизъюнкте в E  .6. Все дизъюнкты из E  и E  объединяются при помощи операции  и образуютаксиому a * , которая считается результатом скрещивания аксиом a и a .Параметром операции скрещивания на уровне аксиом является: Peccr - вероятностьучастия элементарного условия ec в скрещивании.III.

Уровень элементарных условий.Операция мутации.Для каждого элементарного условия из всех аксиом, входящих в системы аксиом изпопуляции Pl , производится операция мутации на уровне элементарных условий. Этаоперация изменяет параметры элементарного условия с заданной вероятностью:79ec( xt* , t , P), с вероятностью 1  Pecmutec( xt* , t , p) = ec( xt* , t , P), с вероятностью Pecmutгде: P = mec ( P, mutec ) - новый набор значений параметров элементарного условияec ; mec ( P, mutec ) - функция мутации параметров элементарного условия.Для изменения каждого из действительных параметров pi  Pec элементарногоусловия ec используется следующий алгоритм:1.

Выбирается действительное число r из диапазона [0, mutec ] .2. Параметр pi изменяется на величину ci  r , где ci - константа, соответствующаяпараметруpi . Знак изменения: ( pi  ci  r ) или ( pi  ci  r ) - выбираетсяслучайным образом.Дляизмененияцелочисленныхпараметровдополнительноиспользуетсяокругление величины, на которую происходит изменение значения параметраэлементарного условия.Параметрами операции мутации на уровне элементарных условий являются: Pecmut вероятность участия элементарного условия ec в мутации; mut- максимальнаяecстепень изменения значения параметра элементарного условия ec в ходе мутации.Операция скрещивания.Для каждой пары элементарных условий [ec, ec] , выбранной в алгоритме скрещиванияна уровне аксиом, производится операция скрещивания на уровне элементарных условий.Эта операция создает новое элементарное условие из двух выбранных элементарныхусловий одного типа:[ec( xt , t , P)  ec( xt , t , P)]  ec* ( xt , t , P* )Тип нового условия совпадает с типом скрещиваемых условий.

Каждый издействительныхпараметровpi*  P *новогоэлементарногоусловияec*определяется как среднее между соответствующими параметрами ec и ec :pi* =Дляцелочисленныхпараметровpi  pi2дополнительноприменяетсяпроцедураокругления: p  pipi* =  i 2 80Если элементарное условие ec* имеет нечисловые параметры, то они наследуютсяу одного из условий ec и ec . Для каждого такого параметра случайным образомопределяется то условие, от которого наследуется значение данного параметра.В операциях мутации и скрещивания для выбора случайных чисел из заданногодиапазона используется функция с равномерным распределением на этом диапазоне.Функции значимостиОперации мутации и скрещивания являются достаточно сложными и обладаютбольшим набором параметров. В зависимости от значений этих параметров операциямутации может быть более или менее дестабилизирующей.

Для того, чтобы параметрыопераций мутации и скрещивания определялись автоматически для каждой системыаксиом на каждой итерации генетического алгоритма, было предложено использоватьфункции значимости для особей популяции и для элементов особей в отдельности.Функция значимости системы аксиом M as определяется следующим образом:M as = c1e1  c2 e2  c3 as (e1 , e2 )  1 min (e1 , e2 )  1где: e1 , e2 - число ошибок распознавания I и II рода алгоритма распознавания на основесистемы аксиом as ;  as (e1 , e2 ) - значение целевой функции для системы аксиом as наобучающей выборке TS ;  min (e1 , e2 ) - минимальное значение целевой функции среди всехсистем аксиом в популяции; ci ,i = 1,3 - положительные константы.Слагаемые (c1  e1 ) и (c2  e2 ) входят в функцию M as для того, чтобы функциязначимости отражала насколько качественно алгоритм работает на контрольной выборке.Последнее слагаемое в формуле для M as позволяет оценить относительное качествоработы алгоритма распознавания на основе системы аксиом as по сравнению с другимисистемами аксиом в популяции.

Чем лучше система аксиом, тем меньше она изменяется входе мутации и с большей вероятностью участвует в скрещивании.Функция значимости аксиомы M a определяется как:M a = c4 M as  c5Num( X )  numaL  etha c6Num( X )Lгде: M as - функция значимости системы аксиом as , в которую входит аксиома a ;Num( X ) - число участков нештатного поведения в обучающей выборке TS ; numa - числосрабатываний аксиомы на траекториях обучающей выборки; L - число эталонных81траекторий; etha - число срабатываний аксиомы на эталонных траекториях; ci ,i = 4,6 положительные константы.Слагаемое (c4  M as ) входит в формулу M a для того, чтобы функция значимостиаксиомы отражала качество работы алгоритма распознавания на основе всей системыаксиом, в которую входит аксиома a .

Второе и третье слагаемое в формуле позволяютоценить относительный вклад аксиомы в распознавание участков нештатного поведения.Если условия аксиомы выполняются по разу только на участках нештатного поведения, товклад аксиомы в распознавание считается большим. Если же условия аксиомы невыполняются нигде или выполняются многократно и не только на участках нештатногоповедения, то вклад аксиомы считается меньшим. Чем больше значение функциизначимости M a , тем сильнее изменяется аксиома в ходе мутации и с меньшейвероятностью участвует в скрещивании.Параметры операций мутации и скрещивания определяются в зависимости отфункций значимости:mutcr[ Pasmut , mutas , Ras , Pas ] = F1 ( M as )crmutcr[ Pecmut , mut, mutec , Pec , Paa , Pa ] = F2 ( M a )Функции F1 , F2 построены таким образом, чтобы выполнялись условия:Все параметры операций скрещивания и мутации принимают значения от 0 до 1.mutmutmutmutВсе параметры мутации: Pecmut , mut, mut--- прямоec , Paa , Pas ,  as , Rasпропорциональны соответствующей функции значимости.Все параметры скрещивания: Peccr , Pacr , Pascr--- обратно пропорциональнысоответствующей функции значимости.Таким образом, чем меньше значение функции значимости, тем меньше изменяетсяособь или элемент особи при мутации и больше участвует в скрещивании.В данной работе для параметров мутации используются функции F1 и F2следующего вида:Pasmut =M as (1  d asmut )  d asmutmaxM asгде: d asmut  (0,1) - константа, которая ограничивает минимальное значение параметра Pasmut ;M asmax - параметр, который определяет максимальное значение для функции M as : есливычисленное значение M as превышает M asmax , то M as устанавливается равным M asmax .82Использование максимального ограничения для M as позволяет гарантировать, чтозначение Pasmut находится в диапазоне [0,1] .

Остальные параметры операции мутацииmutmutmut( Pecmut , mut, mutec , Paa ,  as , Ras ) определяются аналогичным образом.Для параметров скрещивания используются функции вида:Pascr =1  d ascr d ascr1  M asгде: d ascr --- константа, которая ограничивает минимальное значение параметра Pascr .Остальные параметры операции скрещивания ( Peccr , Pacr ) определяются аналогичнымобразом.Автоматическое определение параметров операций мутации и скрещивания накаждой итерации алгоритма для всех систем аксиом, на основании M as , и параметровэтих операций для аксиом и элементарных условий, на основании M a , позволяет:избежать ручного подбора параметров операций мутации и скрещивания;улучшить сходимость генетического алгоритма по сравнению со случаем, когдапараметры операций не изменяются на итерациях генетического алгоритма.Эффективность алгоритмаИспользование для построения системы аксиом генетического алгоритма сфункциями значимости позволяет получать алгоритмы распознавания, точность которых в2-3 раза выше по сравнению с алгоритмами распознавания для построения которыхиспользовался простой генетический алгоритм.С материалами подраздела 4.3.1.

можно ознакомиться в работах:1.Коваленко Д.С., Костенко В.А., Щербинин В.В. Параметрическое семейство алгоритмовраспознаваниянелинейноискаженныхфазовыхтраекторийдинамическихсистем//XIVВсероссийская научно-техническая конференция "Нейроинформатика-2012": Сборник научныхтрудов. Ч.1. М.: НИЯУ МИФИ, 2012. – С.266-276.2.В.А. Костенко, Д.С. Коваленко.

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

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