Интеллектуальный анализ данных

• Название: Интеллектуальный анализ данных
• Дата: 11.10.2022
• Размер: 7.76 Mb.
• Имя файла: iad_iadl.pdf
• Тип: Учебное пособие; #726651
• страница: 23 из 23

S
0
S
Ng
S
1
...
...
S
1
...
S
Ng
S
1
...
S
Na
Первое
поколение
Механизм селекции
Механизм изменчивости
S
Ng
S
1
...
...
S
1
...
S
Ng
S
1
...
S
Na
Второе
поколение
S
1
...
S
Na
……………………………………………
S
R
: Eff(S
R
)=max
Третье
поколение

169
На втором шагу формируются
d
N
стратегий-потомков путем внесения различного рода изменений в
a
N
стратегий-предков. В результате образуется
d
a
g
N
N
N


управляющих стратегий, эффективность каждой из которых
1
,...,
0
),
(
N
i
S
Eff
i

вновь оценивается на том же временном ряду наблюдений
)}
(
),
(
{
T
t
Y
t
Y

. Каждая из отобранных СР порождает путем модификаций
d
N
стратегий-потомков (СП). Тогда общее количество стратегий нового поколения (g, generation) составит
).
1
(
d
a
g
N
N
N


Последующие итерации повторяют последовательную работу механизмов изменчивости, селекции и отбора.
Процессы "Изменения-размножения" и "Селекции-отбора" стратегий повторяются в течении заданного числа поколений. Остановка цикла генерации поколений может быть проведена и раньше, например, на основе критерия превышения порога точности или критерия сходимости результатов прогноза на тестовой совокупности данных. В конечном счете, итерационная процедура позволяет выявить наилучшую стратегию, наиболее успешно функционирующую на заданном интервале наблюдений.
6. Пример. Идентификация поверхности отклика второго порядка.
Имеется некоторая априорная нелинейная гиперповерхность отклика M-го поряд- ка
)
x
,...,
x
,
x
(
y y
M
2 1

(1) и совокупность из N векторных наблюдений за каждым из M независимых параметров Z

Осуществляется МНК аппроксимация этой гиперповерхности полиноми- альной моделью не выше 2-го порядка. При этом
).
x x
...,
,
x x
...,
,
x x
,
x
...,
,
x
,
x
...,
,
x
(
f yˆ
M
1
M
M
1 2
1 2
M
2 1
M
1


(2)
Требуется построить наилучшую аппроксимацию, для которой





N
1
i
2
i i
N
min
)
y

y
(
Q
(3)
Состав модели (2) может быть любым. Таким образом, речь идет о выборе наилучшей структуры аппроксимирующей модели.
Очевидно, что такой выбор можно сделать полным перебором переменных, входящих в (1). В правую часть (1) входит переменных N
ALL
= М (число независи- мых переменных) + М (число квадратов независимых переменных) +(M*M-M)/2
(число различных парных произведений независимых переменных).
Тогда полное число возможных моделей составит
N
Мод
=
C
C
C
C
ALL
ALL
ALL
ALL
ALL
ALL
N
N
1
N
N
2
N
1
N





Альтернативу к полному перебору дант технология эволюционного модели- рования, имитирующая процесс биологической эволюционной оптимизации, осно- ванной на принципах рандомизации, наследственности, селекции, отбора.
В соответствии с технологией эволюционного моделирования, поиск опти- мальной модели (2) представлен в виде блок-схемы на рис. 1 и состоит в сле- дующем:
1. Формируется полная модель наблюдений второго порядка с двумя пере- менными. x
x a
x x
a x
a x
a x
a x
a a
Y
2 1
6 2
1 5
2 2
4 2
1 3
2 2
1 1
0







Выбирается базовая модель (из таблицы 1 вариантов моделей, подлежа- щих идентификации).

170 2. Формируется первое поколение моделей-родителей, состоящее из
3
M
p

моделей путем случайного выбора значений
6
,...
1
i
,
a i

из интервалов их допустимых вариаций
6
,...
1
i
,
Da i

3. Формируется поколение моделей-потомков , путем внесения в каждую из моделей-родителей только по одному изменению. Каждай из моделей-родителей порождает 3 модели-потомка. Таким образом, формируется матрица моделей- потомков, состоящая из
9 3
3
k
M
M
b p
d





моделей. Здесь
3
k b
 - коэффици- ент размножения моделей (kBreading).
Для формирования каждой модели потомка осуществляется следующая последовательность операций:
- выбор номера параметра модели, подлежайшего изменению, осуществля- ется случайным розыгрышем;
- разыгрывается один из трех возможных типов модификации: с вероятностью
7
.
0
P
1

осуществляется небольшая (в пределах 10% от ис- ходного значения) параметрическая модификация одного из шести параметров модели; с вероятностью
2
.
0
P
2

осуществляется большая (в пределах 30% от ис- ходного значения) параметрическая модификация одного из шести параметров модели (параметричсекая мутация);
Выбор базовой модели, подлежащей идентификации
Генерация первого поколения моделей-родителей
Генерация матрицы моделей нового поколения
Цикл по числу поколений
НК-оценка качества моделей поколения
Рейтинг моделей.
Селекция и отбор моделей-родителей нового поколения
Критерий остановки
Решение
Рис. 1. Блок-схема решения задачи эволюционной идентификации
Выбор параметров размножения, селекции и отбора

171 с вероятностью
1 0
P
2

осуществляется структурная мутация, т.е. данный параметр (ген) исключается из модели (или, наоборот, в слуцчае его отсутствия, добавляется в модель).
4. Матрица поколения Generation формируется путем объединения (верти- кальная конкатенация) матрицы-родителей и матрицы-потомков.
5. Организуется процесс селекции и отбора. Простейший вариант селекции связан с использованием квадратичной метрики рассогласования между парамет- рами базовой модели и параметрами каждой модели (генома) из матрицы- поколения:





m
1
k
2
ki k
)
a a
(
)
i
(
Формируется рейтинг моделей поколения по критерию
)}
i
(
min{
. Первые
mSurvive моделей выживают и образуют матрицу-родителей следующего поколе- ния.
5. Осуществляется переход к п.3., формируется матрица следующего поко- ления и т.д.
Программа завершается по достижению заданного уровня
0
 точности под- гонки или по достижению заданной величины числа итераций (поколений)
.
N
g
Вопросы для самопроверки:
1. Для решения каких задач используетcя ЭМ?
2. Чем отличается ЭМ от случайного поиска.
3. Назовите критерии селекции.
4. Перечислите особенности реализации алгоритма ЭМ.
5. Каким образом реализуется процесс изменчивости наследования?
6. Каким образом реализуется процесс параметрической мутации наследования?
ЛИТЕРАТУРА
1.
Fogel L.J., Owens A.J., Walsh M.J. Artificial intelligence through simulated evolu- tion. / N.Y.: John Wiley & Sons. – 1966. – 231p.
2.
Аверченков В.И. Эволюционное моделирование и его применение: моно- графия / В.И. Аверченков, П.В. Казаков. 2-е изд., стереотип. — М.: ФЛИНТА. — 2011. —
200с.
3.
Каширина И.Л. Эволюционное моделирование: учебное пособие для втузов.
/ Воронеж: Изд. центр ВГУ. — 2011. — 60с.
4.
Курейчик В. Эволюционное моделирование и генетические алгоритмы. /
В. Курейчик, Л. Гладков, В. Курейчик. — Lambert Academic Publishing. — 2011. —
260с.
5.
Карпов В.Э. Методологические проблемы эволюционных вычислений // Ис- кусственный интеллект и принятие решений. — 2012. — №4. — C.95-102.
6.
Рутковский Л. Методы и технологии искусственного интеллекта. / М.: Горя- чая линия–Телеком. — 2010. — 520с.
7.
Mukhopadhyay A. A. Survey of Multiobjective Evolutionary Algorithms for Data
Mining: Part I / Mukhopadhyay A., Maulik U., Bandyopadhyay S., Coello C.A. IEEE Transac- tions on Evolutionary Computation. — 2014. — V.18. — N1. — P. 4-19.
8.
Mukhopadhyay A. A. Survey of Multiobjective Evolutionary Algorithms for Data
Mining: Part II // Mukhopadhyay A., Maulik U., Bandyopadhyay S., Coello C.A. IEEE Transac- tions on Evolutionary Computation. — 2014. — V.18. — N1. — P. 20–35.

172 9.
Carreno J. E.
Multi-objective optimization by using evolutionary algorithms:
The p-Optimality Criteria // IEEE Transactions on Evolutionary Computation. — 2014. — V.18.
— N 2. — P. 167–179.
10.
Das. S. Differential Evolution: A Survey of the State-of-the-Art. // Das.
S., Suganthan. P.N. IEEE Transactions on Evolutionary Computation. — 2011. — v.15. — N 1.
— P. 4-31.
11.
Мусаев А.А.Эволюционно-статистический подход к самоорганизации про- гностических моделей управления технологическими процессами. // Автоматизация в промышленности. – 2006. – Вып. 7. — С. 31-35.
12.
Мусаев А.А. Алгоритмы Data Mining в задачах управления динамическими процессами // Труды СПИИРАН. – 2007. – Вып. 5. — С. 299-312.
13.
Metropolis N., Ulam S.The Monte Carlo Method. J. Amer. statistical assoc. —
1949. — 44. — N 247. — Pp. 335-341.
14.
Ермаков С. М. Метод Монте-Карло в вычислительной математике: вводный курс / СПб. : Невский Диалект. —М. : БИНОМ. Лаборатория знаний. — 2009 . – 192с.
15.
Редько В.Г. Эволюционная кибернетика. / М.: Наука. — 2001. — 159 с.
16.
Емельянов В.В., Курейчик В.М, Курейчик В.В. Теория и практика эволюци- онного моделирования. — М.: Физматлит. — 2003. — 432 с.
17.
Гудман Э.Д. Эволюционные вычисления и генетические алгоритмы // Обо- зрение прикладной и промышленной математики. — 1996. — Т. 3. — Вып. 5. — 179c.
18.
David E. Goldberg. Genetic algorithms in search, optimization, and machine learning. // Addison-Wesley Publishing Co. — 1989. — 432p.