Один из способов решения многоцелевой оптимизации - это найти решение, которое удовлетворяет одной цели, а затем использовать local search, чтобы попытаться удовлетворить остальные ограничения.
Например, если вы игнорируете ограничение, которое вы хотели бы свести к минимуму количество используемых классов, то вы можете рассматривать это как вариант в Stable Marriage Problem (или взвешенной двухпартийной проблеме сопоставления графа) - это имеет приятное свойство, которое она может быть решена в полиномиальное время. Ваш вариант по проблеме наиболее похож на проблему «больницы/жители» (назначение многих жителей нескольким больницам на основе предпочтений).
Это оставит вас с несколькими классами, в которых учатся всего несколько учеников, поэтому вы выполните локальный поиск, чтобы удовлетворить ограничение «свести к минимуму количество классов» (если вы правильно сформулировали алгоритм «Стабильный брак», то вы должны иметь уже удовлетворил «ни один класс не превышает 25 студентов» ограничений) - оттуда у вас есть два варианта:
Сортировка классов с наименьшим количеством для большинства студентов и закрыть классы с наименьшим количеством студентов, переназначения выселенных студентов к оставшиеся классы
Продолжайте брать стул предпочтения вмятин и сортировать классы от наименее предпочтительных до наиболее предпочтительных (так что если у вас есть 5 учеников в классе, которые назначили ему вес 10, то сначала вы должны закрыть класс с 10 учениками, которые назначили ему вес 2).
Вы бы затем выполнить еще один локальный поиск, чтобы удовлетворить учитель часов ограничений - вы бы выполнить „учитель не может научить больше, чем X часов“ поиск после выполнения „минимизировать число классов“ поиска , так как последняя оптимизация упростит выполнение прежней оптимизации.
Если результирующий алгоритм достаточно быстр, вы можете рандомизировать его и запустить его несколько десятков раз, сохранив наилучший результат. Например, вместо того, чтобы закрыть класс с наименьшим количеством студентов первого, случайным образом выбрать класс, чтобы закрыть (вес выбора, так что он обычно выбирает наименьший класс - это полностью случайный поиск не будет хорошо работать)
Пришло возможно, вы обнаружите, что одно из ваших ограничений вызывает множество конфликтов, например при соблюдении ограничений часов преподавателей вы обнаружите, что вам приходится перестраивать большой процент учащихся.Если это произойдет, измените порядок привязки, так что выполнение часов учителей выполняется на втором или даже первом проходе, а не на третьем проходе.
Ограничение класса-типа может фактически принадлежать вершине списка ограничений (даже если оно имеет низкий приоритет), в зависимости от его спецификаций. Например, у вас может быть требование, чтобы класс макияжа возникал перед любым другим классом (так, например, у студента с классом во вторник может быть класс макияжа в понедельник и догонять до его обычного класса); хотя ограничение класса макияжа имеет низкий приоритет, оно имеет самые жесткие требования, и поэтому ему нужно сначала заказать его.
Вы говорите «что они наиболее предпочтительны», но это может быть их второй или третий выбор, не так ли? Если я правильно вас понимаю, вы балансируете потенциально конфликтующие ограничения. Как вы оцениваете стоимость ухода от идеального выбора для определенного ограничения? – hatchet
Да, это может быть их второй или третий выбор. Это похоже на проблему стабильного брака. За исключением того, что мы группируем 25 человек в 1 классе вместо того, чтобы сопоставлять только 2 человека – hvu89
Это вы имеете в виду? «планирование учеников» http://www.unitime.org/uct_students.php – Karussell