Сравнительное исследование эффективности методов

В этом параграфе проводится сравнительное исследование поисковых методов минимизации мультимодальной функции одной переменной на основе схем отбора интервалов, метода последовательного перебора, монотонного алгоритма глобального поиска Стронгина и метода ломаных. В качестве параметра эффективности метода выберем количество вычисления значений функций для достижения заданной точности.

Подобный метод определения эффективности численных методов используется многими другими авторами, например Стронгиным [17]. В таблицах 4−9 представлены результаты вычисления этого параметра эффективности для перечисленных методов. Результаты для метода ломаных и поискового метода на основе трехзвенной схемы отбора интервалов первого порядка были взяты из работы [9]. Результаты для монотонного алгоритма глобального поиска Стронгина и поискового метода на основе трёхзвенной схемы отбора интервалов второго порядка были взяты из работы [14]. Под точностью будем понимать абсолютную погрешность значения точки глобального минимума, где — точное значение точки глобального минимума, — приближенное значение точки глобального минимума, вычисленное с помощью программы. Для достижения нужной точности используется параметр, который есть в каждом методе и при устремлении его к нулю, заданная точность должна быть достигнута. Для всех поисковых методов, метода последовательного перебора, метода ломаных и монотонного алгоритма глобального поиска Стронгина таким параметром является — оценка погрешности приближенного значения точки глобального минимума. Этот параметр используется и вводится непосредственно в программе. Т.о. при его последовательном уменьшении абсолютная погрешность точки глобального минимума также будет уменьшаться.

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

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

Характерной особенностью всех методов, кроме поисковых, является использование в качестве исходного данного константы Липшица для функции на .В простейших случаях константа Липшица вычисляется аналитически. Аналитический метод вычисления константы Липшица заключается в том, что находится производная функции и вычисляется ее максимум на том отрезке, для которого ищется минимум функции. Таким образом, на отрезке вычисляется производная исследуемой функции равное. Константа Липшица выбирается равной. Часто константу Липшица аналитически вычислить очень сложно, например, если исследуемая функция не является элементарной или если метод одномерной минимизации используется в качестве вспомогательного метода в решении задач много мерной минимизации. Поэтому методы, использующие ее для своих вычислений, сопровождаются дополнительной программой вычисления константы Липшица.

Вычисление константы Липшица обычно производится сеточным методом. На отрезке строится сетка из точек, таким образом получена последовательность точек, где, ,. Затем производится вычисление значений — значения функции в точках, .

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

Зададим последовательность для каждой пары вычисляются значения и. Вычисляем, где — значения функции в соседних узлах сетки. Затем вычисляем значение, где и сравниваем по модулю разность значений и. Если меньше заданного некоторого, то константа Липшица считается найденной и равной с погрешностью, иначе удваиваем значение и вычисляем новые значения и. Погрешность значения зависит от значения и припогрешность .

Данный метод можно оптимизировать, если вместо использовать. Данная оптимизация ускоряет вычисление константы Липшица в и более раз, но при этом необходимо отдельно рассмотреть случай, при котором Это происходит в том случае, если функция является постоянной (константой), в этом случае значение константы Липшица берется равным .

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

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

В таблицах 4−9 используются следующие обозначения:

— заданная точность искомого приближенного значения точки глобального минимума;

sL — Число вычислений функции для определения константы Липшица, найденное при определении константы Липшица сеточным методом;

sML1 — Число вычислений функции для метода ломаных с вычисленной константой Липшица;

sML2 — Число вычислений функции для метода ломаных с найденной константой Липшица используя максимум производной функции;

sSL1 — Число вычислений функции для АГП (алгоритм глобального поиска) Стронгина с вычисленной константой Липшица;

sSL2 — Число вычислений функции для АГП Стронгина с найденной константой Липшица используя максимум производной функции;

sPL1 — Число вычислений функции для метода последовательного перебора с вычисленной константой Липшица;

sPL2 — Число вычислений функции для метода последовательного перебора с найденной константой Липшица используя максимум производной функции;

s3z1 — Число вычислений функции для метода на основе трёхзвенной схемы отбора интервалов первого порядка;

s3z2 — Число вычислений функции для метода на основе трёхзвенной схемы отбора интервалов второго порядка;

s2z1 — Число вычислений функции для метода на основе двухзвенной схемы отбора интервалов первого порядка.

Модельная задача 1. Ищется минимум функции на отрезке (рис. 4). Вычисленное значение константы Липшица = 35 452. Точное значение точки минимума функции = 1,54 978 592 608 382.

График функции.

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