4.3. Комбинаторный алгоритм МГУА.

МГУА имеет особенности, позволяющие улучшить прогнозирование моделей сложных объектов и придать им объективный характер:

Самоорганизация физической модели для познания объекта исследований и нескольких нефизических – для долгосрочного.
Выбор класса уравнений и вида опорной функции получается ЭВМ, которая перебирает многие варианты по критериям выбора модели.
Выбор множества выходных и входных переменных, а также “ведущей” переменной поручается ЭВМ.
Плохо прогнозирующиеся переменные прогнозируются во вторую очередь
Возможность прогнозирования при неполном информационном базисе.
Самоорганизация физической и прогнозирующих моделей возможна при сильно зашумленных исходных данных.

В комбинаторных алгоритмах выполняется перебор всевозможных перебор всевозможных моделей из заданного базиса с выбором лучшей из этих моделей по заданному критерию селекции.

При переборе сложность частичных моделей, то есть число аргументов постепенно наращивается от 1 до максимального числа n (числа аргументов базисного набора функций).

Таким образом, общая схема комбинаторного алгоритма включает следующие операции:

По МНК определяются коэффициенты всех частных моделей при сложности s=1..n .
Для каждой из них вычисляется значение внешнего индивидуального или комбинированного критерия сложности селекции.
Единственная модель оптимальной сложности выбирается по минимальному значению критерия.

Опорным набором аргументов являются n членов некоторого полинома заданной максимальной степени от заданного числа переменных:

Иногда в состав аргументов требуется ввести обратные величины

их степени или другие нелинейные функции. В любом случае полный полином является линейным по коэффициентам, для определения которых применяются МНК. При этом степени и ковариации исходных переменных рассматриваются как “переобозначенные” линейные аргументы.

Сначала определяются все модели при s=1, то есть из одного аргумента (всего ):

Далее рассматриваются всевозможные модели при s=2 (всего

Таким образом, общее число

всевозможных частных моделей, построенных из n аргументов полного полинома методом полного комбинаторного алгоритма вычисляются:

При большом n приходится применять целесообразное усечение перебора. Максимальная сложность задается числом точек исходных данных, длинной обучающей последовательности:

Структура комбинаторного алгоритма

В структуре каждого из алгоритмов МГУА можно выделить три основных блока:

Преобразование исходных данных в соответствии с выбранной системой опорных функций, в которой ищется модель.
Генерирование полного или неполного множества усложняющихся частных моделей в выбранном базисе.
Вычисление значений некоторого критерия селекции, имеющего свойства внешнего дополнения и последовательного отбора частных моделей, лучших по этому критерию.

Блок формирования базиса

Если заданы измерения некоторых входных переменных моделируемого объекта и максимальная степень полинома, то число слагаемых n в полном полиноме степени от v переменных определяется однозначно:

Сам полный полином записывается в следующем общем виде:

, где каждый обобщенный “линейный” аргумент

является нелинейной функцией исходных переменных

Итак,

– базисный набор опорных функций.

Описанная процедура позволяет сформировать матрицу измерений обобщенных аргументов , где N – число точек измерений.

Эти точки разделены на три последовательности: обучающую (A) длиной , проверочную (B) длиной и экзаменационную (C) длиной . Причем

Блок перебора частных моделей

Основные операции:

формирование структуры очередной частной модели;
формирование соответствующей нормальной системы уравнений;
решение полученной системы (оценка коэффициентов модели).

Формирование структур частной модели формализуется с помощью структурного вектора : если элемент этого вектора принимает значение 1, то соответствующий i-й аргумент включается в частную модель, если 0 – не включается.

Используется схема изменения двоичного вектора по принципу работы двоичного счетчика, в последний разряд которого добавляется единица.

Для формирования нормальной системы уравнений, соответствующей очередному структурному вектору, можно поступить формально: из столбцов полной матрицы х, указанных единичными элементами d, составляется частная матрица , а затем вычисляются элементы , .

B комбинаторном алгоритме достаточно один раз вычислить матрицы полной нормальной системы, которая содержит элементы всех частных нормальных систем:

Для получения любой частной нормальной системы достаточно взять элементы матрицы , находящиеся на пересечении строк и столбцов, указанных единицами вектора d, а также соответствующие элементы вектора .

Для решения каждой нормальной системы , то есть для вычисления оценок коэффициентов частной модели, можно применять любые процедуры решения систем алгебраических уравнений.

Блок отбора по критериям

Рассмотрим вопрос о вычислении значений критериев селекции для произвольной частной модели с вектором коэффициентов a, оценки которого уже получены на A и B в отдельности.

Критерий несмещенности:

где – оценка выходной величины, полученные по коэффициентам ; – сумма матриц и .

Критерий регулярности:

где – исходный вектор измерений выходной величины на последовательности B; – оценки входа на B по модели .

На последовательности C

где – оценки коэффициентов частных моделей, отобранных по и после пересчета на объединенной последовательности .

Селекция моделей обычно выполняется в процессе перебора. Для этого запоминаются значения критерия для заданной свободы выбора f первых моделей, а затем величина каждой последующей модели сравнивается с худшим из f значений.

В алгоритмах самоорганизации применяется отбор по двум и более критериям.

Обычно несколько критериев применяются последовательно: отбирается наименее смещенных моделей, затем по самых точных на проверочной последовательности.

Используется также информация последовательности C по критерию регулярности.

Так же в алгоритмах МГУА обычно выполняется еще один этап вычислений – оценка качества отобранных лучших моделей.

Ошибку МНК , определяемую после пересчета коэффициентов на W, также можно выразить через нормальные матрицы

где нужно

Селекция продолжается до тех пор, пока не достигается минимум критерия смещения. Затем отбирается наиболее регулярная модель.