Обобщенный релаксационный алгоритм МГУА
В работе осуществлён анализ архитектуры Многорядного Упрощенного Алгоритма (МУА) МГУА, выявлены его недостатки и преимущества. Предложен обобщённый релаксационный итерационный алгоритм, не содержащий недостатков МУА и имеющий принципиально новую архитектуру для итерационных алгоритмов МГУА, строящих...
Збережено в:
| Опубліковано в: : | Індуктивне моделювання складних систем |
|---|---|
| Дата: | 2011 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2011
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45937 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Обобщенный релаксационный алгоритм МГУА / А.В. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2011. — Вип. 3. — С. 121-134. — Бібліогр.: 5 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860000651507924992 |
|---|---|
| author | Павлов, А.В. |
| author_facet | Павлов, А.В. |
| citation_txt | Обобщенный релаксационный алгоритм МГУА / А.В. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2011. — Вип. 3. — С. 121-134. — Бібліогр.: 5 назв. — рос. |
| collection | DSpace DC |
| container_title | Індуктивне моделювання складних систем |
| description | В работе осуществлён анализ архитектуры Многорядного Упрощенного Алгоритма (МУА) МГУА, выявлены его недостатки и преимущества. Предложен обобщённый релаксационный итерационный алгоритм, не содержащий недостатков МУА и имеющий принципиально новую архитектуру для итерационных алгоритмов МГУА, строящих модели, линейные по параметрам.
The paper gives an architecture analysis of Multilayered Simplified Algorithm (MSA) of GMDH, its advantages and disadvantages have been revealed. Generalized relaxational iterative algorithm of GMDH free from the MSA disadvantages has been introduced having an essentially new architecture for iterative GMDH algorithms that build models linear in coefficients.
|
| first_indexed | 2025-12-07T16:35:34Z |
| format | Article |
| fulltext |
Обобщенный релаксационный алгоритм МГУА
УДК 681.513.8
ОБОБЩЁННЫЙ РЕЛАКСАЦИОННЫЙ АЛГОРИТМ МГУА
А.В. Павлов
Международный научно-учебный центр ЮНЕСКО информационных технологий и систем
НАНУ и МОНУ, 03680, Киев, пр. Глушкова 40
Me_ovechka@bigmir.net
Abstract. The paper gives an architecture analysis of Multilayered Simplified Algorithm (MSA) of
GMDH, its advantages and disadvantages have been revealed. Generalized relaxational iterative
algorithm of GMDH free from the MSA disadvantages has been introduced having an essentially
new architecture for iterative GMDH algorithms that build models linear in coefficients.
Keywords: Group Method of Data Handling (GMDH), multilayered simplified algorithm,
generalized relaxational iterative algorithm, algorithm architecture.
В работе осуществлён анализ архитектуры Многорядного Упрощенного Алгоритма (МУА)
МГУА, выявлены его недостатки и преимущества. Предложен обобщённый релаксационный
итерационный алгоритм, не содержащий недостатков МУА и имеющий принципиально
новую архитектуру для итерационных алгоритмов МГУА, строящих модели, линейные по
параметрам.
Ключевые слова: Метод Группового Учета Аргументов (МГУА), многорядный упрощённый
алгоритм, обобщённый релаксационный итерационный алгоритм МГУА, архитектура
алгоритма.
Вступление
В работе выполняется анализ архитектуры многорядного упрощённого
алгоритма (МУА) МГУА [1] и предлагается обобщённый релаксационный
итерационный алгоритм МГУА, свободный от недостатков МУА МГУА.
1. Постановка задачи
Пусть имеем выборку данных, заданную матрицей , dim X = n)( yXW M= W
× m, dim y = nW ×1, mix Wn
i ,1, =ℜ∈ , где nW – количество наблюдений (точек), m
– число аргументов (вектор-столбцов матрицы Х). Предполагается, что выход-
ная переменная y( является некоторой функцией ),( MMXf ((
(((
Θ от истинных ар-
гументов XX M ⊆(
(
и неизвестного истинного вектора параметров M
(
(
Θ ,
MnX WM
((
( ×=dim , 1dim ×=Θ MM
((
( . Множество аргументов матрицы Х выбира-
ется из условий конкретной задачи, но, кроме истинных аргументов, может со-
держать и фиктивные (лишние). В выходной переменной y( присутствует адди-
тивный шум ξ, который является случайной величиной, распределённой по
нормальному закону с нулевым математическим ожиданием и неизвестной ко-
нечной дисперсией:
ξξ +Θ=+= ),( MMXfyy ((
(((( .
По данным наблюдений необходимо построить функцию
Індуктивне моделювання складних систем, випуск 3, 2011 121
mailto:Me_ovechka@bigmir.net
Павлов А.В.
),( ****
** MMXfy Θ=
)) , (1)
при которой целевая функция (критерий) принимает минимальное значение
),( ** yyCR ) . Заданному критерию соответствует тройка:
)),(,(minarg),(minarg},,{
,,,,
***
** MM
XXfXXf
MM
XfyCRyyCRXf
M
MM
M
MM
Θ==Θ
ℜ∈Θ⊆Φ∈ℜ∈Θ⊆Φ∈
)))
)) ,
где Φ – множество функций заданного класса, генерируемых соответствующим
алгоритмом МГУА (примерами классов являются тригонометрические, поли-
номиальные и другие функции, линейные или нелинейные разностные уравне-
ния и пр.); ХМ – некоторая подматрица матрицы Х , dim XМ = nW × M, M ≤ m; MΘ
)
– вектор оценок параметров конкретной функции f, dim ΘM = M×1; – М-
мерное пространство действительных значений вектора параметров Θ
Mℜ
M.
В данной постановке выделим две задачи:
1) задачу дискретной оптимизации множества аргументов матрицы X,
преобразованных в заданном классе функций
)),(,(minarg),(minarg},,{
,,
***
** MM
XXfXXf
MM XfyCRyyCRXf
MM
Θ==Θ
⊆Φ∈⊆Φ∈
)))
; (2)
2) задачу оптимизации непрерывных значений параметров ΘM функции f,
зависящей от множества аргументов ХМ
)),(,(minarg),(minarg MMM XfyQRyyQR
MM
Θ==Θ
ℜ∈Θℜ∈Θ
))
. (3)
Структурой модели будем называть функцию ),( MMXf Θ , заданную с
точностью до значений параметров ΘМ. Полностью заданную функцию
),( MMXf Θ
)
будем называть некоторым решением или моделью, а функцию
),( ** MMXf Θ*** )
– оптимальным решением задачи (оптимальной моделью). В (3)
QR является критерием, в соответствии с которым определяются оптимальные
значения вектора параметров MΘ
)
для некоторой структуры модели; в (2) CR –
критерий для определения оптимальной структуры модели и, в конечном итоге,
оптимальной модели. Под построением модели понимается генерация её струк-
туры и оценивание параметров, соответствующих этой структуре.
МУА МГУА в общем случае строит как статические, так и динамические
степенные аддитивно-мультипликативные модели, включая на каждой итера-
ции один аддитивный одночлен. В результате структура модели может иметь,
например, вид:
2
13
341
3
222
2
1
10
1
xx
xxx
x
xy θθθθ +++= .
Мультипликативным одночленом будем называть одночлен, состоящий
из произведений соответствующих элементов вектор-столбцов входной матри-
цы. Если в [2] анализ МУА МГУА был сконцентрирован на алгоритмах оценки
122 Індуктивне моделювання складних систем, випуск 3, 2011
Обобщенный релаксационный алгоритм МГУА
коэффициентов Θ и расчете критериев селекции CR, то в данной работе содер-
жится подробный анализ процесса работы алгоритма в целом.
2. Анализ МУА МГУА
В архитектуре МУА МГУА можно выделить три блока (рис. 1):
− блок формирования обобщённых переменных, в котором имеется воз-
можность увеличить размерность исходного пространства;
− блок подготовительных вычислений, результаты которых позже ис-
пользуются при оценивании параметров Θ и расчёта критериев селекции моде-
ли;
− блок итераций, где непосредственно строится модель.
На каждой итерации выполняется Алгоритм Поиска Одночлена (АПО),
который нужно включить в модель. АПО состоит из трёх этапов:
1. Для построения F1 лучших моделей, линейных по входным перемен-
ным, сначала строятся m моделей вида:
irA
r
irAirA xy ,1,
1
,1,,1,
~~
+
+
++ = ω)
)
, i = 1,…, m, r = 0, (4)
irA
r
irArAirAirA xyy ,1,
1
,1,,,1,,1,
~~~
+
+
+++ += ωω ))))
, i = 1,…, m, r > 0, (5)
где irAy ,1,
~
+
)
– оценка решения для центрированного на обучающей выборке
А выхода y~, полученное на (r+1)-й итерации для i-й модели; irAx ,1,
~
+ – аргумент
(центрированный на выборке А столбец матрицы Х), добавляемый в модель на
(r+1)-й итерации; rAy ,
~) - оценка лучшего решения предыдущей итерации; 1
,1,
+
+
r
irAω) ,
irA ,1, +ω) – оценки коэффициентов, определяемые по методу наименьших квадра-
тов. Отбираются F1 лучших моделей, где F1 – свобода выбора, F1 ≤ m.
2. Если строятся аддитивно-мультипликативные модели, то для каждой i-
й модели (4), (5), i = 1, …, F1 осуществляется Процедура Конструирования
Мультипликативных Одночленов (ПКМО).
3. Выбор по критерию CR одной лучшей (F=1) среди F1 построенных мо-
делей, где F – свобода выбора моделей на каждой итерации.
После окончания каждой итерации проверяется одно из условий останова
алгоритма:
− CRr+1 > CRr или
− r+1 = R,
где R – наперед заданное количество итераций алгоритма. Если условие
останова не выполняется, выбранная модель передаётся на следующую итера-
цию.
Індуктивне моделювання складних систем, випуск 3, 2011 123
Павлов А.В.
Рис. 1. Архитектура МУА МГУА и процесс его работы.Процедура конструиро-
вания мультипликативных одночленов.
Входным параметром ПКМО является multNum – максимальное
количество мультипликаций (умножений), которые допускаются для
формирования одночлена zA,r+1,i, при исходном его значении, совпадающем с
124 Індуктивне моделювання складних систем, випуск 3, 2011
Обобщенный релаксационный алгоритм МГУА
xA,r+1,i. Пусть it текущее количество мультипликаций; CRit – значение критерия
CR для лучшей модели итерации it-й мультипликации. Блок-схема ПКМО
представлена на рис. 2.
Рис. 2. Блок-схема ПКМО.
Далее при условии, что it < multNum осуществляется построение моделей вида:
rAirAirA
r
irAirA yzy ,,1,,1,
1
,1,,1,
~~~ )
++
+
++ += ωω , i = 1, …, m,
где элементы вектора являются центрированными на выборке A значе-
ниями вектора-столбца z
irAz ,1,
~
+
A,r+1,i. В случае it > 0 вектор zA,r+1,i обозначен как zA,r+1,i,it,
при it = 1 элементы вектора рассчитываются по формуле
zA,r+1,i,it,j = xA,r+1,i,j ⋅ xA,r+1,k,j, j = 1, …, nA; i, k = 1, …, m,
а при it > 1 по формуле
zA,r+1,i,it+1,j = zA,r+1,i,it,j ⋅ xA,r+1,k,j, j = 1, …, nA; i, k = 1, …, m.
Індуктивне моделювання складних систем, випуск 3, 2011 125
Павлов А.В.
Работу АПО удобно представить в виде дерева, изображенного на рис. 3.
Пусть матрица аргументов Х = (х1, х2, х3); свобода выбора лучшего мультипли-
кативного одночлена F1 = 3; r=1 – первая итерация; multNum = 2.
Рисунок 3. Иллюстрация работы АПО МУА в виде дерева:
«*» – знак умножения; – рассчитанный одночлен; – нерассчитанный
одночлен; – лучший одночлен на итерации мультипликаций; – одно-
член, который необходимо ввести в модель на (r+1)-й итерации.
На рис. 3 виден существенный недостаток реализации АПО: при построе-
нии дерева, расчет некоторых моделей производится дважды. Следует отме-
тить, что на текущей итерации мультипликации выбор F1 лучших моделей
осуществляется путём селекции одной лучшей модели-потомка для каждой мо-
дели-родителя, а не выбором F1 лучших среди всех моделей-потомков. Этот
факт объясняет целесообразность генерации всех возможных (m штук) моде-
лей-потомков для каждой модели-родителя.
Также очевидно, что АПО реализует направленный перебор, в который
не входят мультипликативные одночлены, присутствующие в полном переборе:
, , т.е. в результате имеем усеченное дерево структур. Хотя при условии
multNum ≤ 1, АПО всегда реализует полный перебор.
321 xxx 3
2x
Таким образом, при multNum > 1 АПО не гарантирует нахождение гло-
бального оптимума критерия CR на текущей итерации, что в свою очередь
уменьшает вероятность нахождения глобального оптимума критерия в целом.
Поэтому отсутствие полного перебора в АПО можно отнести к недостаткам ар-
хитектуры МУА МГУА.
Учитывая анализ МУА МГУА [2] и сказанное выше, данный алгоритм
имеет следующие недостатки:
1. Архитектура алгоритма не реализует принцип неокончательных реше-
ний (F = 1), что при условии неполного перебора структур является нежела-
тельным, т.к. не гарантирует нахождение истинной структуры модели при от-
сутствии шума в данных.
2. АПО не гарантирует нахождение глобального оптимума критерия CR
на множестве перебираемых структур.
3. Алгоритмы оценки параметров и расчёта критериев селекции модели
зависят от количества наблюдений.
4. АПО выполняет больше операций, чем необходимо при построении
моделей с мультипликативными одночленами, поскольку имеются повторные
генерации одночленов.
126 Індуктивне моделювання складних систем, випуск 3, 2011
Обобщенный релаксационный алгоритм МГУА
К преимуществам МУА МГУА относится экономия оперативной памяти,
поскольку в оперативной памяти сохраняется только матрица H, содержащая
исходные и преобразованные входные переменные. Память под мультиплика-
тивные одночлены выделяется и освобождается динамически при их конструи-
ровании.
3. Обобщённый релаксационный итерационный алгоритм МГУА
В основе Обобщённого Релаксационного Итерационного Алгоритма
(ОРИА) МГУА лежат некоторые идеи МУА МГУА, а именно: добавление
только одного одночлена в модель на каждой итерации; центрирование аргу-
ментов с целью оценки только двух коэффициентов; алгоритм (видоизменен-
ный) направленного перебора при поиске лучшего мультипликативного аргу-
мента.
Мультипликативным аргументом будем называть аргумент, состоящий из
произведений соответствующих элементов вектор-столбцов входной матрицы.
В результате анализа известных алгоритмов МГУА в [3] выделены сле-
дующие их составляющие:
− класс моделей;
− генератор структур моделей;
− метод оценивания параметров;
− алгоритм расчета критериев селекции.
ОРИА включает в себя три алгоритма, описанных в [4], для оценивания
параметров и расчёта критериев селекции:
− алгоритм с нерекуррентными вычислениями;
− два варианта алгоритмов с рекуррентными вычислениями.
Каждый из этих алгоритмов устраняет третий недостаток МУА МГУА:
зависимость от числа точек.
Кроме того, предлагаются два генератора структур:
− с направленным перебором, в основе которого лежит идея генератора
МУА МГУА, однако его реализация не имеет выявленного четвёртого недос-
татка;
− с полным перебором мультипликативных аргументов, устраняющий
второй недостаток МУА МГУА.
Таким образом, в ОРИА можно выделить три компонента:
1) класс моделей (алгоритм реализует следующие модели многих пере-
менных: степенные, аддитивно-мультипликативные и их разностные аналоги);
2) генератор структур (с полным и направленным перебором);
3) алгоритмы оценки параметров и расчёта критерия селекции (алгоритм
с нерекуррентными вычислениями; два варианта алгоритмов с рекуррентными
вычислениями).
Каждая из трёх компонент ОРИА является независимой от остальных, т.е.
можно конструировать различные РИА, взяв по одному из вариантов каждой
компоненты. Отметим, что для компоненты «класс моделей» возможна комби-
Індуктивне моделювання складних систем, випуск 3, 2011 127
Павлов А.В.
нация вариантов, поскольку, например, можно построить разностно-
полиномиальную модель.
На рис. 4 показаны составляющие процесса построения ОРИА-модели.
Рис. 4. Составляющие ОРИА и процесс построения модели.
В архитектуре ОРИА компонент «класс моделей» не специфицирует кон-
кретный релаксационный итерационный алгоритм, поскольку фактически дан-
ный компонент является составляющей блока преобразования исходных дан-
ных. Имея матрицу Х, и выполнив соответствующие преобразования её аргу-
ментов, можно сформировать указанный класс моделей. При этом созданная
матрица H рассматривается в качестве исходной в любом возможном РИА
МГУА.
Предложенную архитектуру ОРИА МГУА можно обобщить на любой
алгоритм МГУА, строящий модели, линейные по параметрам Θ. Все
возможные варианты алгоритмов РИА МГУА, объединенные в ОРИА МГУА,
представлены на рис. 5.
128 Індуктивне моделювання складних систем, випуск 3, 2011
Обобщенный релаксационный алгоритм МГУА
Рисунок 5. Схема получения возможных РИА в ОРИА МГУА.
Детальная схема роботы ОРИА показана на рис. 6. Выделим три стадии:
1. Стадию преобразования матрицы Х при формировании класса моделей.
2. Подготовительную стадию, на которой выполняются вспомогательные
вычисления, использующиеся на стадии построения моделей.
3. Стадию итераций, на которой непосредственно осуществляется по-
строение моделей.
В данной архитектуре в алгоритм вводиться свобода выбора F > 1 лучших
моделей, которые переходят на следующую итерацию, что устраняет первый
недостаток МУА МГУА.
Первая стадия ОРИА состоит из последовательности двух этапов:
1) осуществление унарных преобразований аргументов матрицы Х;
2) формирование мультипликативных аргументов.
Основой для осуществления унарных преобразований является множест-
во функциональных трансформаций Ψ, которое в текущей версии алгоритма
состоит из двух элементов:
Ψ = {ϕ1(x)= 1/х, ϕ2(x,l) = lag(x,l)},
где lag(x,l) = x-l – функция взятия l-го запаздывания (лага) от переменной х. В
дальнейшем Ψ может быть расширена, например, функциями ln(x), exp(x), sin(x)
и т. д. При осуществлении преобразований имеется возможность выполнять су-
перпозицию функций, например, ϕ1(ϕ2(x1,5))= 1 / x1,-5.
После применения унарных преобразований можно осуществить k-арное
преобразование (мультипликацию) над аргументами исходной матрицы с
заданной максимальной степенью.
Індуктивне моделювання складних систем, випуск 3, 2011 129
Павлов А.В.
Рис. 6. Архитектура ОРИА и процесс его работы.
130 Індуктивне моделювання складних систем, випуск 3, 2011
Обобщенный релаксационный алгоритм МГУА
Опишем данную процедуру. Без ограничения общности, пусть на вход проце-
дуры формирования мультипликативных аргументов поступает исходная мат-
рица X. Необходимо сформировать матрицу Z, состоящую из произведений со-
ответствующих элементов вектор-столбцов матрицы Х без повторов получен-
ных столбцов. Пусть dim X = nA × m и задана максимальная степень полинома
pow (pow > 1), которую нужно получить для элементов вектор-столбцов матри-
цы Х. Тогда элементы вектор-столбца z матрицы Z рассчитываются по формуле:
zj = ∏ , j =1, ..., n
=
K
k
kjv
1
A,
где ∈ {xkv 1, …, xm}, k = 1, …, K, K = 2, 3, … pow.
Расширенная матрица H = (X MZ), dim H = nA × . 1−+
pow
powmC
На стадии подготовительных вычислений происходит центрирование
вектор-столбцов матрицы W = (HMy) на выборке А, а также вычисление матриц
системы нормальных уравнений:
rA
T
rA HH ,,
~~ , rB
T
rB HH ,,
~~ , rA
T
rA yH ,,
~~ , rB
T
rB yH ,,
~~ ,
элементы которых используются при построении моделей на последней стадии
ОРИА МГУА.
Условие останова ОРИА – аналогичное условию останова МУА МГУА,
при этом CRr и CRr+1 обозначают значения критериев селекции для самых луч-
ших из F > 1 лучших моделей на r-й и (r+1)-й итерации соответственно.
Опишем новую реализацию генератора направленного перебора.
4. Алгоритм поиска мультипликативного одночлена ОРИА МГУА
В результате анализа АПО МУА в основе реализации АПО ОРИА пред-
лагается использование префиксного дерева [5]. Префиксное дерево – это абст-
рактная структура данных, которая позволяет сохранять и осуществлять поиск
ассоциативного массива, ключами которого являются строчки. Для построения
дерева задаётся алфавит символов ℵ, из которых составляются слова (строчки).
Значение ключа получается путём просмотра всех родительских узлов, каждый
из которых сохраняет один или несколько символов алфавита, и конкатенации
их символов в порядке просмотра.
В нашем случае алфавит символов ℵ – это индексы вектор-столбцов мат-
рицы X: Множеству индексов ℵ = {‘0’, ‘1’, …, ‘m – 1’} соответствует множест-
во {‘x1’, ‘х2’, …, ‘xm’}. Словами этого алфавита являются: ‘012’, которому соот-
ветствует ‘x1x2x3’; ‘000’ – ‘x1x1x1’ и т. д. Каждому слову ставится в соответствие
вектор-столбец из произведений элементов закодированных вектор-столбцов
матрицы Х, например, слову ‘000’ – вектор-столбец . 3
1x
Блок-схема алгоритма представлена на рис. 7.
Індуктивне моделювання складних систем, випуск 3, 2011 131
Павлов А.В.
Рис. 7. Блок-схема алгоритма построения префиксного дерева.
Алгоритм построения префиксного дерева реализуется с помощью
следующей процедуры:
AddChildren(node, beginPosition, endPosition, maxMultiplicationsNumber),
где: node – узел, в который добавляются потомки; beginPosition – указатель на
начальный элемент массива индексов; endPosition – указатель на элемент, сле-
дующий за последним элементом массива индексов, например, null;
maxMultiplicationsNumber – максимальное количество мультипликаций.
Перед запуском процедуры необходимо инициализировать указатели
beginPosition и endPosition, используя исходный массив индексов символов
indicesArray. Данный алгоритм строит полное дерево структур, представленное
на рис. 8.
132 Індуктивне моделювання складних систем, випуск 3, 2011
Обобщенный релаксационный алгоритм МГУА
Рис. 8. Результат работы алгоритма построения префиксного дерева.
Изображенное дерево является минимальным (не имеет повторов), по-
этому при использовании алгоритма обхода префиксного дерева быстродейст-
вие ОРИА по сравнению с МУА увеличивается (см. рис. 8).
Алгоритм обхода префиксного дерева.
1. Строятся модели для узлов первого уровня и из них отбираются F1
лучших по минимуму критерия CR. Отобранные модели добавляются в массив
bestModelsArray.
2. Для каждого выбранного узла первого уровня выполняется процедура
CalculateNode(parentNode, parentNodeFitnessCriterion), где parentNode – узел, для
потомков которого будут строиться модели; parentNodeFitnessCriterion – значе-
ние критерия этого узла. В нашем случае parentNode является текущим выбран-
ным узлом первого уровня.
Процедура CalculateNode.
2.1 Строятся модели для каждого из узлов-детей родительского узла
parentNode. Определяются среди них F2 лучших моделей и добавляются в мас-
сив bestModelsArray.
2.2 Для каждого из F2 выбранных узлов рекурсивно выполняется проце-
дура CalculateNode при выполнении следующих условий:
а) значение критерия CR модели, построенной с включением нового узла
меньше parentNodeFitnessCriterion;
б) выбранный узел имеет потомков.
2.3 Среди всех моделей массива bestModelsArray выбирается одна лучшая.
В отличие от реализации АПО МУА, данная реализация является более
гибкой, поскольку позволяет варьировать количество лучших моделей F2, кото-
рые переходят на следующую it-у итерацию мультипликаций при it > 1. При F2
= 1 получаем АПО МУА.
Для создания матрицы Z на первой стадии ОРИА удобно воспользоваться
процедурой построения префиксного дерева. При добавлении узла-потомка
рассчитывается вектор zi,it+1 , соответствующий этому узлу по формуле:
⎩
⎨
⎧
=⋅=
>⋅=+
1,
1,
,,1,,
,,,1,,
itxxz
itxzz
kjijij
kjitijitij , j = 1, …, nA, k, i ∈{1, …, m},
Індуктивне моделювання складних систем, випуск 3, 2011 133
Павлов А.В.
где it – номер итерации мультипликаций; xi – узел верхнего уровня дере-
ва; zi,it – вектор родителя.
Описанный подход имеет следующие преимущества:
1. Строится префиксное дерево, которое в дальнейшем используется в
АПО.
2. Формируется матрица H.
3. Процедура имеет минимальное количество операций умножения.
5. Заключение
В работе осуществлён анализ архитектуры МУА МГУА, выявлены её не-
достатки и преимущества. С целью устранения недостатков предложен обоб-
щённый релаксационный итерационный алгоритм МГУА, основными преиму-
ществами которого являются:
− независимость от числа точек в процессе поиска структуры модели;
− архитектура, реализующая принцип неокончательных решений (F >1),
способствующая нахождению глобального оптимума критерия CR при исполь-
зовании генератора структур с направленным перебором;
− новая реализация алгоритма поиска лучшего мультипликативного одно-
члена, позволяющая ускорить работу МУА МГУА;
− генератор структур с полным перебором находит оптимум критерия CR
на текущей итерации алгоритма. Этот алгоритм назовём релаксационный ите-
рационный алгоритм с полным деревом структур (РИА ПДС).
Предложена принципиально новая архитектура для алгоритмов МГУА,
строящих модели, линейные по параметрам.
Литература
1. Шелудько О.И. Самоорганизация математических моделей при решении
некоторых задач надежности и контроля. // Дисс. на соиск. учен. степ. канд.
техн. наук. – Киев. – 1975. –166 с.
2. Павлов А.В. Модифицированный алгоритм с комбинаторной селекцией
и ортогонализацией переменных и его анализ // Індуктивне моделювання скла-
дних систем. Збірник наук. праць. – К.: МННЦІТС, – 2010. – С. 130-139.
3. Степашко В.С. Алгоритмы МГУА как основа автоматизации процесса
моделирования по экспериментальным данным // Автоматика. - 1988. - № 4. -
С.44-55.
4. Павлов А.В., Степашко В.С. Рекуррентные алгоритмы расчёта коэффи-
циентов и критериев селекции в релаксационном алгоритме МГУА // Киберне-
тика и вычислительная техника, – 2011. – вып. 165. – С.72-82.
5. Префиксное_дерево – доступно на сайте http://ru.wikipedia.org/wiki/.
134 Індуктивне моделювання складних систем, випуск 3, 2011
|
| id | nasplib_isofts_kiev_ua-123456789-45937 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0044 |
| language | Russian |
| last_indexed | 2025-12-07T16:35:34Z |
| publishDate | 2011 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Павлов, А.В. 2013-06-20T19:42:12Z 2013-06-20T19:42:12Z 2011 Обобщенный релаксационный алгоритм МГУА / А.В. Павлов // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2011. — Вип. 3. — С. 121-134. — Бібліогр.: 5 назв. — рос. XXXX-0044 https://nasplib.isofts.kiev.ua/handle/123456789/45937 681.513.8 В работе осуществлён анализ архитектуры Многорядного Упрощенного Алгоритма (МУА) МГУА, выявлены его недостатки и преимущества. Предложен обобщённый релаксационный итерационный алгоритм, не содержащий недостатков МУА и имеющий принципиально новую архитектуру для итерационных алгоритмов МГУА, строящих модели, линейные по параметрам. The paper gives an architecture analysis of Multilayered Simplified Algorithm (MSA) of GMDH, its advantages and disadvantages have been revealed. Generalized relaxational iterative algorithm of GMDH free from the MSA disadvantages has been introduced having an essentially new architecture for iterative GMDH algorithms that build models linear in coefficients. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Індуктивне моделювання складних систем Обобщенный релаксационный алгоритм МГУА Article published earlier |
| spellingShingle | Обобщенный релаксационный алгоритм МГУА Павлов, А.В. |
| title | Обобщенный релаксационный алгоритм МГУА |
| title_full | Обобщенный релаксационный алгоритм МГУА |
| title_fullStr | Обобщенный релаксационный алгоритм МГУА |
| title_full_unstemmed | Обобщенный релаксационный алгоритм МГУА |
| title_short | Обобщенный релаксационный алгоритм МГУА |
| title_sort | обобщенный релаксационный алгоритм мгуа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45937 |
| work_keys_str_mv | AT pavlovav obobŝennyirelaksacionnyialgoritmmgua |