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

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

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

Ее приоритет не может быть изменен и всегда остается наименьшим, чтоотражает ее индекс  . Для любой системы аксиом, дополненной тождественнойаксиомой, выполняется условие полноты.71Таким образом, в результате работы первого шага рассматриваемого генетическогоалгоритма построения системы аксиом формируется начальная популяция, состоящая изсистем аксиом с приоритетами, дополненными тождественными аксиомами:Pl = {as1 , as2 , , asn }Операции мутации и скрещивания генетического алгоритмаОперация мутации особи популяции преобразует эту особь:as  as *Операция скрещивания для двух особей популяции создает новую особь:[as  as]  as *Особью в популяции Pl является система аксиом, которая имеет многоуровневуюструктуру: система аксиом представляет собой упорядоченный набор аксиом, каждаяаксиома – это булева функция над множеством элементарных условий, каждое условиеимеет собственный набор параметров. Операции мутации и скрещивания должны иметьвозможность изменять каждую составляющую особи.

Поэтому эти операции определенына трех уровнях:I. Уровень систем аксиом.Операция мутации.Для каждой особи в популяции выполняется операция мутации:as  Pl :as, с вероятностью 1  Pasmutas = mutmutmas (as, mutas , Ras ), с вероятностью Pasmutгде: mas (as, mutas , Ras ) - функция мутации системы аксиом as .С вероятностью Pasmut система аксиом as изменяется функцией мутации mas .Функция мутации на уровне систем аксиом mas использует следующие вариантыизменения системы аксиом:o Удаление некоторой аксиомы из системы аксиом.o Замена некоторой аксиомы в системе аксиом на новую.

Новая аксиомасоздается случайным образом, как и при генерации начальной популяции.o Добавление новой аксиомы в систему аксиом. Новая аксиома создаетсяслучайным образом, как и при генерации начальной популяции. Приоритетновой аксиомы в системе аксиом определяется случайным образом.72o С вероятностью Rasmut изменение приоритета некоторой аксиомы в системеаксиом.Функция мутации работает по следующему алгоритму:1. Выбирается первая аксиома ai ,i = 1 в системе аксиом as .2. Для выбранной аксиомы ai выполняется:a) Случайным образом выбирается число: r  [0,1] .b) Если r > mutas , то происходит переход на шаг 3.c) С вероятностью 1/2 выбирается одно из действий, которое затемприменяется к аксиоме ai :o Удаление аксиомы из системы аксиом.o Замена аксиомы на новую.

При этом, новая аксиома создаетсяслучайным образом, как и при генерации начальной популяции.3. Если в системе аксиом as были выбраны все аксиомы, за исключениемтождественной a , то переход на шаг 4. Иначе, выбор следующей аксиомыai 1 и переход на шаг 2.4. Приоритет аксиом в системе выравнивается: если аксиома с индексом iотсутствует в системе, то все аксиомы с индексомj > i уменьшаютзначение индекса на единицу.5. Выбирается первая аксиома ai ,i = 1 в системе аксиом as .6. Для выбранной аксиомы ai выполняется:a) Случайным образом выбирается число: r  [0,1] .b) Если r > Rasmut , то происходит переход на шаг 7.c) Случайным образом выбирается аксиома a j , с которой ai обмениваетсяиндексами.7.

Если в системе аксиом as были выбраны все аксиомы, за исключениемтождественной a , то переход на шаг 8. Иначе, выбор следующей аксиомыai 1 , которая еще не была выбрана, и переход на шаг 6.8. Случайным образом выбирается целое число p от 0 до [mutas  N a ] , где: N a это число аксиом в системе аксиом as до начала выполнения данногоалгоритма мутации. Если ( N a  p) > N amax , то p уменьшается: p = N amax  N a .739. Случайнымобразомсоздаетсяpновыхаксиомпоалгоритму,используемому при генерации начальной популяции.10. Новые аксиомы добавляются в систему as .

Приоритет каждой новойаксиомы определяется случайным образом из диапазона [1, N a*  1] , где N a* текущее число аксиом в системе as . При добавлении новой аксиомы свыбранным индексом i все аксиомы с индексомj > i увеличиваютзначение индекса на единицу.Параметрами операции мутации на уровне систем аксиом являются: Pasmut вероятность мутации особи на уровне систем аксиом; mutas - вероятность измененияаксиомы в системе as ; Rasmut - вероятность изменения приоритета аксиомы всистеме аксиом as .Операция скрещивания.Выбор особей для скрещивания в популяции Pl происходит по следующемуалгоритму:1. Индекс особей в популяции устанавливается на первую систему аксиом:i = 1.2.

Для системы аксиом asi выбирается случайное число r  [0,1] . Если r > Pascr ,iто переход на шаг 4.3. Для системы аксиом asi выбирается пара для скрещивания:a) Выбирается(as j Plслучайноедействительноечислоrот0доPascr  Pascr ) .jib) Определяется индекс k , для которого выполняется:j[1, k 1], j  iPascr  r jj[1, k ], j  iPascrjЕсли таких индексов оказалось несколько1, то значение k выбираетсяслучайным образом из них.c) Пара индексов (i, k ) сохраняется в множестве Ccr .4. Если индекс i соответствует последней особи в популяции Pl , то алгоритмвыбора особей для скрещивания завершается. Иначе, выбор следующейсистемы аксиом ( i = i  1 ) и переход на шаг 2 данного алгоритма.1crЭто возможно, если несколько систем аксиом имеют нулевое значение Pas = 0 .74В результате работы данного алгоритма в множестве Ccr формируется набор париндексов особей в популяции, для каждой из которых запускается процедураскрещивания.Операция скрещивания двух систем аксиом формирует новую систему аксиом:[as{a1, a2 ,  , am , a }  as{a1, a2,  , an, a }]  as *{a1* , a2* ,  , ak* , a }Каждая аксиома ai* системы as * получена одним из следующих способов:- ai* взята из as ;- ai* взята из as ;- ai* получена в результате скрещивания аксиом aj  as и al as .Операция скрещивания систем аксиом as и as проходит по следующемуалгоритму:1.

Случайным образом определяется число аксиом от первой системы аксиом:rand (1,2) n1 =  N a 3где: N a --- число аксиом в системе аксиом as ; rand (1,2) --- функциягенерации случайных чисел из заданного диапазона с равномернымраспределением.2.

Случайным образом определяется число аксиом от второй системы аксиом:rand (1,2) n2 =  N a 3где: N a --- число аксиом в системе аксиом as .3. Если (n1  n2 ) > N amax , то выбирается наименьшее целое число k , прикотором:n1  n2  2  k < N amaxЗначения числа аксиом от каждой из систем уменьшается на k :n1 = n1  k , n2 = n2  k4. От первой системы аксиом as выбирается n1 аксиом. Множествовыбранныхаксиом обозначимA .Каждаяизаксиомвыбираетсяследующим образом:a) Вычисляется сумма:75S=ai as \ APacrib) Случайным образом выбирается действительное число r из диапазона[0, S ] .c) Выбирается такая аксиома ak , для которой выполняется:ai as \ A , i < kPacr  r iai as \ A, i  kPacri5.

Аналогично от второй системы аксиом as выбирается n2 аксиом.Множество выбранных аксиом обозначим A .6. Пусть для определенности n1  n2 . Обозначим: ncr = [n2 /2] . Из множества Aслучайным образом выделяется ncrаксиомAcr , из множестваAвыделяется ncr аксиом Acr :  Acr , A = Ano  Acr , | Acr |=| Acr |= ncrA = Ano7. Для каждой аксиомы из множества Acr случайным образом выбираетсясоответствующая аксиома изAcr . Для сформированных пар аксиомпроизводится скрещивание на уровне аксиом.

Полученное в результатемножество аксиом обозначим Acr . , Ano и Acr объединяются в систему аксиом as * .8. Аксиомы из множеств AnoПриоритеты аксиом в новой системе определяются случайным образом.Кроме того, в as * добавляется тождественная аксиома a с минимальнымприоритетом.Параметрами операции скрещивания на уровне систем аксиом является: Pascr- вероятность участия системы аксиом as в скрещивании; Pacr - вероятность участияаксиомы a в скрещивании.II.

Уровень аксиом.Операция мутации.Для всех аксиом a из каждой системы аксиом as  Pl производится операция мутации науровне аксиом. Эта операция изменяет аксиому с заданной вероятностью:a, с вероятностью 1  Pamuta=mutma (a, muta ), с вероятностью Paгде: ma (a, muta ) - функция мутации аксиомы.76Как было указано выше, аксиома представляет собой булеву формулу надмножеством элементарных условий:a( xt* , t ) =   ecij ( xt* , t , Pij )i ijjФункция мутации ma использует следующие варианты изменения аксиомы a :o Изменение логической связки между элементарными условиями в аксиоме:  ,   o Добавление или снятие знака отрицания для некоторого элементарногоусловия в аксиоме:ec  ec, ec  eco Удаление элементарного условия из аксиомы.o Замена условия на новое.o Добавление нового элементарного условия в аксиому.Функция мутации ma работает по следующему алгоритму:1.

Выбирается первое элементарное условие eci , i = 1 , входящее в аксиому a .2. Для выбранного элментарного условия eci выполняется:a) Случайным образом выбирается число: r  [0,1] .b) Если r > muta , то происходит переход на шаг 3.c) Случайным образом выбирается один из следующих вариантов мутации,который, затем, применяется к условию eci :o Изменение логической связки перед элементарным условием:  ,   o Добавление или снятие знака отрицания:eci  eci , eci  ecio Удаление элементарного условия из аксиомы.o Замена условия на новое. Тип нового условия выбирается случайнымобразом из множества {ec} , которое фиксировано в используемомшаблоне S k .

Параметры условия определяются случайным образом.3. Если в аксиоме a были выбраны все элементарные условий, то переход нашаг 4. Иначе, выбор следующего условия eci 1 , которое еще не быловыбрано, и переход на шаг 2.774. Случайным образом выбирается целое число p от 0 до [muta  N ec ] , где: N ec- это число элементарных условий в аксиоме a до начала выполненияданного алгоритма мутации. Если( N ec  p) > N ecmax , то значениеpполагается равным:p = N ecmax  N ec5. Случайным образом выбирается p элементарных условий из множества{ec} , которое фиксировано в используемом шаблоне S k . Типы выбранныхусловий могут совпадать, параметры каждого условия определяютсяслучайным образом.6. Новые элементарные условия добавляются в аксиому a .

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

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