Ознакомительная версия. Доступно 17 страниц из 85
1. Выбирается стартовый узел. Начиная с этого узла, выполняется процедура исследующего поиска. Данная процедура заключается в исполнении нескольких циклов описанного выше метода покоординатного подъема. Один цикл исследующего поиска состоит из n циклов покоординатного поиска (n – количество параметров). Для двумерного оптимизационного пространства требуется провести два цикла покоординатного подъема с тем, чтобы дополнительно к стартовому узлу найти два субоптимальных узла.
2. Выполняется процедура поиска по образцу. Для этого необходимо определить направление от стартового узла на найденный (в результате исполнения первого цикла исследующего поиска) узел. В этом направлении значение функции росло, и можно предположить, что, двигаясь далее в том же направлении, получим дальнейшее улучшение.
3. Выполняется процедура поиска в направлении, определенном на предыдущем этапе. В отличие от покоординатного подъема, данная оптимизация происходит при одновременном изменении всех параметров. Если в покоординатном подъеме движение возможно только по горизонтали или по вертикали (в двумерном случае), то поиск по образцу допускает движение вдоль любой прямой принадлежащей оптимизационной поверхности (или пространству в случае оптимизации более двух параметров).
4. Найдя наилучшую точку в этом направлении, повторяем цикл исследующего поиска, после чего вновь выполняем поиск по образцу, пока не достигнем точки, неулучшаемой ни на том, ни на другом этапе.
Рассмотрим применение метода Хука-Дживса на примере оптимизации базовой дельта-нейтральной стратегии по целевой функции «прибыль». По аналогии с предыдущим примером ограничим области допустимых значений параметров теми же диапазонами (2–80 для параметра «число дней до экспирации» и 100–300 для параметра «период истории для расчета HV»). Выполнение алгоритма происходит следующим образом:
1. Случайным образом выбираем стартовую точку. Предположим, что был выбран узел с координатами 68 и 300. Данный узел отмечен номером 1 на рис. 2.7.2.
2. Начинаем процедуру исследующего поиска, заключающуюся в исполнении двух (по числу параметров) циклов покоординатного подъема. Зафиксировав параметр «число дней до экспирации» на значении 68, вычисляем целевую функцию для всех значений параметра «период истории для расчета HV». Определяем узел с максимальным значением целевой функции, каковым является узел с координатами 30 и 225 (точка номер 2 на рис. 2.7.2).
3. Фиксируем значение параметра «период истории для расчета HV» на значении 225 и вычисляем целевую функцию для всех значений параметра «число дней до экспирации». Максимальное значение функции приходится на узел с координатами 36 и 225 (третья точка).
4. Выполняем процедуру поиска по образцу. Определяем направление от стартового узла (номер 1) на узел 3 (стрелка на рис. 2.7.2) и выполняем одномерную оптимизацию в найденном направлении. Вычисляем значение целевой функции во всех узлах, пересекаемых диагональю в заданном направлении.
5. Выбираем узел с максимальным значением целевой функции (четвертая точка с координатами 30 и 210). Начиная с этого узла, повторяем цикл исследующего поиска.
6. Фиксируем значение параметра «число дней до экспирации» на значении 30 и вычисляем целевую функцию для всех значений параметра «период истории для расчета HV». Максимальное значение функции оказывается в узле с координатами 30 и 105 (пятая точка).
7. Фиксируем период истории на значении 105 и вычисляем целевую функцию для всех дней до экспирации. Выясняем, что дальнейшего улучшения не происходит и, следовательно, алгоритм останавливается. Оптимальным решением является узел номер 5.
Метод Розенброка
Данный метод, называемый также методом вращающихся координат, является следующим шагом в усложнении метода покоординатного подъема. Первый его этап совпадает с методом покоординатного спуска. Затем, аналогично методу Хука и Дживса, находится направление, в котором улучшается целевая функция. Однако, помимо этого направления, строится еще (n − 1) направление, каждое из которых ортогонально найденному направлению и все они ортогональны между собой. Таким образом, вместо исходных параметров получается новая система координат. По отношению к исходной системе координат она повернута так, что одна из ее осей совпадает с направлением возрастания функции, найденном на предыдущем этапе. В этой системе координат производится очередной цикл покоординатного подъема, результат которого используется для нового вращения координат и следующего шага оптимизации. Для двумерного пространства алгоритм метода Розенброка имеет следующий вид.
1. Выбирается стартовый узел, начиная с которого выполняется цикл исследующего поиска (то есть два цикла покоординатного подъема).
2. Определяется направление от стартового узла на найденный узел и выполняется процедура поиска в этом направлении (поиск по образцу).
3. Найдя наилучший узел в этом направлении, строится направление перпендикулярное к ранее найденному направлению.
4. Производится поиск в перпендикулярном направлении и находится узел с наибольшим значением целевой функции.
5. Начиная с узла, найденного на перпендикулярном направлении, повторяем все процедуры (исследующий поиск, поиск по образцу, перпендикулярный поиск).
Рассмотрим практическое применение метода Розенброка на примере базовой дельта-нейтральной стратегии. Как и в предыдущих примерах, ограничим области допустимых значений параметров: 2–80 для параметра «число дней до экспирации» и 100–300 для параметра «период истории для расчета HV». Для выполнения алгоритма следует исполнить следующие процедуры:
1. Случайным образом выбираем стартовую точку. Предположим, что был выбран узел с координатами 70 и 180. Данный узел отмечен номером 1 на рис. 2.7.3.
2. Начинаем процедуру исследующего поиска, заключающуюся в исполнении двух циклов покоординатного подъема. Фиксируем параметр «число дней до экспирации» на значении 70 и вычисляем целевую функцию для всех значений параметра «период истории для расчета HV». Узел с максимальным значением целевой функции имеет координаты 70 и 240 (точка номер 2 на рис. 2.7.3).
3. Зафиксировав параметр «период истории для расчета HV» на значении 240, вычисляем целевую функцию для всех значений параметра «число дней до экспирации». Максимум функции приходится на узел с координатами 36 и 240 (третья точка).
4. Выполняем процедуру поиска по образцу. Определяем направление от стартового узла (номер 1) на узел 3 (правая верхняя стрелка на рис. 2.7.3) и вычисляем значение целевой функции во всех узлах, пересекаемых данным направлением.
5. Находим узел с максимальным значением целевой функции (четвертая точка с координатами 40 и 230) и строим направление, перпендикулярное к ранее найденному направлению.
Ознакомительная версия. Доступно 17 страниц из 85
