Los algoritmos naturales (o evolutivos) son una rama de la inteligencia artificial que modela los procesos de selección natural, mutación y reproducción.
Uno de los tipos de algoritmos naturales es el método del enjambre de abejas. Su propósito es concentrar más abejas en las áreas con mayor densidad de flores.
Las abejas inicialmente no saben nada sobre el campo, los obstáculos y la disposición de las flores. Empiezan su búsqueda desde posiciones aleatorias, con velocidades y direcciones aleatorias.
Cada abeja recuerda la posición donde encontró más flores y el área donde otras abejas encontraron más flores. A la hora de elegir una nueva dirección, la abeja irá entre estos dos puntos, dando preferencia a uno de ellos, según lo que sea más importante para él: la percepción personal o el reflejo social. Si en el proceso de movimiento se encuentra un lugar más floral, en el futuro se puede designar como el lugar de mayor concentración de flores, marcado por todo el enjambre.
La abeja puede volar más allá del objetivo. Para evitar que esto suceda, la velocidad de la abeja disminuye a medida que se acerca al lugar de concentración. Así, pronto todo el enjambre se reúne en lugares de flores.
La tarea consistía en planificar las vacaciones de los empleados con las siguientes condiciones:
- Hay preferencias por periodos vacacionales. Cambiar y cambiar estos períodos no es deseable. Algunas vacaciones tienen prohibido alterar.
- Los empleados pueden tener un número diferente de días de vacaciones.
- Cantidad mínima de vacaciones 7 días
- Una parte de las vacaciones debe ser de al menos 14 días.
- Cuantos menos días libres te vayas de vacaciones, mejor
- Más del 30% de los empleados no deberían estar ausentes en un departamento
Para la solución, usaremos un algoritmo genético y un algoritmo de enjambre de abejas. En el papel de las abejas habrá períodos de vacaciones (Clase de vacaciones). Cada período pertenece a un empleado (Clase Empl), cada empleado está en un departamento (Clase 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() { ... }
}Cada una de las clases contiene la función score (): la puntuación de los criterios del algoritmo, que se calcula en función de la lista de sanciones.
Las abejas (hojas) se pueden crear, mover, eliminar y mutar (cambiar de tamaño). Después de cargar las preferencias de los trabajadores en períodos libres, los días de vacaciones no asignados de los trabajadores se asignan al azar. Si el empleado ha designado más días, sus vacaciones se reducirán hasta que se lleven al estándar.
El problema se considera resuelto si se distribuyen todos los días de vacaciones no planificados, se cumplen las preferencias y se cumplen las demás condiciones del problema. En la vida real, rara vez satisface a todos, pero el algoritmo puede intentar encontrar la solución más óptima. Para hacer esto, en cada iteración, las clases evalúan su cumplimiento de las condiciones del problema y completan la lista de penalizaciones. Se elegirán más mutaciones dependiendo del número individual de penalizaciones y penalizaciones de clases adyacentes. Al final de cada movimiento de todas las abejas, se prueba la convergencia del algoritmo y se recuerda la solución más exitosa. La calidad de la solución se calcula en función de las sanciones de todas las abejas. Si no se encuentra una solución ideal, el algoritmo devolverá el resultado con la penalización más pequeña.
//
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 función findPenalties () es responsable de completar la lista de penalizaciones para todos los objetos swarm La
clase swarm también contiene una función de puntuación de calidad que se calcula a partir de las puntuaciones de todos los miembros del swarm.
Luego de mover todas las abejas se evalúa la convergencia del algoritmo, si no se logra el resultado deseado y no se supera el límite de iteración, se lanzará la siguiente iteración nextIteration (), en
nuestro caso mucho depende de la distribución inicial de vacaciones no planificadas, por lo que se decidió iniciar el enjambre en varios hilos paralelos y elegir el mejor ellos:
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();
El algoritmo no es difícil de implementar y se reduce principalmente a escribir una función de mutación. El uso del algoritmo de enjambre de abejas es apropiado en problemas de optimización para los que no existe una solución formalizada, y la enumeración de todas las opciones y combinaciones no es apropiada debido a su gran número.