Полная версия

Главная arrow Психология arrow Искусство решать сложные задачи. Системный подход

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Методы безусловной оптимизации

1. Область применения. Используются для однокритериальной оптимизации детерминированных функций при отсутствии ограничений на саму функцию или её параметры

2. Сущность. Для поиска минимума функции у = f(x) производятся многократные вычисления при различных значениях параметров лФ, причём на каждом к-ом шаге вычислений контролируется выполнение условий которые должны

привести к минимальному значению функции.

  • 3. Особенности применения. Основные трудности заключаются в определении шага изменения параметра лФ, направления этого изменения и начального приближения д:(0). Неудачное решение этой проблемы может привести либо к потере минимального значения функции (в этом случае говорят о расходимости процесса), либо к нахождению “не самого маленького” минимума (так называемого “локального”, в то время как нужен абсолютный минимум на интервале поиска, иначе — глобальный), либо к неоправданному увеличению времени счёта.
  • 4. Наиболее употребительные методы. Классификация методов производится на основании возможности определения производных исследуемой функции. Если производную найти нельзя, а это часто бывает в случаях задания функции в неявном виде (совокупностью нескольких зависимостей) или при наличии разрывов функции, то используются методы нулевого порядка, если возможно найти первую производную — то методы первого порядка, если вторую — то методы второго порядка. Внутри каждого класса методы различаются по способам определения шага изменения параметров (шага поиска) и направления этого изменения. Номенклатура используемых в настоящее время методов достаточно широка, коротко рассмотрим суть наиболее характерных.

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

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

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

Методы первого порядка

К данному классу относятся так называемые градиентные методы. Их суть заключается в определении лучшего направления и шага поиска минимума функции по значениям первых производных в некоторой точке X. Наибольшее значение производной показывает направление наискорейшего уменьшения функции, и в этом направлении рассчитывается следующее приближение функции у = /(x(fc+1)), параметры которой отличаются на величину некоторого шага Ах. В зависимости от способа задания этого шага и производится классификация градиентных методов: градиентный спуск; наискорейший спуск; градиентный с постоянным шагом; градиентный с переменным шагом. Методы эффективны для функций со слабо выраженной нелинейностью.

Методы второго порядка

Их основой является метод Ньютона, предполагающий аппроксимацию исследуемой функции V—f(x) квадратичным полиномом в окрестностях некоторой точки Х(к) (точка начального приближения). Следующее приближение Х(к+1) определяется путём поиска минимума квадратичной аппроксимации функции F(x} , то есть такой точки в окрестности x(fc), в которой вид функции в наибольшей степени “похож” на квадратичную. Различные модификации метода Ньютона, в основном, отличается друга от друга способами расчета вторых производных. Кроме того, для устранения зависимости метода от начального приближения, различным образом определяются направление поиска по значениям первых производных. Методы второго порядка сходятся быстрее градиентных, однако требуют вычислений вторых производных.

Все перечисленные методы и их модификации широко представлены в общем математическом обеспечении ПЭВМ, более подробно с их алгоритмами, достоинствами и недостатками можно ознакомиться в /39, 9/.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>