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

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

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

Функция выбора точки следующего испытания в~этом случае принимает следующий вид: I ( X , M , T )  f ( X ) . Недостатком даннойстратегии является высокая вероятность "зацикливания" алгоритма, что происходит, если~для точки X * , доставляющей минимум функции f ( X ) и , тем самым, являющейсярешением задачи (4), уже существует запись в БД (т.е.

если значение "настоящей" целевойфункции f ( X * ) уже было вычислено ранее). В этом случае повторное вычислениезначения f ( X * ) не дает оснований для уточнения модели М или области поиска S cur , ипоследующие итерации алгоритма не приносят новых результатов. При этом точка X *даже не обязательно является точкой локального минимума функции f ( X ) . Способомизбежатьзацикливания"поощрения"заявляетсяотдаленностьвведениеточкивXфункциюотI ( X , M ,T )точек,аддитивногопомещенныхвБД:~I ( X , M , T )  f ( X )    d ( X , T ) , где d ( X , T )  min X  X ' , и   0 - параметр (величинаX 'Tпоощрения).Более надежной является стратегия, предложенная в рамках P-алгоритма [A.

Zilinskas.Axiomatic characterization of a global optimization algorithm and investigation of its search strategy. OperationsResearch Letters, 4(6):35–39, 1985.].Пусть f min  min f ( X ) - наименьшее значение целевойX Tфункции, найденное на текущий момент. Идея P-алгоритма заключается в поиске точки,для которой с максимальной вероятностью значение целевой функции будет меньше чемf min как минимум на некоторую пороговую величину  :Prob( f ( X )  f min   )  max(6.2.)~Для вычисления вероятности (6.2.) используются оценка f ( X ) значения целевой функции~и оценка ~ ( X ) математического ожидания ошибки аппроксимации  ( X )  f ( X )  f ( X )~(стандартное отклонение для оценки f ( X ) ). Предполагается, что для любого X ' S cur ,~o оценка f ( X ' ) является несмещенной: E ( X ' )  0 , иo ошибка аппроксимации  ( X ' ) имеет нормальное распределение.107В этом случае распределение значений целевой функции в точке X ' S cur может~быть описано нормальным распределением: f ( X ' )  N ( f ( X ' ), ~ ( X ' )) .

