ДонНТУ   Портал магистров

МУЛЬТИАГЕНТНЫЙ ПОДХОД К ЗАДАЧЕ КОЛЛЕКТИВНОГО ВЫБОРА КОМПРОМИССНОГО ВАРИАНТА РАСПРЕДЕЛЕНИЯ СТУДЕНТОВ НА ФИРМЫ

Федяев О.И. Мультиагентный подход к задаче коллективного выбора компромиссного варианта распределения студентов на фирмы // В сборнике: Электронное обучение в непрерывном образовании 2018. V Международная научно-практическая конференция. — 2018. — С. 310-317.

О.И. Федяев

ДНР, Донецк, ДонНТУ
E-mail: fedyaev@donntu.org

Аннотация

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

Ключевые слова: трудоустройство студентов; агенты; мультиагентная система; роли агентов; имитационная модель; сотрудничество агентов.

Введение

Оценка эффективности процессов подготовки специалистов и их трудоустройство очень важна для анализа и управления сложной и инерционной системой образования, в рамках которой решаются задачи составления правильных государственных стандартов, организации эффективного учебного процесса, распределения выпускников на предприятия в соответствии с полученной квалификацией и требованиями заказчиков. Перечисленные задачи являются трудно формализуемыми и поэтому не могут быть решены традиционными математическими методами. Кроме того, участники рассматриваемых процессов взаимосвязаны и образуют распределенную, неоднородную и интеллектуальную систему [1], [2].

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

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

Модель динамического процесса трудоустройства студентов на фирмы (предприятия) представлена двумя группами взаимодействующих искусственных агентов:

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

\( t_{n,m} = \varphi_n(c_m), \)

где \( t_{n,m} \) – оценка привлекательности m-ой фирмы для n-го студента; \( \varphi_n \) – многомерная функция субъективной оценки студентом \( x_n \) привлекательности фирмы \( f_m \); \( c_m \) – вектор значений социально-экономических характеристик, т. е. социальный пакет, который предлагается студенту на фирме \( f_m \). Компоненты вектора \( c_m \) определяют размер зарплаты, продолжительность рабочего дня, форму собственности, обеспеченность жильем, возможность удаленной работы и другие показатели, значения которых характеризуют условия работы на m-ой фирме.

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

\( g_{n,m} = \sum_{j=1}^{J_m} \mu_{m,j}(z_n), \)

где \( z_n \) – вектор значений уровней знаний и умений, которыми обладает студент \( x_n \) (в частном случае – по одной дисциплине); \( \mu_{m,j} \) – многомерная функция субъективного оценивания m-ой фирмой способность студента \( x_n \) решать j-ое задание, предлагаемое фирмой; \( g_{n,m} \) – оценка профессиональных компетенций n-го студента, выставленная m-ой фирмой; \( J_m \) – количество тестовых заданий у m-ой фирмы (\( 1 \le j \le J_m \)).

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

Задача 1. Она относится к классу обратных задач и заключается в нахождении функций \( \varphi_n (\cdot) \) и \( \mu_{m,j}(\cdot) \). Функция \( \varphi_n (\cdot) \) отражает мнение конкретного студента или группы студентов и описывает зависимость привлекательности фирмы от предлагаемого фирмой социального пакета. Вторая функция \( \mu_{m,j}(\cdot) \) имитирует поведение работников фирмы, занимающихся подбором кадров, при тестировании уровня компетенции студентов в зависимости от их знаний и умений по профилю деятельности фирмы. Поскольку обе функции связывают качественные данные, то для их конструирования применена нейронно-сетевая методология как универсальное средство функциональной аппроксимации. Для обучения нейросетевых моделей функций использовались данные реально проводимых опросов нескольких десятков респондентов. Решение этой задачи не рассматривается в данной статье.

Задача 2. Эта задача относится к проблеме коллективного выбора с учетом взаимных требований сторон, которая типична для задач многокритериального принятия решений [1], [2]. В содержательной форме эта задача состоит в распределении студентов на фирмы так, чтобы отклонения от планов приема отобранных лучших студентов были минимальными, а желания студентов были максимально учтены.

Рассмотрим математическую постановку данной задачи. Каждый студент с учетом своих желаний создает для себя список фирм \( Q_n = \{q_{n,1}, q_{n,2}, ..., q_{n,M}\}, q_{n,m} \in F \), который показывает очередность посещения им фирм при поиске работы, т. е. в каком порядке студент будет обходить фирмы. Для этого списки \( Q = \{Q_1, Q_2, ..., Q_N\} \), входящие во множество, упорядочены по убыванию оценок привлекательности фирм, полученных с помощью функции \( \varphi_n (\cdot) \):

