Optimisasi

Mendefinisikan algoritma genetika

Ketika membahas bagaimana cBot dapat dioptimalkan, kami telah menyebutkan bahwa cBot dapat disempurnakan menggunakan metode algoritma genetika. Dalam panduan ini, kami menjelaskan secara tepat apa itu dan bagaimana cara kerjanya.

Metode algoritma genetika didasarkan pada teori seleksi alam. Teori ini menyatakan bahwa hanya individu yang paling sesuai yang bertahan untuk reproduksi selanjutnya.

Dalam optimisasi cBot, setiap pass optimisasi dianggap sebagai individu. Untuk mengevaluasi pass individu, algoritma genetika menghitung skor kebugaran tertentu untuk setiap pass dan membandingkan skor ini dengan semua pass lainnya.

Agar berfungsi, algoritma genetika membutuhkan populasi awal. Untuk menghasilkannya, pengoptimal akan menjalankan beberapa pass berbeda dengan parameter yang diacak. Setelah membuat populasi awalnya, algoritma akan memulai proses mencari pass optimisasi yang paling sesuai. Proses ini berlanjut sampai skor kebugaran pass anak mulai stagnan dan konvergen. Pada titik ini, algoritma dihentikan.

Tahapan algoritma genetika

Setiap algoritma genetika memiliki tahapan berikut.

graph TB
  B([Seleksi]) ==> C([Persilangan]);
  C ==> D([Mutasi]);
  D ==> B;

Tahapan tersebut dijelaskan sebagai berikut.

Seleksi

Selama tahap ini, algoritma menemukan dua pass optimisasi yang paling sesuai menggunakan skor kebugaran masing-masing.

Persilangan

Setelah menemukan dua pass optimisasi yang paling sesuai, algoritma menggunakannya untuk membuat pass anak (atau keturunan) baru dengan menggunakan kombinasi nilai parameter dari kedua pass induk.

Mutasi

Pada tahap ini, algoritma memutasi pass keturunan dengan memodifikasi secara acak satu atau lebih nilai parameter.

Setelah tahap mutasi, pengoptimal akan menjalankan pass optimisasi keturunan baru. Selanjutnya, ia akan mengulangi semua tahapan tetapi hanya jika skor kebugaran pass keturunan lebih tinggi dari pass optimisasi yang paling sesuai terakhir. Hasil seperti itu akan berarti bahwa ada ruang untuk perbaikan, menunjukkan bahwa optimisasi harus dilanjutkan.

Jika tidak, algoritma akan meningkatkan penghitung stagnasinya. Jika penghitung stagnasi mencapai nilai parameter periode stagnasi algoritma, proses optimisasi akan dihentikan secara otomatis.

Parameter algoritma genetika

Algoritma genetika memiliki beberapa parameter yang digunakan selama masa hidupnya. Parameter ini tidak dapat diubah.