РЕШЕНИЯ ЗАДАЧ СТАБИЛЬНОГО РАСПРЕДЕЛЕНИЯ В ОБРАЗОВАТЕЛЬНЫХ УЧРЕЖДЕНИЯХ

Во все времена неотъемлемой частью общества всегда было образование, но с развитием научно-технического прогресса были выявлены ряд специфических проблем. Рассмотрим две из них: распределение студентов на практику и распределение студентов по научным руководителям. Эти две проблемы при сравнительно небольшом количестве входных данных легко решаются человеком, но при больших объемах информации – для человека эти задачи становятся практически нерешаемыми. Для решения обозначенных проблем за основу возьмем алгоритм стабильного распределения, освященный в статье Ллойдом Шепли и Элвином Ротом «теорию стабильного распределения и практики устройства рынков», номинированная на нобелевскую премию в 2012 году.

Схема работы алгоритма выглядит следующим образом [3].

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

Далее объекты из первой группы соотносят с первыми объектами из списка предпочтений.

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

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

Если в первой группе не остается нераспределенных объектов, то работа алгоритма завершается, а результат распределения называют стабильным [1].

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

Рассмотрим алгоритм в разрезе поставленных задач. В роли объектов из первой группы будут выступать студенты, а в роли объектов из второй группы – научные руководители/предприятия.

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

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

Будем рассматривать два варианта фитнесс-функции, которые дают наиболее точные результаты.

Числовая фитнесс-функция.

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

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

Критериальная фитнесс-функция.

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

Отличительная особенность

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

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

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

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

Критериальную фитнесс-функция более рационально применять для распределения, где важную роль играет качество индивидуального объекта.

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

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

Заключение.

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