Главная Прочее
Проблемы автоматизированной обработки информации
|
|
|||||
Оптимизация дискретных системПусть система может находиться в одном из состояний дискретного множества 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) в отдельных точках области определения. В особо сложных случаях оценку численного значения производной можно получить, используя конечные приращения функции в нужных точках. |
<< | СОДЕРЖАНИЕ | >> |
---|