ОПТИМИЗАЦИЯ КОЭФФИЦИЕНТА РАЗМЫТОСТИ ЯДРА В НЕПАРАМЕТРИЧЕСКОМ МОДЕЛИРОВАНИИ


Цитировать

Полный текст

Аннотация

Исследуется проблема моделирования дискретно-непрерывных процессов в пространстве входных-выходных переменных. Моделирование данных процессов может осуществляться при помощи различных параметрических и непараметрических методов. Рассмотрено моделирование при помощи непараметрических методов. Такое решение было принято ввиду того, что непараметрическая теория, в отличие от параметрической теории, предполагает, что известны только качественные характеристики процесса. Зачастую, моделируемые объекты обладают неизвестной, сложной структурой. Учитывая эти факты, использование и развитие непараметрической теории продолжает быть актуальной задачей современности. Результаты статьи могут быть использованы для моделирования и управления оборудованием космических аппаратов. При построении модели объекта при помощи ядерных оценок, важным параметром является коэффициент размытости ядра. Рассмотрены алгоритмы оптимизации коэффициента размытости ядра, а именно: метод перебора, метод деформируемого многогранника и генетический алгоритм. В качестве критерия оптимизации была выбрана среднеквадратичная ошибка модели исследуемого процесса, вычисленная при помощи скользящего экзамена. Стоит еще также сказать, что будут представлены результаты при оптимизации вектора параметров размытости ядра (для каждого входного воздействия) и при оптимизации общего коэффициента на все входные взаимодействия. Как выясняется, точность модели с одним оптимизированным параметром размытости ядра несколько уступает точности модели с оптимизированным вектором параметров размытости ядра, при этом вычисление коэффициента размытости ядра выполняется в разы быстрее и, как следствие, быстрее строится модель. Данные результаты могут быть крайне полезны при моделировании и управлении в условиях быстрого поступления информации и меняющейся обстановки.

Полный текст

