Диссертация (Интервальные методы оптимизации нелинейных детерминированных динамических систем при неполной информации о состоянии и параметрах объекта), страница 6

Уменьшение этихпараметров приводит к одновременному увеличению точности и времени работы алгоритма.Увеличение же приводит к общему ускорению за счет снижения точности работы алгоритма.Параметр  может уменьшить время работы алгоритма за счет удаления частивиртуальных значений. Тем не менее, слишком большие значения приведут к общемузамедлению работы, а также могут вызвать проблемы, связанные с нехваткой памятикомпьютера, на котором запускается алгоритм.1.2.3. МЕТОД СТОХАСТИЧЕСКОЙ ОТСЕЧКИ ВИРТУАЛЬНЫХ ЗНАЧЕНИЙСтратегия поискаСтратегия метода аналогична стратегии метода отсечки виртуальных значений,отличие заключается в способе работы оператора сжатия.

Метод использует стохастическихподход, применение которого обосновано тем, что, ввиду отсутствия предварительногоанализа функции, делается допущение, что границы множества виртуальных значенийрасположены случайно.АлгоритмШаг 1. Задать s – область поиска,  {0} - количество циклов,  – параметр точности,отвечающий за размер бруса во множестве, которое будет вырабатываться инвертером, и – параметр точности остановки алгоритма.Шаг 2. Положить y  f ( s) , pl  pr  mid( y ) .Шаг 3. Оператор сжатия. Вследствие наличия зависимости множества виртуальныхзначений от размера области поиска и структуры функции строится разбиение областипоиска для последующего сжатия множества виртуальных значений следующим образом:Шаг 3.1. Если  равно нулю, то перейти к шагу 4, в противном случае – к шагу 3.2.24Шаг 3.2. Случайным образом взять две точки  ~ U ( y, p l ) , 2 ~ U ( p r , y ) , где U (, )обозначает равномерное распределение.

Выработать с помощью инвертера множества1 INV ( f , s,[ y; 1 ], ) и2 INV ( f , s,[2 ; y ], ) .Шаг 3.3. Если множество1пустое, то положить y  [1 ; y ] , в противном случае2пустое, то положить y  [ y; 2 ] , в противном случаеположить pl  1 .Шаг 3.4. Если множествоположить pr  2 .Шаг 3.5. Уменьшить  на единицу. Перейти к шагу 3.1.Шаг 4. Дихотомически разделить интервалy2  [y y2yна два интервалаy1  [ y;y y2] и; y] .Шаг 5.

Инвертировать интервал y1 . В ходе данного шага вырабатывается множество брусов INV ( f , s, y1 , ) .Шаг 6. Если множество, выработанное инвертером, непустое, то перейти к шагу 7, еслипустое – к шагу 8.Шаг 7. Если ( y1 )   , тогда перейти к шагу 9. В противном случае положить интервал [ y ]равным y1 и вернуться к шагу 4.Шаг 8. Положить интервал y равным y 2 и если ( y)   , то вернуться к шагу 4. Впротивном случае пересчитать INV ( f , s, y, ) и перейти к шагу 9.Шаг 9. Выбор бруса.Шаг 9.1. Положить i  1 , множествоШаг 9.2. Если ( pi )   , где pi Шаг 9.3.

Добавить в множество., то перейти к шагу 9.4.брусы, полученные с помощью процедурыбисекции интервального вектора p i , удалить p i .Шаг 9.4. Увеличить i на единицу. Если i || , где |  | - мощность множества, топерейти к шагу 9.2.Шаг 9.5. Для каждого pi f ( pi ) .найти f ( pi ) и выбрать p*  Arg minip25Рекомендации по подбору параметровПараметры ,  имеют одинаковое влияние на работу алгоритма. Уменьшение этихпараметров приводит к одновременному увеличению точности и времени работы алгоритма.Увеличение же приводит к общему ускорению за счет снижения точности работы алгоритма.Параметр  может уменьшить время работы алгоритма за счет удаления частивиртуальных значений. Тем не менее, слишком большие значения приведут к общемузамедлению работы, а также могут вызвать проблемы, связанные с нехваткой памятикомпьютера, на котором запускается алгоритм.1.2.4. МЕТОД СТОХАСТИЧЕСКИХ ВЫРЫВАНИЙСтратегия поискаСтратегия метода заключается в отбраковывании брусов в области поиска за счет«вырывания» из области поиска небольших интервальных векторов (омега-характеристикакоторых не превосходит некоторого, заранее объявленного значения).

