Разделы



Оптимизация моделированием отжига

Оптимизаторы, основанные на моделировании отжига, воспроизводят термодинамический процесс замерзания жидкостей и отжига металлов. При высокой температуре атомы в жидкости или расплавленном металле быстро перемещаются случайным образом. При медленном остывании они располагаются в упорядоченную кристаллическую структуру, пред­ставляющую минимальное энергетическое состояние системы. При про­граммном моделировании этот термодинамический процесс успешно ре­шает крупномасштабные задачи оптимизации.

Как и генетическая оптимизация, моделирование отжига — очень мощ­ная стохастическая методика, основанная на естественном явлении, кото­рое может находить глобально оптимальные решения и работать с неупо­рядоченными функциями эффективности. Моделирование отжига эффек­тивно решает комбинаторные проблемы, включая известную задачу о коммивояжере или проблему оптимального расположения миллионов эле­ментов современных интегральных микросхем, например компьютерных процессоров. Методы, основанные на моделировании отжига, не следует ограничивать комбинаторной оптимизацией; они могут быть легко приме­нены для оптимизации параметров с реальными значениями. Следователь­но, оптимизаторы, основанные на моделировании отжига, применимы к широчайшему кругу задач, включая задачи, интересующие трейдеров.

Поскольку генетические оптимизаторы столь эффективны, мы не столкнулись с необходимостью широко исследовать оптимизаторы, ос­нованные на моделировании отжига. Кроме того, поступали сообщения, что во многих случаях алгоритмы отжига уступают генетическим, таким образом, не было необходимости давать примеры метода моделирования отжига и рассматривать его далее.

Аналитические оптимизаторы

Анализ (в смысле .математический или комплексный анализ) являет­ся расширением классического исчисления. Аналитические оптимиза­торы используют наработанные методы, в особенности методы диффе­ренциального исчисления и исследования аналитических функций для решения практических задач. В некоторых случаях анализ дает прямой (без перебора вариантов) ответ на задачу оптимизации. Так происходит при использовании множественной регрессии, где решение находится с помощью нескольких матричных вычислений. Целью множественной регрессии является подбор таких весов регрессии, при которых миними­зируется сумма квадратов ошибок. В других случаях требуется перебор вариантов, например невозможно определить напрямую веса связей в нейронной сети, их требуется оценивать при помощи алгоритма обрат­ного распространения.

Биржа Forex позволяет каждому желающему получать прибыль на колебаниях курсов валют любых мировых валют легально, круглые сутки, не выходя из дома и даже не имея специального образования!

Многие методы перебора данных, используемые для решения много­вариантных проблем оптимизации, применяют в том или ином виде ме­тод сопряженных градиентов (максимальной крутизны). В общем виде оптимизация методом сопряженных градиентов ведется следующим об­разом. Некоторым образом выбирается точка на поверхности функции пригодности. Вектор градиента поверхности в данной точке оценивается с помощью дифференцирования функции пригодности по каждому из параметров. Полученный градиент указывает направление максимального роста функции пригодности в n-мерном пространстве параметров. В на­правлении градиента делаются шаги до тех пор, пока функция пригодно­сти не перестанет расти.

п»ї

Затем расчет градиента повторяется, движение начинается в новом направлении, и так раз за разом, пока не будет достигнута вершина, т.е. точка с нулевым градиентом.

Для применения оптимизации по методу сопряженных градиентов необходимо разработать правила определения размеров каждого шага, а также правила корректировки направления, задаваемого градиентом. Примитивные версии исходят из того, что существует поверхность функ­ции пригодности (приближаемая сходящимися степенными рядами), где имеются холмы, по которым следует подниматься. Более продвинутые версии идут далее, исходя из того, что функция пригодности может быть неплохо приближена квадратичной формой. Если функция пригодности соответствует этому предположению, то найти решение можно гораздо быстрее. Впрочем, если поверхность функции пригодности имеет сильно изрезанную форму с впадинами и выступами неправильных очертаний, квадратичные формы часто не могут дать хорошего приближения. В та­ких случаях сложные методы могут вовсе не находить решения или по крайней мере работать гораздо медленнее.

Тем не менее низкая скорость оптимизации не является главным пре­пятствием на пути аналитика. Гораздо сложнее справиться с так называе­мой проблемой локальных решений. Почти все аналитические методы, будь они простыми или сложными, легко попадаются в ловушку локаль­ных максимумов; при наличии множества впадин и выступов на поверх­ности они не могут найти наилучшее глобальное решение. Метод наимень­ших квадратов, моделирование нейронными сетями дают поверхности функции пригодности неправильной формы с большим количеством ло­кальных экстремумов. Данные поверхности чрезвычайно сложны для стандартных аналитических методов, таких как метод сопряженных гра­диентов или алгоритм обратного распространения, применяемый в ней­ронных сетях. Впрочем, местные максимумы можно обойти, соединив аналитический метод с генетическим. Для поверхностей, которые можно исследовать аналитическими методами, такой двойной алгоритм может оказаться наилучшим решением; он позволит быстро и с большой точно­стью найти глобальные оптимумы.

Некоторые поверхности функции пригодности просто не поддаются аналитической оптимизации; как правило, это поверхности, имеющие плос­кие участки или разрывы в областях, где следует искать решение. Плоско­сти не имеют градиентов, следовательно, нельзя выбрать направление для движения. В точках разрыва также нельзя определить градиент и направ­ление движения. Даже если метод и не использует градиенты напрямую, эта информация все равно потребуется алгоритму оптимизации. К несчас­тью, многие функции пригодности, важные для трейдеров, — включая все функции, связанные с общей прибылью, максимальными падениями ка­питала, долей выгодных сделок, отношением риска/прибыли и подобны­ми показателями — страдают наличием плоскостей и разрывов. Следова­тельно, их нельзя исследовать методами аналитической оптимизации.

п»ї

Хотя обсуждение было в основном посвящено максимизации функ­ции пригодности, все вышесказанное применимо и к минимизации рас­ходов. Любая техника максимизации может быть применена для мини­мизации, и наоборот: умножьте функцию пригодности на — 1 для получе­ния эквивалентной функции расходов; умножьте функцию расходов на - 1, и получится функция пригодности. Если вам нравится алгоритм ми­нимизации, но нужно применять максимизацию; можно использовать этот фокус вместо перекодировки алгоритма оптимизации.

Читать далее: Линейное программирование