Генетический алгоритм: группировка студентов без знания точного количества групп

Question

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

Я хотел бы знать, будет ли работать генетический алгоритм. Гены хромосомы будут представлять одного учащегося и его назначение в класс. Часть фитнес-функции будет использовать все ограничения (максимальный размер группы, минимальный размер группы). Как я понял для применения генетического алгоритма, мне нужно знать количество групп, что не ясно в моем случае. Есть идеи?

Answer 1

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

Я предлагаю, чтобы ваши индивидуумы («хромосомы») были списком групп для нового поколения. Чтобы сэкономить время, ваш генератор должен давать только жизнеспособных детей: тех, которые соответствуют требованиям размера группы. Любой ребенок, который не удовлетворяет этим требованиям, должен быть пропущен и заменен.

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

Достаточно ли этого, чтобы вы пошли в полезном направлении?

---

Обновление на комментарий пользователя:

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

Я бы начал исследовать «удобное» количество хромосом, возможно, количество групп, умноженное на квадратный метр (количество новых студентов). В зависимости от временных ограничений, я думаю, что от 20 до 200 хромосом будет полезно для вас. Ваши критические показатели успеха - это то, как часто он находит отличное решение и сколько времени вы тратите на его поиск.