Будем отыскивать минимум функции на отрезке [a,b]. Допустим, что целевая функция унимодальна, т.е. на данном отрезке она имеет только один минимум. Отметим, что в инженерной практике обычно встречаются именно такие целевые функции. Погрешность приближенного решения задачи определяется разницей между оптимальным значением проектного параметра и принятым приближением к нему . Потребуем, чтобы эта погрешность была по модулю меньше заданного допустимого значения .
Процесс решения задачи методом перебора состоит в последовательном сужении интервала изменения проектного параметра, называемого интервалом неопределенности. В начале процесса оптимизации его величина составляет b-a, а в конце процесса она должна стать меньше , т.е. оптимальное значение проектного параметра должно находиться в интервале неопределенности , причем .
В качестве приближения к оптимальному значению можно принять любое значение
,
например, или , или
.
Наиболее простым способом сужения интервала неопределенности является деление его на некоторое количество равных частей с дальнейшим вычислением целевой функции в точках разбиения. Сравнивая полученные значения , отыскиваем среди них наименьшее.
|
|
Пример:
Проиллюстрируем суть метода равномерного поиска посредством рассмотрения задачи нахождения минимума.
Пусть задана функция
.
И задача оптимизации выглядит так:
Пусть также задано число наблюдений .
Тогда отрезок разбивают на равных частей точками деления:
Вычислив значения в точках , найдем путем сравнения точку , где — это число от до такую, что
для всех от до .
Тогда интервал неопределённости составляет величину , а погрешность определения точки минимума функции соответственно составляет: .
Метод “золотого сечения”
Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:
Рис. 2 Иллюстрация выбора промежуточных точек
метода золотого сечения
, где — пропорция золотого сечения.
Таким образом:
То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.