5Л_СтохастическоеПрогр

Презентационные материалы к лекции:

«Стохастическое программирование»

по дисциплине «Методы оптимизации»

1

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

Модели часто оказываются неадекватными реальным процессам, что объясняется неполнотой или неточностью данных, на основе которых строилась модель

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

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

неопределенными

Оптимизационные задачи, при постановке которых нет исчерпывающих данных об их условиях, называются стохастическими

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

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

Активное стохастическое программирование (АСП ) – это совокупность приемов, позволяющих развивать методы выбора решений в условиях риска и неопределенности

Основным отличием стохастических методов от детерминированных является введение элемента случайности в процесс поиска экстремума

Стандартный стохастический алгоритм состоит из 2х шагов: сбор информации; принятие решения о движении

Алгоритмы случайного поиска различаются условиями выбора рабочего шага по направлению и возможностью изменения его размера в процессе поиска, а также возможностями алгоритма изменять вероятностные свойства случайности

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

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

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

Процесс самообучения и адаптации имеют много общего, и точную границу между ними провести трудно

Ненаправленный случайный поиск

Задача поиска оптимальных решений : требуется найти минимума функции W(X) векторного аргумента Х=(х1,x2,…,xn) в некоторой заданной области D допустимых значений X. Область D определяет пространство допустимых решений, каждой точке которого соответствует некоторое значение вектора X и целевой функции W(X), удовлетворяющие заданным ограничениям. Вектор X* D, соответствующий минимуму оптимизируемой функции W(X), является целью поиска.

Ненаправленный случайный (слепой) поиск экстремума производят следующим образом:

строят последовательность

X 1 (x11, x12 ,...,x1n ); X 2 (x12 , x22 ,...,xn2 );...; X N (x1N , x2N ,...,xnN )

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

W1(x11, x12 ,...,x1n );W 2 (x12 , x22 ,...,xn2 );...;W N (x1N , x2N ,...,xnN )

из которых выбирают наименьшую: W ( X *) min W1,W 2 ,...,W N

Если задано Wmin, то поиск осуществляется до тех пор, пока не будет найден Х*, т.ч.

В основе метода лежит проведение испытаний модели с использованием выборки объема N независимых случайных точек исследования {хi} для выявления области вероятного экстремума

Основной и весьма существенный недостаток метода — большая трудоемкость

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

Просматриваемое ограниченное подмножество вариантов выбирается случайным образом, что позволяет равномерно просмотреть все множество вариантов точек D. С увеличением объема выборки увеличивается вероятность получения оптимального решения задачи

Оценка требуемого объема вычислений может проводиться в ходе поиска

Необходимость продолжения вычислений определяется тем, насколько подробно была просмотрена область D:

1. Область D разбивают на l интервалов, вычисляют эмпирические частоты vi(1) Nl (i=1,2,…,l) попадания отдельных значений целевой функции W в i-й интервал. Поиск прекращается, если на некотором s-шаге для любого интервала выполняется условие

2.По результатам большого числа Nl испытаний (Nl>100) строят вариационный ряд (последовательность расположенных в возрастающем порядке значений целевой функции):

W1˂W2 ˂… ˂WN и эмпирическую интегральную функцию распределения FN1 ( ). Если после проведения дополнительного числа испытаний интегральная функция несущественно отличается от предыдущей, то говорят о достаточности объема вычислений

При реализации метода ненаправленного случайного поиска трудно получить равномерное распределение случайных точек в области D со сложной конфигурацией

Эффективность ненаправленного случайного поиска

Пусть заданы вероятность р и точность нахождения экстремума функции W(X) в области D. Точность определяет множество оптимальных решений {X*}. Отношение объема области оптимальных решений к объему области D обозначим через . Если случайные точки равномерно распределены в области D, то вероятность попадания в множество

{X*} на любом шаге равна , а вероятность попадания за N шагов составляет p 1 (1 )N

Необходимое число шагов для однократного попадания в область {X*} с вероятностью p определится по формуле

Nlg(1 p) lg(1 )

Для случая, когда области D и {X*} представляют собой n-мерные гиперсферы с соответствующими радиусами, вероятность попадания на одном шаге (при одном испытании) составит (r R)n

Число шагов N, необходимое для попадания в область {X*} с заданной вероятностью р, в этом случае находится по формуле

N lg(1 p) lg(1 (r R)n )

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

Направленный случайный поиск

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

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

Эти числа получают масштабированием случайных чисел ri, равномерно распределенных в интервале (0, 1), в соответствии с формулой: i0 1 2ri

Метод с возвратом при неудачном шаге. В пространстве параметров произвольно выбирается точка Х0. Задается постоянный шаг h. Из точки Х0 в случайном направлении, определенном случайным единичным вектором ζ = (ζ1,…, ζn), осуществляется шаг на величину h. Вычисляется значение целевой функции в новой точке X1. Если значение W(X1) W(X0) (в случае поиска минимума), то шаг считается рабочим, и новый шаг осуществляется из точки X1 в случайном направлении. Если W(X1) > W(X0), то шаг считается неудачным, производится возвращение в точку X0, из которой в случайном направлении снова совершается пробный шаг:

где ( 1, 2 ,..., n ) — n-мерный независимый случайный вектор

Повторное определение W(X) при возвращении в исходный центр поиска следует применять в тех случаях, когда целевая функция по каким-либо причинам изменяется во времени, например при наличии помех

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

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

поиском с линейным пересчетом

При неудачном j-ом шаге, когда W W ( X j ) W (X j 1 ) 0 , новым центром поиска служит точка X j 1 X j 2 X j

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

Движение из центра зоны поиска Xj-1 , найденного в процессе поиска, ведется в

случайном направлении X X a до тех пор, пока не обнаружится

j j 1

благоприятное направление такое, что W W ( X j 1 a j ) W (X j 1 ) 0 . После этого осуществляют движение в найденном благоприятном направлении с фиксированным шагом X a j и соответствующим смещением зоны поиска до тех пор, пока W 0

В начале поиска используют достаточно большой шаг, а затем его уменьшают. Недостаточная длина рабочего шага поиска приводит к возрастанию вероятности «застревания» в локальном экстремуме

В рассматриваемом алгоритме случайность вводится как отрицательная реакция на неудачный шаг

Алгоритмы поиска с «наказанием» случайностью предполагают смещение зоны поиска в благоприятном направлении сразу после удачного шага

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