Перейти к содержимому


Фотография

Об оптимизации методом Монте-Карло


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 6

#1 Anatoly Utkin

Anatoly Utkin

    Активный участник

  • Пользователи
  • PipPipPip
  • 158 сообщений

Отправлено 03 Февраль 2011 - 17:22

Оптимизация–это настройка торговой системы на рынок. Если взглянуть широко, то по сути весь процесс построения системы–это оптимизация. Однако в настоящей заметке я бы хотел продемонстрировать свои текущие подходы к оптимизации в классическом понимании этого слова. Если следовать классическому подходу, то процесс построения системы можно условно разбить на следующие этапы: 1) Наблюдения за рынком, 2) Формулировка какого-то количества грубых закономерностей, 3) Выбор некоего множества этих закономерностей и сведение их в единый алгоритм, 4) Подбор параметров (Это оптимизация в общепринятом смысле). Этапы 1 и 2–это в большей мере искусство, и эта часть определяется, в основном, опытом и знаниями трейдера. Этапы же 3 и 4 поддаются формализации, причем одновременно, нет необходимости разделять 3 и 4. Вот как это может быть выполнено. Допустим, есть две грубых закономерности (Они приведены ниже, но это модельные вещи, а в реальном рынке к поиску закономерностей следует относиться серьезно. Еще раз подчеркну: поиск закономерностей–это искусство): а) Если цена выше длиннопериодной средней, то рынок настроен на рост, б) Если короткопериодная средняя ниже среднепериодной, то рынок настроен на разворот вверх. Задача–слепить из этих закономерностей систему. Зададимся вопросом–сколько здесь параметров? Прежде всего, это периоды средних–их три. Кроме того, можно включать, или не включать саму закономерность–это еще два параметра со значениями 1 или 0 (используем или не используем закономерность). Нам необходимо выбрать из всех возможных вариантов некий один, устраивающий нас. Вопрос–как это сделать? Первый вариант–перебрать все возможности. К сожалению, экспоненциальный рост числа возможностей от числа параметров делает эту идею при большом числе параметров безнадежной. Это то же самое, что угадать многозначный пароль. Посчитаем общее число вариантов в нашей задаче. Пусть период короткой средней лежит от 1 до 10, среднепериодной–от 11 до 50, длиннопериодной–от 51 до 200. Тогда общее число вариантов составит 10*40*150*2*2=240 000. Даже в нашем небольшом наборе правил четверть миллиона возможностей. Если тестер тратит 0.01 секунды на прогон (что быстро), то даже при этом будет потрачено 2400 секунд, то есть 40 минут. При увеличении числа параметров это время растет экспоненциально и для систем средней сложности может достигать веков и тысячелетий. Поэтому прямой перебор применим лишь для простейших систем. Как же быть? Для нахождения оптимальных параметров в многокритериальных задачах человечеством давно уже придуманы мощные и быстрые методы. Основный из них–это генетическая оптимизация. Однако, поскольку я ей в настоящее время в трейдинге не пользуюсь, то про нее рассказывать здесь не буду. Опишу то, чем пользуюсь я. Это так называемый метод Монте-Карло (в физике его еще называют методом отжига). Фактически, это весьма усеченная версия генетики. Его суть такова: случайным образом выбирается точка в пространстве параметров. Затем от нее в некоторой окрестности радиуса R1 также случайным образом выбираются другие точки и смотрится, в какой из них целевая функция наилучшая (назовем эту точку A). Затем от точки A в радиусе R1 опять случайно выбираются точки и смотрится наилучшая. И такой процесс повторяется много раз, причем R1–сравним с размером всей области параметров. Назовем все вышеописанное фазой 1. После окончания фазы 1 наступает фаза 2. Она совпадает с первой фазой, единственное отличие–в радиусе. Для фазы 2 радиус R2 меньше R1. После фазы 2 проводится фаза 3 с R3<R2<R1, и так далее. На некотором числе фаз процесс останавливается. Вся эта процедура приводит к тому, что точка в пространстве параметров в среднем двигается в направлении максимума целевой функции (но не факт, что глобального, в этом недостаток и Монте-Карло и генетики). При этом число прогонов тестера равно ”число фаз*число процессов*число точек в процессе”. Видно, что число прогонов тестера не зависит от числа параметров вообще, и в этом огромное преимущество метода. Хорошей физической моделью метода Монте-Карло является неровная поверхность с песком. Если ее потрясти, то песок скопится в наинизшей точке, то есть найдет оптимальную наинизшую точку неровной поверхности. Таким образом, пользуясь современными методами поиска экстремумов, можно весьма упростить процесс системостроительства по сравнению с ”индикаторной эрой”.

