Прикладная математика

Абдул-заде С.И., Халилова Д.М.

Азербайджанский Государственный Экономический Университет

ОБ ОДНОМ МЕТОДЕ ПРОГНОЗИРОВАНИЯ, ОСНОВАННОМ НА РАСПОЗНАВАНИИ ОБРАЗОВ И ЭВОЛЮЦИОННЫХ ВЫЧИСЛЕНИЯХ

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

1. Постановка задачи

Пусть

(1)

представляет конечное множество некоторых сложных, динамических объектов, состояния каждого из которых описываются Q набором (вектором) признаков

(2)

Совокупность всевозможных наборов значения признаков (2) образует пространство признаков размерности n. Объекты , состояния которых в каждый момент описываются векторами (2), имеют одну и ту же длину и один и тот же состав компонент. Такие объекты называются однородными или однотипными. В пространстве признаков (2) каждому объекту соответствует дискретная траектория, имитирующая функционирование соответствующего ей объекта, наблюдаемого на временном отрезке .

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

Отрезок разбивается на части интервал предыстории для контрольных траекторий где Т-момент прогнозирования; интервал упреждения, т.е.

Рассматривается набор признаков (2) как ряд наблюдений, на отрезке для объектов, , которые можно представить в виде матриц размерности . Очевидно, что, матриц будет N (по числу объектов), при этом строками являются состояния объекта, а столбцами – значения признаков (2), а именно

(3)

где, .

Значения признаков (2) объектов , которые получаются посредством испытаний, реализуемых в дискретные моменты времени.

(4)

представляются в виде матриц размерности , т.е.

, (5)

где, .

В пространстве признаков объектам соответствуют

, (6)

определенных на отрезке , продолжения которых на интервале упреждения остаются неизвестными. Требуется построить продолжения выборки (6) на интервале упреждения относительно некоторой характеристики, с учетом заданных в момент ограничений, то есть требуется решить задачу прогнозирования контрольных траекторий на интервале упреждения с учетом ограничений. Ограничения сводятся к требованию попадания (6) в момент в классы с вероятностями (надежностями), удовлетворяющими заданным ограничениям.

2. Методы решения

Введем некоторую функцию, связанную с каждым объектом из множества

(13)

содержательно. Функция характеризует какой-либо вид ресурса, который необходим для перевода соответствующего объекта (7) из одного состояния в другое. А функция для каждого в точках определяется значениями

(8)

и для каждого объекта в точках (10) отрезка значениями

(9)

Учитывая (8), (9) расширим матрицы исходной информации (3), (5) посредством добавления одного столбца, в следующей форме для обучающих объектов матрицами размерности , т.е.

, где (10)

Аналогичном образом, информация о контрольных объектах представляется на отрезке соответствующими расширенными матрицами размерности , а именно,

(11)

где

Пусть дано - начальная информация [2], т.е. данные матриц (11), - заданные величины. Рассмотрим функцию , характеризующую траектории го объекта, т.е. функцию ресурса, зависящую от времени и признаков

(12)

Предложим, что функция представимо в виде:

(13)

где - некоторые неизвестные постоянные, подлежащие определению. Слагаемое - случайное отклонения в тех же точках. Система (13) может быть представлена в матричной форме в следующем виде

(14)

где- вектор значений функции на - неизвестный вектор; - вектор случайных отклонений.

(15)

Предполагается, что случайный вектор или .

Далее для любых . Здесь -дисперсия отклонений. Кроме того, предполагается, что ранг матрицы (15) равен n.

При этих допущениях для оценивания неизвестного вектора на интервале использован метод наименьших квадратов отклонений. Согласно этому методу минимизируется сумма квадратов отклонений, то есть

(16)

где вектор «оцененных» отклонений. Функционал (16) достигается минимума в точке

(17)

Оценка (17) является оценкой метода наименьших квадратов [1].

На интервале упреждения среднее значение функции прогноза определяется линейной функцией

(18)

где коэффициенты вычисляются по формуле (17). Поскольку на интервале значения признаков в (18) являются неизвестными, то возникает необходимость прогнозирования значений ; в точках . Для решения задачи прогнозирования значений для каждой траектории можно воспользоваться авторегрессионной моделью или экспоненциальным сглаживанием [1,4].

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

(19)

; где значения прогноза признаков в точках .

Обозначим истинные неизвестные значения функции ресурса в точках интервала упреждения через и предположим, что она представима в виде

(20)

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

Пусть и u = 1,2,….,l – некоторые значения функции ресурса, характеризующие принадлежность обучающих траекторий классам К₁,К₂,….,К_l в момент . Если 0 ≤ А_u < 1, u = 1,2,….,l – заданные значения, ограничивающие вероятности попаданий в классы прогнозируемой части контрольной траектории и › 0 – некоторое положительное число, то неравенства

(21)

u = 1,2,….., j – 1, j + 1,….,l, являются аналитическим выражением требования попадания траектории объекта в класс K_j c вероятностью не меньше A_j , в остальные классы K_u, u = 1,2,…,j – 1, j + 1,…,l с вероятностями не большими чем A_u, u = 1,2,…,j – 1, j + 1,…,l в момент . При этом задаются следующим образом:

