Оптимизация траектории развития слабоформализованного объекта с иерархической структурой

УДК 519.254

О. В. Махныткина

Оптимизация траектории развития слабоформализованного объекта с иерархической структурой

O. V. Makhnitkina

Optimizing a Trajectory of Development of Weakly Formalized Object with Hierarchical Structure

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

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

In the article it is offered to use new approach to modeling a trajectory of weakly formalized object with changeable hierarchical structure basing on a method of dynamic programming. The research considers a problem of optimizing a trajectory of training students.

Key words: weakly formalized object, hierarchical structure, dynamic programming, training trajectory.

Многие социальные, экономические и технические объекты характеризуются качественной природой параметров предметной области, неоднородностью шкал измерений параметров, нелинейным характером взаимосвязи характеристик, т. е. относятся к слабоформализованному типу. Для большинства объектов при этом характерна иерархическая структура показателей. Среди работ, посвященных математическому моделированию слабоформализо-ванных объектов, широкое распространение получили подходы к изучению статических состояний объектов, такие как теория комплексного оценивания [1-3], метод анализа иерархий Т. Саати [4; 5], гибридные экспертные системы [6; 7], и в меньшей мере изучены вопросы динамических изменений состояния слабоформализованного объекта. Особую сложность и актуальность представляет временной анализ слабоформализованных объектов с изменчивой структурой. Например, на социально-экономическое состояние регионов влияют различные целевые программы, действующие ограниченный период времени; результат обучения (компетентность) студента зависит от меняющихся каждый семестр дисциплин и тем научно-исследовательской работы и т. д. Рассматриваются постановка и решение задачи нахождения оптимальных состояний слабоформали-зованных объектов с изменчивой иерархической структурой.

В общем виде оценку состояния иерархического объекта можно записать в следующем виде.

Обозначим: М = {1, 2,т} — множество частных критериев, оценки хр е X по которым принимают значения из множеств X , р е М , у0 е Y0 — интегральный показатель оценки, который вычисляется

в соответствии с процедурой агрегирования ¥(•): X ^ У0 или с учетом иерархической структуры:

У у...И = РЦ..М

У ц.л = РЦ.Л

...

У = р

^ Уо = Р0

где х = (х1,х2,...,хт)еX = ПХр, ,= 1,т1, ] = 1,т. ,

реМ

к = 1,тк , I = 1,т1 — индексы уровней иерархии; т — количество показателей на уровне иерархии , ; ¥ к — процедура агрегирования на ц...к -м уровне иерархии. Множество оценок у = (у0,у1,...,у.. к,...утт щ щ ...Утщ ...щщ ) описывает состояние объекта.

Для описания изменений состояний слабофор-мализованного объекта будем использовать понятие траектории — последовательная смена состояний объекта во времени. Оптимальной будем называть траекторию, обеспечивающую на протяжении изучаемого периода лучшие результаты относительно заданного общего критерия качества системы. Нахождение оптимальной траектории развития объекта и оптимальных наборов управляющих воздействий на него возможно на основе метода динамического программирования, в основе которого лежит принцип оптимальности Р. Беллмана [8]: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приво-

дило к оптимальному выигрышу на всех оставшихся шагах, включая данный. Опишем метод динамического программирования.

Рассмотрим состояние у объекта в динамике. Переход системы из состояния у' в состояние у,+1 осуществляется под воздействием вектора управления и' еО с компонентами и',...,и' в соответствии

и 1 ’ $

с функциональной зависимостью у'+1 = F'+1(у',и'). В начальный момент времени система находится в состоянии у0. На 1-м шаге под действием переменной управления и0 система переходит из состояния у0 в состояние у1, т. е. у1 = F1 (у0,и0). На последнем п -м шаге под действием переменной управления и”-1 система переходит из состояния у”-1 в состояние у”, т. е. у” = Fn (у”-1,и”-1). Обозначим показатель эффективности процесса управления в момент времени ' через Z, = ^(у'-1,и'-1). Учитывая требование аддитивности функции [9], показатель эффективности на всем промежутке времени можно записать

Z = Хg(yt 1 >и< 1) + f”(у”). Тогда задача

нахождения

