OPTIMIZATION OF COEFFICIENT OF BLURRING OF THE KERNEL IN NONPARAMETRIC MODELLING
- Authors: Mihov E.D.1
-
Affiliations:
- Siberian Federal University
- Issue: Vol 16, No 2 (2015)
- Pages: 338-342
- Section: Articles
- URL: https://journals.eco-vector.com/2712-8970/article/view/504702
- ID: 504702
Cite item
Full Text
Abstract
A modeling of discrete-continuous processes in space “input-output” variables. Modeling of these processes can be carried out using various parametric and nonparametric. This article deals with modeling using nonparametric methods. This decision was taken in view of the fact that non-parametric theory, in contrast to the parametric theory assumes that the only known qualitative characteristics of the process. The modeling objects often have an unknown and complex structure. Given these facts, the use and development of nonparametric theory continues to be an urgent task of our time. Our results can be used to equipment spacecraft modeling and them managing. When building a model of the object by means of nuclear grade, an important parameter - the coefficient blur kernel. The algorithms optimize the ratio blur kernel, namely the method of enumeration, the flexible polyhedron method and genetic algorithm. As an optimization criterion was selected standard error of the test process models, calculated using the sliding test. It is worth also say that the results will be presented in the optimization parameter vector blur kernel (for each input action), and in the optimization of the overall coefficient on the interaction of all the input. As it turns out, the accuracy of the model to optimize the parameters of a blur kernel is slightly inferior to the accuracy of the model with optimized parameter vector blur kernel, and the calculation of the coefficient of blur kernel runs much faster and, as a consequence, the model will be built. These results can be extremely useful in modeling and managing the rapid flow of information and the changing environment.
Full Text
Введение. Идентификация многих стохастических объектов часто сводится к идентификации статических систем. Наиболее общая схема исследуемого дискретно-непрерывного процесса может быть представлена на нижеследующем рисунке[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 Как мы можем видеть из таблицы, оптимизация вектора коэффициента размытости занимает во много раз больше времени, чем оптимизация скалярного значения, при этом модель практически не становится лучше. Также стоит отметить, что оптимизация при помощи метода деформируемых многогранников действует гораздо быстрее, чем оптимизация при помощи стандартного перебора или генетического алгоритма. Заключение. В статье приведены такие методы оптимизации, как метод деформируемых многогранников, генетический алгоритм и простой перебор возможных значений, и показаны результаты работы данных методов. Также была доказана возможность использования методов локальной оптимизации для нахождения наилучшего коэффициента размытости ядра. Было проведено сравнение между оптимизацией при помощи метода деформируемых многогранников, генетического алгоритма и оптимизацией при помощи стандартного перебора, где было доказано превосходство первого в задаче оптимизации коэффициента размытости ядра. Доказано, что оптимизация вектора коэффициентов размытости является нецелесообразной вследствие больших затрат времени и малого изменения в точности модели исследуемого процесса.×
About the authors
E. D. Mihov
Siberian Federal University
Email: edmihov@mail.ru
79, Svobodny Av., Krasnoyarsk, 660041, Russian Federation
References
- Tweedle V. Smith R. A mathematical model of Bieber Fever // Transworld Research Network. 2012. vol. 37/661, № 2. Р. 157-177.
- Lingefard T. Faces of mathematical modeling // ZDM. 2006. vol. 38, № 2. Р. 96-112.
- Советов Б. Я, Яковлев С. А. Моделирование систем : учебник для вузов. М. : Высш. шк., 2001. 343 с.
- Арнольд В. Теория катастроф. М. : Наука, 1990. 128 с.
- Медведев А. В. Некоторые замечания к Н-моделям безынерционных процессов с запаздыванием // Вестник СибГАУ. 2014. № 2(54). С. 24-34.
- Медведев А. В. Анализ данных в задаче идентификации // Компьютерный анализ данных моделирования. Т. 2. Минск : БГУ, 1995. С. 201-206.
- Медведев А. В. H-модели для безынерционных систем с запаздыванием // Вестник СибГАУ. 2012. № 5(45). С. 84-89.
- Цыпкин Я. З. Адаптация и обучение в автоматических системах. M. : Наука, 1968. 400 с.
- Фельдбаум А. А. Основы теории оптимальных автоматических систем. М. : Физматгиз, 1963. 552 с.
- Рубан А. И. Методы анализа данных : учеб. пособие. 2-е изд., испр. и доп. Красноярск : ИПЦ КГТУ, 2004. 319 с.
- Marco A., Rodolphe Le Riche. Globalized Nedler-Mead methods for engineering optimization // ELSIVIER Science direct. 2004. vol. 1. Р. 2-10.
- 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.
- Colin R. Reeves Genetic Algorithms for the Operations Researcher // INFORMS Journal on Computing. 1997. vol. 9, no. 3. Р. 231-250.
- 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.
- Raymond C., Ooi Koon B. A Comparison between Genetic Algorithms and Evolutionary Programming based on Cutting Stock Problem // Engineering Letters. 2007. Р. 115.
- Tweedle V., Smith R. A mathematical model of Bieber Fever. Transworld Research Network, 2012, Vol. 37/661, No. 2, P. 157-177.
- Lingefard T. Faces of mathematical modeling. ZDM, 2006, Vol. 38, No. 2, P. 96-112.
- Sovetov V., Yakovlev S. Modelirovanie sistem [Simulation systems]. Moscow, Vysshaya shkola Publ., 2001, P. 343.
- Arnold V. Teoriya katastrof [Catastrophe Theory]. Moscow, Nauka Publ., 1990, 128 p.
- 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.).
- 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.
- Medvedev A. V. [H-model for non-inertia systems with delay]. Vestnik SibGAU. 2012, No. 5 (54), P. 84-89 (In Russ.).
- Zipkin Ya. Adaptatsiya i obuchenie v avtomaticheskikh sistemakh [Adaptation and learning in automatic systems], Moscow, Nauka Publ., 1968, 400 p.
- Feldbaum A. Osnovy teorii optimal'nykh avtomaticheskikh sistem [Fundamentals of the theory of optimal automatic systems]. Moscow, Fizmatgiz Publ., 1963, 552 p.
- Ruban A. I. Metody analiza dannykh [Methods of Data Analysis]. Krasnoyarsk, CPI KSTU Publ., 2004, 319 p.
- Marco A., Rodolphe Le Riche. Globalized Nedler-Mead methods for engineering optimization. ELSIVIER Science direct, 2004, Vol. 1, P. 2-10.
- 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.
- Colin R. Reeves. Genetic Algorithms for the Operations Researcher. INFORMS Journal on Computing, 1997, Vol. 9, No. 3, P. 231-250.
- 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.
- Raymond C., Ooi Koon B. A Comparison between Genetic Algorithms and Evolutionary Programming based on Cutting Stock Problem. Engineering Letters 2007, 115 p.
Supplementary files
![](/img/style/loading.gif)