#2 Николай Степенко

Николай Степенко

    Активный участник

  • Главные администраторы
  • PipPipPip
  • 9 440 сообщений
  • Пол:Мужчина
  • Город:Холон
  • Интересы:трейдинг, биржа, обучение трейдингу, технический анализ, фундаментальный анализ, велосипед, море, путешествия

Отправлено 03 Февраль 2011 - 21:50

Это так называемый метод Монте-Карло (в физике его еще называют методом отжига). Фактически, это весьма усеченная версия генетики. Его суть такова: случайным образом выбирается точка в пространстве параметров. Затем от нее в некоторой окрестности радиуса R1 также случайным образом выбираются другие точки и смотрится, в какой из них целевая функция наилучшая (назовем эту точку A). Затем от точки A в радиусе R1 опять случайно выбираются точки и смотрится наилучшая. И такой процесс повторяется много раз, причем R1–сравним с размером всей области параметров. Назовем все вышеописанное фазой 1. После окончания фазы 1 наступает фаза 2. Она совпадает с первой фазой, единственное отличие–в радиусе. Для фазы 2 радиус R2 меньше R1. После фазы 2 проводится фаза 3 с R3<R2<R1, и так далее. На некотором числе фаз процесс останавливается.

Вся эта процедура приводит к тому, что точка в пространстве параметров в среднем двигается в направлении максимума целевой функции (но не факт, что глобального, в этом недостаток и Монте-Карло и генетики). При этом число прогонов тестера равно ”число фаз*число процессов*число точек в процессе”. Видно, что число прогонов тестера не зависит от числа параметров вообще, и в этом огромное преимущество метода. Хорошей физической моделью метода Монте-Карло является неровная поверхность с песком. Если ее потрясти, то песок скопится в наинизшей точке, то есть найдет оптимальную наинизшую точку неровной поверхности.

Таким образом, пользуясь современными методами поиска экстремумов, можно весьма упростить процесс системостроительства по сравнению с ”индикаторной эрой”.

А можно по-проще? Монте - Карло имеет отношение к рулетке. Значит на примере казино можно описать. Или нет? И написанное выше - самый простой вариант описания?

#3 Anatoly Utkin

Anatoly Utkin

    Активный участник

  • Пользователи
  • PipPipPip
  • 158 сообщений

Отправлено 04 Февраль 2011 - 00:27

А можно по-проще? Монте - Карло имеет отношение к рулетке. Значит на примере казино можно описать. Или нет? И написанное выше - самый простой вариант описания?

Монте-Карло в названии связано с использованием случайных величин для решения детерминированной задачи. Насчет самого простого--не уверен, ничего самого-самого в этом мире вообще нет :)

Попробую пояснить методу на простом примере. Пусть нам надо найти минимум функции y=N*N, где N изменяется от -1000 до +1000 с шагом 1. Этот пример хорош тем, что ответ в нем очевиден--минимум достигается при N=0 и равен нулю. Простым перебором необходимо 2000 шагов, чтобы прийти к ответу. Проделаем то же самое методом Монте-Карло. Выберем случайным образом некое N из интервала (-1000, 1000). Пусть это 789. Дальше нам нужен генератор случайных чисел--в роли него используем монетку. Если орел, то прибавим к 789 четверть всего интервала (то есть 500), если решка--отнимем. Кидаю монету :) Получился орел. Добавляя к 789 500, получим 1289, что во-первых, выводит нас за рамки диапазона, и во-вторых, 789*789<1289*1289. Поэтому не будем менять точку. Кидаем монету еще раз. Блин, опять орел--все то же. Еще раз кинул--монетка упала со стола, но счастье--выпала решка. Вычитая из 789 500 получим 289. Можно еще покидать монетку (каждый кидок--это "процесс" в моей терминологии), допустим, в каждой фазе у нас по 10 процессов--то есть 10 кидков монеты. Но ясно, что в нашей простой задаче итогом первой фазы будет точка 289. Приступим ко второй фазе. Она совпадает с первой, но изменять точку будем не на 500 а на 250 (уменьшаем радиус--он стал восьмой частью всего интервала). И опять, при орле мы будем уходить в точку 289+250=539, а при решке в точку 289-250=39. Ясно, что 39*39<289*289, поэтому нам нужна точка 39. Так закончится фаза 2. На третьей фазе будем прибавлять/отнимать шестнадцатую часть всего интервала, то есть 125. Ясно, что как 39+125, так и 39-125 дадут большие значения N*N, чем само значение 39, поэтому итогом третьей фазы будет 39. Четвертая фаза опять даст 39, а вот пятая, на которой прибавлять/отнимать надо 31, выведет нас в точку 39-31=8, то есть уже совсем вблизи минимума. Вот приблизительно так.