оптимальной траектории формулируется как задача определения управлений и0,..., и” и значений после-

О ”

довательности у ,..., у , которые в совокупности приводят к максимальному (минимальному) значению критерия Z .

Рассмотрим возможность применения метода динамического программирования для иерархической структуры, заданной соотношением (1). Пусть в момент времени t система показателей описывается вектором х‘ = {х‘р}. Предполагается воздействие каждого х'р сразу на несколько показателей у. к1 нижнего уровня иерархии показателей, которые в свою очередь влияют на показатели верхних уровней иерархии. Тогда в качестве управления и1 будем рассматривать значения показателей х‘. Для описания изменений в структуре на каждом шаге введем переменную:

t I 1, если показатель р участвует в оценке критерия у.

р,ц...ы = | п 0

I О, иначе

С учетом введенных предположений получаем постановку. В начальный момент времени система находится в состоянии:

У0 = Fo Iх0 8°

ij...kl ij...kl p p,ij...

)

)

j = Fo.k I yo

ij... k ij... kl

yo = F01УІ)

yo = Fo I yo)

На 1-м шаге под действием переменной управления и0 система переходит из состояния у0 в состояние у1 , т. е.

У1 = F1 ,, IУ0 ,,,иo,8і : ,,)

ij kl ij kl ij kl p,ij kl

yij... k = Fij...k Iyij... k > yij...kl )

У = F I yo, уі. )

уі = Fo I yo, у! )

На последнем ” -м шаге под действием перемен-

4 ”-1

ной управления и система переходит из состояния у”-1 в состояние уп, т. е.

ЕГ” /-..”-1 „.”-1 5?” \

Уу...И = ^у...к1

, Л — ТТ” ( Л >”~1 Л,п \

Уц...к Гд...к\Уу...к > Уц...к1 ]

у” = Fn I У”-1, У”)

yo” = Fo I У”-1, У”1)

Показатель эффективности процесса управления в момент времени ' на нижнем уровне иерархии обозначим Z,jj И = g,(у^,и'-1). Эффективность управления для остальных уровней иерархии обозначим

7' ~'/..' - .'-1 \

Z ц...к = g (Уу...к > Уд...к ) .

Тогда эффективность управления в момент времени ' вычислим по формуле

^ (и'-1,у'-1 ) = а0^ (У0,У0-1) + ^а£(у',у'-1) + •••

•••+ЕЕа?'

^ ^ ] к I

где а и — коэффициент значимости показателя.

Решение задачи нахождения оптимальной траектории представляет собой набор векторов 5 = {(и0, у0 ),...,(и”-1, у”-1),(у”)} для каждого периода времени '. Поиск оптимальной траектории осуществляется за счет нахождения набора управляющих воздействий, обеспечивающего достижение оптимального значения показателя эффективности:

Z =Y,Zt (ut-1, /-1) + Fn (y”).

Обозначим Zt — максимальное значение критерия эффективности Z‘ для оптимального процесса, начинающегося в момент времени t, тогда поиск решения осуществляется согласно следующим рекуррентным соотношениям:

Zи = max Zn[un-1,yn-1 ],

U" EQ,n

Zn-1

V ’ u"-1£Qun_i L J

Zt

v ’ U eQ l j

u

Задача оптимизации слабоформализованного объекта с изменчивой иерархической структурой воз-

t=i

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

Пусть компетентность У0 определяется общекультурной компетенцией у1' и профессиональной компетенцией у2 . Общекультурная компетенция у\ оцени-

вается на основании компетенций у1'1, у[2 и у\ъ, а профессиональная — на основании у21 и у22. Пусть в каждый период времени студент осваивает одну базовую дисциплину А' и 1 дисциплину по выбору (В[ или В2), в этом случае управление и‘ заключается в выборе одной из дисциплин. Пусть оценки по каждой дисциплине могут принимать значения: 1 — дисциплина освоена и 0 — дисциплина не освоена. Определим оптимальную индивидуальную траекторию для четырех семестров, т. е. ' = 1,4 .

Для описания взаимосвязи дисциплин и частных компетенций зададим значения 8'р^ с помощью карты компетенций.

Таблица 1

Карта компетенций

Дисциплина у и у12 у13 у 21 У 22 Трудоемкость

1 семестр

Дисциплина А1 О 1 1 1 О 2

Дисциплина В О О 1 1 1 2

Дисциплина В1 О О 1 О 1 2

2 семестр

Дисциплина А2 1 1 1 4

Дисциплина В2 1 О 1 1 1 2

Дисциплина В22 1 О 1 О 1 2

3 семестр

Дисциплина А3 О 1 О 3

Дисциплина В3 1 О 1 1 1 2

Дисциплина В23 О О 1 1 1 2

4 семестр

Дисциплина А4 О 1 1 1 2

Дисциплина В^ О О 1 1 1 2

Дисциплина В24 О О 1 О 1 2

В качестве эффективности управления будем рассматривать компетентности. В соответствии с [10] уровень сформированности частных компетенций может быть вычислен по формуле:

у'+1 = У‘~ +

У ц У V

ъ

Р=1

. .. 2

рч р

к'

где — трудоемкость дисциплины р; к‘р1 — коли-

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

Уровень сформированности компетенций у,і рассчитывается на основании оценок частных компетенций:

у =ЪацУц

І =1

где аі — оценка значимости компетенции у.; у. — нормированное значение уІ; к. — количество частных компетенций уІ, формирующих компетенцию у].

Компетентность оценивается в соответствии с правилами, представленными в таблице 2.

Правила оценки компетентности

Таблица 2

—г

№ Общекультурные компетенции Профессиональные компетенции Оценка

1 >О.75 >О.85 3

2 >О.75 >О,5 2

3 >О,5 >О.8 2

4 >О.25 >О.3 1

5 <О.5 0

6 <О.5 0

Рассмотрим ее возможные варианты состояний в 4-м семестре.

Таблица 3

Траектории обучения в 4-м семестре

Траектория обучения У11 У12 У13 У 21 У 22 У1 У 2 У0 ЦФ

в; ^ в2 ^ в3 ^ В4 2,33 5,67 3,67 5,00 2,33 0,97 0,95 3 6,76

в; ^ в2 ^ в3 ^ в24 2,33 5,67 4,00 4,33 2,67 0,98 0,93 3 6,75

В1 ^ в2 ^ в23 ^ в14 1,83 5,67 3,83 5,17 2,50 0,94 1 3 6,76

в! ^ в2 ^ в23 ^ в24 1,83 5,67 4,17 4,50 2,83 0,96 0,97 3 6,76

в! ^ в22 ^ в3 ^ в14 2,50 5,67 3,83 4,50 2,50 1,00 0,90 3 6,75

в1 ^ в22 ^ в3 ^ в24 2,50 5,67 4,17 3,83 2,83 1,01 0,88 3 6,74

в1 ^ в22 ^ в23 ^ в14 2,00 5,67 4,00 4,67 2,67 0,98 0,93 3 6,76

в1 ^ в22 ^ в23 ^ в24 2,00 5,67 4,33 4,00 3,00 0,99 0,92 3 6,75

в1 ^ в^ ^ в3 ^ в14 2,33 5,67 4,00 4,33 2,67 1,01 0,88 3 6,75

в1 ^ в2 ^ в3 ^ в24 2,33 5,67 4,33 3,67 3,00 1,02 0,87 3 6,74

в1 ^ в2 ^ в23 ^ в4 1,83 5,67 4,17 4,50 2,83 0,99 0,92 3 6,76

в1 ^ в" ^ в23 ^ в24 1,83 5,67 4,50 3,83 3,17 1,00 0,90 3 6,75

в1 ^ в22 ^ в3 ^ в14 2,50 5,67 4,17 3,83 2,83 0,97 0,83 2 5,74

в1 ^ в22 ^ в3 ^ в24 2,50 5,67 4,50 3,17 3,17 0,99 0,82 2 5,74

в1 ^ в22 ^ в23 ^ в14 2,00 5,67 4,33 4,00 3,00 0,95 0,87 3 6,75

в2 ^ в22 ^ в23 ^ в24 2,00 5,67 4,67 3,33 3,33 0,96 0,85 2 5,74

Для каждой траектории определяем максималь- стре. Рассмотрим все возможные состояния системы

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

бор дисциплины для каждого состояния в 4-м семе-

Таблица 4

Траектория обучения в 3-м семестре

Траектория обучения У11 У12 У13 У 21 У 22 У1 У 2 У0 ЦФ

в1 ^ в2 ^ в3 2,33 5,00 2,33 3,67 1,67 0,58 0,58 1 12,34

в1 ^ в2 ^ в23 1,83 5,00 2,50 3,83 1,83 0,57 0,60 1 12,36

в1 ^ в22 ^ в3 2,50 5,00 2,50 3,17 1,83 0,60 0,55 1 12,33

в1 ^ в22 ^ в23 2,00 5,00 2,67 3,33 2,00 0,59 0,57 1 12,34

в1 ^ в2 ^ в3 2,33 5,00 2,67 3,00 2,00 0,61 0,53 1 13,33

в1 ^ в2 ^ в23 1,83 5,00 2,83 3,17 2,17 0,60 0,55 1 13,34

в2 ^ в22 ^ в3 2,50 5,00 2,83 2,50 2,17 0,56 0,50 1 12,32

в2 ^ в22 ^ в23 2,00 5,00 3,00 2,67 2,33 0,55 0,52 1 13,33

Рассмотрим все возможные состояния системы во 2-м семестре.

Таблица 5

Траектория обучения во 2-м семестре

Траектория обучения У11 У12 У13 У 21 У 22 У1 У 2 У0 ЦФ

в1 ^ в2 1,83 2,00 1,83 3,17 1,17 0,26 0,32 1 19,76

в1 ^ в22 2,00 2,00 2,00 2,67 1,33 0,27 0,30 1 19,74

в1 ^ в2 1,83 2,00 2,17 2,50 1,50 0,28 0,28 0 19,74

в\ ^ в22 2,00 2,00 2,33 2,00 1,67 0,22 0,27 0 19,66

Рассмотрим все возможные состояния системы в 1-м семестре.

Таблица 6

Траектория обучения в 1-м семестре

Траектория обучения У11 У12 УїЗ У 21 У 22 Уї У 2 У0 ЦФ

в; 0,00 0,б7 1,33 1,33 0,б7 0,07 0,10 0 23,93

в\ 0,00 0,б7 1,б7 0,б7 1,00 0,08 0,08 0 23,91

В результате решения оптимизационной задачи получаем оптимальную траекторию обучения

в; ^ в22 ^ в;3 ^ в;4.

Новым результатом работы является рассмотрение возможности применения метода динамического программирования для моделирования и оптимизации траектории слабоформализованного объекта с измен-

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

Библиографический список

1. Андронникова Н. Г., Бурков В. Н., Леонтьев С. В. Комплексное оценивание в задачах регионального управления. — М., 2002.

2. Новиков Д. А., Глотова Н. П. Модели и механизмы управления образовательными сетями и комплексами. — М., 2004.

3. Семенов И. Б., Чижов С. А., Полянский С. В. Комплексное оценивание в задачах управления социально-экономическими системами. — М., 1996.

4. Горбатков Д. Г. Алгоритм поиска рассогласованных оценок предпочтительности для метода анализа иерархий // Вестник университетского комплекса: сб. науч. тр. / под общ. ред. Н. В. Василенко. — Красноярск, 2005.

5. Чернышева Т. Ю., Захарова А. А., Мицель А.А. Иерархическая модель оценки состояния социально-экономического развития муниципального образования //

Известия Томского политехнического университета. — 2008. — Т. 313, № 6.

6. Пятковский О. И. Интеллектуальные компоненты автоматизированных информационных систем управления предприятием: монография. — Барнаул, 1999.

7. Томашев М. В. Прогнозирование востребованности специальности с использованием гибридной экспертной системы // Ползуновский вестник. — 2006. — № 1.

8. Беллан Р. Динамическое программирование. — М., 1960.

9. Черноусько Ф.Л. Динамическое программирование // Соросовский образовательный журнал. - 1998. - №2.

10. Алгазин Г. И., Чудова О. В. Информационные технологии комплексной оценки компетентности выпускника вуза // Вестник НГУ Сер.: Информационные технологии. — 2009. — Т. 7, вып. 3.