الجدول الزمني المثالي للعطلة. الخوارزميات الطبيعية. سلوك سرب النحل

الخوارزميات الطبيعية (أو التطورية) هي فرع من فروع الذكاء الاصطناعي الذي يصمم عمليات الانتقاء الطبيعي والطفرة والتكاثر.



أحد أنواع الخوارزميات الطبيعية هو طريقة سرب النحل. والغرض منه هو تركيز المزيد من النحل في المناطق ذات الكثافة العالية من الأزهار.





لا يعرف النحل في البداية أي شيء عن الحقل والعقبات وترتيب الزهور. يبدأون البحث من مواقع عشوائية بسرعات واتجاهات عشوائية.



تتذكر كل نحلة المكان الذي وجدت فيه أكبر عدد من الزهور والمنطقة التي وجد فيها النحل الآخر معظم الزهور. عند اختيار اتجاه آخر ، ستنتقل النحلة بين هاتين النقطتين ، مع إعطاء الأفضلية لإحدى هاتين النقطتين ، اعتمادًا على ما هو أكثر أهمية بالنسبة لها: الإدراك الشخصي أو الانعكاس الاجتماعي. إذا تم العثور ، في عملية الحركة ، على مكان أكثر الأزهار ، في المستقبل يمكن تحديده كمكان لأعلى تركيز للزهور ، والذي يتميز بالسرب بأكمله.



يمكن للنحلة أن تطير بعد الهدف. لمنع حدوث ذلك ، تنخفض سرعة النحلة مع اقترابها من مكان التركيز. وهكذا ، سرعان ما يتجمع السرب كله في أماكن الزهور.







كانت المهمة تخطيط إجازات الموظفين بالشروط التالية:

1. هناك تفضيلات لفترات الإجازة. تغيير وتغيير هذه الفترات أمر غير مرغوب فيه. يحظر تغيير بعض الإجازات.
2. قد يكون للموظفين عدد مختلف من أيام الإجازة
3. الحد الأدنى للإجازة 7 أيام
4. يجب ألا يقل جزء من الإجازة عن 14 يومًا
5. كلما قل عدد أيام الإجازة التي تذهب إليها في إجازة ، كان ذلك أفضل
6. يجب ألا يتغيب أكثر من 30٪ من الموظفين عن إدارة واحدة

بالنسبة للحل ، سوف نستخدم خوارزمية جينية وخوارزمية سرب النحل. في دور النحل ستكون فترات الإجازات (Class Holyday). تنتمي كل فترة إلى موظف (Class Empl) ، كل موظف في قسم (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()    {        ...    }
}

تحتوي كل فئة على وظيفة النتيجة () - درجة معايير الخوارزمية ، والتي يتم احتسابها بناءً على قائمة العقوبات.



يمكن إنشاء النحل (المغادرة) ونقله وإزالته وتحويره (تغيير حجمه). بعد تحميل تفضيلات العمال في فترات الفراغ ، يتم تحديد أيام الإجازة غير المخصصة للعمال بشكل عشوائي. إذا كان الموظف قد حدد أيامًا أكثر ، فسيتم تقليل إجازاته حتى تصل إلى المستوى القياسي.



تعتبر المشكلة محلولة إذا تم توزيع جميع أيام الإجازة غير المخطط لها ، واستيفاء التفضيلات ، واستيفاء الشروط الأخرى للمشكلة. في الحياة الواقعية ، نادرًا ما يحدث ذلك لإرضاء الجميع ، لكن الخوارزمية يمكنها محاولة إيجاد الحل الأمثل. للقيام بذلك ، في كل تكرار ، تقوم الفصول بتقييم امتثالها لشروط المشكلة وملء قائمة العقوبات. سيتم اختيار المزيد من الطفرات اعتمادًا على العدد الفردي للعقوبات والعقوبات المفروضة على الفئات المجاورة. في نهاية كل حركة لجميع النحل ، يتم اختبار الخوارزمية للتقارب ويتم تذكر الحل الأكثر نجاحًا. يتم حساب جودة المحلول بناءً على عقوبات جميع النحل. إذا لم يتم العثور على حل مثالي ، فستعيد الخوارزمية النتيجة بأقل عقوبة.

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



، وفي حالتنا يعتمد الكثير على التوزيع الأولي للإجازات غير المخطط لها ، لذلك تقرر بدء السرب في عدة سلاسل متوازية واختيار أفضل واحد معهم:

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

الخوارزمية ليست صعبة التنفيذ وتتلخص بشكل أساسي في كتابة دالة طفرة. يعد استخدام خوارزمية سرب النحل مناسبًا في مشكلات التحسين التي لا يوجد لها حل رسمي ، ولا يعد تعداد جميع الخيارات والتركيبات مناسبًا بسبب عددها الضخم.