Метод поиска с «наказанием случайностью»

Метод является аналогом метода наискорейшего спуска, только направление локального поиска не градиентное, а случайное. Из текущей точки делают случайные шаги до тех пор, пока не будет найдена точка с лучшим значением критерия оптимальности. Затем в этом направлении регулярным методом одномерного поиска ищут оптимум. В точке оптимума по направлению опять случайным образом ищут новое направление и т.д

Если при выполнении случайного шага получается большее значение, он оказывается неудачным, то производиться выборка следующего случайного вектора и из точки хⁱ снова делается шаг. Пробные шаги из точки хⁱ делаются до тех пор, пока не будет найдена точка хⁱ⁺¹, в которой функция цели имеет меньшее значение, после чего пробные шаги будут выполняться уже из точки хⁱ⁺¹.

Есть модификация метода, которая заключается в следующем: если в точке получилось худшее значение критерия, то следующая точка берется в противоположную сторону.

Условием окончания обычно является невозможность получения лучшей точки из текущей за предварительно заданное число попыток.

К достоинствам данного метода относят: 1) проста в реализации (не требует вычисления градиента); 2)надежность и помехоустойчивость; 3)универсальность; 4)эффективен при поиске глобального экстремума.

Основными недостатками являются: 1) большое количество вычислений минимизируемой функции; 2)медленная сходимость в районе экстремума.

Экспериментальная часть

В начальной точке координатами (2;2;2) проведем 20 экспериментов, определим оценку дисперсии.

Таблица 1 – Оценка дисперсии

где ² – дисперсия;

– среднее квадратическое отклонение;

n– число экспериментов.

Абсолютная погрешность

Δx=(диапазон изменения х/100%)*класс точности

Класс точности промышленного прибора 0,5

Δx=(5-(-5))/100)*0,5=0,05

Δx≥0,05

Соответственно шаг h должен быть больше h_min=0,05.

Пусть число повторений в процессе проведения эксперимента равно пяти. Чем больше количество экспериментов, тем выше точность решаемой задачи, но большое количество экспериментов влечет за собой увеличение стоимости исследуемого процесса.

3. 1 Метод Гаусса-Зайделя.

Из начальной точки (2; 2; 2) с у_ср= 32,0411 ищем минимум критерия оптимальности по переменной х1. Используем прием последовательного сканирования, т.е. «шагаем» до первого лучшего значения критерия, применяя алгоритм х₁ⁱ⁺¹=хⁱ₁ h, где h – шаг. Знак «+» или «-» выбирается в зависимости от направления изменения критерия: нужно взять такой знак, при котором критерий уменьшается.

Возьмем в первом цикле нашего поиска h=1.

Таблица 2 – Первый цикл

Наилучшая точка в первом цикле получилась (-1, 4, 0). Далее из нее продолжаем поиск с шагом h=0,5.

Таблица 3 – Второй цикл

Наилучшая точка во втором цикле получилась -2; 5; 0,5. Далее из нее продолжаем поиск с шагом h=0,2.

Таблица 4 – Третий цикл

Получили точку (-2; 5; 0,5) с критерием у=-8,3344. На этом этапе эксперимент может быть завершен, т.к. не наблюдается изменение критерия оптимальности и ни по одной из переменных не удается получить лучшее значение. Данная точка является решением поставленной задачи.

Для того, чтобы определить, является ли найденный экстремум локальным или глобальным, возьмем новую начальную точку и проведем эксперимент.

Вторая точка (-2; -2; -2). Возьмем в первом цикле нашего поиска h=1.

Таблица 5 – Первый цикл

Наилучшая точка в первом цикле (1; -4; 0). Далее из нее продолжаем поиск с шагом h=0,5.

Таблица 6 – Второй цикл

Наилучшая точка во втором цикле получилась (2; -5; -0,5). Далее из нее продолжаем поиск с шагом h=0,2.

Таблица 7 – Третий цикл

Наилучшая точка в третьем цикле получилась (2; -5; -0,5). На этом этапе эксперимент может быть завершен, т.к. не наблюдается изменение критерия оптимальности и ни по одной из переменных не удается получить лучшее значение.

В результате проведения экспериментов мы получили две разные точки с координатами (-2; 5; 0,5) и (2; -5; -0,5) с критериеями оптимальности у=-8,3344 и у=-8,9286, поэтому можно предположить, что мы попали в локальный экстремум.