\( t_{n,k}(q_{n,i}) \ge t_{n,l}(q_{n,i+1}) \) если \( q_{n,i} = f_k \) , \( q_{n,i+1} = f_l \).

Поскольку один студент не может одновременно посетить все фирмы, то трудоустройство всех студентов происходит за несколько циклов посещений ими выбранных фирм. На каждом цикле для каждой фирмы формируется очередной поток (множество) \( R_m = \{r_{m,i} | r_{m,i} \in X, 1 \le i \le I\} \) из студентов \( x_n \), которые хотели бы устроиться на данную фирму, где \( I \) – размер группы претендентов в данном потоке; \( \bigcap_{m=1}^{M} R_m = \varnothing \); \( \varnothing \) – пустое множество (рис. 1).

Структурная модель динамической системы трудоустройства студентов на фирмы

Рис. 1. Структурная модель динамической системы трудоустройства студентов на фирмы

Перед каждым новым циклом посещений все потоки в множестве \( R = \{R_1, R_2, ..., R_M\} \) обновляются. Например, в очередной \( k \)-й поток соискателей на фирму \( R_m \) попадают те студенты \( x_n \), у которых первыми в очереди \( Q_n \) стоит фирма \( f_m \), т. е. \( q_{n,1} = f_m \) (\( 1 \le n \le N \)). Целое число \( k \) также можно трактовать как порядковый номер цикла посещения студентами фирм.

Пусть планы приема студентов на фирмы задаются множеством \( L = \{l_1, l_2, ..., l_M\} \), где \( l_m \) – количество вакансий на m-ой фирме (\( 0 \le l_m \le N \)). Введем множество последовательностей \( Y = \{Y_1, Y_2, ..., Y_M\} \), в котором каждая \( Y_m \) определяет список кандидатов, отобранных в ходе тестирования студентов на фирме \( f_m \). Каждая последовательность \( Y_m \) представляет собой множество студентов, упорядоченное по убыванию полученной ими оценки по тестированию. В каждой последовательности (упорядоченном множестве) \( Y_m = \{y_{m,1}, y_{m,2}, ..., y_{m,N}\} \) элементы \( y_{m,n} \) состоят из студентов, входящих во множество \( X \), т. е. \( y_{m,n} \in X \). Из этого следует, что \( g_{k,m}(y_{m,i}) \ge g_{l,m}(y_{m,i+1}) \), если \( y_{m,i} = x_k \), \( y_{m,i+1} = x_l \), \( 1 \le i \le N-1 \). В целом \( Y \) - это мультимножество, т. е. каждый студент \( x_n \) может успешно пройти тестирование на нескольких фирмах и таким образом принадлежать нескольким последовательностям \( Y_n \).

Кроме того, студенты и фирмы могут устанавливать для себя пороговые значения соответственно по уровню привлекательности фирмы и уровню компетентности студента в виде множеств \( P = \{p_1, p_2, ..., p_N\} \) и \( D = \{d_1, d_2, ..., d_M\} \), где \( p_n \) – минимально-допустимое значение привлекательности фирмы у n-го студента; \( d_m \) – минимально-допустимый уровень компетентности для соискателей на m-ой фирме.

На каждом \( k \)-м цикле отбора студентов каждая фирма \( f_m \) – принимает на входе соответствующий поток студентов \( R_m = \{r_{m,i} | r_{m,i} \in X\} \), которые желают работать на фирме. Фирмы в своих списках кандидатов \( Y_m \) всем элементам \( y_{m,n} \in X \) из пересечения множеств \( R_m \cap Y_m \) приписывают приоритет, равный номеру цикла \( k \). Условимся считать, что чем меньше значение \( k \), тем выше приоритет студента \( x_n \) в последовательности \( Y_m \). Обозначим через \( p(y_{m,n}) \) значение приоритета студента \( x_n \), находящегося на месте \( y_{m,n} \) в последовательности \( Y_m \). В ходе циклического процесса все студенты-кандидаты в мультимножестве \( Y \) получат свои значения приоритетов.

Таким образом, задача квазиоптимального распределения студентов на фирмы сводится к такой расстановке элементов \( y_{m,n} \in X \) в последовательностях \( Y_1, Y_2, ..., Y_M \), где

\( Y_m = \{x_n | (x_n \in X) \& (g_{n,m}(x_n) \ge d_m) \& (t_{n,m}(f_m) \ge p_n) \} \),

при которой минимизируются, во-первых, невыполнение заявок фирм на молодых специалистов с учетом сохранения ранжирования отобранных кандидатов по уровню их квалификации \( g_{n,m}(\cdot) \) и, во-вторых, сумма всех значений приоритетов \( p(y_{m,n}) \) во множестве \( Y \) (оно должно быть уже не мультимножеством), гарантирующая рациональную расстановку студентов на основе введенных приоритетов \( p(y_{m,n}) \), выражающих желания студентов через функцию \( t_{n,m}(\cdot) \):

