Natural (or evolutionary) algorithms are a branch of artificial intelligence that models the processes of natural selection, mutation, and reproduction.
One of the types of natural algorithms is the bee swarm method. Its purpose is to concentrate more bees in areas with the highest density of flowers.
Bees initially do not know anything about the field, obstacles and the arrangement of flowers. They start their search from random positions, with random speeds and directions.
Each bee remembers the position where it found the most flowers and the area where other bees found the most flowers. When choosing a further direction, the bee will go between these two points, giving preference to one of them, depending on what is more important for it: personal perception or social reflex. If in the process of movement a more floral place is found, in the future it can be designated as the place of the highest concentration of flowers, marked by the entire swarm.
The bee can fly past the target. To prevent this from happening, the speed of the bee decreases as it approaches the place of concentration. Thus, soon the whole swarm gathers in flower places.
The task was to plan employee vacations with the following conditions:
- There are preferences for vacation periods. Changing and shifting these periods is undesirable. Some vacations are prohibited from altering.
- Employees may have a different number of vacation days
- Minimum vacation amount 7 days
- One part of the vacation must be at least 14 days
- The fewer days off you go on vacation, the better
- More than 30% of employees should not be absent in one department
For the solution, we will use a genetic algorithm and a bee swarm algorithm. In the role of bees will be periods of vacations (Class Holyday). Each period belongs to an employee (Class Empl), each employee is in a department (Class 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() { ... }
}Each of the classes contains the score () function - the score for the algorithm criteria, which is calculated based on the list of penalties.
Bees (leave) can be created, moved, removed and mutated (resized). After loading the preferences of workers in free periods, unallocated vacation days of workers are randomly assigned. If the employee has appointed more days, his holidays will be reduced until they are brought to the standard.
The problem is considered solved if all unscheduled vacation days are distributed, preferences are met, and the other conditions of the problem are met. In real life, it rarely happens to please everyone, but the algorithm can try to find the most optimal solution. To do this, at each iteration, the classes evaluate their compliance with the problem conditions and fill out the list of penalties. Further mutation will be chosen depending on the individual number of penalties and penalties of adjacent classes. At the end of each movement of all bees, the algorithm is tested for convergence and the most successful solution is remembered. The quality of the solution is calculated based on the penalties of all bees. If an ideal solution is not found, the algorithm will return the result with the smallest penalty.
//
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;
}
}The findPenalties () function is responsible for filling the list of penalties for all swarm objects. The swarm
class also contains a quality score function that is calculated from the scores of all swarm members.
After moving all the bees, the convergence of the algorithm is evaluated, if the desired result is not achieved and the iteration limit is not exceeded, the next iteration nextIteration () will be launched.In
our case, a lot depends on the initial distribution of unplanned vacations, so it was decided to start the swarm in several parallel threads and choose the best one them:
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();
The algorithm is not difficult to implement and boils down mainly to writing a mutation function. The use of the bee swarm algorithm is appropriate in optimization problems for which there is no formalized solution, and the enumeration of all options and combinations is not appropriate due to their huge number.