Теперь о скорости счета. Допустим, у нас 10 фаз по 10 кидков монеты в каждой. Это значит, что нам надо вычислить целевую функцию 10*10=100 раз, и вычислим мы ее с точностью до 2000/2^13, то есть с точностью до числа, меньшего единицы, то есть точно. Поэтому даже в этом простом примере Монте-Карло находит минимум гораздо быстрее, чем простой перебор. Если же функция многопараметрическая (то есть зависит не от одного N, а от N, M, K, J, H), то прямой перебор потребует 2000^5=32 000 000 000 000 000 вычислений, тогда как Монте-Карло--приблизительно те же 10 фаз по 10 бросков.

О недостатках Монте-Карло (и генетики вообще). Если целевая функция имеет не один, а много локальных минимумов (например, N^4-N^2+N), то Монте-Карло выдаст какой-то из них, не обязательно самый глубокий. Тогда как прямой перебор выдал бы самый глубокий.

#4 Николай Степенко

Николай Степенко

    Активный участник

  • Главные администраторы
  • PipPipPip
  • 9 440 сообщений
  • Пол:Мужчина
  • Город:Холон
  • Интересы:трейдинг, биржа, обучение трейдингу, технический анализ, фундаментальный анализ, велосипед, море, путешествия

Отправлено 04 Февраль 2011 - 00:44

Кидаю монету :) .... Кидаем монету еще раз. Блин, ...

Другое дело. Когда про монетки и кидаем, то быстрее доходит. Если б ты написал - Кидаем золотую монетку... дошло бы быстрее.

#5 Anatoly Utkin

Anatoly Utkin

    Активный участник

  • Пользователи
  • PipPipPip
  • 158 сообщений

Отправлено 04 Февраль 2011 - 11:49

Другое дело. Когда про монетки и кидаем, то быстрее доходит. Если б ты написал - Кидаем золотую монетку... дошло бы быстрее.

Да, это верное замечание. В реальных задачах монетка должна быть не простой, а золотой. То есть не одномерной дискретной, а многомерной континуальной, и желательно с неравномерным распределением :)

#6 mikki33

mikki33

    Активный участник

  • Друзья
  • PipPipPip
  • 231 сообщений
  • Пол:Мужчина
  • Город:Израиля

Отправлено 07 Февраль 2011 - 13:11

Но проблема локальных экстремумов все-равно остается. И даже делая много прогонов с различными (тоже случайными) начальными условиями не гарантирует, что мы опять не сойдемся к локальному горбу.

#7 Anatoly Utkin

Anatoly Utkin

    Активный участник

  • Пользователи
  • PipPipPip
  • 158 сообщений

Отправлено 07 Февраль 2011 - 18:28

Но проблема локальных экстремумов все-равно остается. И даже делая много прогонов с различными (тоже случайными) начальными условиями не гарантирует, что мы опять не сойдемся к локальному горбу.

Да, есть такое дело. За скорость счета приходится платить локальностью экстремума.

Эту проблему можно решить, если приблизительно представлять, где находится оптимум. То есть сужать размеры области параметров. Но это уводит нас от полностью автоматической оптимизации--то есть процедура опять же становится частично искусством.




Количество пользователей, читающих эту тему: 0

0 пользователей, 0 гостей, 0 анонимных