Введение. Идентификация многих стохастических объектов часто сводится к идентификации статических систем. Наиболее общая схема исследуемого дискретно-непрерывного процесса может быть представлена на нижеследующем рисунке[1-3]: На рис. 1 приняты следующие обозначения: А - исследуемый объект (процесс); - выходной вектор процесса; - вектор управляющих воздействий; - вектор входных неуправляемых, но измеряемых переменных процесса; - вектор входных неуправляемых и неизмеряемых переменных процесса; - случайное воздействие, - переменные процесса, контролируемые по длине объекта; (t) - непрерывное время; , , , , , - каналы связи, соответствующие различным переменным, включающие в себя средства контроля, приборы для измерения наблюдаемых переменных; , , , - означают измерение , , , в дискретное время; , , , со значком вверху - случайные помехи измерений соответствующих переменных процесса. Идентификация в узком и широком смысле. При моделировании разнообразных дискретно-непрерывных процессов в настоящее время доминирует теория идентификации в узком смысле [4; 5]. Ее содер-жание состоит в том, что на первом этапе, на основании имеющейся априорной информации, определяется пара-метрический класс оператора объекта А, например: , (1) где - параметрическая структура модели; α - вектор параметров. На втором этапе осуществляется оценка параметров α на основе имеющейся выборки , s - объем выборки. Успех решения задачи идентификации в этом случае существенно зависит от того, насколько «удачно» определен оператор (1). Идентификация в широком смысле предполагает отсутствие этапа выбора параметрического класса оператора. Часто оказывается значительно проще определить класс операторов на основе сведений качественного характера, например, линейности процесса или типа нелинейности, однозначности либо неоднозначности и др. В этом случае задача идентификации состоит в оценивании этого оператора на основе выборки [6; 7]: , (2) где - временные векторы. Оценка оператора может быть осуществлена средствами непараметрической статистики. Примечательным здесь является то, что при этом исключается этап выбора параметрической структуры. Тем самым можно утверждать, что идентификация в этом случае, а это вариант идентификации в широком смысле, является более адекватной реальным задачам практики. Непараметрическая идентификация. Непараметрическая идентификация представляется в виде моделирования при помощи ядерных оценок (3) [8; 9]: (3) где Ф(*) - это ядерная «сглаживающая» функция (4), а - коэффициент размытости ядра: (4) Стоит сказать, что от выбранного коэффициента размытости напрямую зависит качество построенной модели. Данный коэффициент определяет степень участия элементов выборки в вычислении в точке uм (рис. 2). Ход исследования. Смысл исследования заключается в выборе наиболее точного и быстрого способа оптимизации, а также в выяснении вопроса о необходимости оптимизации коэффициента размытости для каждого входного воздействия. Все исследования проведены на машине с 4-ядерным процессором, с частотой ядер 2,8 ГГц. Программы написаны в среде Visual Studio 2010, на языке программирования C#. Для начала оптимизируем вектор коэффициента размытости ядра при помощи метода деформируемых многогранников. Слабостью данного метода можно считать то, что при нахождении минимума он может «застрять» в локальном экстремуме. Для того чтобы определить, применим ли данный метод для оптимизации cs, построим график зависимости среднеквадратичной ошибки (σ) от cs (рис. 3). Как видно на рис. 3, данная зависимость плавная, и в ней нет большого количества локальных минимумов. В связи с этим можно проводить оптимизацию cs при помощи метода деформируемого многогранника [10; 11]. Алгоритм данного метода следующий: Параметрами метода являются: - коэффициент отражения α > 0, обычно выбирается равным 1; - коэффициент сжатия β > 0, обычно выбирается равным 0,5; - коэффициент растяжения γ > 0, обычно выбирается равным 2. Рис. 1. Общая схема исследуемого процесса Рис. 2. Определение коэффициента размытости ядра Рис. 3. Зависимость среднеквадратичной ошибки от коэффициента размытости ядра 1. «Подготовка». Вначале выбираются n + 1 точки xi = (xi(1), xi(2), …, xi(n)), i = 1…n + 1, образующие симплекс n-мерного пространства; в этих точках вычисляются значения функции: f1 = f(x1), f2 = f(x2), …, fn+1 = f(xn+1). (5) 2. «Сортировка». Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, со следующим по величине значением и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh. 3. Найдём центр тяжести всех точек, за исключением xh: (6) 4. «Отражение». Отразим точку xh относительно xh с коэффициентом α, получим точку xr и вычислим в ней функцию fr = f(xr). Координаты новой точки вычисляются по формуле (7) 5. Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fh, , fl. Если fr < fl, то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение». Новая точка xe = (1 - γ)xc + γxr и значение функции fe = f(xe). Если fe < fr, то можно расширить симплекс до этой точки: присваиваем точке xh значение xe и заканчиваем итерацию (шаг 9). Если fr < fe, то переместились слишком далеко: присваиваем точке xh значение xr и заканчиваем итерацию (шаг 9). Если fl < fr < , то выбор точки неплохой (новая лучше двух прежних). Присваиваем точке xh значение xr и переходим на шаг 9. Если < fr < fh, то меняем местами значения xr и xh. Также нужно поменять местами значения fr и fh. После этого идём на шаг 6. Если fh < fr, то просто идём на следующий шаг 6. В результате (возможно, после переобозначения) fl < < fh < fr. 6. «Сжатие». Строим точку xs = βxh + (1 - β)xc и вычисляем в ней значение fs = f(xs). 7. Если fs < fh, то присваиваем точке xh значение xs и идём на шаг 9. 8. Если fs > fh, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса - гомотетию к точке с наименьшим значением xl: . (8) 9. Последний шаг - проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2. После этого вектор коэффициентов размытости ядра будет оптимизироваться при помощи генетического алгоритма [12-15]. Генетический алгоритм выглядит следующим образом: 1. Перед первым шагом нужно случайным образом создать начальную популяцию. Даже если она окажется совершенно неконкурентоспособной, вероятно, что генетический алгоритм всё равно достаточно быстро переведёт её в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей. 2. Размножение в генетических алгоритмах обычно половое - чтобы произвести потомка, нужны несколько родителей, обычно два. Размножение в разных алгоритмах определяется по-разному - оно, конечно, зависит от представления данных. Главное требование к размножению, чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо способом. Особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H0 из-за того, что проблема многих генетических алгоритмов - недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом. Один из них - выбор для размножения не самых приспособленных, а вообще всех особей. 3. К мутациям относится все, что и к размножению: есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма, и на шаге мутаций нужно выбрать mN особей, а затем изменить их в соответствии с заранее определёнными операциями мутации. На этапе отбора нужно из всей популяции выбрать определённую её долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма и её просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают. Вычислительный эксперимент. Моделируемый процесс имеет два входных воздействия и один выходной параметр. Обучающая выборка была взята в количестве 300. Помеха, воздействующая на объект, была равна 7 %. Критерием оптимизации была выбрана среднеквадратичная ошибка σ: (9) Выведем результаты в виде таблицы. Результаты оптимизации cs Метод оптимизации Оптимизируемый параметр Время нахождения оптимального cs, миллисекунд Среднеквадратичная ошибка σ Метод деформируемого многогранника Вектор cs 1118 0,750869 Метод деформируемого многогранника Скаляр cs 100 0,755853 Перебор возможных значений Вектор cs 26808 0,780678 Перебор возможных значений Скаляр cs 934 0,78102 Генетический алгоритм Вектор cs 39067 0,758035 Генетический алгоритм Скаляр cs 37028 0,761118 Как мы можем видеть из таблицы, оптимизация вектора коэффициента размытости занимает во много раз больше времени, чем оптимизация скалярного значения, при этом модель практически не становится лучше. Также стоит отметить, что оптимизация при помощи метода деформируемых многогранников действует гораздо быстрее, чем оптимизация при помощи стандартного перебора или генетического алгоритма. Заключение. В статье приведены такие методы оптимизации, как метод деформируемых многогранников, генетический алгоритм и простой перебор возможных значений, и показаны результаты работы данных методов. Также была доказана возможность использования методов локальной оптимизации для нахождения наилучшего коэффициента размытости ядра. Было проведено сравнение между оптимизацией при помощи метода деформируемых многогранников, генетического алгоритма и оптимизацией при помощи стандартного перебора, где было доказано превосходство первого в задаче оптимизации коэффициента размытости ядра. Доказано, что оптимизация вектора коэффициентов размытости является нецелесообразной вследствие больших затрат времени и малого изменения в точности модели исследуемого процесса.
×

