Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 4
Текст из файла (страница 4)
Рассмотрим объект управления (рис. 2.1) как специальный случай общей системы, т. е. ориентированный абстрактный объект. Этот объект подвергается воздействию входного сигнала 1! (вектора) и выдает выходной сигнал Х (вектор), причем имеет силу отношение: 0 = (3 ( ! ), Х ==- Х ( ((); ()— = [((, ()(!)), — оа~.(< оо). Обозначим Ь'(!а, 1,) — семейство ориентировочных пар (!), Х) временных функций — — следующим образом: Й [(а, (~) = [(() ((а, !1), Х (!а, (и) ) ).
(2.2.2) Тогда под понятием системы А будем подразумевать семейство пар (13, Х) временных функций !т [та, г1), !а, 11 еп ( — оо, оо), (2.2.3» причем ((3, Х) аиА, если (1), Х) аи)т[(а, (1). Семейство )т[(а, (1) всех пар (и((а, (~), Х((а,(1) относится к А и представляет собой подмножество произведения й[ЩР',Й[Х], т. е. каждому ()((а, (~) соответствует единственное Х(!а, ! ). Если нам удастся найти любую функцию А, прп которой действительно отношение Х=А(а, !!), (2,2А) тогда и может быть состоянием системы А, причем должно выполняться условие сопряженной реакции: А (а, (), 0') = А (а, !)) А (иа, $У), (2.2.5) где а* представляет собой сопряженный параметр, а и'= и ((, (,) .
20 Для определенного таким образом ориентированного объекта отношение Х=А(а, 0) является характеристикой чвход--выхода объекта А. Если (3=(3(1о, 1), то а представляет собой исходное состояние системы А и обозначается как Я(та), т. е. Х(Ем 3) =А ($(1~) 13((м 3)). (2.2,6) Состояние системы в любом времени 3 определяется в таком случае следующим образом: Х(г) =Х(8(г,), 13(г,, 1), 1). (2.2.7) Если ориентированный объект подвергается также воздействию вектора помехи Х, то состояние объекта определяется следующим образом; Х(3) =Х(8(1,), Х(3), (3(3,, Г), г), (2.2.8) где векторам 2, 13, Х свойственны некоторые ограничения (Х) е Е; ((3) ен 13; (Х) = Н($3, Х, 3) я 3(.
(2.2.9) Как правило, выходной вектор Х(1) должен удовлетворять определенному условию, Введем функционал 3= )'а(Х, 13, Х,(),33+д(Х(т)), о (2.2.10) 21 где Т вЂ” фиксированное число; Я, 6 -- скалярные функции вектора. Нашей задачей является определение такого 0(3), который дал бы возможность достичь экстремума функционала (2.2.10), если таковой существует. Надо заметить, что нам неизвестно соотношение (2.2.8).
Известными являютсн: а) исходное состояние; б) соотношение (2.2.10). Можно произвести измерение Х(1) или же измерение определяющих состояние объекта величин. Основной задачей является вопрос — каким образом определить 13(1), т. е. каким образом, исходя изначальногосостояния, достичь экстремума функционала (2.2.10) и по достижении экстремума удержать последний в изменяющихся условиях (2.2.!О) нли же в изменяющихся характеристиках (2.2.8). В основу положим (без потери общности) итерационный, дискретный н стохастический алгоритмы. Тогда задача случайного поиска будет сводиться к следующему.
Надо определить такой случайный процесс Хэ, Х'„..., Х"', Хн+', чтобы ех!г(/-1*) ~э е, (2.2.11) 0 гэ !йп !к Следовательно, основная идея состоит в определении Хн+'. В сущности, речь идет о решающем процессе. Этот решающий процесс определяется методом случайного поиска, т. е. следующий шаг выводится из предыдущего состояния. Реализация следующего шага определяется на основе вероятности определяющего состояние системы параметра.
Если, например, эксперимент бьп успешен, то продолжаем двигаться в этом же направления; в противном случае возвращаемся в предыдущее состояние. Отдельные виды таких алгоритмов подробно приводятся в [!!. В большинстве опубликованных случаев решались сравнительно несложные задачи, т. е. такие, когда функционал (2.2,10) имел вид 1=1~ [Х), (2.2.! 2) В этом случае говорим, что речь идет об оптимальном управлении в установившемся состоянии, т. е. о так называемом статическом управлении. В то же время интересно рассмотреть следующие проблемы: 1.
Не решены задачи динамического управления методом случайного поиска (без помехи и с помехой). Особый случай статистической оптимизации с применением случайного поиска представлйет собой так называемый случай с плавающим экстремумом. Целевая функция в этом случае будет времешюй функцией, 2. Не решены методом случайного поиска задачи с плавающим экстремумом. В некоторых специальных случаях управляемая система должна соответствовать не только одному, но и нескольким критериям, т.
е. целевая функция будет вектором, 1 = Я [Х (1) ). (2.2.13) 3. Не решены методом случайного поиска задачи с несколькими целевыми функциями, или же функционалами. При теоретическом решении нас интересуют прежде всего следующие вопросы: а) наличие решения; б) сходимость решения (предельные теоремы); в) конкретная форма решения. Ввиду того что уже существует целый ряд алгоритмов, весьма важное значение имеет вопрос взаимного сопоставления отдельных видов алгоритмов — их качества и сложности. Число шагов Ф и общее время вычисления т не являются достаточными критериями для такого обсуждения. 4.
Не решена задача о сопоставлении алгоритмов случайного поиска по сложности. В 2.3. ЛОКАЛЪНЪ|Е АЛГОРИТМЫ СЛУЧАЙНОГО ПОИСКА Остановимся пока на задачах, в которых целевая функция имеет единственный экстремум. Вопрос решения задач методом случайного поиска с несколькими экстремумами будет описан в $2.5. В этом параграфе нами будут рассматриваться нерешенные вопросы, относящиеся к локальным экстремумам.
С теоретической точки зрения, процесс случайного поиска можно рассматривать как марковский 13). В приведенной работе эти проблемы еще не разработаны достаточно хорошо, поэтому нани будут рассматриваться следующие случаи: а) управляемые марковские процессы случайного поиска; б) сложные управляемые марковские процессы случайного поиска; в) мартингальпые илп же полумартингальные процессы случайного поиска.
3.1. Управляемые марковские процессы случайного поиска Общая теория управляемых марковских процессов общеизвестна и сравнительно хорошо разработана 14). Нами процесс случайного поиска будет представлен как управляемый марковский процесс. Пусть Х вЂ” фазовое пространство, определяющее состояние системы с конечным числом точек. Пусть случайный процесс с дискретным временем В= Д„, п=О, 1,...), $|~Х образует марковский неуправляемый процесс (цепь), тогда с вероятно- стью 1 действительно отношение Р(с|~;> =.Хна>) Бв..... Цо) =Р(~ы.» =.Хп+>) фа). (2 3 1) В случае управляемого марковского процесса будем предполагать, что  — пространство решения, нлн пространство управляемых величин.
Кроме того, дана матрица перехода вероятности Р($л+>=Х ч>(с„, И„), п=-0, 1. (2,3.2) зависящая от решения Н„е=-с>. Предположим, что в кз>кдок> временном моменте а решение о выборе конкретного значения параметра г(„зависит от предыдущпх наблюдений Хм Хо...,Х„. Каждая нз этнх функций, заданная в пространстве Х" »= =ХХХ>сХХ...ХХ, определяет управление в момент времени и. Точнее говоря, если результат зкспернмепта, наблюдаемого во время 1=0,1,..., и, является Хм..., Х„н если нами было определено управление, как функция д„(- ), то состояние системы во времени и+! определяется переходной вероятностью 113 >> Хй+! ) 5а — — Хв, с>„(Хю,..., Хп) ) (2.3.3) Тогда последовательность б=(п>„, п~0) функций А = >(о (Хо); Ы =>1>(Х, Х ); дз=Н>(Хо, Хь Хз); (2.3.4) (,,= („(Х,, Х,...
Х„) определяет управление б. Такой случайный процесс (с, б), который завнсит от б, принято называть управляемым (посредством б) марковским процессом. Управление б называется марковским в том случае, еслп каждая нз функций о>„=>(„( ) зависит только от последнего аргумента 0„=А(Х„), илн же, точнее, управление является марковским, если а> (Х'о, Х'ь..., Х' ->, Х ) =Ы (Х"о, Х"ь Х"„ь Х„) (2.3.5) для любого Х'м Х'>,..., Х',, и Х",, Х"ь..., Х", > Особый случай наблюдается, если управление б таково, что („ (х) = („"(х) (2.3.6) для всех и' и и". Тогда иы говорим, что это — однородное марковское управление.
Качество управлении, как правило, определяется функцией (р*(Х, д) в пространстве ХХ)9, характеризующей потери в результате управления а, когда система находилась в состоянии Х. Как правило, рассматривается функция Я„а=Им апр — ~ М„'И(ль А), ! (2.3.7) г Т г=а где М.д — такое математическое ожидание процесса, при котором Д, б) э(0) =Х.
Если обозначить о(х) =(п( )с„а (2.3.8) и назвать беи.0, е оптимальным управлением, то для всех хенХ имеет место отношение (2.3.9) 0(х) »я„а — а; 0 — оптимальное управление, которое обычно называется просто оптимальным. При определенном таким образом случайном процессе в теории случайного поиска мы будем интересоваться: а) условиями существования однородных марковских управлений; б) качеством алгоритма случайного поиска. Сравнительно хорошо разработан случай, когда наблюдаемый случайный процесс определяется неизвестным параметром пен(э, если этот параметр не изменяется во времени. Наш случай аналогичен, если целевая функция не зависит от времени й Такие случаи приводят к применению аппарата теории решающих функций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
