Опционы

Наихудшие результаты были получены для метода Нелдера – Мида. Хотя количество вычислений для этого метода оказалось наименьшим по сравнению с другими методами, все показатели его эффективности находятся на очень низком уровне. Всего в 7 % случаев решение совпало с глобальным максимумом и лишь в 15 % случаев оптимальное решение находилось в оптимальной области. В 60 % случаев решения оказались неудовлетворительными.

Для другого оптимизационного пространства, построенного на основе целевой функции «процент прибыльных сделок», эффективность методов покоординатного подъема Хука−Дживса и Розенброка оказалась приблизительно одинаковой (если не считать того, что последний метод был несколько хуже по показателю «процент попаданий в оптимальную область»). Метод Нелдера – Мида вновь показал наихудшие результаты. Такая низкая эффективность данного метода весьма удивительна. Возможно, она объясняется тем, что для успешного применения этого метода необходимо тщательно подбирать стартовые условия (размер симплекса), а также значения его многочисленных параметров (коэффициенты отражения, сжатия, редукции, расширения). Мы же выбрали размер симплекса произвольно, а для коэффициентов приняли обычно используемые значения. Вероятно, для получения удовлетворительных результатов необходима более тонкая настройка параметров и некоторые априорные предположения о свойствах оптимизационного пространства.

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

2.7.3. Случайный поиск

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

Основной и единственный фактор, влияющий на эффективность случайного поиска, – это количество выбираемых ячеек. Чем больше делается попыток, тем выше вероятность того, что оптимальное решение совпадет с глобальным максимумом или будет лежать в непосредственной близости от него. При этом количество попыток должно определяться в зависимости от размеров оптимизационного пространства. В наших примерах это пространство состоит из 3600 ячеек. Если для случайного поиска в таком пространстве использовать 100 попыток, то обследованными окажутся менее 3 % ячеек, что, очевидно, недостаточно для нахождения удовлетворительного оптимального решения. Однако если оптимизационное пространство состоит из 500 ячеек, то 100 попыток составят 20 %, что может оказаться достаточным.

В этом разделе мы проанализируем три аспекта эффективности случайного поиска:

1. Зависимость эффективности поиска от количества случайно выбираемых узлов. Эффективность будет тестироваться для 100, 200, …, 1000 попыток (всего 10 вариантов количества выбираемых узлов).

2. Влияние формы оптимизационного пространства на эффективность случайного поиска. Как и в предыдущем разделе, мы применим метод случайного поиска к оптимизационным пространствам, соответствующим целевым функциям «прибыль» и «процент прибыльных сделок».

3. Сравнение эффективности случайного поиска с двумя методами целенаправленного поиска – покоординатным спуском и методом Хука−Дживса (которые оказались наиболее эффективными среди других методов целенаправленного поиска).

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