Natürliche (oder evolutionäre) Algorithmen sind ein Zweig der künstlichen Intelligenz, der die Prozesse der natürlichen Selektion, Mutation und Reproduktion modelliert.
Eine der Arten natürlicher Algorithmen ist die Bienenschwarmmethode. Ziel ist es, mehr Bienen in Gebieten mit der höchsten Blumendichte zu konzentrieren.
Bienen wissen zunächst nichts über das Feld, Hindernisse und die Anordnung der Blumen. Sie beginnen ihre Suche an zufälligen Positionen mit zufälligen Geschwindigkeiten und Richtungen.
Jede Biene erinnert sich an die Position, an der sie die meisten Blumen gefunden hat, und an den Bereich, an dem andere Bienen die meisten Blumen gefunden haben. Bei der Wahl einer weiteren Richtung bewegt sich die Biene zwischen diesen beiden Punkten und bevorzugt einen von ihnen, je nachdem, was für sie wichtiger ist: persönliche Wahrnehmung oder sozialer Reflex. Wenn im Verlauf der Bewegung ein blumigerer Ort gefunden wird, kann dieser in Zukunft als der Ort mit der höchsten Blumenkonzentration bezeichnet werden, der durch den gesamten Schwarm gekennzeichnet ist.
Die Biene kann am Ziel vorbei fliegen. Um dies zu verhindern, nimmt die Geschwindigkeit der Biene ab, wenn sie sich dem Konzentrationsort nähert. So versammelt sich bald der ganze Schwarm an Blumenorten.
Die Aufgabe bestand darin, Mitarbeiterferien unter folgenden Bedingungen zu planen:
- Es gibt Präferenzen für Urlaubszeiten. Das Ändern und Verschieben dieser Zeiträume ist unerwünscht. Einige Ferien dürfen nicht geändert werden.
- Mitarbeiter haben möglicherweise eine andere Anzahl von Urlaubstagen
- Mindesturlaubszeit 7 Tage
- Ein Teil des Urlaubs muss mindestens 14 Tage dauern
- Je weniger freie Tage Sie in den Urlaub fahren, desto besser
- Mehr als 30% der Mitarbeiter sollten nicht in einer Abteilung abwesend sein
Für die Lösung werden wir einen genetischen Algorithmus und einen Bienenschwarmalgorithmus verwenden. In der Rolle der Bienen werden Ferienzeiten (Klasse Holyday) sein. Jede Periode gehört einem Mitarbeiter (Class Empl), jeder Mitarbeiter ist in einer Abteilung (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() { ... }
}Jede der Klassen enthält die Funktion score () - die Bewertung für die Kriterien des Algorithmus, die anhand der Liste der Strafen berechnet wird.
Bienen (Blätter) können erstellt, verschoben, entfernt und mutiert (in der Größe geändert) werden. Nach dem Laden der Präferenzen der Arbeitnehmer in freien Zeiträumen werden nicht zugewiesene Urlaubstage der Arbeitnehmer nach dem Zufallsprinzip zugewiesen. Wenn der Mitarbeiter mehr Tage festgelegt hat, werden seine Ferien reduziert, bis sie auf den Standard gebracht werden.
Das Problem gilt als gelöst, wenn alle außerplanmäßigen Urlaubstage verteilt sind, Präferenzen erfüllt sind und die anderen Bedingungen des Problems erfüllt sind. Im wirklichen Leben gefällt es selten jedem, aber der Algorithmus kann versuchen, die optimalste Lösung zu finden. Zu diesem Zweck bewerten die Klassen bei jeder Iteration die Einhaltung der Problembedingungen und füllen die Liste der Strafen aus. Eine weitere Mutation wird in Abhängigkeit von der individuellen Anzahl der Strafen und Strafen benachbarter Klassen gewählt. Am Ende jeder Bewegung aller Bienen wird der Algorithmus auf Konvergenz getestet und die erfolgreichste Lösung wird gespeichert. Die Qualität der Lösung wird anhand der Strafen aller Bienen berechnet. Wenn keine ideale Lösung gefunden wird, gibt der Algorithmus das Ergebnis mit der geringsten Strafe zurück.
//
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;
}
}Die Funktion findPenalties () ist dafür verantwortlich, die Liste der Strafen für alle Schwarmobjekte zu füllen. Die Schwarmklasse
enthält auch eine Qualitätsbewertungsfunktion, die aus den Bewertungen aller Schwarmmitglieder berechnet wird.
Nach dem Bewegen aller Bienen wird die Konvergenz des Algorithmus bewertet. Wenn das gewünschte Ergebnis nicht erreicht wird und das Iterationslimit nicht überschritten wird, wird die nächste Iteration nextIteration () gestartet. In
unserem Fall hängt vieles von der anfänglichen Verteilung der ungeplanten Ferien ab. Daher wurde beschlossen, den Schwarm in mehreren parallelen Threads zu starten und den besten auszuwählen Sie:
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();
Der Algorithmus ist nicht schwer zu implementieren und läuft hauptsächlich darauf hinaus, eine Mutationsfunktion zu schreiben. Die Verwendung des Bienenschwarmalgorithmus eignet sich für Optimierungsprobleme, für die es keine formalisierte Lösung gibt, und die Aufzählung aller Optionen und Kombinationen ist aufgrund ihrer großen Anzahl nicht geeignet.