Ознакомительная версия. Доступно 17 страниц из 85
2.4.2. Оптимизация по методу Парето
Применение метода Парето позволяет решить задачу выбора в условиях, когда показатели различных критериев противоречат друг другу. Подобная ситуация, когда некоторые узлы оптимизационного пространства превосходят другие узлы по одной из целевых функций (например, по прибыли), но являются хуже их по другой функции (например, по максимальной просадке), возникает довольно часто. Основным недостатком метода Парето является то, что в результате оптимизации может быть получено множество оптимальных решений вместо одного. Это потребует дальнейшего анализа, и выбор придется делать на основе применения дополнительных методик. Такая же проблема свойственна и методу свертки, но в гораздо меньшей степени.
Формализация задачи многокритериальной оптимизации выглядит следующим образом. Пусть для каждого узла (альтернативы) a из оптимизационного пространства задан n-мерный вектор значений целевых функций (критериев) x(a) = (x1(a), …, xn(a)). Используя показатели n критериев, необходимо найти альтернативы с максимальными значениями координат векторов (то есть с максимальными показателями целевых функций). Будем считать, что чем больше значение критерия, тем лучше альтернатива. При сравнении двух альтернатив a и b альтернатива a доминирует над альтернативой b, если выполняется следующая совокупность неравенств: xi(a) ≥ xi(b), для всех значений i = 1, …, n, и существует хотя бы один критерий j, для которого выполняется строгое неравенство xj(a) > xj(b). Другими словами, узел a предпочтителен узлу b, если a не уступает b по значениям всех целевых функций и хотя бы по одной из них превосходит b.
Очевидно, что наличие доминирования однозначно определяет, какая из двух сравниваемых альтернатив лучше. Если же отношение доминирования установить невозможно, то вопрос о том, какая из них лучше, остается открытым. В этом случае говорят, что ни одна из альтернатив не обладает однозначным превосходством (не доминирует) над другой.
Используя приведенные рассуждения, задачу многокритериальной оптимизации можно сформулировать следующим образом: среди множества всех альтернатив найти такое подмножество, в которое входят только недоминируемые альтернативы, то есть те, для которых не существует доминирующих их альтернатив. Это подмножество и называется множеством Парето. Каждый элемент такого множества можно считать наилучшим в определенном выше смысле. При этом число альтернатив, составляющих это множество, может быть самым различным. Например, это может быть как одна, доминирующая над всеми остальными, альтернатива, так и несколько «лучших» альтернатив или даже все исходное множество.
В нашем примере оптимизации базовой дельта-нейтральной стратегии мы имеем оптимизационное пространство A = (a1, …, am), состоящее из m узлов-альтернатив (в примере m = 3600), оцененных с помощью n функций-критериев (n = 3) со значениями x(a) = (x1(a1), …, xn(am)). Для построения множества Парето необходимо попарно сравнить все альтернативы, отбрасывая доминируемые, а недоминируемые добавляя в множество Парето. Очередной элемент ak сравнивается со всеми оставшимися. Если встречается элемент al, над которым ak доминирует, то элемент al отбрасывается. Если оказывается, что ak доминируем каким-либо элементом am из оставшихся, то отбрасывается элемент ak. Если ни один из элементов не доминирует над ak, то последний включается во множество Парето. Далее переходим к сравнениям элемента, следующего за ak, со всеми оставшимися элементами. При этом максимальное количество требуемых сравнений составляет порядка 0,5m (m – 1), что вполне приемлемо для большинства случаев. Более быстрые алгоритмы требуются при построении множества Парето для большого числа критериев и альтернатив.
Как было сказано выше, недостатком метода Парето является невозможность повлиять на количество узлов, попадающих в оптимальное множество Парето. Число элементов множества может изменяться от случая к случаю и не зависит от наших пожеланий и предпочтений. Единственное оптимальное решение может быть получено только в том случае, когда оптимизационное пространство имеет узел, для которого показатели всех критериев превосходят соответствующие показатели для других узлов. В большинстве случаев вместо единственного оптимального решения получается множество.
Рассмотрим применение метода Парето на примере базовой дельта-нейтральной стратегии. В качестве критериев будем использовать те же три целевые функций, что использовались в многокритериальной оптимизации методом свертки (прибыль, максимальная просадка и процент прибыльных сделок). В отличие от свертки, метод Парето не позволяет построить полное оптимизационное пространство, аналогичное поверхности, показанной на рис. 2.4.1. Вместо этого мы получаем перечень доминирующих узлов, составляющих оптимальное множество. В результате оптимизационная поверхность превращается в координатную плоскость, обозначающую положение отдельных оптимальных узлов (рис. 2.4.2).
Двигаясь от простого к более сложному, рассмотрим сначала оптимальное множество Парето, полученное путем применения двух критериев. Из трех целевых функций можно составить три пары критериев, что позволяет получить три варианта оптимального множества. Узлы, попавшие в эти оптимальные множества, группируются на координатной плоскости в пяти областях. На левом графике рис. 2.4.2 эти области обозначены условными порядковыми номерами. Интересно отметить, что ни в одну из пяти областей не попали все три варианта оптимального множества. В третью область попал единственный узел множества, полученного в результате применения целевых функций «прибыль» и «максимальная просадка». Узлы, выбранные этой парой функций, попали также во вторую и пятую области. Узлы, соответствующие паре функций «прибыль» и «процент прибыльных сделок», расположены в первой, второй и четвертой областях. И, наконец, узлы, попавшие в оптимальное множество функций «максимальная просадка» и «процент прибыльных сделок», находятся в областях 1, 4 и 5. Такое распределение оптимальных множеств по областям координатной плоскости свидетельствует о том, что каждая из трех целевых функций вносит свой вклад в поиск оптимального решения. Поэтому в данном случае имеет смысл включить все три функции в систему многокритериальной оптимизации по методу Парето.
Множество оптимальных решений, полученное в результате применения трех критериев показано на правом графике рис. 2.4.2. Узлы, попавшие в оптимальное множество Парето, расположены на координатной плоскости приблизительно в тех же пяти областях, что и в предыдущем примере, когда для оптимизации использовались пары критериев. Наибольшее количество узлов (всего семь) попало во вторую область, в первой области оказалось пять узлов, а в третьей, четвертой и пятой областях – всего по два узла.
Ознакомительная версия. Доступно 17 страниц из 85
