Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 32
Текст из файла (страница 32)
С математической точки зрения, задача восстановления указанной функции по ее значениям в отдельных точках (узлах) является задачей теории интерполирования функций многих переменных. Однако применение методов этой теории к решению поставленной задачи в общем случае затруднено тем оостоятельством, что узлы интерполирования здесь могут бгять расположены произвольно. Развитый в работах !17, !8) метод потенциальных функций снимает последнее требование и позволяет решить задачу восстановления функции (9.1.4).
Метод основывается на предположении, что существует такая система ортогональных функций ~г,(А), <рз(А),...,~рр(А), что функция х=х(аь аь..., а ) может быть представлена конечным. рядом: (9.1.6) Р х (А) = 2, с,.~р, (А) . г".1 (9.1.7) 2!7 Восстановление (аппроксимация) функции осуществляется с помощью рекурреитных алгоритмов. При каждом появленнк новой точки А~ и соответствующего значения функции х; происходит корректировка ранее построенной функции (корректировка коэффициентов с;) и получение функции х;(А) таким образом, что ошибка аппроксимации в показанной на этом шаге точке уменьшается. Одновременно может несколько увеличиваться ошибка в некоторых ранее показанных точках, однако это обстоятельство, как доказано в работе !18], не препятствует сходимости алгоритмов.
Рекуррентное соотношение, аналогичное алгоритмам метода потенциальных функций, предложено в работе [19). В работах (20 †2 показано, что задачу восстановления многопараметрической функции, а, значиг, в рассматриваемой постановке и задачу адаптации модели можно решить с применением методов стохастической аппроксимации.
Согласно этим методам, предложенным в работах [23, 24] и развитым или систематизированным в работах [25— 31], функция (9.!.6) также аппроксимируется взвешенной суммой (9.1.7) линейно .независимых функций. Алгоритмы стохастической аппроксимации также имеют внд рекуррентных соотношений. Множество алгоритмов, позволяющих решить задачуприближенпого восстановления функции по ее значениям в случайно наблюдаемых точках,:.не исчерпывается приведенными выше. Как указывается в работе [31], читатель сам может синтезировать подобные алгоритмы, основываясь на теореме Дворецкого [26] при доказательстве сходимости того или иного алгоритмаа.
Общим недостатком изложенных методов аппроксимации функции является то, что при заданном числе наблюдений Ж ошибка аппроксимации существенно зависит от вида выбранных функций ~р,(А). Следовательно, указанные процедуры могут обеспечить удовлетворительное восстановление функции только при достаточно большом числе У .наблюдений. В ряде случаев, однако, стоимость каждого эксперимента (показа) |весьма внушительна. В результате возникает потребность в оценке значения функции в произвольной точке на базе ограниченной обучающей последовательности.
Иногда число й показов может быть меньшим размерности пространства ситуаций. Для решения задачи приближенной адаптации модели на основе короткой обучающей последовательности предложен алгоритм многомерной линейной экстраполяции, развитый в работах [32 — 34]. 5 92. МЕТОД МНОГОМЕРНОН ЛИНЕННОИ ЭКСТРАПОЛЯЦИИ По этому методу оценки для оптимальных параметров системы находятся следующим образом [31, 32]: через векторы, входящие в состав обучающей последовательности (9.1.5), проводятся гнперплоскости Б' и 0' в пространстве ситуаций 8 и пространстве оптимальных решений К Очевидно, любой элемент А'сна' в предположении о линейности пространства ситуаций можно предста~вить в виде линейной комбинации: а-1 А'=А|+ ~, Х;(А,+~-А~), (9.2.1) ьм 218 где )и являются координатами А' в базисе, построенном на элементах обучающей последовательности.
Аналогична для Х'ен(Д получим ь-! Х'=Х*,+ ~ р,(Х,„.,— Х",). (9.2.2) ~'-! Преобразование узловых точек Аь...,Ал гиперплоскостп 5' в соответствующие точки Х~"'..,.. Хь" гиперплоскости (I' осуществляется путем прнравниванпя одноименных коэффициентов линейной формы: Х;=рь Далее вводится гипотеза линейности, согласно которой предполагается, что любая неузловая точка А'ы5' преобразуется в соответствующую точку Х'~п(/' с помощью указанного преобразования. Таким образом, искомая зависимость (9.1.4) линеаризуется на подпространствах 3' и У', что позволяет для любой ситуации А'~5' находить оценку для оптимальных параметров системы путем линейной экстраполяции. Если новая ситуация А находится вне гнперплоскости 5', то ее естественно отождествить с ближайшей к ней в определенном смысле ситуацией, лежащей в 5'.
Для этого в пространство ситуаций вводится метрика. что позволяет каждой паре ситуаций поставить в соответствие число о, определяющее меру нх близости. Например, если близость ситуаций оценивать по величине геометрического расстояния между ними о(А А) ~А А ~а (9.2.3) то в этом случае ситуация А~Я будет отождествляться сосвоей ортогональной проекцией А' на гиперплоскость Б'. Отождествление Аем А', по сути дела, означает, что свойства подпространства Я' распространяются (экстраполируются) на близлежащую область простра,истаа 5, Символическая запись алгоритма; А А'-э- Х'= Х~. (9.2.4) Предложенный алгоритм целесообразно применять, если 1) область варьирования параметров ситуации относительно мала, вследствие чего приспособление системы осуществляется путем изменения ее параметров при фиксированной структуре; 2) имеется опыт оптимального,приспособления системы к некоторым ситуациям из указанной области, на основании которого строится обучающая последовательность; 219 3) неизвестную функциональную зависимость (9.1.4) можно с достаточной точностью линеаризовать в области изменения параметров ситуации.
Если длина обучающей последовательности (9.!.5) превышает размерность пространства ситуаций, то третье условие ослабляется: в этом случае зависимость (9.!.4) должна допускать локально-линейное приближение в окрестности любой произвольной точки из указанной области. Это объясняется тек, что прп й»п оценка для оптимальных параметров системы определяется не по всем располагаемым наблюдениям, а лишь по ближайшим (в смысле введенной метрики) к исследуемой ситуации. На практике проверку третьего условия применимости метода нетрудно провести после получения обучающей последовательности. Для этого достаточно провести «самовосстановление> обучающей последовательности: в качестве новой ситуации А, поочередно выорать каждую из ситуаций полученной после. довагельности и для нее найти оценку вектора Хн Анализ ошибок ЛХ;= Х,« — Х,' «самовосстановления» последовательности позволяет принять решение о допустимости перехода в дальнейшем на экстраполяцнонный метод приспособления системы на базе полученной информации.
Алгоритм многомерной линейной экстраполяции реализован в программе для ЭЦВМ «БЭСМ-ЗМ». Исходными данными в программе являются числовые значения компонент векторов обучающей последовательности и вектора новой ситуации, Программа автоматически настраивается на указанные значения размерности вектора ситуации и, размерности вектора параметров системы п н длины обучающей последовательности й, Блок-схема программы представлена на рис. 9.1. На первом этапе производится сортировка векторов ситуации обучающей последовательности в порядке возрастания их удаленности от вектора новой ситуации. Одновременно в той же последовательности перестраиваются векторы оптимальных параметров, соответствующих ситуациям обучающей последовательности.
Это осуществляется в блоке сортировки. Далее делается попытка пахом<пения оценки вектора Х" по ближайшим й ситуациям. Решение системы линейных уравнений производится по схеме обыкновенных жордановых исключений в блоке жордановых исключений. Если некоторые из ближайших й ситуаций оказываются линейно зависимыми, онн отбрасываются и заменяются последую- 22! шими в порядке удаленности. Этот анализ производится в блоке анализа линейной за~висимостп векторов. Здесь же выясняется, достаточно ли й векторов ситуаций обучающей последовательности для построения базиса в пространстве ситуаций. Если их недостаточно, то находится ближайший к новой ситуации вектор, принадлежащий подпространству векторов известных ситуаций, и по нему отыскивается оценка вектора Х"'.
Перестройка программы на размерность подпространства производится в блоке переформирования программы. $93. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА МНОГОМЕРНОЙ ЭКСТРАПОЛЯЦИИ Экспериментальная проверка алгоритма была проведена на примере корректировки параметров модели (8.2.4) динамического объекта (8.2.1). Предполагалось, что объект является квазистациоиариым, т.
е. характеристики входного сигнала и объекта остаются постоянными в течение промежутка времени, необходимого для выполнения цикла самонастройки модели. Затем происходит скачкообразное изменение характеристик объекта и входного сигнала, и цикл самонастройки модели повторяется. Из сущности метода многомерной экстраполяции следует, что вначале определенное число корректировок модели проводится с применением процедуры многопараметрической оптимизации.
Это — период обучения экстраполятора, во время которого он запоминает состояния объекта и соответствующие им векторы оптимальных параметров модели. Последующие корректировки модели осуществляются экстраполятором на основании опыта, накопленного за период обучения. Время от времени опыт экстраполятора следует обновлять. Это особенно необходимо, когда параметры объекта подвержены не только случайному, но и регулярному дрейфу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
