🎣 👏🏼 🎸 完璧な休暇のスケジュール。自然なアルゴリズム。蜂の群れの行動 🙏 🧛🏾 🌭

自然な（または進化的な）アルゴリズムは、自然な選択、突然変異、および複製のプロセスをモデル化する人工知能のブランチです。

自然なアルゴリズムのタイプの1つは、蜂の群れ法です。その目的は、花の密度が最も高い地域により多くの蜂を集中させることです。

蜂は最初、畑、障害物、花の配置について何も知りません。彼らはランダムな位置から、ランダムな速度と方向で検索を開始します。

各蜂は、最も多くの花を見つけた位置と、他の蜂が最も多くの花を見つけた領域を覚えています。さらに方向を選択すると、蜂はこれら2つのポイントの間を行き来し、個人的な認識または社会的反射という、より重要なものに応じて、どちらか一方を優先します。移動の過程でより花の多い場所が見つかった場合、将来的には、群れ全体でマークされた、花が最も集中する場所として指定できます。

蜂はターゲットを越えて飛ぶことができます。これを防ぐために、蜂が集中する場所に近づくにつれて、蜂の速度は低下します。したがって、すぐに群れ全体が花の場所に集まります。

タスクは、次の条件で従業員の休暇を計画することでした。

休暇期間の好みがあります。これらの期間を変更およびシフトすることは望ましくありません。一部の休暇は変更が禁止されています。
従業員の休暇日数は異なる場合があります
最小休暇日数7日
休暇の一部は少なくとも14日でなければなりません
休暇に行く休日が少なければ少ないほど良い
従業員の30％以上が1つの部門に欠席してはなりません

解決策として、遺伝的アルゴリズムと蜂の群れアルゴリズムを使用します。ミツバチの役割は休暇期間（クラスホリデー）になります。各期間は従業員（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()    {        ...    }
}

各クラスには、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();

アルゴリズムは実装するのが難しくなく、主に突然変異関数を書くことに要約されます。蜂の群れアルゴリズムの使用は、正式な解決策がない最適化の問題に適切であり、すべてのオプションと組み合わせの列挙は、それらの数が膨大であるため適切ではありません。

完璧な休暇のスケジュール。自然なアルゴリズム。蜂の群れの行動

More articles: