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

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

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

При практической реализацииданного метода возникают затруднения, связанные с тем, что множество L(C) можетиметь сложную форму, быть несвязным. Поэтому сначала приближенно оцениваетсяминимальный гиперкуб B(C), целиком содержащий L(C), затем текущая область поискаустанавливается как S cur  B(C )  S .Критерий завершения. Алгоритм завершается при выполнении одного илинескольких из следующих условий:выполнение заданного числа вычислений "настоящей" целевой функции f ( X ) ;неулучшение решения за заданное число итераций;оценка значений производных в точке X min , которая представляет наилучшеенайденное на настоящий момент решение, позволяет говорить о достижении~локального минимума: f ( X min )  оценка вероятности улучшения решения на величину  на следующей итерациименьше некоторого порога pcrit : Prob( f ( X * )  f min   )  p crit ;оценка величины Imp( X ) ожидаемого на следующей итерации улучшениярешения меньше, чем некоторый порог  crit : Imp( X * )   crit .112Приложение 1.

Операторы мутации и скрещиванияОператор мутацииОбозначим символом x  ( x1 x 2 ...x n ) “родительское” решение, представленное каквектор числовых значений, в свою очередь обозначенных символами xi . Для элементов xiзаданы ограничения lbi  xi  ubi . Каждое из значений xi имеет один из следующих типов:вещественное число, целое число, номер элемента перечислимого множества. Оператормутации xˆ  m( x, Pm , S m ) порождает новое решение xˆ  ( xˆ1 xˆ2 ...xˆn ) по следующей схеме:для каждого i  1,2,.., n выбирается случайное число ri  (0,1) .ms( xi , S m ), if ri  Pmновое решение определяется по следующей формуле : xˆi  xi ,otherwiseЗдесь ms( xi , S m ) - функция мутации скалярного числового значения, которая мутируетотдельные элементы вектора решения x.

Различные способы определения ms( xi , S m )описаны ниже по тексту.Оператор мутации xˆ  m( x, Pm , S m ) зависит от двух основых параметров:Pm  (0,1) - вероятность мутации (чем больше это число, тем выше вероятностьтого, что любой наперед взятый элемент родительского решения будет изменен врезультате применения оператора мутации);S m  0 - степень (“сила”) мутации (чем больше это число, тем выше вероятностьтого, что изменения в элементах родительского решения будут скорее большими,нежелималыми;значениеSm  1соответствует“стандартному”маломуизменению)Функция мутации скалярного числового значения ms( xi , S m ) определяется, вобщем случае, по разному в зависимости от типа значения xi (вещественное число, целоечисло, элемент перечислимого множества).

Более того, для каждого типа значенийсуществует несколько альтернативных способов определения ms( xi , S m ) . Некоторые извозможных способов определения ms( xi , S m ) описаны ниже.Для вещественныхxi , функция ms( xi , S m )может быть определена двумяспособами:o "Простая" функция мутации числового значения. На первом шагевычисляется t – начальное приближение (предварительная оценка) длязначения функции ms( xi , S m ) :113ub  lbi ubi  lbit  xi  i2 ubi  lbi, if S m  10  4ri , где    S mi 1 ubi  lbi , otherwisemax(1, )Здесь ri  (0,1) - равномерно распределенные и независимые случайныевеличины,асимволомxобозначаетсяцелочисленноезначение,ближайшее к x.На втором шаге начальное приближение t корректируется исходя изнеобходимости попасть в интервал lbi  xi  ubi : t  ubi  lbims ( xi , S m )  tt  (ub  lb )iiif t  lbiif lbi  t  ubiif t  ubiКорректирующий шаг повторяется несколько раз, если это необходимо.o "Полиномиальная" функция мутации числового значения основана наполиномиальном операторе мутации, впервые описанном Дебом в работе[Kalyanmoy Deb and Mayank Goyal.

A Combined Genetic Adaptive Search GeneAS forEngineering Design. Computer Science and Informatics, 26(4):30--45, 1996.].В настоящейработе используется модифицированная версия оригинального оператора:1. Выбирается случайное значение u  (0,1) .2. Вычисляется параметр  m  min(S m ,1  10 2 ) , называемый индексомраспределения мутации (mutation distribution index). Чем большезначение этого индекса, тем менее сконцентрированным являетсяраспределение вероятных значенийms( xi )вокруг исходногозначения xi .3. Вычисляется параметр  ,используя функцию распределенияплотности вероятности P ( )  0.5( m  1)(1   ) m :11if u  0.5 (2u ) 1 m  1, 11  2(1  u ) 1 m 1 , if u  0.54.

