Поиск экстремума унимодальной функции
Пусть известно, что целевая функция имеет только один экстремум на интервале a, b. Такая функция F=f(x) называются унимодальными. Определим значения ЦФ при X=x1 и x2. С точки зрения расположения экстремума (в примере – максимума) возможны три варианта:
F(x1) < F(x2) – максимум лежит в между x2 и b.
F(x1) = F(x2) – максимум лежит между x2 и x1.
F(x1) > F(x2) – максимум лежит в между x1 и a.
Это означает, что при выполнении первого условия на отрезке [x1, b] не может находиться xopt, следовательно, его можно исключить из дальнейшего рассмотрения. Если же выполняется третье условие, то на отрезке [a, x2] не может находиться xopt, следовательно, его можно исключить из рассмотрения. Выбирая новые x2 и x1 и последовательно повторяя анализ, сужаем область определения экстремума до любого разумного предела. Выбор значений x2 и x1 с учетом предыдущих результатов определяет различие методов последовательного поиска.
Например, метод половинного деления (дихотомии), когда пары x2 и x1 выбираются симметрично относительно центра текущего интервала, на расстоянии ±d от него, где d - некоторая константа. Если при прямом переборе эффективность поиска оптимума прямо пропорционально числу расчетов, то по методу дихотомии она возрастает с ростом итераций экспоненциально. Например, если при прямом переборе требуется 1000 расчетов для того, чтобы сузить зону поиска экстремума в N раз, то по методу дихотомии – только 20.
Дата добавления: 2017-09-01; просмотров: 909;