РАКЕТНО-КОСМИЧЕСКОЕ ПРИБОРОСТРОЕНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ
2015, том 2, выпуск 4, c. 59–65
РАДИОТЕХНИКА И КОСМИЧЕСКАЯ СВЯЗЬ
УДК 621.37
Проблемы синтезаадаптивных фильтров
методами генетических алгоритмов
с программной реализацией на языке С++ в ОС МСВС
В.М.Ватутин1, С.А.Донцов2, Ю.В.Ефремов, А.Н.Сиренко
1д. т. н., проф., 2к. т. н.
АО «Российские космические системы»
e-mail: vladmvat@mail.ru
Аннотация. При решении задачи излучения устойчивых сигналов, имеющих постоянный спектральный состав,
требуется синтезировать уравнение соответствующей модели сигнала.
Для синтеза предлагается использовать одну из разновидностей генетических алгоритмов — метод группового
учета аргументов (МГУА). Фактически синтезированное этим методом уравнение является оптимальным фильтром
— частным представлением разложения в ряд Лотки–Вольтерра.
Получение результата разложения — результат работы генетического алгоритма.
Проблемами при синтезе оптимального фильтра являются правило разделения данных, правило генерации моделейпретендентов,
метод получения коэффициентов модели и форма квадратичного критерия отбора модели.
В докладе приводятся алгоритмы для решения перечисленных проблем, реализованные на языке С++ и работающие
под управлением ОС МСВС.
Особый интерес представляет модифицированный алгоритм Зейделя для определения коэффициентов оптимальной
модели, способный работать с плохо определенными матрицами, имеющими значение определителя близким
или равным нулю.
Ключевые слова: синтез оптимального фильтра, метод группового учета аргументов, системы линейных уравнений,
генетический алгоритм
Problems of Synthesis of Adaptive Filter Techniques
of Genetic Algorithms to Software in C++ OS MSVS
V.M.Vatutin1,S.A.Dontsov2, Yu.V. Efremov, A. N. Sirenko
1doctor of engineering science, professor, 2candidate of engineering science
Joint Stock Company “Russian Space Systems”
e-mail: vladmvat@mail.ru
Abstract. In solving the problem of radiation stable signals with constant spectral composition is required to synthesize
the appropriate signal model equation.
For the synthesis is proposed to use one of the types of genetic algorithms — a method of group account of arguments
(GMDH). In fact, synthesized by this method the equation is the optimal filter — a private performance of the series
expansion Lotka–Volterra.
The results obtained expansion — the result of a genetic algorithm.
The problems in the synthesis of the optimal filter are usually separate data, usually generate models of applicants, the
method of obtaining the coefficients of the model and the form of the quadratic model selection criterion.
The report provides algorithms for solving these problems, implemented in C++ and runs under OS MSVS.
Of particular interest is the modified algorithm for determining the coefficients Seidel optimal model capable of operating
with a poorly-defined matrices having determinant value close or equal to zero.
Key words: the synthesis of the optimal filter, method of group account of argume, a system of linear equations,
genetic algorithm
Стр.1
60
В.М.ВАТУТИН, С. А.ДОНЦОВ, Ю.В.ЕФРЕМОВ, А.Н.СИРЕНКО
Метод группового учетааргументов
Метод группового учета аргументов — это семейство
индуктивных алгоритмов для математического
моделирования мультипараметрических данных.
Метод основан на рекурсивном селективном
отборе моделей, на основе которых могут строиться
более сложные модели.
Автор метода — академик АН СССР, академик
Национальной академии наук Украины (НАНУ), директор
Института кибернетики им. В.М.Глушкова
Алексей Григорьевич Ивахненко.
Метод группового учета аргументов применяется
в самых различных областях науки и техники
для анализа данных и отыскания закономерностей
для прогнозирования и моделирования систем,
решения задач оптимизации и распознавания образов.
Индуктивные алгоритмы МГУА дают уникальную
возможность автоматически находить взаимозависимости,
выбрать оптимальную структуру модели
или сети и увеличить точность существующих
алгоритмов.
Этот подход самоорганизации моделей принципиально
отличается от обычно используемых дедуктивных
методов. Он основан на индуктивных
принципах — нахождение лучшего решения основано
на переборе всевозможных вариантов.
Метод группового учета аргументов состоит из
нескольких алгоритмов для решения разных задач.
В него входят как параметрические алгоритмы,
так и алгоритмы кластеризации, комплексирования
аналогов и вероятностные алгоритмы. Этот подход
к самоорганизации уравнений основан на переборе
постепенно усложняющихся моделей и выборе
наилучшего решения согласно минимуму внешнего
критерия, в общем случае — квадратичного. В качестве
базисных моделей могут использоваться не
только алгебраические полиномы, но и разностные,
нелинейные и вероятностные функции.
Анализ входных данных
Отсчеты модулированного сигнала поступают
с выхода приемного устройства. В итоге на вход
программы поступает вектор значений, взятых
с определенной частотой дискретизации. Количество
измерений может варьироваться в очень
широких пределах.
Для того чтобы все данные находились в одном
диапазоне изменения значений, необходимо
произвести нормализацию. Это поможет легко сопоставлять
полученные значения и повышает обусловленность
матриц, предназначенных для получения
коэффициентов моделирующего уравнения.
Из ряда входных отсчетов получаем систему
уравнений. Для этого выберем уравнение линии
регрессии в виде линейной разностной схемы,
представимой в следующем виде:
yN = a0 +a1x1 +a2x2 +a3x3 +.. .+aNxN =
= a0 +
i=1
N
aixi,
где N — число членов линейного разностного уравнения
(интервал корреляции со значением выходного
сигнала модели yN), а x — значение сигнала,
отстоящее по времени на i шагов назад от текущего
(N-го) значения сигнала.
Для каждой точки q экспериментальных данных
можно подсчитать величину квадрата отклонения
(ошибки):
δ2 =(q −q2
0).
Суммируя уравнения такого вида для всех N
экспериментальных точек, получим выражение для
средней квадратической ошибки:
∆2 =
i=1
N
δ2
t .
Для вычисления минимума среднеквадратической
ошибки находим выражение для частных производных
(по числу определяемых коэффициентов
уравнения регрессии) и приравниваем их к нулю:
∂∆2
∂a0
= 0, ∂∆2
∂a1
уравнений Гаусса.
РАКЕТНО-КОСМИЧЕСКОЕ ПРИБОРОСТРОЕНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ т. 2 вып. 4 2015
= 0, ∂∆2
∂a2
= 0, ...
Отсюда получим систему так называемых
Стр.2
ПРОБЛЕМЫ СИНТЕЗА АДАПТИВНЫХ ФИЛЬТРОВ МЕТОДАМИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 61
РАКЕТНО-КОСМИЧЕСКОЕ ПРИБОРОСТРОЕНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ т. 2 вып. 4 2015
Рис. 1. Схема алгоритма синтеза модели
Стр.3
62
В.М.ВАТУТИН, С. А.ДОНЦОВ, Ю.В.ЕФРЕМОВ, А.Н.СИРЕНКО
Разделение данных на обучающую
и проверочную выборки
Основной критерий требует разбиения выборки
минимум на две равные части: Обучающую
(training sample) и Проверочную (validation sample).
Обычно таблица исходных данных делится на
три части: проверочная, обучающая и экзаменационная
(test sample). Обучающая выборка используется
для получения оценок параметров модели
(например, коэффициентов регрессии), а проверочная—длявыбора
структуры модели.
Обучающая выборка — выборка, по которой
производится настройка (оптимизация параметров)
модели зависимости.
Если модель зависимости построена по обучающей
выборке, то оценка качества этой модели,
сделанная по той же выборке, оказывается,
как правило, неустойчивой, то есть становящейся
неточной при малых изменениях данных. Это
нежелательное явление называют переобучением.
На практике оно встречается очень часто. Хорошуюэмпирическуюоценкукачествапостроенной
модели
дает ее проверка на независимых данных,
которые не использовались для обучения.
Тестовая (или контрольная) выборка — выборка,
по которой оценивается качество построенной
модели. Качество получаемой модели оценивается
по величине специального квадратичного критерия.
Оценку качества, сделанную по тестовой выборке,
можно применить для выбора наилучшей
модели. Однако тогда она снова окажется смещенной.
Для получения несмещенной оценки выбранной
модели приходится выделять третью выборку.
Несмещенной называется оценка, математическое
ожидание которой равно оцениваемому параметру.
Проверочная выборка — выборка, по которой
осуществляется выбор наилучшей модели из множества
моделей, построенных по обучающей выборке.
Метод Гаусса–Зейделя для решения
систем линейных алгебраических
уравнений
Для генерации уравнений-претендентов необходимо
решать системы линейных уравнений.
Для этого можно воспользоваться методом Гаусса–
Зейделя. Преимущество метода заключается в способности
решать разреженные матрицы — матрицы
с преимущественно нулевыми элементами.
Метод Гаусса–Зейделя — классический итерационный
метод решения системы линейных уравнений.
В
виде исходных данных задачи имеем систему
линейных уравнений вида
чу в виде:
a11x1 = −a12x2 −a13x3 −...−a1nxn +b1,
a21x1 +a22x2 = −a23x3 −...−a2nxn +b2,
.. .
a(n−1)1x1 +a(n−1)2x2 +.. .+a(n−1)(n−1)x(n−1) =
= −a(n−1)nxn +bn−1,
an1x1 +an2x2 +...+an(n−1)xn−1 +annxn = bn.
Здесь в j-м уравнении мы перенесли в правую
часть все члены, содержащие xi,для i>j.Эта
запись может быть представлена
(L+D)x = −Ux+b,
где в принятых обозначениях D означает матрицу,
у которой на главной диагонали стоят соответствующие
элементы матрицы A,авсеостальныенули;
тогда как матрицы U и L содержат верхнюю и нижнюю
треугольные части A, на главной диагонали
которых нули.
Итерационный процесс в методе Гаусса–
Зейделя состоится по формуле
(L+D)x(k+1) = −Ux(k) +b, k = 0, 1, 2, . . .
После выбора соответствующего начального приближения
x(0).
Метод Гаусса–Зейделя можно рассматривать
как модификацию метода Якоби. Основная идея модификации
состоит в том, что новые значения x(i)
используются здесь сразу же по мере получения,
РАКЕТНО-КОСМИЧЕСКОЕ ПРИБОРОСТРОЕНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ т. 2 вып. 4 2015
a11x1 +.. .+a1nxn = b1,
...
an1x1 +.. .+annxn = bn.
Чтобы пояснить суть метода, перепишем зада
Стр.4
ПРОБЛЕМЫ СИНТЕЗА АДАПТИВНЫХ ФИЛЬТРОВ МЕТОДАМИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 63
в то время как в методе Якоби они не используются
до следующей итерации:
Ax(k+1) −b
x(k+1)
x(k+1)
n = cn1x(k+1)
...
x(k+1)
где
cij =
1 = c12x(k)
2 +c13x(k)
2 = c21x(k+1)
1 +c23x(k)
ε,
3 +...+c1nx(k)
3 +...+c2nx(k)
2 +cn2x(k+1)
2 +...
...+cn(n−1)x(k+1)
−
0,
aij
aii
, j = i,
j = i.
n−1 +dn,
di = bi
aii
n +d1,
n +d2,
выбранному внешнему критерию. Различают два
основных вида алгоритмов — однорядный и многорядный.
Все
алгоритмы МГУА воспроизводят схему
массовой селекции: последовательно порождаются
модели возрастающей сложности. Каждая модель
настраивается: методом наименьших квадратов
находятся значения параметров. Из моделей
претендентов выбираются лучшие в соответствии
с выбранным критерием. Многорядные алгоритмы
могут вычислять остатки регрессионных моделей
после каждого ряда селекции или не вычислять,
при этом используются исходные данные.
Каждая полиномиальная модель однозначно
,
ближения вычисляется по формуле
x(k+1)
i =
i−1
j=1
cijx(k+1)
j +
j=i
n
cijx(k)
i = 1, . . . , n.
Таким образом, i-я компонента (k +1)-го приj
+di,
i = 1, . . . , n.
Условия окончания итерационного процесса
Зейделя при достижении точности ε вупрощенной
форме имеет вид
x(k+1) −x(k)
го процесса имеет вид
Ax(k+1) −b
ε
и требует больше вычислений. Благодаря критерию
окончания итерационного процесса, алгоритм решения
систем линейных уравнений хорошо подходит
для разреженных матриц, так как при их решении
не происходит зацикливания.
Генерация моделей-претендентов
Целью МГУА является получение модели
в результате перебора моделей из индуктивнопорождаемого
множества. Параметры каждой модели
настраиваются так, чтобы доставить минимум
ε.
Более точное условие окончания итерационноопределяется
набором индексов s входящих в него
мономов (одночленов):
y = a0 +w(s)a(s).
Элементы вектора w — коэффициенты при мономе
полинома; элементы вектора a —результат
произведения свободных переменных соответствующих
мономов. Индексы s ∈{1, . . . ,F0} есть индексы
мономов, входящих в модель. Иначе производная
модель
y = a0 +w(s)a(s)
порождается набором индексов s ∈{1, . . . ,F0},
включающих соответствующие элементы векторов
w = w1, ... ,wF0
r=1
R
и a = a1,. . . , aF0
мономов полинома равно
F0 =
CP
¯
.Здесь CP
r =
r=1
R
.
При ограничении полинома числом R число
(r +p−1)!
P!(r −1)! ,
а число моделей первого ряда соответственно равно
2F0
r — число сочетаний с повторениями
из P по r, P — число свободных переменных —
элементов вектора x.
Модели-претенденты порождаются индуктивно.
При этом вводится ограничение на длину полинома
базовой модели. Например, степень полинома
базовой модели не должна превышать заданное
число R. Тогда базовая модель представима в виде
линейной комбинации заданного числа F0 произведений
свободных переменных:
y = f(x1,x2, ... ,x2
1,x1x2,x2
2, ... ,xR
m).
РАКЕТНО-КОСМИЧЕСКОЕ ПРИБОРОСТРОЕНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ т. 2 вып. 4 2015
Стр.5
64
В.М.ВАТУТИН, С. А.ДОНЦОВ, Ю.В.ЕФРЕМОВ, А.Н.СИРЕНКО
Здесь f — линейная комбинация. Аргументы
этой функции переобозначаются следующим образом:
x1
→a1, x2 →a2, ... , x2
x2
2 →aγ, ... , xq
То есть
y = f(a1,12,. . . , aF0
ется одноиндексная нумерация
w = w1, ... ,wF0
линейной комбинации.
y = w0 +
).
Для линейно входящих коэффициентов зада
.
Тогда модель может быть представлена в виде
i=1
F0
wiai.
Каждая порождаемая модель задается линейной
комбинацией элементов {(wi, ai)}, в которой
множество индексов {i} = s является подмножеством
{1, . . . ,F0}.
Определение и выбор критерия
Вычисление значения оптимального уравнения
на проверочной выборке осуществляется с помощью
внешнего критерия.
Критерий выбора модели может быть назван
внешним, если он получен с помощью дополнительной
информации, не содержащейся в данных,
которые использовались при вычислении параметров
моделей. Например, такая информация есть
в дополнительной, тестовой выборке.
Алгоритм МГУА использует и внутренний
и внешний критерий. Внутренний критерий применяется
для настройки параметров модели, внешний
критерий — для выбора модели оптимальной
структуры. Возможен выбор модели по нескольким
внешним критериям.
В данной работе одним из внешних критериев
является проверка на соответствие спектра сигнала,
полученного из обучающей выборки, и спектра,
полученного из тестовой выборки.
Рис. 3.Спектр сигналанаобучающейвыборке
Модель претендент будет определена тем правильнее,
чем меньше значение критерия:
Cr = 1
N
k=1
N
(Skn −Sko)2.
Правильней всего выбирать не один внешний
критерий, а несколько. Возьмем в качестве дополнительного
критерия критерий регулярности.
Критерий регулярности ∆2(C) включает среднеквадратичную
ошибку на обучающей подвыборке
C, полученную при параметрах модели, настроенных
на тестовой подвыборке l:
∆2(C)= |yC −AC -
wl|2 =(yC −AC -
wl)T (yC −AC -
wl),
где A — система линейных уравнений, полученная
из выборки, и
yC(l)= AC -
-
wl.
Для того чтобы учитывать результаты вычислений
нескольких критериев, необходимо использовать
комбинированный критерий
k2 =
i=1
K
aik2
i
РАКЕТНО-КОСМИЧЕСКОЕ ПРИБОРОСТРОЕНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ т. 2 вып. 4 2015
Рис. 2. Спектр сигналанапроверочной выборке
1 →aα, x1x2 →aβ,
m →aF0
.
Стр.6
ПРОБЛЕМЫ СИНТЕЗА АДАПТИВНЫХ ФИЛЬТРОВ МЕТОДАМИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 65
при условии нормировки
k2 =
i=1
K
ai
k2
i
k2
imax
i=1
K
ai = 1.
рии, а ai — веса этих критериев, назначенные в начале
вычислительного эксперимента.
Здесь ki — принятые на рассмотрение критеИспользуются
так же нормализованные значения
критериев. При этом предыдущая формула
имеет вид
k2 =
i=1
K
ai
k2
i
k2
imax
идентифицированы, по внешнему критерию из них
отбирают лучшую.
После того, как все зависимости yi, i = 1, p
.
Заключение
Приведенный выше алгоритм может работать
в режиме реального времени для синтеза оптимального
фильтра.
Список литературы
1. Дьяконов В.П. Справочник по алгоритмам и программам
на языке бейсик для персональных ЭВМ.
М.: Наука. Физмалит, 1989. 240 с.
2. Коршунов Ю.М. Математические основы кибернетики.
2-е изд., перераб. и доп. М.: Энергия, 1980.
424 с.
3. Фадеев Д.К., Фадеева В.Н. Вычислительные методы
линейной алгебры.
4. Рабинер Л., Гоулд Б. Теория и применение цифровой
обработки сигналов. М.: Мир, 1978.
РАКЕТНО-КОСМИЧЕСКОЕ ПРИБОРОСТРОЕНИЕ И ИНФОРМАЦИОННЫЕ СИСТЕМЫ т. 2 вып. 4 2015
Стр.7