Экспериментальные методы одномерного поиска.
Рассматривается функция одной переменной y=f(x). Предпола-гается, что функция имеет только один экстремум (унимодальна); интервал поиска ограничен: ; значения выходной переменной неслучайны. Поиск осуществляется последовательно путем сравнения значений целевой функции в двух точках, выбираемых определенным образом. Эффективность E поиска характеризуется степенью локализации области экстремума после N экспериментов и выражается отношением длины начального интервала к остаточному , внутри которого находится экстремум целевой функции: .
Далее для определенности будем полагать, что ищется максимум функции.
Эквидистантные планы Начальный отрезок делится на (N-1) равных частей, опыты проводятся при значениях:
. Поиск прекращается как только .
В зависимости от вида функции поиск прекращается при различных i, так что средняя эффективность составит E=(N–1)/2.
Метод деления отрезка пополам (метод последовательной дихотомии)
Эксперименты ставят парами в точках, отстоящих по обе стороны от середины отрезка. Координаты первой пары:
где – малая величина.
Если , то максимальное значение надо ожидать на отрезке ; при на отрезке . Этот новый отрезок объявляется исходным, и далее процесс повторяется. Мера эффективности равна .
Заметим, что при наличии случайного компонента значение не должно быть малым, что иллюстрируется рис.3.
x
Рис. 3. Метод деления отрезка пополам
Если в точке х1 случайная компонента окажется отрицательной, а в точке х2 положительной, и значительной по величине в обеих точках, результаты сравнения значений отклика в этих точках направят поиск в противоположную сторону, Вот почему применение метода деления отрезка пополам в этих условиях становится проблематичным.
Достарыңызбен бөлісу: |
