Электронный научный журнал

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

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В ОБРАЗОВАНИИ

Раздел: Эффективность и управление ресурсами с использованием ИИ

Журнал: Материалы Всероссийской научно-практической конференции «Искусственный интеллект в образовании. Современные достижения и перспективы применения: в генерации знаний, управлении, обучении, оценке результатов обучения и формировании компетенций обучающихся»

22 мая 2023 г.

Авторы: Решетникова Елена Васильевна , Решетников Михаил Максимович

Информационно-коммуникационные технологии в педагогическом образовании. http://infed.ru

_______________________________________________________________________

УДК 519.168

Е. В. Решетникова, М. М. Решетников

E. V. Reshetnikova, M. M. Reshetnikov

Решетникова Елена Васильевна, к. т. н., заведующий кафедрой математики, физики и математического моделирования, КГПИ КемГУ, г. Новокузнецк, Россия.

Решетников Михаил Максимович, студент, КГПИ КемГУ, г. Новокузнецк, Россия.

Reshetnikova Elena Vasilevna, Candidate of Technical Sciences, Associate Professor, Kuzbass Humanitarian Pedagogical Institute of Kemerovo State University, Novokuznetsk, Russia.

Reshetnikov Michael Maksimovich, student, Kuzbass Humanitarian Pedagogical Institute of Kemerovo State University, Novokuznetsk, Russia.

 

ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В ОБРАЗОВАНИИ

APPLICATION OF GENETIC ALGORITHMS IN THE FIELD OF EDUCATION

 

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

Annotation. The review of the processes in the field of education, the optimization of which is possible with the help of genetic algorithms. The features of the use of genetic algorithms by various researchers for solving the tasks of scheduling training, developing individual educational trajectories, creating intelligent learning systems.

Ключевые слова: генетические алгоритмы, образовательные процессы, учебное расписание, образовательные траектории.

Keywords: genetic algorithms, educational processes, curriculum, educational trajectories.

 

Генетические алгоритмы используются в тех сферах, где решаются задачи оптимизации [10]. Существует большое количество исследований, направленных на оптимизацию той или иной характеристики учебного процесса.

Наиболее распространенной для применения генетических алгоритмов в образовании является задача составления расписания. Особью в этом случае является вариант расписания. В [15] для школьного расписания в качестве гена предлагается брать тройку: учитель, класс и урок, причем изменяемой частью может быть только номер урока. Преподаватели вузов не привязаны к аудитории и предмету, поэтому в [1] для вузовского расписания в качестве гена выбрана тройка: дата, номер пары и номер аудитории. В [8] для составления вузовского расписания производится агрегирование занятий в блоки, особь составляется из двух хромосом (аудитории, временные интервалы), связанных взаимо-однозначным соответствием с блоками занятий. В [9] в особь предлагается добавить третью хромосому с преподавателями. В [18] для оптимизации расписания экзаменов в вузе хромосома представляется матрицей, строки – экзамены, столбцы – дни сессии, гены – ячейки матрицы, содержащие информацию об экзамене. В [7] хромосома также представляется матрицей, каждый столбец которой это расписание одной группы.

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

Наиболее популярным оператором скрещивания является кроссинговер – обмен случайно выбранными генами двух хромосом [10]. В более простых моделях [15] это не приводит к нарушению ограничений, при более сложном виде хромосомы, [8] требуется выполнять обмен генов, имеющих одинаковые позиции. Не менее важно для работы алгоритма правильно подобрать механизм отбора, например, в [18] родителей для кроссинговера отбирают по критерию наименьшей похожести.

Мутация касается изменения генов одной особи. В [8] мутации производятся изменением значений некоторых генов, на другие из допустимых. В [7] мутация это обмен генами внутри расписания одной группы. При матричном представлении хромосомы [18] мутация производится перераспределением генов по ячейкам таблицы, в [9] мутируют только гены, не удовлетворяющие ограничениям.

После применения генетических операторов необходимо произвести отбор особей в следующую популяцию. Часто исследователи используют стратегию «элитизма» [8, 9, 15], согласно которой лучшие особи переходят в следующее поколение без изменений. Остальные особи для перехода в следующую популяцию ранжируются по значению целевой функции.

Целью решения задачи составления расписания является готовое расписание занятий, удовлетворяющее всем ограничениям. Поэтому в качестве целевой функции обычно рассматривается некоторая арифметическая комбинация штрафных функций за нарушение ограничений, которая минимизируется [7, 8].

