Естественные (или эволюционные) алгоритмы – это направление в искусственном интеллекте, которое моделирует процессы естественного отбора, мутации и воспроизводства.
Одним из видов естественных алгоритмов является метод роя пчел. Его целью является концентрация бОльшего количества пчел в областях с наибольшей плотностью цветов.
Пчелы изначально ничего не знают о поле, преградах и расположении цветов. Они начинают поиск со случайных позиций, со случайными скоростями и направлениями.
Каждая пчела помнит позицию, где она нашла наибольшее количество цветов и области где другие пчелы нашли наибольшее количество цветов. При выборе дальнейшего направления пчела направится между двумя этими точками отдав предпочтение одной из них в зависимости от того, что для нее важнее: личное восприятие или социальный рефлекс. Если в процессе движения будет найдено более цветочное место, в будущем оно может быть назначено как место наибольшей концентрации цветов, отмеченное всем роем.
Пчела может пролететь мимо цели. Чтобы этого не произошло, скорость пчелы уменьшается с приближением к месту концентрации. Таким образом, вскоре весь рой собирается в цветочных местах.
Стояла задача спланировать отпуска работников со следующими условиями:
- Имеются предпочтения по периодам отпусков. Изменение и сдвиг этих периодов нежелателен. Некоторые отпуска запрещено изменять.
- У работников может быть разное количество дней отпуска
- Минимальные размер отпуска 7 дней
- Одна из частей отпуска должна быть не меньше 14 дней
- Чем меньше выходных попадает на отпуск – тем лучше
- В одном отделе не должно отсутствовать более 30% работников
Для решения будем использовать генетический алгоритм и алгоритм роя пчел. В роли пчел будут периоды отпусков (Класс Holyday). Каждый период принадлежит работнику (Класс Empl), каждый работник находится в отделе (Класс Dep).
//структура класса отпуска
class Holiday
{
public List<Penalty> penalties;
public Empl empl;
public DateTime start;
public DateTime end;
...
/// оценка от -1 до 100. -1 - противоречет условиям.
/// 100 - полностью соответсвует целевой функции
/// 100-50 - попадает в целевой интервал
/// 50-0 - не попадает в целевой интервал, чем дальше от интервала, тем меньше значение
public sbyte score() { ... }
}
//структура класса работника
internal class Empl:IEquatable<Empl>
{
private readonly int id;
public int daysNorm;
public string fio;
public Dep dep;
public readonly List<Penalty> penalties;
public int cntPlannedDays { get {
int result = 0;
foreach (Holiday h in holidays)
result += (h.end - h.start).Days + 1;
return result;
} }
public List<Holiday> holidays;
public sbyte score() { ... }
}
//структура класса отдела
class Dep
{
/// максимальное к-во одновременно отсутствующих работников
public int maxDepAbcenceCnt { get {... } }
/// возвращает список интервалов доступных для планирования
public List<Tuple<DateTime,DateTime>> GetFreeIntervals() {... }
public string name;
public List<Empl> empls;
public List<Penalty> penalties;
public sbyte score() { ... }
}Каждый из классов содержит функцию score() – оценка критериям алгоритма, которая вычисляется исходя из списка штрафов penaltyes.
Пчелы (отпуска) могут создаваться, сдвигаться, удаляться и мутировать (изменять свой размер). После загрузки предпочтений работников в свободные периоды случайным образом назначаются не распределенные дни отпуска работников. Если работник назначил больше дней, его отпуска будут уменьшаться пока не будут приведены к нормативу.
Задача считается решенной, если все не запланированные дни отпусков распределены, соблюдены предпочтения и выполняются остальные условия задачи. В реальной жизни угодить всем получается редко, но алгоритм может попробовать найти самое оптимальное решение. Для этого на каждой итерации классы оценивают свое соответствие условиям задачи и заполняют список штрафов. В зависимости от индивидуального количества штрафов и штрафов смежных классов будет выбрана дальнейшая мутация. В конце каждого перемещения всех пчел проходит проверка на сходимость алгоритма и запоминается самое удачное решение. Качество решения вычисляется исходя из штрафов всех пчел. Если идеальное решение не будет найдено алгоритм выдаст результат с наименьшим штрафом.
//структура класса роя
class Swarm
{
public void toXlsx(string path){…}
public List<Dep> deps;
public List<Empl> empls;
public List<Holiday> holidays;
public sbyte _score = -127;
//вычисление штрафов
public void findPenalties(){…}
public void nextIteration()
{
resetScore();
findPenalties();
foreach (Empl e in empls)
{
foreach (Penalty p in e.penalties)
{
switch (p.name)
{
case "PenaltyAboveNormalHolidayCnt": //запланировано много дней
…
break;
case "PenaltyNo14DaysPart"://одна из частей должна быть не менее 14 дней
…
break;
case "PenaltyBellowNormalHolidayCnt": //запланировано мало дней
…
break;
default:
Log.WriteLine("Не задан алогритм для штрафа " + p.name);
break;
}
}
}
}
//функция оценки качества
public sbyte score(bool reCalculate=false)
{
if (_score != -127)
return _score;
if (reCalculate)
resetScore();
float resultH = 0,resultD=0,resultE=0;
findPenalties();
foreach (Holiday h in holidays)
{
resultH += (float)h.score();
}
resultH = resultH / (float)holidays.Count;
foreach (Dep d in deps)
{
resultD += (float)d.score();
}
resultD = resultD / (float)deps.Count;
foreach (Empl e in empls)
{
resultE += (float)e.score();
}
resultE = resultE / (float)empls.Count;
_score = (sbyte)((resultH+resultD+resultE)/3);
return _score;
}
public bool isConverged()
{
if (_score == -127)
return false;
findPenalties();
foreach (Dep d in deps)
{
if (d.penaltyes.Count > 0)
return false;
}
foreach(Empl e in empls)
{
if (e.penaltyes.Count > 0)
return false;
}
foreach(Holiday h in holidays)
{
if (h.penalties.Count > 0)
return false;
}
return true;
}
}Функция findPenalties() отвечает за заполнение списка штрафов всех объектов роя
Класс роя так же содержит функцию оценки качества, которая вычисляется из оценок всех элементов роя.
После перемещения всех пчел происходит оценка сходимости алгоритма, если искомый результат не достигнут и лимит итераций не превышен будет запущена следующая итерация nextIteration()
В нашем случае много зависит от первоначального распределения незапланированных отпусков, поэтому было решено запустить рой в несколько параллельных потоков и выбрать лучший из них:
List<int> list = new List<int>();
for (int i = 1; i < CONST.SWAM_SIZE; i++)
list.Add(i);
int bestScore = 0;
Parallel.ForEach(list, new ParallelOptions() { MaxDegreeOfParallelism = 10 }, x => {
Swarm iterSwarm = new Swarm(swarm);
int currIter = 0;
while (true)
{
if (iterSwarm.isConverged())
{
Console.WriteLine($"Алгоритм сошелся за {currIter} итераций score={iterSwarm.score()}");
break;
}
if (currIter >= CONST.MAX_ITER_CNT)
{
Console.WriteLine("Решение не найдено");
break;
}
iterSwarm.nextIteration();
currIter++;
lock(isLock)
{
if (iterSwarm.score(true) > bestScore)
{
bestScore = iterSwarm.score();
bestSwarm = new Swarm(iterSwarm);
}
}
}
});
Console.WriteLine($"Source swarm score={swarm.score()}");
Console.WriteLine("");
Console.WriteLine($"Result bestSwarm={bestSwarm.score()}");
bestSwarm.toXlsx();
Алгоритм не сложен в реализации и сводится, в основном, к написанию функции мутации. Использование алгоритма роя пчел уместно в задачах оптимизации, для которых нет формализованного решения, а перебор всех вариантов и комбинаций не уместен в силу их огромного количества.