Об авторах

Е. Д. Михов

Сибирский федеральный университет

Email: edmihov@mail.ru
Российская Федерация, 660041, г. Красноярск, просп. Свободный, 79

Список литературы

  1. Tweedle V. Smith R. A mathematical model of Bieber Fever // Transworld Research Network. 2012. vol. 37/661, № 2. Р. 157-177.
  2. Lingefard T. Faces of mathematical modeling // ZDM. 2006. vol. 38, № 2. Р. 96-112.
  3. Советов Б. Я, Яковлев С. А. Моделирование систем : учебник для вузов. М. : Высш. шк., 2001. 343 с.
  4. Арнольд В. Теория катастроф. М. : Наука, 1990. 128 с.
  5. Медведев А. В. Некоторые замечания к Н-моделям безынерционных процессов с запаздыванием // Вестник СибГАУ. 2014. № 2(54). С. 24-34.
  6. Медведев А. В. Анализ данных в задаче идентификации // Компьютерный анализ данных моделирования. Т. 2. Минск : БГУ, 1995. С. 201-206.
  7. Медведев А. В. H-модели для безынерционных систем с запаздыванием // Вестник СибГАУ. 2012. № 5(45). С. 84-89.
  8. Цыпкин Я. З. Адаптация и обучение в автоматических системах. M. : Наука, 1968. 400 с.
  9. Фельдбаум А. А. Основы теории оптимальных автоматических систем. М. : Физматгиз, 1963. 552 с.
  10. Рубан А. И. Методы анализа данных : учеб. пособие. 2-е изд., испр. и доп. Красноярск : ИПЦ КГТУ, 2004. 319 с.
  11. Marco A., Rodolphe Le Riche. Globalized Nedler-Mead methods for engineering optimization // ELSIVIER Science direct. 2004. vol. 1. Р. 2-10.
  12. Prayoth Kumsawat A Genetic Algorithm Optimization Technique for Multiwavelet - Based Digital Audio Watermarking // EURASIP Journal on Advances in Signal Processing. 2010. vol. 1. Р. 15-25.
  13. Colin R. Reeves Genetic Algorithms for the Operations Researcher // INFORMS Journal on Computing. 1997. vol. 9, no. 3. Р. 231-250.
  14. Jeffrey J. The application of genetic algorithm in GIS network analysis // International Archives of Photogrammetry and Remote Sensing. 2000. vol. 33, part B 4. Р. 1184-1191.
  15. Raymond C., Ooi Koon B. A Comparison between Genetic Algorithms and Evolutionary Programming based on Cutting Stock Problem // Engineering Letters. 2007. Р. 115.
  16. Tweedle V., Smith R. A mathematical model of Bieber Fever. Transworld Research Network, 2012, Vol. 37/661, No. 2, P. 157-177.
  17. Lingefard T. Faces of mathematical modeling. ZDM, 2006, Vol. 38, No. 2, P. 96-112.
  18. Sovetov V., Yakovlev S. Modelirovanie sistem [Simulation systems]. Moscow, Vysshaya shkola Publ., 2001, P. 343.
  19. Arnold V. Teoriya katastrof [Catastrophe Theory]. Moscow, Nauka Publ., 1990, 128 p.
  20. Medvedev A. V. [Some notes on H-models for non-inertis systems with a delay] Vestnik SibGAU. 2014, No. 5 (54), P. 24-34 (In Russ.).
  21. Medvedev A. V. [Analysis of the data in the problem identification]. Komp’yuternyy analiz dannykh modelirovaniya [Computer analysis of simulation data]. 1995. Vol. 2, P. 201-206.
  22. Medvedev A. V. [H-model for non-inertia systems with delay]. Vestnik SibGAU. 2012, No. 5 (54), P. 84-89 (In Russ.).
  23. Zipkin Ya. Adaptatsiya i obuchenie v avtomaticheskikh sistemakh [Adaptation and learning in automatic systems], Moscow, Nauka Publ., 1968, 400 p.
  24. Feldbaum A. Osnovy teorii optimal'nykh avtomaticheskikh sistem [Fundamentals of the theory of optimal automatic systems]. Moscow, Fizmatgiz Publ., 1963, 552 p.
  25. Ruban A. I. Metody analiza dannykh [Methods of Data Analysis]. Krasnoyarsk, CPI KSTU Publ., 2004, 319 p.
  26. Marco A., Rodolphe Le Riche. Globalized Nedler-Mead methods for engineering optimization. ELSIVIER Science direct, 2004, Vol. 1, P. 2-10.
  27. Prayoth Kumsawat. A Genetic Algorithm Optimization Technique for Multiwavelet - Based Digital Audio Watermarking. EURASIP Journal on Advances in Signal Processing, 2010, Vol. 1, P. 15-25.
  28. Colin R. Reeves. Genetic Algorithms for the Operations Researcher. INFORMS Journal on Computing, 1997, Vol. 9, No. 3, P. 231-250.
  29. Jeffrey J. The application of genetic algorithm in GIS network analysis. International Archives of Photogrammetry and Remote Sensing, 2000, Vol. 33, Part B4, P. 1184-1191.
  30. Raymond C., Ooi Koon B. A Comparison between Genetic Algorithms and Evolutionary Programming based on Cutting Stock Problem. Engineering Letters 2007, 115 p.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML

© Михов Е.Д., 2015

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Данный сайт использует cookie-файлы

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

О куки-файлах