\( \sum_{m=1}^{M} (|Y_m| - l_m) \to \min_{y_{m,n} \in X, l_m \le |Y_m|} \)

\( \sum_{m=1}^{M} \sum_{n=1}^{s_m} p(y_{m,n}) \to \min \) ,

\( \bigcap_{m=1}^{M} Y_m = \varnothing \),

где \( |Y_m| \) – мощность множества \( Y_m \); \( \cap \) – операция пересечения множеств; \( \varnothing \) – пустое множество; \( s_m \) – количество кандидатов, принятых на \( m \)-ю фирму (\( s_m \le l_m \)).

2. Координируемое сотрудничество агентов

Моделирующая система трудоустройства студентов на фирмы является динамической, распределенной, интеллектуальной по характеру деятельности ее компонент, что обуславливает возможность ее моделирования методами теории многоагентных систем. Один из подходов к решению второй задачи (трудоустройство студентов на фирмы) может быть реализован средствами мультиагентных технологий в рамках виртуальной кафедры [4], [5]. Для облегчения взаимодействия между основными Агентами-студентами и Агентами-фирм вводится дополнительный Агент-координатор, который реализует роль одного из сотрудников кафедры (например, заведующего кафедрой) (см. рис. 2 в полной версии работы). При координируемом сотрудничестве основные агенты могут передать Координатору некоторые функции согласования своих действий для того, чтобы он выступил в роли арбитра в разрешении возникающих конфликтов (например, в нахождении компромисса между интересами студентов и фирм).

В частности рассматриваемую на последнем этапе взаимодействия агентов задачу поиска оптимального распределения студентов со всеми ее ограничениями можно сформулировать как задачу о назначениях и ее решение возложить на Агента-координатора.

3. Простое сотрудничество агентов

В этом подходе поставленная задача решается на основе убеждений, желаний и намерений основных агентов (Студентов и Фирм) без помощи по координации их действий. Взаимодействие основных агентов реализует динамический процесс распределения студентов на фирмы. Состояния Агента-студента и Агента-фирмы будем определять переменными \( v_n \) и \( u_m \):

\( v_n = \begin{cases} 0, \text{ студент ищет работу} \\ 1, \text{ студент принят на работу} \\ -1, \text{ студенту отказано в работе} \end{cases} \)

\( u_m = \begin{cases} 0, \text{ фирма имеет вакансии} \\ 1, \text{ фирма не имеет вакансий} \end{cases} \)

Перед началом моделирования устанавливаются исходные значения всех параметров многоагентной системы: \( k=0, v_n=0, u_m=0 \), а также \( Y \) и \( L \). Тогда динамику агентно-ориентированного моделирования процесса трудоустройства студентов в общем виде можно описать в терминах структурной схемы на рис. 1. Искомыми параметрами являются новые списки множества \( Y = \{Y_1, Y_2, ..., Y_M\} \), определяющие итоговое распределение студентов по фирмам. Один цикл взаимодействия между группами агентов Студентов и Фирм определяется следующими функциями \( \Phi \):

\( k = 1, 2, ... \) , пока не наступит равновесие между агентами, определяемое условием

\( (\forall f_m \in F, u_m^{k+1} = 1) \lor (\forall x_n \in X, v_n^{k+1} = \mp 1) \lor (\forall Q_n \in Q, Q_n^{k+1} = \varnothing) \).

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

Заключение

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

Список литературы

  1. Тельнов Ю.Ф., Данилов А.В., Казаков В.А. Применение многоагентной технологии для решения образовательных задач в информационно-образовательном пространстве // Инжиниринг предприятий и управление знаниями. Сб. науч. тр. 18-й научно-практической конференции (ИПи УЗ-2015, 21-24 апреля 2015 г., Москва, МЭСИ). - М.: МЭСИ, 2015. С. 451-457.
  2. Федяев О.И. Модель системы подготовки и трудоустройства специалистов на основе программных агентов с нейросетевой архитектурой // Пятнадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2016, Труды конференции. В 3-х томах. Т.2. – Смоленск: Универсум, 2016.
  3. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. - М.: Эдиториал УРСС, 2002. – 352 с.
  4. Андрейчиков А.В., Андрейчикова О.Н. Интеллектуальные информационные системы: Учебник. – М.: Финансы и статистика, 2006. – 424 с.
  5. Федяев О.И. Анализ и прогнозирование процесса трудоустройства молодых специалистов с помощью мультиагентной имитационной модели / Федяев О.И., Лукина Ю.Ю., Стропалов А.С. // Труды конференции ИАИ-2013, КПИ, Киев, 2013. - С. 47-53.
↑