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

Главная arrow Прочее arrow Проблемы автоматизированной обработки информации

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


<<   СОДЕРЖАНИЕ   >>

Оптимизация дискретных систем

Пусть система может находиться в одном из состояний дискретного множества S. S* - дискретное фазовое пространство.

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

(12)

Здесь - состояние системы на i-м шаге.

Методы решения экстремальных задач при отсутствии ограничений.

Градиентные методы.

Пример отыскания максимума функции одной переменной.

Пусть y=f(x) (Рис. 28).

Рис. 28

Выберем произвольную точку х из области определения функции y=f(x). Заметим, что если точка выбрана слева от точки максимума (х = х1), то производная от f(x) в точке х1 и следовательно точка при разумном выборе величины параметра k находится ближе к экстремальной точке х0.

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

Таким образом, может быть построена последовательность точек

x(1), x(2), …, x(l), x(l+1), … , (1)

вычисляемых по рекуррентному правилу

, (2)

стягивающаяся к искомой экстремальной точке х0.

Сходимость последовательности (1) к точке х0 обеспечивается рациональным выбором численного значения k, определяющего длину шага. Рекурсивное соотношение (2) легко обобщается на случай отыскания экстремума функции многих переменных.

Пусть X*T=(x*1, x*2, …, x*n) - вектор, доставляющий максимальное значение функции F(x1, x2, …, xn). Введём вектор-столбец значений частных производных от оптимизируемой функции F(X) в точке Xl , называемый градиентом, т.е.

(39)

и матрицу K(Xl).

Теперь вычисление точки Xl+1 на очередном шаге градиентной процедуры осуществим по формуле

(40) (3)

В соответствии с (3) вектор-градиент определяет направление перемещения от Xl к Xl+1, а матрица K(Xl) - длину шага.

Длина шага выбирается из следующих соображений:

её не следует выбирать слишком большой, чтобы не «проскочить» экстремум, т.к. при этом появляется опасность зацикливания;

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

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

При этом (3) записывается в виде

,

где скаляр kl определяется из условия

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

В результате проведения некоторого числа шагов в соответствии с (3) обеспечивается попадание внутрь произвольно малой окрестности экстремальной точки.

Критерием для останова может служить величина модуля вектора-градиента

Градиентную процедуру считаем законченной, как только численное значение модуля окажется < .

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

«Метод переменной метрики» использует информацию о поведении оптимизируемой функции в уже пройденных точках.

Достоинство: не требуется наличия аналитического представления производной от оптимизируемой функции и умение решать систему уравнений (7.1).

Необходимо уметь вычислять частные производные от функции F(X) в отдельных точках области определения.

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

 
Перейти к загрузке файла
<<   СОДЕРЖАНИЕ   >>