Решение задачи. Типовые задачи и примеры их решения

Типовые задачи и примеры их решения

Задача 5.1. Реализовать алгоритм выбора множества максимально различающихся квантов Г*.

Итеративный алгоритм выбора множества Г* (рис. 5.2) состоит из этапов:

1. Устанавливается количество необходимых максимально отличающихся квантов Г*, т.е. количество элементов множества Г*. При этом необходимо учитывать неравенство r £ çГ₀ç, а также вычислительные ресурсы (память и машинное время), имеющиеся для синтеза, отбора и структурного анализа вариантов.

2. Формируется первое приближение Г^{( i )}, i = 1 множества Г, в которое включаются первые r ² элементы множества Г₀.

3. Устанавливаются начальные значения счетчика рассмотренных квантов t =0, порогового значения степени различия g₀=0, а также константа e, задающая необходимую точность расчетов.

4. Вычисляется средняя степень различия g _i квантов множества Г^{( i )}:

g _i = , i ¹ j. 2.

5. Если g _i – g _{i –1} < e, то переходим к п. 10 (конец алгоритма).

6. Увеличивается значение t = t + 1 для рассмотрения следующего элемента множества Г₀, которое обозначается G_{r + t}.

7. Если r + t ³ çГ₀ç или израсходовано машинное время, отведенное для выбора вариантов квантов, то переходим к п. 10 (конец алгоритма).

Рис 5.2. Алгоритм формирования множества максимально различающихся квантов

8. Квант G_{r + t} попарно сравнивается со всеми квантами G_i Î Г^{( i )} по выражению (5.1). Если выполняется условие

[($ G_{r + t} Î )&(" G_i Î Г^{( l )})]: ,

где – дополнение Г^{( l )} до множества Г₀, то переходим к следующему пункту. В противном случае – переходим к п. 6.

9. В множестве Г^{( i )} находится квант G_k, который максимально подобен остальным элементам множества Г^{( i )}, т.е. G_k, для которого выполняется условие

[($ G_k Î Г^{( i )}) &(" G_i Î Г^{( i )})]: <0.

Если квант G_k найден, то в дополнение Г^{( l )} вместо него включается квант G_r+k и осуществляется переход к п. 6. В противном случае получено (l +1)-е приближение Г^{( l +1)} множества Г, поэтому увеличивается l = l + 1 и осуществляется переход к п. 4.

10. Конец алгоритма.

В данном алгоритме постепенно увеличивается пороговое значение степени подобия g _l, которое используется для принятия решения при отборе вариантов квантов. Прерывается выполнение алгоритма в любой момент времени. При этом в множестве Г^{( i )} содержатся наиболее различающиеся кванты из r + t квантов, рассмотренных до момента прерывания.

Задача 5.2. Реализовать алгоритм кластеризации квантов.

Решение задачи. На рис. 5.3 приводится алгоритм максиминного расстояния, предназначенный для кластеризации допустимых вариантов формирования областей определения X исходной области значений Y:

1. Устанавливаются начальные значения вектора текущего количества элементов кластеров = 0, текущего количества кластеров p = 2 и количества кластеризованных квантов, не являющихся центрами кластеров t = 0. Подмножества Г _i Ì Г в начале алгоритма пусты и постепенно пополняются квантами из множества Г.

2. В множестве Г* ищется пара квантов G_{p 1}, G_{p –1,1}, для которой:

[($ G_{p 1} Î Г*) & ($ G_{p –1, 1} Î Г*)]: I (G_{p 1}, G_{p –1,1}) = ,

где I (G_i, G_j) – расстояние между квантами G_i и G_j определяемое по выражениям (5.1, 5.2).

ВВОД

[(&(]: I (G_{p 1}, G_{p -1,1}) = I (G_i, G_j)

p = p +2

Г = Г'

Г' = Г'U{ G_{p -1, i} }

V = 0; p = 2; t = 0

Г*^{( p + t )} = Г*^{( p + t -1)}ç{ G_{p -1,1}}

Г*^{( p + t )} = Г*^{( p + t -1)}ç{ G_{p ,1}}

Г^{( Vp )} = Г^{( Vp ) -1}U{ G_{p -1,1}}

Г^{( Vp )}= Г^{( Vp ) -1}U{ G_{p 1}}

Г^{( p + t)} = Г^{( p + t – 1)}ç{ G_{i 1}}

ВЫХОД

V_j = V_j +1

min I (G_{p 1}/ G_{p- 1,1}; G_i)< <0,5(p -1)^–2= = I_m

Г^{( Vp -1)} = Г^{( Vp -1)-1}U{ G_{p 1}/ G_{p- 1,1}}

Рис. 5.3. Алгоритм кластеризации квантов

3. Найденные кванты назначаются центрами для двух первых кластеров Г₁ и Г₂, т.е. формируются текущие варианты множеств , и на базе предыдущих их вариантов , и по выражениям

V_{p –1}= V_{p –1}+1; =|{}; =U{ G_{p –1,1}}.

4. V_p = V_p +1; =U{ G_{p 1}}; p = p +1.

5. Среди оставшихся элементов множества Г ищется квант G_{p 1}, для которого выполняется условие

($ G_{p 1} Î Г): .

6. Найденный квант исключается из множества Г, т.е.

Г^{( p + t )} = Г^{( p + t –1)}|{ G_{p 1}}.

7. При выполнении условия

(" i =:= I_m,

квант G_{p 1} (G_{p –1,1}) обозначается G_iVj и включается в ближайший кластер Г _j, т.е. V_j = V_j + 1; Г= ГU{ G_iVj }; t = t + 1, и переходим к п. 8, а в противном случае к п. 9.

8. Проверяется количество рассмотренных квантов. Если p + t ³ r, то переходим к п.13 (конец алгоритма), в противном случае к п. 5.

9. Найденный квант включается в переходное множество Г¢, в котором накапливаются кванты, не вошедшие в уже сформированные кластеры, т.е.

Г¢ = Г¢U{ G_{p -1, i} }.

10. Если множество Г* ¹ Æ, то переходим к п. 5. В противном случае переходим к следующему пункту.

11. Среди сформированного переходного множества Г¢ ищется квант G_{j 1}, для которого выполняется условие

($ G_{j 1} Î Г¢): .

Найденный квант G_{j 1} назначается центром нового кластера и переходим к п.13. В противном случае переходим к следующему пункту.

12. Сформированное множество Г¢ объявляется множеством Г, то есть выполняется условие Г = Г¢, а p = p + 2, и переходим к п. 2.

13. Конец алгоритма.

Описанный алгоритм выполняет кластеризацию структур G_i ÎГ с автоматическим выбором количества кластеров s, где 2£ s £ r. В любой момент выполнения алгоритма . В конце алгоритма s = p, а . Преимуществом алгоритма является кластеризация без повторного пересмотра элементов.

Задача 5.3. Реализовать алгоритм формирования переменных модели измерения.

Дата добавления: 2014-01-05