Идеальный график отпусков. Естественные алгоритмы. Поведение роя пчёл
Естественные (или эволюционные) алгоритмы – это направление в искусственном интеллекте, которое моделирует процессы естественного отбора, мутации и воспроизводства.
Одним из видов естественных алгоритмов является метод роя пчел. Его целью является концентрация бОльшего количества пчел в областях с наибольшей плотностью цветов.
Пчелы изначально ничего не знают о поле, преградах и расположении цветов. Они начинают поиск со случайных позиций, со случайными скоростями и направлениями.
Каждая пчела помнит позицию, где она нашла наибольшее количество цветов и области где другие пчелы нашли наибольшее количество цветов. При выборе дальнейшего направления пчела направится между двумя этими точками отдав предпочтение одной из них в зависимости от того, что для нее важнее: личное восприятие или социальный рефлекс. Если в процессе движения будет найдено более цветочное место, в будущем оно может быть назначено как место наибольшей концентрации цветов, отмеченное всем роем.
Пчела может пролететь мимо цели. Чтобы этого не произошло, скорость пчелы уменьшается с приближением к месту концентрации. Таким образом, вскоре весь рой собирается в цветочных местах.
Стояла задача спланировать отпуска работников со следующими условиями:
- Имеются предпочтения по периодам отпусков. Изменение и сдвиг этих периодов нежелателен. Некоторые отпуска запрещено изменять.
- У работников может быть разное количество дней отпуска
- Минимальные размер отпуска 7 дней
- Одна из частей отпуска должна быть не меньше 14 дней
- Чем меньше выходных попадает на отпуск – тем лучше
- В одном отделе не должно отсутствовать более 30% работников
Для решения будем использовать генетический алгоритм и алгоритм роя пчел. В роли пчел будут периоды отпусков (Класс Holyday). Каждый период принадлежит работнику (Класс Empl), каждый работник находится в отделе (Класс Dep).
Каждый из классов содержит функцию score() – оценка критериям алгоритма, которая вычисляется исходя из списка штрафов penaltyes.
Пчелы (отпуска) могут создаваться, сдвигаться, удаляться и мутировать (изменять свой размер). После загрузки предпочтений работников в свободные периоды случайным образом назначаются не распределенные дни отпуска работников. Если работник назначил больше дней, его отпуска будут уменьшаться пока не будут приведены к нормативу.
Задача считается решенной, если все не запланированные дни отпусков распределены, соблюдены предпочтения и выполняются остальные условия задачи. В реальной жизни угодить всем получается редко, но алгоритм может попробовать найти самое оптимальное решение. Для этого на каждой итерации классы оценивают свое соответствие условиям задачи и заполняют список штрафов. В зависимости от индивидуального количества штрафов и штрафов смежных классов будет выбрана дальнейшая мутация. В конце каждого перемещения всех пчел проходит проверка на сходимость алгоритма и запоминается самое удачное решение. Качество решения вычисляется исходя из штрафов всех пчел. Если идеальное решение не будет найдено алгоритм выдаст результат с наименьшим штрафом.
Функция findPenalties() отвечает за заполнение списка штрафов всех объектов роя
Класс роя так же содержит функцию оценки качества, которая вычисляется из оценок всех элементов роя.
После перемещения всех пчел происходит оценка сходимости алгоритма, если искомый результат не достигнут и лимит итераций не превышен будет запущена следующая итерация nextIteration()
В нашем случае много зависит от первоначального распределения незапланированных отпусков, поэтому было решено запустить рой в несколько параллельных потоков и выбрать лучший из них:
Алгоритм не сложен в реализация и сводится, в основном, к написанию функции мутации. Использование алгоритма роя пчел уместно в задачах оптимизации, для которых нет формализованного решения, а перебор всех вариантов и комбинаций не уместен в силу их огромного количества.
А вы не могли бы привести пример результата? Например, составить таблицу отпусков для воображаемой компании?
Кирилл, спасибо за Ваш вопрос, перешлем автору статьи, уточним. К сожалению, оперативно ответить не сможем.
Хорошо, спасибо :)