Les algorithmes naturels (ou évolutifs) sont une branche de l'intelligence artificielle qui modélise les processus de sélection naturelle, de mutation et de reproduction.
L'un des types d'algorithmes naturels est la méthode de l'essaim d'abeilles. Son but est de concentrer davantage d'abeilles dans les zones à plus forte densité de fleurs.
Au départ, les abeilles ne savent rien du champ, des obstacles et de la disposition des fleurs. Ils commencent leur recherche à partir de positions aléatoires, avec des vitesses et des directions aléatoires.
Chaque abeille se souvient de la position où elle a trouvé le plus de fleurs et de la zone où les autres abeilles ont trouvé le plus de fleurs. Lors du choix d'une autre direction, l'abeille ira entre ces deux points, en privilégiant l'un d'entre eux, en fonction de ce qui est le plus important pour elle: la perception personnelle ou le réflexe social. Si, dans le processus de mouvement, on trouve un endroit plus floral, il peut à l'avenir être désigné comme le lieu de la plus forte concentration de fleurs, marqué par tout l'essaim.
L'abeille peut voler au-delà de la cible. Pour éviter que cela ne se produise, la vitesse de l'abeille diminue à mesure qu'elle s'approche du lieu de concentration. Ainsi, bientôt tout l'essaim se rassemble dans les lieux fleuris.
La tâche consistait à planifier les vacances des employés dans les conditions suivantes:
- Il y a des préférences pour les périodes de vacances. Changer et déplacer ces périodes n'est pas souhaitable. Certaines vacances ne peuvent pas modifier
- Les employés peuvent avoir un nombre différent de jours de vacances
- Montant minimum des vacances 7 jours
- Une partie des vacances doit durer au moins 14 jours
- Moins vous partez en vacances, mieux c'est
- Plus de 30% des employés ne devraient pas être absents d'un service
Pour la solution, nous utiliserons un algorithme génétique et un algorithme d'essaim d'abeilles. Dans le rôle des abeilles, il y aura des périodes de vacances (classe de vacances). Chaque période appartient à un salarié (Classe Employ), chaque salarié est dans un département (Classe 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() { ... }
}Chacune des classes contient la fonction score () - le score pour les critères de l'algorithme, qui est calculé sur la base de la liste des pénalités.
Les abeilles (feuilles) peuvent être créées, déplacées, supprimées et mutées (redimensionnées). Après avoir chargé les préférences des travailleurs pendant les périodes libres, les jours de vacances non alloués des travailleurs sont attribués au hasard. Si l'employé a nommé plus de jours, ses vacances seront réduites jusqu'à ce qu'elles soient ramenées à la norme.
Le problème est considéré comme résolu si tous les jours de vacances imprévus sont distribués, les préférences sont satisfaites et les autres conditions du problème sont remplies. Dans la vraie vie, cela arrive rarement à plaire à tout le monde, mais l'algorithme peut essayer de trouver la solution la plus optimale. Pour ce faire, à chaque itération, les classes évaluent leur conformité aux conditions du problème et remplissent la liste des pénalités. Une mutation supplémentaire sera choisie en fonction du nombre individuel de pénalités et de pénalités des classes adjacentes. À la fin de chaque mouvement de toutes les abeilles, l'algorithme est testé pour la convergence et la solution la plus réussie est mémorisée. La qualité de la solution est calculée en fonction des pénalités de toutes les abeilles. Si une solution idéale n'est pas trouvée, l'algorithme retournera le résultat avec la plus petite pénalité.
//
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;
}
}La fonction findPenalties () est chargée de remplir la liste des pénalités pour tous les objets de l'essaim. La
classe d' essaim contient également une fonction de score de qualité qui est calculée à partir des scores de tous les membres de l'essaim.
Après avoir déplacé toutes les abeilles, la convergence de l'algorithme est évaluée, si le résultat souhaité n'est pas atteint et que la limite d'itération n'est pas dépassée, la prochaine itération nextIteration () sera lancée.Dans
notre cas, beaucoup dépend de la distribution initiale des vacances non planifiées, il a donc été décidé de démarrer l'essaim dans plusieurs threads parallèles et de choisir le meilleur. leur:
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();
L'algorithme n'est pas difficile à mettre en œuvre et se résume principalement à l'écriture d'une fonction de mutation. L'utilisation de l'algorithme de l'essaim d'abeilles est appropriée dans les problèmes d'optimisation pour lesquels il n'y a pas de solution formalisée, et l'énumération de toutes les options et combinaisons n'est pas appropriée en raison de leur grand nombre.