🧜🏼 😃 🙍🏾 完美的假期时间表。自然算法。蜂群行为 👩🏽‍🎓 💂 🦎

自然（或进化）算法是人工智能的一个分支，可以对自然选择，突变和繁殖的过程进行建模。

蜂群方法是自然算法的类型之一。其目的是将更多的蜜蜂集中在花朵密度最高的区域。

蜜蜂最初对田野，障碍和鲜花的安排一无所知。他们从具有随机速度和方向的随机位置开始搜索。

每只蜜蜂会记住发现最多花朵的位置以及其他蜜蜂发现最多花朵的区域。当选择其他方向时，蜜蜂会在这两个点之间移动，优先选择其中之一，这取决于对它更重要的是：个人感知或社交反应。如果在移动过程中发现了花朵较多的地方，将来可以将其指定为花朵最多的地方，并以整个群为标志。

蜜蜂可以飞过目标。为了防止这种情况的发生，蜜蜂的速度会随着其接近集中位置而降低。因此，很快整个群聚集在花的地方。

任务是在以下条件下计划员工休假：

假期有优惠。更改和转移这些时间段是不可取的。某些假期被禁止更改。
员工可能有不同的休假天数
最少休假7天
假期的一部分必须至少14天
休假天数越少越好
一个部门不应缺勤超过30％

对于解决方案，我们将使用遗传算法和蜂群算法。蜜蜂的角色将是休假期间（Classic Holyday）。每个期间都属于一个员工（班级Empl），每个员工都在一个部门中（班级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()    {        ...    }
}

每个类都包含score（）函数-算法标准的得分，该得分基于罚金清单计算。

可以创建，移动，删除和变异蜜蜂（叶子）（调整大小）。在空闲时段加载工人的偏好之后，将随机分配未分配的工人休假日。如果员工指定了更多的工作日，则他的假期将减少，直到达到标准为止。

如果分配了所有计划外的休假日，满足了偏好并且满足了该问题的其他条件，则认为该问题已解决。在现实生活中，这种情况很少会取悦所有人，但是该算法可以尝试找到最佳解决方案。为此，在每次迭代中，这些类都会评估其对问题条件的符合性，并填写罚款清单。将根据惩罚的数量和相邻类别的惩罚来选择进一步的突变。在所有蜜蜂每次运动结束时，都要对该算法进行收敛性测试，并记住最成功的解决方案。解决方案的质量是根据所有蜜蜂的罚款计算得出的。如果找不到理想的解决方案，该算法将以最小的代价返回结果。

//  
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;
    }
}

findPenalties（）函数负责填充所有群集对象的惩罚列表，群集

类还包含一个质量得分函数，该函数是根据所有群集成员的分数计算得出的。

移动所有的蜜蜂后，算法的收敛性进行评估，如果没有达到预期的结果和迭代限制不超过，下一次迭代nextIteration（）将launched.In

我们的情况，在很大程度上依赖于计划外休假的初次分配，所以决定开始在多个并行线程群，并选择最好的一个他们：

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();

该算法并不难实现，并且主要归结为编写变异函数。蜂群算法的使用适用于没有形式化解决方案的优化问题，并且由于数量众多，所有选项和组合的枚举都不适用。

完美的假期时间表。自然算法。蜂群行为

More articles: