Algoritmos naturais (ou evolutivos) são um ramo da inteligência artificial que modela os processos de seleção natural, mutação e reprodução.
Um dos tipos de algoritmos naturais é o método do enxame de abelhas. Seu objetivo é concentrar mais abelhas nas áreas com maior densidade de flores.
As abelhas inicialmente não sabem nada sobre o campo, os obstáculos e o arranjo das flores. Eles começam sua busca em posições aleatórias, com velocidades e direções aleatórias.
Cada abelha lembra a posição onde encontrou mais flores e a área onde as outras abelhas encontraram mais flores. Ao escolher outra direção, a abelha irá passar entre esses dois pontos, dando preferência a um deles, dependendo do que for mais importante para ela: percepção pessoal ou reflexo social. Se, no processo de movimentação, for encontrado um local mais floral, no futuro poderá ser designado como o local de maior concentração de flores, marcado por todo o enxame.
A abelha pode voar além do alvo. Para evitar que isso aconteça, a velocidade da abelha diminui à medida que se aproxima do local de concentração. Assim, logo todo o enxame se reúne em locais de flores.
A tarefa era planejar as férias dos funcionários com as seguintes condições:
- Existem preferências por períodos de férias. Mudar e mudar esses períodos é indesejável. Algumas férias estão proibidas de se alterar.
- Os funcionários podem ter um número diferente de dias de férias
- Quantidade mínima de férias 7 dias
- Uma parte das férias deve ser de pelo menos 14 dias
- Quanto menos dias de férias você sair de férias, melhor
- Mais de 30% dos funcionários não devem estar ausentes em um departamento
Para a solução, usaremos um algoritmo genético e um algoritmo de enxame de abelhas. No papel das abelhas haverá períodos de férias (Aula Dia das Bruxas). Cada período pertence a um funcionário (Class Empl), cada funcionário está em um departamento (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() { ... }
}Cada uma das classes contém a função score () - a pontuação para os critérios do algoritmo, que é calculada com base na lista de penalidades.
As abelhas (sair) podem ser criadas, movidas, removidas e transformadas (redimensionadas). Após carregar as preferências dos trabalhadores nos períodos livres, os dias de férias não alocados dos trabalhadores são atribuídos aleatoriamente. Se o funcionário designou mais dias, suas férias serão reduzidas até que sejam normalizadas.
O problema é considerado resolvido se todos os dias de férias não planejados forem distribuídos, as preferências forem atendidas e as outras condições do problema forem atendidas. Na vida real, raramente acontece para agradar a todos, mas o algoritmo pode tentar encontrar a solução ideal. Para isso, a cada iteração, as classes avaliam o cumprimento das condições do problema e preenchem a lista de penalidades. Outras mutações serão escolhidas dependendo do número individual de penalidades e penalidades de classes adjacentes. Ao final de cada movimento de todas as abelhas, o algoritmo é testado quanto à convergência e a solução de maior sucesso é lembrada. A qualidade da solução é calculada com base nas penalidades de todas as abelhas. Se uma solução ideal não for encontrada, o algoritmo retornará o resultado com a menor penalidade.
//
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;
}
}A função findPenilities () é responsável por preencher a lista de penalidades para todos os objetos de enxame. A
classe de enxame também contém uma função de pontuação de qualidade que é calculada a partir das pontuações de todos os membros do enxame.
Após movimentar todas as abelhas, avalia-se a convergência do algoritmo, se o resultado desejado não for alcançado e o limite de iteração não for ultrapassado, a próxima iteração nextIteration () será lançada. No
nosso caso, muito depende da distribuição inicial de férias não planejadas, por isso decidiu-se iniciar o enxame em vários threads paralelos e escolher o melhor eles:
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();
O algoritmo não é difícil de implementar e se resume principalmente a escrever uma função de mutação. O uso do algoritmo Bee Swarm é apropriado em problemas de otimização para os quais não há solução formalizada, e a enumeração de todas as opções e combinações não é apropriada devido ao seu grande número.