2014-02-04
1318
Ранее отмечалось, что использование алгоритма метода случайного поиска для одномерного пр-ва на многомерное пр-во, приводит к увеличению числа вычислений по степенному закону. Поэтому целесообразно для уменьшения числа вычислений осуществлять поиск экстремума с некоторой долей риска или неопределенности.
Метод закл-ся в том, что пр-во нормируется и представляется в виде гиперкуба со стороной равной единице. Далее, внутри пр-ва или гиперкуба строится сетка путем деления каждой стороны на 10 равных частей.
Далее случайным образом выбирают наиболее перспективные ячейки, кол-во которых определяется вероятностью поиска перспективных ячеек. Это кол-во м.б. представлено в виде таблицы, в которой указывается, сколько ячеек нужно выбрать случайным образом, чтобы обеспечить заданную вероятность при заданной доле наиболее перспективных ячеек.
f – доля наиболее перспективных ячеек. Р – вероятность.
| f | Р | |||
| 0.8 | 0.9 | 0.95 | 0.99 | |
| 0.1 | ||||
| 0.5 | ||||
| 0.01 | ||||
| 0.005 |
Преимущества метода:
|
|
|
1. метод пригоден для целевой ф-ции любого вида, независимо от того, явл-ся ли она унимодальной.
2. вероятность успеха при попытках не зависит от размерности пр-ва.
Недостатком метода: явл-ся то, что он не позволяет непосредственно найти оптимальное решение, а позволяет только сузить область поиска для применения других методов.
Второй алгоритм метода многомерного случайного поиска основан на выборе случайного направления движения в пр-ве управляемых пар-ов. И состоит в том, что выбирается точка, в пр-ве поиска, случайно выбирается направление поиска. Далее в этом направлении определенным образом выбираются точки, в которых производится вычисление целевой ф-ции.
Если эти точки показывают перспективность движения в данном направлении, то это движение продолжается. В противном случае производится возраст в наиболее перспективную точку из ранее вычисленных, определяется новое направление, оценивается его перспективность и процедура повторяется.
Если после определенного числа неудачных попыток пр-сс поиска м.б. продолжен с более мелким шагом продвижения.
Если 
- направление перспективно.
Если 
- направление не перспективно.
15. Градиентные методы.
Сущ-ет целый ряд методов, который при поиске экстремума ф-ции используется значение градиента целевой ф-ции:
.
Если мы имеем многопараметрическую ф-цию, то можно выбрать сис-му координат:
В этой сис-ме выбрать единичный вектор:
,
то градиент можно найти:
, где
i = 1…n.
j = 1…n.
Если частная производная не м.б. вычислена аналитически, ее заменяют конечной разностью:
|
|
|
.
Зная направления локального градиента можно определить направление движения в сторону экстремума.
Графически это можно представить как ф-цию двух пар-ов:
Если градиент попадает на точку излома, то:
Рассм-м несколько алгоритмов градиентных методов.
