Algoritme alam (atau evolusi) adalah cabang kecerdasan buatan yang memodelkan proses seleksi alam, mutasi, dan reproduksi.
Salah satu jenis algoritma alam adalah metode bee swarm. Tujuannya adalah untuk memusatkan lebih banyak lebah di area dengan kepadatan bunga tertinggi.
Lebah awalnya tidak mengetahui apapun tentang bidang, rintangan dan penataan bunganya. Mereka memulai pencarian mereka dari posisi acak, dengan kecepatan dan arah acak.
Setiap lebah mengingat posisi di mana ia menemukan bunga paling banyak dan area tempat lebah lain menemukan bunga paling banyak. Saat memilih arah lebih jauh, lebah akan pergi di antara dua titik ini, memberikan preferensi kepada salah satunya, tergantung pada apa yang lebih penting untuknya: persepsi pribadi atau refleks sosial. Jika, dalam proses pergerakan, tempat yang lebih berbunga ditemukan, di masa mendatang tempat tersebut dapat ditetapkan sebagai tempat dengan konsentrasi bunga tertinggi, yang ditandai dengan seluruh gerombolan.
Lebah bisa terbang melewati target. Untuk mencegah hal ini terjadi, kecepatan lebah berkurang saat mendekati tempat konsentrasinya. Jadi, segera seluruh kawanan berkumpul di tempat-tempat bunga.
Tugasnya adalah merencanakan liburan karyawan dengan ketentuan sebagai berikut:
- Ada preferensi untuk periode liburan. Mengubah dan menggeser periode ini tidak diinginkan. Beberapa liburan dilarang diubah
- Karyawan mungkin memiliki jumlah hari libur yang berbeda
- Jumlah liburan minimal 7 hari
- Satu bagian dari liburan harus setidaknya 14 hari
- Semakin sedikit hari libur Anda, semakin baik
- Lebih dari 30% karyawan tidak boleh absen di satu departemen
Untuk solusinya, kita akan menggunakan algoritma genetika dan algoritma kawanan lebah. Dalam peran lebah akan menjadi periode liburan (Kelas Holyday). Setiap periode menjadi milik seorang karyawan (Kelas Ketenagakerjaan), setiap karyawan berada dalam satu departemen (Kelas 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() { ... }
}Setiap kelas berisi fungsi score () - skor untuk kriteria algoritma, yang dihitung berdasarkan daftar penalti.
Lebah (cuti) dapat dibuat, dipindahkan, dihilangkan dan dimutasi (diubah ukurannya). Setelah memuat preferensi pekerja dalam periode bebas, hari libur pekerja yang tidak terisi ditetapkan secara acak. Jika karyawan telah menunjuk lebih banyak hari, hari liburnya akan dikurangi hingga mencapai standar.
Masalah dianggap terselesaikan jika semua hari libur tak terjadwal didistribusikan, preferensi terpenuhi, dan kondisi masalah lainnya terpenuhi. Dalam kehidupan nyata, jarang terjadi untuk menyenangkan semua orang, tetapi algoritme dapat mencoba menemukan solusi yang paling optimal. Untuk melakukan ini, pada setiap iterasi, kelas mengevaluasi kepatuhan mereka dengan kondisi masalah dan mengisi daftar hukuman. Mutasi lebih lanjut akan dipilih tergantung pada jumlah masing-masing hukuman dan hukuman dari kelas yang berdekatan. Pada akhir setiap gerakan semua lebah, algoritme diuji untuk konvergensi dan solusi yang paling berhasil diingat. Kualitas solusi dihitung berdasarkan penalti semua lebah. Jika solusi ideal tidak ditemukan, algoritma akan mengembalikan hasil dengan penalti terkecil.
//
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;
}
}Fungsi findPenalties () bertanggung jawab untuk mengisi daftar penalti untuk semua objek swarm. Kelas swarm
juga berisi fungsi skor kualitas yang dihitung dari skor semua anggota swarm.
Setelah memindahkan semua lebah, konvergensi algoritme dievaluasi, jika hasil yang diinginkan tidak tercapai dan batas iterasi tidak terlampaui, iterasi berikutnya nextIteration () akan diluncurkan. Dalam
kasus kami, banyak bergantung pada distribusi awal liburan yang tidak direncanakan, jadi diputuskan untuk memulai gerombolan di beberapa utas paralel dan memilih yang terbaik mereka:
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();
Algoritma ini tidak sulit untuk diimplementasikan dan intinya pada penulisan fungsi mutasi. Penggunaan algoritme kawanan lebah cocok untuk masalah pengoptimalan yang tidak memiliki solusi formal, dan penghitungan semua opsi dan kombinasi tidak sesuai karena jumlahnya yang besar.