экстремуме, они в действительности имеют в виду локальный экстремум на очень широкой области значений независимых переменных.

Для отыскания максимумов или минимумов в таких случаях сушествует масса методов. Любой из них, как правило, накладывает на переменные некие ограничения, которые должны удовлетворяться применительно к экстремуму. К примеру, в нашем случае эти ограничения заключаются в том, чтобы все независимые переменные (значения f) были бы большими или равными нулю. Нередко требуется выполнение ограничиваюших функций (т. е. чтобы значения других функций от используемых переменных были бы больше/меньше или равны некоторым величинам). Линейное программирование с его симплекс-методом - эта весьма хорошо разработанная область такой оптимизации в условиях ограничений - применима лишь, когда и оптимизируемая, и ог-раничиваюшие функции являются линейными (многочленами первой степени).

В целом, различные методы математической оптимизации могут быть классифицированы по принципу используемого аппарата следующим образом:

1. По размерности целевых функций: с одной переменной (двумерных) или многомерньгх (с размерностью три и более).

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

3. По использованию производньгх. Некоторые методы требуют вычисления первой производной целевой функции. В многомерном случае первая производная представляет собой векторную величину, называемую градиентом.

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

5. По устойчивости. Помните, вы хотели найти локальный экстремум на очень широкой области значений независимых переменных и использовать его вместо глобального экстремума. Поэтому, если в этой области имеется более одного экстремума, вы не захотите попасть в объятия такого из них, который менее экстремален.

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

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

Многомерные методы можно классифицировать по пяти широким категориям.

Во-первых, это симплекс-методы скорейшего подъема. Они, вероятно, становятся наименее эффективными из всех, если вычислительная нагрузка немного увеличивается. Вместе с тем, они обычно легко применимы и не требуют вычисления частных производных первого порядка. К сожалению, им свойственна медлительность, а требуемый объем используемой памяти имеет порядок л1

Второе семейство образуют direction set methods, известные также как line minimization methods или (методы сопряженных направляющих) conjugate direction methods. Наиболее примечательными среди них являются различные методы Пауэла. В смысле скорости они эффективнее симплекс-методов скорейшего подъема (не путайте с симплекс-алгоритмом для линейных функций.

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

Третье семейство образуют метод сопряженных градиентов conjugate gradient methods. Среди них выделяются методы Флет-чера-Ривза и тесно примыкающие к ним методы Полака-Рибьера. Они тяготеют к группе наиболее эффективных методов в смысле скорости и памяти (порядка л), но требуют вычисления частных производных первого порядка.

Четвертое семейство методов многомерной оптимизации образуют квази-ньтоновы, или методы с переменной метрикой variable metric methods. Туда входят алгоритмы Дэвидсона-Флет-чера-Пауэла (DiP) и Бройдена-Флетчера-Голдфарба-Шанно (ВЛ]г8). Подобно conjugate gradient methods, они требуют вычисления частных производных первого порядка, обычно быстро приводят к экстремуму, однако эти алгоритмы требуют большей памяти (порядка tf). Вместе с тем они уравновешивают достогшства conjugate gradient methods тем, что дольше известны, шире используются и лучше документально обеспечены.

Пятое семейство - это имитационные методы многомерной огтгимизации. Они гораздо более примечательны, поскольку движутся к экстремуму при помощи процессов моделирования, позаимствованных в природе. В их число входят метод генетического алгоритма (genetic algorithm) и имитируемого отжига (simulated annealing), моделирующего процесс кристаллизации, в ходе которого система находит свое минимальное энергетическое состояние. Среди прочих эти методы отличаются наибольшей устойчивостью, почти иммунитетом по отношению к локальным экстремумам, и могут решать задачи огромной сложности. Но они не всегда самые быстрые и стать такими в больщинстве случаев не смогут. Вместе с тем, они так новы, что про них еще мало что известно.

Хотя вы можете использовать любой упомянутый алгоритм многомерной оптимизации, я предпочел генетический алгоритм потому, что он является, возможно, единственным наиболее устойчивым методом математической оптимизации, за исключением весьма фубых приемов перебора всех возможных комбинаций значений переменных.

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

Применимость данного алгоритма, хотя он часто используется в нейронных сетях, не ограничивается исключительно ими. В наших условиях мы можем использовать его в качестве метода отыскания оптимальной точки на {п + 1)-мерном изображении.

Естественный отбор

Считается, что генетический алгоритм реализует принцип естественного отбора в природе. Так оно и происходит, но не совсем так, как в природе. Ведь в действительности мы многого не знаем о том, как природа осуществляет этот принцип.

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

Например, если я бросаю на стол пригоршню монет и еще одну монету использую для подбрасывания, то могу сыграть в следующую игру. Монеты на столе разделены поровну на орлов и решек. Я бросаю переворачивающуюся монету, и если она выпадает орлом, то я убираю монету, лежащую вверх орлом. Если выпадает решкой, то я убираю монету, лежащую вверх решкой. Игра заканчивается, когда остаются только одни орлы или одни решки.

Это - глупая игра, но она доказывает то, что не будучи ни орлом, ни решкой, получаешь в этой ифе селективное пре-

имущество (у орла и решки вероятность стать победителем одинакова), которое вьщвигает одного из них в победители, то есть в самые приспособленные.

Поэтому, когда мы спрашиваем Какой из кандидатов наиболее приспособлен? , мы сталкиваемся с парадоксальным ответом Тот, который является победителем .

Кроме того, создается впечатление, что у природы имеется много различных целевых функций. Если бы это было не так, то мир, в конце концов, заселили бы амфибии, умеющие летать, причем, быстро! Как, например, вы можете объяснить существование колибри? У нее ужасающая, безотлагательная зависимость от Сахаров, по сравнению с людьми она неразумна, и все же выживает на планете вместе со столь многими другими видами. Очевидно, колибри нашла некую нишу в естественном устройстве планеты - предложенную природой целевую функцию, которая так удовлетворяется нашей колибри, чтобы не вымереть.

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

Генетический алгоритм

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

так и свойства предшествующих поколений. Средняя приспособленность популяции за многие поколения будет возрастать и приближаться к оптимуму.

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

Алгоритм содержит следующие основные шаги:

Длина гена. Вы должны задать длину гена. Ген - это двоичное представление члена популяции вариантов решений. Каждый член этой популяции характеризуется значением каждой переменной (т. е. значением /для каждого сценарного спектра). Так, если мы принимаем длину гена в двенадцать раз больше количества сценарных спектров, то каждой переменной (т. е. значению j) у нас будет соответствовать по двенадцать бит. Двенадцати битов достаточно для представления величины в интервале от О до 4095. Последнее число представляется в виде:

2° + 2 -Ь 2 -Ь ... + 2 = 4095

Возводим 2 в степень О и прибавляем 2 в следующей степени, пока не дойдем до степени, равной количеству битов минус 1 (т. е. 11, в данном случае). Если имеется, скажем, три сценарных спектра и на каждый из них мы используем длину в двенадцать битов, то длина гена каждого варианта решения есть 12 * 3 = 36 бит. То есть ген в данном случае - это строка из 36 двоичных битов.