Вычисляется начальное приближение для значения ms( xi ) :t  xi    (ubi  lbi )5. Начальное приближение корректируется исходя из необходимостипопасть в интервал lbi  xi  ubi :114 t  ubi  lbims ( xi , S m )  tt  (ub  lb )iiКорректирующийшагif t  lbiif lbi  t  ubiif t  ubiповторяетсянесколькораз,еслиэтонеобходимо.xi , функция ms( xi , S m )Для целочисленныхможет быть определена двумяспособами:o "Простая" функция мутации числового значения почти полностьюаналогична соответствующей функции, определенной для вещественныхпеременных (см. выше по тексту).

Отличие здесь заключается в том, чтофункция для вещественных переменных не обязательно всегда возвращаетцелочисленное значение. Поэтому вводятся дополнительные шаги постобработки, призванные обеспечить целочисленность результата. Эти шагиприведеныниже(результатфункциимутации,определеннойдлявещественных переменных, обозначен ниже символом msr ):ms   1, if msr   xi1. t   rotherwise msr ,lb , if t  ubi2. ms( xi , S m )   i t , otherwiseo "Бинарная" функция мутации числового значения. В этой функции xiпредставляется как битовая строка, к которой затем применяется“классический”операторпобитовоймутации.Процессвычислениябинарной функции мутации включает следующие шаги:1. Определяется минимальное число битов b необходимых дляпредставленияxiкак битовой строки: b  log 2 (ubi  lbi )  , гдесимволами lbi , ubi обозначены соответственно нижняя и верхняяграницы xi и символом x  обозначена минимальное целое число,большее или равное x.b2.

Значение xi представляется как битовая строка: xi  lbi    k 2 kk 13. Вычисляетсямаксимальноеколичествомутирующихбитов:ni  (b  1)  ( S m  0.5)1154. Выбирается случайный номер l,1  l  b , и в битовой строкеинвертируется бит с номером l:  l  1   l .

Данный шаг повторяетсяni раз.6. Вычисляется предварительныйрезультат tфункции мутации,bиспользуя мутированную битовую строку: t  lbi    k 2 kk 17. Результат корректируется исходя из необходимости попасть винтервал lbi  xi  ubi : t  ubi  lbims ( xi , S m )  tt  (ub  lb )iiДляif t  lbiif lbi  t  ubiif t  ubixi , представляющих собой номер элемента некоторого перечислимогомножества, функцияms( xi , S m )возвращает случайное целое число, равномернораспределенное в интервале [lbi , ubi ] .Оператор скрещиванияПредположим, что x  ( x1 x 2 ...x n ) и y  ( y1 y2 ...

yn ) , где xi , yi - некоторые числовыезначения (имеющие один из следующих типов: вещественное число, целое число, номерэлемента перечислимого множества), являются двумя “родительскими” решениями,выбранными для скрещивания. Оператор скрещивания порождает два новых решения,xˆ  ( xˆ1 xˆ2 ...xˆn ) и yˆ  ( yˆ1 yˆ 2 ... yˆ n ) , используя один из следующих методов:одноточечное скрещивание:Выбирается случайный номер k,1  k  n . Затем элементы нового решенияопределяются по следующим формулам: x , if i  kxˆ i   i y i , if i  k y , if i  kyˆ i   i xi , if i  kсмешивающее скрещивание:Независимо для каждого номера i, 1  i  n , выбирается случайное число r,0  r  1 , затем определяются (по нижеприведенным формулам) элементы новогорешения:116lmix ( xi , y i ), if r  Pcrxˆ i  xi ,otherwisermix( xi , yi ), if r  Pcryˆ i  yi ,otherwiseодноточечное скрещивание со смешиванием центральной точки:Выбирается случайный номер k, 1  k  n .

Элементы нового решения вычисляютсяпо следующим формулам:xi ,if i  kxˆi  lmix ( xi , yi ), if i  kyi ,if i  kxi ,if i  kyˆ i  rmix( xi , yi ), if i  kyi ,if i  kСимволами lmix( xi , yi ) и rmix( xi , yi ) выше обозначены два значения,вычисляемые так называемым смешивающим оператором [lmix, rmix]  mix( xi , yi ) , асимволом Pcr обозначена вероятность скрещивания (это настраиваемый параметр).Смешивающий операторmix( xi , yi )выполняет “скрещивание” двух числовыхзначений (не векторов, а чисел). Смешивающий оператор определяется по разному дляцелочисленных и вещественных значений.Длявещественныхзначений,смешивающийоператорможетбытьопределен одним из следующих способов:o смешивание с использованием оператора SBX (имитация бинарногоскрещивания, simulated-binary crossover).

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

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