Для отбраковываниябрусов используется инвертер. В процессе данного «вырывания» будет постепенноуменьшаться ширина целевого интервала, в котором хранится значение минимума функции.При достижении необходимой ширины целевой интервал инвертируется и из полученногомножества выбирается решение.АлгоритмШаг 1. Задать s – область поиска,  – параметр точности (отвечает за размер выходногобруса),  – параметр точности остановки алгоритма, максимальное количество попыток A имаксимальное количество проходов без улучшений W . {s} , положить величину w  0 и найтиШаг 2.

Создать множество областей поискацелевой интервал y  f ( s) .Шаг 3. Если ( y)   , то перейти к шагу 4. В противном случае сгенерировать множество*INV ( f , s i , y, ) и перейти к шагу 19.si Шаг 4. Сгенерировать A случайных номеров брусов {id i }iA1 и A соответствующихслучайных точек {mi ,id  (m1i ,id ,, mni ,id )T  s id }iA1 (номер id i – указывает на номер бруса s idiизШагiiii, в котором генерировалась точка).5.Накаждойточкеmi ,idiпостроитьинтервальныйqi  ([m1i ,id   / 2; m1i ,id   / 2]  [mni ,id   / 2; mni ,id   / 2])  sid , i  1,, A .iiiiiШаг 6.

Из множества брусов {q i }iA 1 выбрать брус q*  Arg min f (q i ) .i 1,, A26векторШаг 7. Если f (q* )  y , то перейти к шагу 8. В противном случае – к шагу 12.Шаг 8. Положить y  [ y; f (q* )] .Шаг 9. Создать множествоt.результат инвертирования INV ( f , s i , y, ) занести вШаг 10. Для каждого из брусов s i вмножествоt.Шаг 11. Заменить множествомножествомt, положить w  0 . Перейти к шагу 13.Шаг 12.

Увеличить w на единицу.Шаг 13. Если w  W , то перейти к шагу 14. В противном случае – к шагу 3.Шаг 14. Уменьшить w на единицу.Шаг 15. Дихотомически разделить интервалy2  [y y2y1  [ y;y y2] и; y] .Шаг 16. Создать множествоt.результат инвертирования INV ( f , s i , y1 , ) занести вШаг 17. Для каждого из брусов s i вмножествоy на два интервалаt.Шаг 18. Если множествои заменить множествоtпусто, то положить y  y 2 . В противном случае положить y  y1множествомt. Перейти к шагу 3.Шаг 19. Выбор бруса.Шаг 19.1.

Положить i  1 , множествоШаг 19.2. Если ( s i )   , где s i *Шаг 19.3. Добавить в множество**., то перейти к шагу 19.4.*брусы, полученные с помощью процедурыбисекции интервального вектора s i , удалить s i .Шаг 19.4. Увеличить i на единицу. Если i |*| , где |  | - мощность множества, топерейти к шагу 19.2.Шаг 19.5. Для каждого s i *f ( si ) .найти f ( s i ) и выбрать s*  Arg mini*sРекомендации по подбору параметровПараметры , , A,W имеют одинаковое влияние на работу алгоритма. Уменьшениеэтих параметров приводит к одновременному увеличению точности и времени работы27алгоритма.