Ввиду того, что при составлении расписания возникает огромное количество требований от разных участников образовательного процесса, на результаты решения может накладываться большое количество различных ограничений, что не способствует поиску решения, поэтому ограничения делят на обязательные и желательные, вес которых при работе алгоритма учитывается по-разному. Все исследователи к обязательным требованиям относят отсутствие коллизий для групп и преподавателей [15, 21], также это может быть отсутствие окон у обучающихся [8, 15], ограничения на число пар в день и соответствие аудитории проводимому занятию [8, 21]. К желательным обычно относят пожелания преподавателей, переходы между корпусами, равномерность распределения нагрузки на обучающихся [8, 15, 21].

Однако некоторые исследователи все-таки вводят дополнительно целевую функцию, ей может являться время фактического проведения занятий [21], количество несовместимых «предметов» [7] или в [18] она составляется как сумма отношений среднего количества экзаменов в день и среднего окна между экзаменами к требуемым величинам.

На базе разработанных моделей составления расписания с использованием генетических алгоритмов написаны программные комплексы их реализующие [3, 7, 17, 18]. В то же время, как отмечают все исследователи, параметры расписания и ограничения настолько специфичны для каждого учебного учреждения, что использовать готовые решения без адаптации нельзя.

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

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

При проектировании адаптируемых к пользователю обучающих систем генетические алгоритмы используются для поиска наиболее эффективных сценариев обучения. Особью в этих алгоритмах является вариант сценария обучения. В [12] генетический алгоритм формирует учебный контент согласно оптимальному стилю обучения слушателя он-лайн курсов. В [6] на базе генетического алгоритма разработан программный комплекс для оптимизации процесса самостоятельной работы путем формирования плана обучения по представленным материалам. Разработке индивидуального курса для обучения посвящена работа [14], в которой для поиска оптимальной траектории обучения предлагается оптимизировать функционал отношения суммарного ожидаемого эффекта и суммарных временных затрат. В [4] генетический алгоритм используется для проектирования структуры учебного курса в системе дистанционного обучения.

Зачастую генетические алгоритмы используются как вспомогательные для применения других методов. В [5] для обучения нейронной сети интеллектуальной системы для определения уровня адаптивного восприятия объектом инклюзии субъектных характеристик предмета обучения, использован генетический алгоритм, хромосома которого состоит из объема подачи образовательного материала, его сложности и декомпозиции и др. В [16] генетический алгоритм формирует обучающую последовательность из ответов на вопросы для обучения нейросети системы компьютерного контроля знаний. Функция приспособленности обеспечивает репрезентативность обучающей выборки. В [2] генетический алгоритм использован для оптимизации начальных весов и пороговых значений нейросети, для оценки качества преподавания в колледже. В [13] генетический алгоритм использован для обучения параметров гибридной сети нейро-нечёткой системы, реализующей управление информационно-библиотечным фондом (ИБФ) вуза. В [12] представлен генетический алгоритм, использующийся для составления обучающей выборки для методов машинного обучения для прогнозирования и анализа успеваемости студентов.

