Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 6
Текст из файла (страница 6)
Из соотношения (2.4.1) видно, что функция с*(а,т, х) зависит только от апостериорных вероятностей р(и)аат). Эти функции являются достаточными координатами. Если число возможных значений и является конечным, то число независимых достаточных координат на одну единицу меньше числа возможных значений и, так как Яр(и(аат) = 1. И Достаточными координатами могут служить также другие параметры, которые равноценны условной вероятности р(и/г;).
Например, если и может приниматьтолькооднозначныезначения 31 0 или ! с априорными вероятностямн р(0) и р(1), то, согласно отношению (2.4.1), получим с*(гот, х) =с(0, х) р(0(гот)+с(1, х) р(1)гот) = с(0, х) +с(1, х) — Л(го') р(1) р (0) (2.4.3) () 1+ — Л(гот) р(0) р(дзот) 1) где Л(го*) = — — — -- — отношение вероятности. Это отноше( д г о т ) 0 ) ние — единственная достаточная координата. Во введении мы говорили, что «ценная информация» зависит от среднего значения штрафа.
Приведенная форма этой функции была довольно простой. Дело осложняется, если штрафовая функция является, например, квадратической: с' (гот, х) = ~ ( и — х) 'Р (и1гот) . (2.4.4) В этом случае блок !! может быть построен как перцептрон с пороговой логикой. Уровень порога будет достаточной величиной пм 8. До сих пор ие решен случай определения достаточных координат н функций достаточных статистик в случае, если целевая функция имеет общую форму. В 5 2,3 мы говорили, что процесс случайного поиска можно рассматривать как управляемый марковский процесс -- простой или сложный.
И в этом случае можно применять теорию информации в ее специальной части семантических аспектов для оптимального управления марковскими процессами случайного поиска. Основным вопросом и в этом случае является определение того, какие «достаточные статистики» даны на основе проведенных в прошлом экспериментов и наблюдений. Теперь рассмотрим способ определения достаточных статистик в процессе оптимального управления б. Каждое управление б определено случайными величинами $ (собственным процессом) и условием, что оно ие зависит от будущего. Следовательно, решение во времени ! о продолжении или окончании наблюдения или эксперимента детерминируется всеми предыдушими значениями Х"=(хь...,х,). Ясно, что число шагов или экспериментов и будет увеличено объемом памяти, необходимым для запоминания всех предыдуших значений, определяющих процесс. Нас интересует вопрос, возможно ли для определения оптимального б применять другой способ, чтобы сделать объем информаций меньшим.
Эта задача сводится к основной про- блеме нахождения достаточных и марковски достаточных о-ал- гебр и статистик. Например, можно доказать, если 1) интервал наблюдения — конечный, 2) штрафовая функция носит аддитивный характер, 3) воздействующие на систему эксперименты (активные) являются независимыми, 4) процесс будет марковским, что достаточной статистикой является апостернорная вероят- ность. 9, Однако не решена задача — каковы достаточные статис- тики в случае сложного марковского процесса й-го порядка при условии, что интервал наблюдения является конечным (или же бесконечным). Применение теории семантики информации может вести к принципиально новым результатам в теории случайного по- иска.
й 2.5. АЛГОРИТМЫ ГЛОБАЛЬНОГО СЛУЧАИНОГО ПОИСКА Как правило, под понятием алгоритма глобального оптимального управления методом случайного поиска подразумевается способ, позволяющий получить абсолютный экстремум определяемой функции Я(Х) методом случайного поиска. Вопросы получения абсолютного экстремума изложены в нескольких работах (1, 2, 7, 8], использующих теорию «овраговз и теорию обучения с яаправляющим конусом, или же изменение выбора исходных условий. К решению задач глобального случайного поиска можно однако приступать и другим способом - — методом непрерывного случайного диффузионного процесса. В теории вероятности этот процесс известен. Сравнительно хорошо разработана соответствующая теория. Например, доказано, что диффузионный процесс — это такой непрерывный марковский процесс, приращение которого г(х(() является случайным процессом Гаусса со 3 — бг 33 средним значением тдЕ и дисперсией о~ау(Е), где у(Е) — компонента флуктуационного движен~ня.
Если этот диффузионный процесс является стационарным, то переходныс вероятности р(з, к; Е, и) =р( ° ) удовлетворяют илп прямому диффузионному уравнению Фоккер †План: др(з, й; Е,п) д ! дз — * — ' — а — [т(Е,п)р()) — — — [о(Е,т~)'р'())=О, (2.5.!) дЕ дп ' 2 дп' где з — независимая переменная, время; $ — первоначальная координата; — независимая переменная, время; т) — новая координата; р()= др() дп или инверсному диффузионному уравнению Колмогорова: др() [ др() д~р(.) о(з,Цз1 - — -- + ~т (з, ~) + — -- — '- — '- — 1=0. (2.5.2) дз [ ' ' д~ Д~г Поскольку решение приведенных выше уравнений является весьма сложным, более выгодно искать решение разностного уравнения, выражающего диффузионный процесс (2.5.3) дхс =т(Е, хс) дЕ+ о(Е, х~) с1у(Е), в интервале а < Е < Ь.
Тогда уравнение (2.5.3) можно записать в следующей форме: х(Е)-х(а) =- ~ т(з,х(з))с(з+ Е' о[з,х(з))ду(з). (254) Необходимо принять во внимание, что решение существует, если существуют оба интеграла. Самые большие трудности встречаются прн нахождении второго интеграла.
Поскольку интеграл — случайная функция, при его нахождении должны быть соблюдены определенные условия. Уравнение решается, как правило, методом последовательных приближений. Проблема состоит в том, что до сих пор неизвестны эффективные практические методы теории диффузионных процессов. 10. Не разработан алгоритм глобального случайного поиска и случайного диффузионного процесса, особенно с точки зрения рационального алгоритма.
Есть очень интересная идея — решение задачи, ведущее калгоритму глобального случайного поиска как сложного управляемого марковского процесса Ь-го порядка, при котором реализация нового случайного шага с определенной вероятностью считается процессом рождения, а потеря памяти (забывание) —- процессом гибели. В нашем случае успешный шаг зависит ие только от состояния оптимального управления 6 в настоящий момент или же непосредственно предыдущего состояния, но и от результата двух процессов, определяемых состоянием в настоящий момент и состоянием в предыдущий момент, причем каждое состояние в настоящий момент и каждое последующее состояние ведет к потере информации о предыдущем состоянии.
В результате процесс рождения и гибели ведет к эволюции или дегенерации (гибели). В чен состоит основная идея теории обобщенных марковских процессов рождения и гибели (.!)У Процессом рождения и гибели будем называть такой процесс, при котором из состояния Е„в промежуток времени (г,(+Ь) происходит переход в состояние Е„, или Е,+ь Если п --О, то переход происходит только из Е, в Еь Вероятность того, что процесс перейдет из состояния Е„ в Е„ , (н !), есть Хай+ Я(Ь), а вероятность перехода из состояния Е„ в Е„+,-- рпЬ+Я(Ь). Следовательно, можно встретиться с тремя случаями: 1) во времени ! система находится в Е„, а во времени (+Ь остается в первоначальном состоянии; 2) во времени ( система находится в Е„, а во времени (+Ь переходит в Е„~., 3) во времени ! система находится в Е„, а во времени (+Ь переходит в Е„эь Эти три возможности исключают друг друга.
поэтому их вероятности складываются. На основе этого можем написать следующее отношение: Р, (!+Ь) =Р„(()(! — Х„Ь вЂ” рьЬ)+Х ~ЬР,, ~(() + +р, ыЬР„+~+о(Ь). (2.5.5) 35 После нахождения предела при й-~О получим Р' (1) =(Х„.1-9 )Р (()+Х;, ~Р„~(1) +р +~ ° Р„+~(1) (256) для п=О— РдЯ = — Х~Р (() +р~Р (1). (2.5.7) Можно доказать, что решение уравнения (2.5.6) существует [4) для Х )О и р~О и, следовательно, ХР„(1) ~1. Если 1,„ и р„ограничены, тогда решение таково, что ХР„(1) =1.
Подобным же образом можно доказать, что существует 1пп Р (1) =Р„. (2.5.8) Приведенные выше положения можно обобщить, если разрешить системе из любого состояния Е; перейти в любое состояние Е„, прн этом вероятности Р„,(Г) могут изменяться в отдельные интервалы времени.
Будем и далее считать такой процесс марковским. В нашем случае это значит, что если дано состояние системы в какой-то отрезок времени, то будущее состояние не зависит от предыдущих. Например, рассмотрим три отрезка времени т<з<Г и предположим, что в отрезок времени т система находится в состоянии Еь а в отрезок времени з — в состоянии Е,. Вероятность (условная) общего случайного процесса в отрезок времени г в состоянии Е„ зависит также от 1 и о, но это не касается марковских процессов, для которых действительно только следующее отношение: Р;„(т,() =~, Р; (т, з)Р „(з,1). (2.5.9) Для всех т<з<1 — это уравнение Колмогорова — Чепмена. Здесь возникают важные вопросы, так как это уравнение характеризует случайный марковский процесс.
Если процесс является однородным, то уравнение (2.5.9) имеет следующую форму: Ры(Г+з) =~,Р,тЯР„„(з). (2.5.10) т 11. С точки зрения случайного поиска, была бы полезной разработка втой теории для тех типов алгоритмов, которые приводят к обучающимся системам случайного поиска с учетом процесса забывания как сложного марковского или обобщенного случайного процесса, Значение метода случайного поиска в настоящее время не вполне оценено, главным образом с точек зрения практического применения в автоматизации, оптимального управления производственными процессамп и идентификации систем не только в автоматизации, но и в живой природе, при исследовании человека.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