и (22)

В качестве критерия наилучшего прогноза на интервале упреждения рассмотрим следующий функционал

(23)

где М {} – математическое ожидание по всем ;

Функционал (29) характеризует суммарную ошибку отклонения прогнозной траектории объекта на интервале упреждения от истинной неизвестной траектории.

Математическая формулировка задачи продления траектории объекта сводится к следующему:

· По данным , характеризующим значения функции ресурса каждого класса , обычно определяется из матриц обучений (16) как среднее значения функции для объектов, принадлежащих классу в момент ;

· Заданным для объекта и ;

требуется минимизировать функционал

(24)

при ограничениях

(25)

u = 1,2,….., j – 1, j + 1,….,l, где определяются как:

Здесь соответственно характеризует значение функции траекторий из класса .

Задача (24) и (25) является задачей стохастического программирования с вероятностными ограничениями [6]. В работах [3], для определения оптимальных значений (для каждого объекта ) свелось к решению задачи стохастического программирования (24) и (25).

В данной работе, для решения задачи (24) и (25), исходя из работ [5], предложен метод, базирующийся на алгоритме эволюционного принципа Ж. Ламарка. Независимо от идеологии генетического алгоритма, общая схема эволюционных вычислений определяется следующими параметрами:

1. Способом кодировки решения (хромосомами);

2. Функцией оптимальности (оценками);

3. Вероятностными параметрами управления сходимостью эволюции;

4. Условием завершения эволюции;

5. Содержанием операторов: отбором (селекцией), рекомбинацией и мутацией.

6. Для решения задачи (24)-(25) используется мобильный генетический алгоритм, базирующийся на ламаркизме или модели эволюции Ж. Ламарка – хромосома кодируется списком пар <номер гена, значение гена>. Особенность кодирования решения в генетическом алгоритме (модели эволюции Ламарка) – это использование как неполных хромосом, так и избыточных. Для интерпретации такой хромосомы вводится правило экспрессии, то есть правило активации генов – гены доминируют слева направо, что соответствует природе задачи (24)-(25). Использование правила приводит к тому, что самый левый (доминантный) ген используется при подсчете оптимальности хромосомы, но потомки могут унаследовать и какие-то из правых (рецессивных) генов. Схема генетического алгоритма содержит существенные изменения и уточнения схемы эволюционного алгоритма, базирующейся на другой идеологии.

Begin

t=0; установка времени эволюции

init – population (p^t); инициализация исходной популяции

p^pp=preparing_population (p^t); насыщение популяции лучшими хромосомами

while (not done (termination condition)); пока не выполнено условие завершения эволюции

p^s=selection (p^t); выбор индивидуумов

p^r=cut_or_splice (p^s); операция разрезания или сцепления хромосом

p^m(mutation (p^t)); мутация

p^t+1=generation (p^s, p^r, p^m); формирование нового состояния популяции

t=t+1; переход по эволюционному времени

endwhile

end

На этапе инициализации случайным образом генерируются -строк, задается пользователем. Целевая функция (24) вычисляется так же, как при использовании стандартного генетического алгоритма. Оператор селекции для модели эволюции Ж. Ламарка вычисляется на основе пропорционального отбора. Оператор селекции начинает формировать t+1-поколение по t-му поколению. При программной реализации целесообразно ввести два пула: пул текущего и последующего поколений. В пул последующего поколения заносятся все отобранные операторы селекции хромосомы в качестве родителей нового поколения. Особенность идеи генетического алгоритма, базирующейся на модели Ж. Ламарка, состоит в том, что пропорциональный отбор используется только на стадии preparing population – предварительного насыщения популяции , а далее используются вероятности операторов cut и splice - p^c, p^s. Оператор splice выполняется с некоторой фиксированной вероятностью p^s. Операторы имеют два предельных типа поведения. В начале эволюции, когда преобладают длинные хромосомы, в основном выполняются cut. А затем начинает преобладать оператор splice. Оператор мутации – это суммирования значения гена и стратегического параметра – отклонения, задаваемого пользователем в случайной позиции хромосомы. Оператор формирования нового поколения в данной модели эволюции сводится к переходу по счетчику эволюционного времени.

Литература

1. Бокс Дж., Дженкинс Г. 1974, Анализ временных рядов, т.1

2. Журавлев Ю.И. 1978,Об алгебраическом подходе к решению задач распознавания или классификации, Проблемы кибернетики, №33, стр. 5-68

3. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. – М., ФИЗМАТЛИТ, 2003, -432 стр.

4. Курейчик В.М., Родзин С.И. Эволюционные вычисления: генетическое и эволюционное программирование. // ”Теория и системы управления”, РАН, Москва, № 1, 2002, с.127-138.

5. Голубин А.В. Разработка гибридных интеллектуальных моделей эволюционного проектирования. Автореферат дисс.на соиск. уч.степ. канд.тех.наук. Москва – Таганрог – 2006. -25 стр.

6. Ивахненко А.Г., Мюллер Й.-А. 1984. Самоорганизация прогнозирующих моделей. Berlin: Verlag Technik, 223 с.