Исследователи успешно применяют генетические алгоритмы и для оптимизации других процессов в образовании. В [20] производится оптимизация учебных планов при сетевом обучении для рационального распределения студентов по вузам с учетом их предпочтения и организационными возможностями. Аргументами целевой функции являются коэффициенты удовлетворенности студентов. В [19] генетические алгоритмы применяются для оптимального распределения учебной нагрузки кафедры. В [11] для разработки стратегии внедрения инфраструктуры виртуальных рабочих столов в ИТ-инфраструктуру вуза, генетический алгоритм производит выбор серверных ресурсов.

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

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

  1. Агафонов, А. А. Применение генетического алгоритма для решения задачи составления расписания в вузе / А. А. Агафонов. – Текст : электронный // Молодежь и современные Информационные технологии : Сборник трудов XII Международной научно-практической конференции студентов, аспирантов и молодых ученых, Томск, 12–14 ноября 2014 года / Национальный исследовательский Томский политехнический университет. Том 1. – Томск : Национальный исследовательский Томский политехнический университет, 2014. – С. 386-387. – URL : https://www.elibrary.ru/item.asp?id=23110050 (дата обращения : 03.05.2023).
  2. Аль-Дулаими, О. Х. З. Измерение качества образования в вузах с помощью генетических алгоритмов и нейронных сетей / О. Х. З. Аль-Дулаими. – Текст : электронный // Перспективы науки, 2023. – № 1(160). – С. 10-16. – URL : https://www.elibrary.ru/item.asp?id=50734478 (дата обращения : 03.05.2023).
  3. Асвад, Ф. М. А. Схема работы генетического алгоритма для составления расписания для вузов Ирака / Ф. М. А. Асвад. – Текст : электронный // Научный альманах, 2015. – № 8 (10). – С. 730-732. – URL : https://www.elibrary.ru/item.asp?id=24277236 (дата обращения : 03.05.2023).
  4. Беломойцев, Д. Е. Разработка генетических операторов алгоритма составления учебных курсов индивидуального содержания / Д. Е. Беломойцев. – Текст : электронный // Научно-технический вестник Брянского государственного университета, 2017. – № 2. – С. 190-195. – URL : https://www.elibrary.ru/item.asp?id=36706484 (дата обращения : 03.05.2023).
  5. Зиновьев, В. И. Применение генетических алгоритмов в развитии инклюзивного образования / В. И. Зиновьев. – Текст : электронный // ДИНАМИКА ВЗАИМООТНОШЕНИЙ РАЗЛИЧНЫХ ОБЛАСТЕЙ науки в СОВРЕМЕННЫХ УСЛОВИЯХ : сборник статей Международной научно-практической конференции, Уфа, 13 ноября 2017 года. Том Часть 1. – Уфа : Общество с ограниченной ответственностью "Аэтерна", 2017. – С. 172-174. – URL : https://www.elibrary.ru/item.asp?id=30650447 (дата обращения : 03.05.2023).
  6. Иванов, П. Б. Автоматическое формирование учебных треков с использованием генетических алгоритмов / П. Б. Иванов. – Текст : электронный // Нейрокомпьютеры и их применение : XVII Всероссийская научная конференция. Тезисы докладов, Москва, 19 марта 2019 года. – Москва : Московский государственный психолого-педагогический университет, 2019. – С. 35-36. – URL : https://www.elibrary.ru/item.asp?id=41207812 (дата обращения : 03.05.2023).
  7. Каширина, И. Л. Применение генетических алгоритмов для составления расписания учебных занятий / И. Л. Каширина, А. Л. Ухин. – Текст : электронный // Научный вестник Воронежского государственного архитектурно-строительного университета. Серия: Управление строительством, 2015. – № 1(7). – С. 229-235. – URL : https://www.elibrary.ru/item.asp?id=23082743 (дата обращения : 03.05.2023).
  8. Композиционный генетический алгоритм составления расписания учебных занятий / Ю. С. Кабальнов, Л. И. Шехтман, Г. Ф. Низамова, Н. А. Земченкова. – Текст : электронный // Вестник Уфимского государственного авиационного технического университета, 2006. – Т. 7. – № 2. – С. 99-109. – URL : https://www.elibrary.ru/item.asp?id=9289623 (дата обращения : 03.05.2023).
  9. Коробкин, А. А. Использование агрегативного генетического алгоритма для составления расписания / А. А. Коробкин. – Текст : электронный // Вестник Воронежского государственного технического университета, 2009. – Т. 5. – № 11. – С. 184-186. – URL : https://www.elibrary.ru/item.asp?id=12928383 (дата обращения : 03.05.2023).
  10. Курейчик, В. В. Теория эволюционных вычислений / В. В. Курейчик, В. М. Курейчик, С. И. Родзин. – Москва : ООО Издательская фирма "Физико-математическая литература", 2012. – 260 с. – ISBN 978-5-9221-1390-8. – Текст : электронный. – URL : https://www.elibrary.ru/item.asp?id=24056633 (дата обращения : 03.05.2023).
  11. Маковий, К. А. Использование генетического алгоритма для выбора серверных ресурсов при внедрении инфраструктуры виртуальных рабочих столов в вузе / К. А. Маковий, Ю. В. Хицкова, А. И. Шашкин. – Текст : электронный // Актуальные проблемы прикладной математики, информатики и механики : сборник трудов Международной научно-технической конференции, Воронеж, 18–20 декабря 2017 года / Воронежский государственный университет. – Воронеж : Издательство "Научно-исследовательские публикации"; Общество с ограниченной ответственностью "Вэлборн", 2017. – С. 257-263. – URL : https://www.elibrary.ru/item.asp?id=32578088 (дата обращения : 03.05.2023).
  12. Ошкин, А. В. Обзор подходов и методов прикладного использования генетических алгоритмов в образовательной сфере / А. В. Ошкин, В. А. Павлов. – Текст : электронный // Педагогическое мастерство : Материалы XLV Международной научной конференции, Казань, 20–23 марта 2023 года / Под редакцией И. Г. Ахметова [и др.]. – Казань : Общество с ограниченной ответственностью "Издательство Молодой ученый", 2023. – С. 57-70. – URL : https://www.elibrary.ru/item.asp?id=50369401 (дата обращения : 03.05.2023).
  13. Попкова, А. А. Генетический алгоритм обучения нейро-нечёткой сети "Управление ИБФ вуза" / А. А. Попкова. – Текст : электронный // Хроники объединенного фонда электронных ресурсов Наука и образование, 2010. – Т. 1. – № 1(8). – С. 89. – URL : https://www.elibrary.ru/item.asp?id=22564808 (дата обращения : 03.05.2023).
  14. Симонова, А. Г. Разработка электронного курса обучения с использованием генетических алгоритмов / А. Г. Симонова. – Текст : электронный // Современные проблемы горно-металлургического комплекса. Наука и производство : Материалы девятнадцатой Всероссийской научно-практической конференции с международным участием, Старый Оскол, 07 декабря 2022 года. – Старый Оскол: Национальный исследовательский технологический университет "МИСиС", 2023. – С. 505-510. – URL : https://www.elibrary.ru/item.asp?id=50497114 (дата обращения : 03.05.2023).
  15. Тимешов, А. С. Формирование модели генетического алгоритма для решения задачи составления расписания занятий в школе / А. С. Тимешов, М. В. Раскатова. – Текст : электронный // Международный журнал информационных технологий и энергоэффективности. – 2022. – Т. 7, № 2(24). – С. 32-39. – URL : https://www.elibrary.ru/item.asp?id=49100907 (дата обращения : 03.05.2023).
  16. Титов, А. М. Генетический алгоритм формирования обучающей последовательности для нейросетевой технологии компьютерного контроля знаний / А. М. Титов. – Текст : электронный // Ученые записки Российского государственного социального университета. – 2008. – № 5(61). – С. 155-157. – URL : https://www.elibrary.ru/item.asp?id=22968318 (дата обращения : 03.05.2023).
  17. Федькин, Е. Автоматизации процесса составления расписания занятий на основе генетического алгоритма / Е. Федькин, С. Кумаргажанова, И. Увалиева. – Текст : электронный // Вестник Академии гражданской авиации. – 2019. – № 3(14). – С. 91-100. – URL : https://www.elibrary.ru/item.asp?id=42704786 (дата обращения : 03.05.2023).
  18. Частикова, В. А. Генетический подход к решению проблемы формирования расписания экзаменов в высших учебных заведениях / В. А. Частикова, А. С. Бахтин. Текст : электронный // Электронный сетевой политематический журнал "Научные труды КубГТУ", 2021. – № 1. – С. 120-130. – URL : https://www.elibrary.ru/item.asp?id=45589755 (дата обращени : 03.05.2023).
  19. Чернышенко, С. В. Распределение учебной нагрузки кафедры как реализация генетического алгоритма / С. В. Чернышенко, Ю. Ю. Шаталова. – Текст : электронный // Математическое и программное обеспечение интеллектуальных систем (MPZIS-2007) : Тези доповiдей, Днепропетровск, 14–16 ноября 2007 года. – Днепропетровск: Днепропетровский национальный университет им. Олеся Гончара, 2007. – С. 208-209. – URL : https://www.elibrary.ru/item.asp?id=42761610 (дата обращения : 03.05.2023).
  20. Чугунов, А. П. Применение генетического алгоритма поддержки принятия решений при управлении индивидуальными учебными планами студентов / А. П. Чугунов, В. Ю. Столбов. – Текст : электронный // Современные наукоемкие технологии, 2017. – № 5. – С. 157-160. – URL : https://www.elibrary.ru/item.asp?id=29334608 (дата обращения : 03.05.2023).
  21. Яндыбаева, Н. В. Генетический алгоритм в задаче оптимизации учебного расписания вуза / Н. В. Яндыбаева. – Текст : электронный // Современные наукоемкие технологии, 2009. – № 11. – С. 97-98. – URL : https://www.elibrary.ru/item.asp?id=12993841 (дата обращения : 03.05.2023).
PDF