Классификация численных методов оптимизации

Численные методы оптимизации можно разделить на две большие группы:

- методы случайного поиска;

- регулярные методы.

Регулярные методы оптимизации стремятся построить такую последовательность x₁, x₂, x₃ …, при которой ЦФ(x₃) > ЦФ(x₂) > ЦФ(x₁) (при поиске максимального значения ЦФ). Общий алгоритм такого поиска:

1) выбор начальной точки в области определения ЦФ;

2) определение направления поиска на текущем шаге;

3) определение величины шага поиска;

4) вычисление ЦФ;

5) проверка условий окончания поиска.

Сущность метода оптимизации определяется этапами 2 и 3, на которых определяется направление дальнейшего поиска и вычисляются координаты очередной точки на траектории поиска.

Можно выделить следующие классы регулярных методов оптимизации:

- прямые методы поиска, не использующие производные ЦФ. Общий принцип их действия заключается в поочередном изменении каждого параметра до достижения ЦФ минимума (или максимума). Примером может служить метод покоординатного спуска.

- градиентные методы, использующие первые частные производные ЦФ по каждой переменной. Основаны на том, что направление уменьшения ЦФ противоположно направлению ее градиента. Примером может служить метод наискорейшего спуска.

- ньютоновские методы, использующие первую и вторую производную ЦФ. Обычно исходная кривая аппроксимируется (заменяется) набором парабол. Примером может служить метод Ньютона.

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

Поиск экстремума методами случайного поиска

Метод случайного поиска - в области определения ЦФ выбирается N пробных точек. В каждой точке вычисляется значение ЦФ. Наибольшее (наименьшее) значение лежит в области глобального экстремума. В зависимости от способа выбора пробных точек различают метод Монте-Карло (случайный выбор), метод ЛП-поиска - истинно равномерной разбивки многомерного куба, методы полного перебора вариантов и т.д.

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

К достоинствам методов случайного поиска можно отнести:

- слабая зависимость результата от числа изменяемых параметров;

- для расчета используется только само значение ЦФ (нет необходимости расчета ее производных);

- простота постановки и решения задачи поиска области глобального экстремума для ЦФ любого вида.

Недостатки: относительно большие затраты машинного времени на расчет. Впрочем, с развитием ЭВМ этот недостаток сглаживается.