Увеличение же приводит к общему ускорению за счет снижения точности работыалгоритма.1.2.5. ОБОБЩЕННЫЙ ИНВЕРСНЫЙ МЕТОДСтратегия поискаЭтот метод обладает высокой гибкостью и настраиваемостью в связи с тем, чтооператоры сжатия и проверки вынесены в отдельные модули и могут выбираться взависимости от условий задачи. Предложены следующие операторы: операторы проверки:o Original Inverter operator (OI – operator) – базовая проверка, использующаяся вметоде дихотомии целевого интервала;o Original Inverter with Renewaloperator (OIR – operator) – в дополнение кбазовой проверке, выполняемой после каждой успешной операции, множествобрусов, подаваемых на вход, заменяется на множество, выработанноеинвертером;o First True operator (FT – operator) – проверка до первого подходящего элемента;o First True with Renewal operator (FTR – operator) – проверка до первогоподходящего элемента, множество брусов, подаваемых на вход, заменяетсяна множество, выработанное инвертером;o Random Sample operator (RS – operator) – эвристический оператор, которыйиспользует стохастический подход вместо инвертера;o Random Sample with Renewal operator (RSR – operator) – эвристическийоператор, который использует стохастический подход вместо инвертера имодифицирует множество брусов, подаваемых на вход; операторы сжатия:o Search Area Split operator (SAS - operator) – сжатие на основе разбиения областипоиска;o Random Point Sample operator (RPS – operator) – сжатие на основе значенийфункций в случайно сгенерированных интервальных векторах нулевойширины.o Inverter Cut operator (IC – operator) – сжатие на основе инвертера;o Inverter Cut with First True Check operator (ICFTC – operator) – сжатие на основепроверки до первого подходящего бруса;28o Inverter Cut with First True Check with Renewal operator (ICFTCR – operator) –сжатие на основе проверки до первого подходящего интервального вектора собновлением множества брусов, попадающих на вход;Следует упомянуть, что если использовать неэвристические операторы, то сходимостьметода такая же, как и у метода дихотомии целевого интервала.

Основным достоинствомданного обобщенного метода является то, что его компоненты могут быть выбраныэвристическими, что позволить сократить общее время работы метода.Алгоритмы операторов проверкиНа вход всех операторов проверки подается множество брусови проверяемыйинтервал l . Результатом работы является статус проверки: удачный свидетельствует о том,что в множестве брусовесть брус p , для которого выполнено ( p)   и f ( p)  l или( p)   и f ( p)  l   .Алгоритм OI оператора (для работы необходим параметр ширины w ).Шаг 1.

Для каждого бруса из множестваприменить алгоритм SIVIA [97] для интервала lс параметром w . Таким образом, будет выработано множество множеств брусов { i }|i1| (где|  | - мощность множества) .Шаг 2. Еслиi  , то проверка выполнена удачно. В противном случае проверкаiзавершена неудачно.Алгоритм OIR оператора (для работы необходим параметр ширины w ).Шаг 1. Для каждого бруса x i применить алгоритм SIVIA [97] для интервала l спараметром w . Результатом применения будут множества брусов { i }|i1| (где |  | - мощностьмножества).Шаг 2. Найти множествоi.i  , тогда проверка завершена неудачно. В противном случае проверкаШаг 3.

Еслизавершена удачно, заменить заданное множествона найденное множество.Алгоритм процедуры SIVIA_check (для работы необходим параметр ширины w ).Шаг 1. Для каждого бруса x найти f ( x ) .Шаг 2. Проверить выполнение следующих условий (сам брус x после проверки условийудаляется из):1) если f ( x )  l   , то продолжить работу;2) если f ( x)  l или f ( x )  l  , ( x )  w , то процедура завершена удачно;293) в случае невыполнения условий 1 и 2 найти брусы x1 , x 2 , полученные с помощьюпроцедуры бисекции интервального вектора x , и добавить их в множество.  , то перейти к шагу 1, в противном случае – процедура завершенаШаг 3.