В данныхпредположениях вероятность в формуле (6.2.) может быть вычислена явно, и функциявыбора точки след. испытания принимает следующий вид:~f min   f  f ( X )),I ( X , M , T )   (~ ( X )(6.3.)где  () - функция распределения стандартного нормального распределения N (0,1) .Можно показать, что задача минимизации функции (6.3.) эквивалентна задачеминимизации следующей функции:~ ( X )I ( X , M ,T )   ~f ( X )  f min   f2(6.4.)Рассмотрим свойства функции (6.4.). Пусть X T - множество точек, значения целевойфункции для которых известны (есть записи вида {( X i , f ( X i ))}  T , где X i  X T ). Еслимодель M целевой функции строится посредством точной интерполяции (например, с~использованием DACE модели [DaceMod]), то для X  X T выполняется f ( X )  f ( X ) и~( X )  0 , из чего следует I ( X i , M , T )  0 .

С другой стороны, для X  X T выполняется~ ( X )  0 , из чего следует I ( X , M , T )  0 . Таким образом, функция I ( X , M , T ) достигаетX *  X T , что предотвращает повторные вычисленияцелевой функции и "зацикливание" (исключая вырожденный случай ~ ( X )  0 ).минимума в некоторой точкеНедостатком P-алгоритма является сложность выбора порога  , которыйнепосредственно влияет на скорость сходимости алгоритма и сложность минимизациифункции (7). Один из возможных подходов к выбору  заключаются в применениидинамической адаптации.

На разных итерациях алгоритма используются разные значенияпорога  f , для оценки пригодности конкретного значения  *f анализируются данные,собранные по предыдущим итерациям алгоритма (предсказанная вероятность (5)наступления событияf ( X * )  f min   *f , и факт наступления/ненаступления данногособытия, проверяемый апостериорно, после вычисления значения f ( X * ) ).На рис. 6.1.

приведена иллюстрация работы P-алгоритма. Критерий выбора точкииспытания - максимум вероятности (5) (черная линия).108f(x)Узлы интерполяцииfmin~f ( x)  ~( x)~f ( x)Prob( f ( x)  f min  0.01)Рис.6.1. Иллюстрация работы P-алгоритма (красные линии - моделируемая функция,синие линии - DACE интерполяция, черная линия - вероятность (5)) .Cтратегия максимального ожидаемого улучшения [J. Mockus. Application of bayesianapproach to numerical methods of global and stochastic optimization.

Journal of Global Optimization, 4:347–365,1994.].Обозначим Imp( X )  max{ f ( X )  f min ,0} - величину улучшения наименьшегозначения целевой функции, найденного на текущий момент, которое может произойтипосле проведения испытания в точке X. Cтратегия максимального ожидаемого улучшениязаключается в поиске точки, для которой математическое ожидание ожидаемогоулучшения максимально:EImp( X )  max(6.5.)Вычислить значение Imp( X ) возможно при принятии тех же предположений о модели M,что и в случае с P-алгоритмом (несмещенность оценки~f (X ')и нормальноераспределение ошибки аппроксимации  ( X ' ) ).

Функция выбора точки след. испытанияпринимает следующий вид:~~ f min  f ( X )f min  f ( X ) ~~  ( f  f ( X ))   ()  ,)   ( X ) (I ( X , M , T )    min~ ( X )~ ( X ),0~ ( X )  0~ ( X )  0Здесь, () и  () - функции распределения и плотности стандартного нормальногораспределения N (0,1) .109Как для P-алгоритма, так и для стратегии максимального ожидаемого улучшения,при использовании точной интерполяции при построении модели М минимум функцииI ( X , M , T ) достигается в точке X *  X T .Cтратегия достижения наибольшей гладкости (наименьшей "холмистости")интерполяционной функции [D.R.

Jones, M. Schonlau, and W.J. Welch. E_cient global optimization ofexpensive black-box functions. Journal of Global Optimization, 13(4):455–492, 1998.].Пусть f a  f min -некоторая априорная оценка минимального достижимого значения функцииf (X ) ,X T  { X i } - множество точек, для которых значения целевой функции f ( X i ) известны,~f ( X ) - интерполяционная оценка значения целевой функции f ( X ) на множестве S cur~(однозначно определяемая набором узлов интерполяции), S [ f ] - некоторый функционал,~оценивающий гладкость (в каком-либо смысле) интерполяционной функции f ( X ) навсем множестве S cur . Предположим, что точка X a  X T является решением задачи (1),~т.е. что f ( X a )  f a . В этом случае интерполяция f ( X ) зависит от X a и однозначнозадается уравнениями:~f ( X i )  f ( X i ) для X i  X T~f (X a )  fa~Оценка гладкости S [ f ] может рассматриваться как функция отX a .

Cтратегиядостижения наибольшей гладкости заключается в поиске такой точки X a , для которой~результирующая интерполяция была бы наиболее "гладкой": S [ f ]  min .При реализации данной стратегии существенное значение имеют способ оценки~гладкости интерполяции f ( X ) , и способ выбора значения f a . В общем случае, хорошейоценкой~S[ f ] гладкости  f ( X ) dX ,~S2являетсяинтегралквадратавторойпроизводной~f (X ) :однако на практике вычисление такого интеграла часто являетсяcurвесьма трудной задачей.

Тем не менее, для интерполяции с помощью функцийрадиального базиса в работе [Gutmann H-M. A radial basis function method for global optimization. //Technical report DAMTP 1999/NA22, Department of Applied Mathematics and Theoretical Physics, University ofCombridge, England, (1999).]Значения~разработаны эффективные методы оценки значения S [ f ] .f a могут выбираться в зависимости от номера итерации циклически измножества { f min  k1 ,..., f min  k n } , где k1 ,..., k n - возрастающая последовательность чисел.110Большие значения ki соответствуют "глобальному" поиску в области S cur , малыезначения ki с большей вероятностью направляют поиск в окрестность текущегонаилучшего найденного решения.Алгоритм решения задачи оптимизации на модели.

Для решения задачи (4) можетиспользоваться любой алгоритм оптимизации, обеспечивающий отыскание глобальногоминимума с достаточной вероятностью. Поскольку затраты на вычисление функциивыбора точки испытания I ( X , M , T ) обычно малы по сравнению с затратами навычисление "настоящей" целевой функцииf ( X ) , вполне допускается выполнениебольшого числа итераций в процессе решения задачи (4) - приоритетом здесь являетсянахождение глобального минимума с как можно большей точностью.В качестве примера алгоритмов, пригодных для решения задачи (6.1.), можнопривестиалгоритмдифференциальнойэволюцииигенетическийалгоритм,использующий кодирование решения числами с плавающей точкой.

Стоит отметить, чтодля ряда способов построения модели M и функцииI ( X , M , T ) возможно получениеаналитических выражений для градиента I ( X , M , T ) , что дает возможность эффективноиспользовать алгоритмы локальной оптимизации для ускорения решения задачи ибыстрой доводки текущих решений до ближайшего локального оптимума. Таким образом,для решения задачи (6.1.) весьма эффективным представляется подход, основанный насовместном применении методов локальной и глобальной оптимизации (т.н.

гибридныеалгоритмы).Алгоритм уточнения области поиска. В процессе работы алгоритма увеличиваетсяколичество доступной информации о целевой функцииf ( X ) , что влечет за собойповышение достоверности и точности аппроксимирующей модели M. Поэтому, начиная снекоторого момента, на основании анализа модели M становится возможно сопределеннойстепеньюдостоверностиидентифицировать"перспективные"и"неперспективные" области (в смысле вероятности отыскания глобального минимумафункцииf ( X ) ). Периодическое уточнение области поискаS cur  Sпреследуетследующие цели:сконцентрировать поисковые усилия в наиболее "перспективных" областяхмножества S допустимых значений параметров;избежать ненужных затрат на построение и исследование аппроксимирующеймодели M в областях, где отыскание глобального минимума функции f ( X )маловероятно.111Один из методов состоит в ограничении текущей области поиска некоторойокрестностью точки X min , которая представляет наилучшее найденное на настоящиймомент решение.

Текущая область поиска S cur определяется как пересечение исходнойобласти поиска S и гиперкуба co сторонами ri , i  1,2,.., N и центром в точке X min :(i )S cur  {S | S min S ( i )  ri }  S ,Размерыгиперкуба, заданные значениями ri , постепенно уменьшаются с работойалгоритма.Степеньуменьшенияможетзависетьотрезультатовпериодическипроводящейся оценки корректности модели М.Альтернативныйсостоит в ограничении текущей области поиска~множеством L(C) точек, где оценка f ( X ) значения целевой функции не превосходитнаилучшегометоднайденногозначенияf minнанекоторуюконстантуС:~L(C )  { X | f ( X )  f min  C}  S . В процессе работы алгоритма константа С уменьшается,что приводит к постепенному сужению области поиска.

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

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