Pada tutorial ini, kita akan mempelajari metode seleksi gelanggang (roulette) dalam algoritma genetika.

Pemilihan kromosom untuk rekombinasi adalah langkah penting dalam algoritma genetika. Algoritma genetika sendiri adalah suatu algoritma yang terinspirasi oleh proses evolusi spesies biologis, tetapi tidak dapat dikurangi hanya dengan itu.

Algoritma genetika memiliki aplikasi yang penting dalam pembelajaran mesin. Contohnya, kita menggunakan mereka untuk memilih kebijakan dalam reinforcement learning. Namun, juga digunakan dalam pengoptimalan parameter untuk deep learning, masalah subset sum, pathfinding, atau solusi masalah pencarian lainnya.

Masalah-masalah dunia nyata yang dipecahkan oleh algoritma genetika meliputi penemuan bahan baru, identifikasi biomarker dalam biologi computational, pengujian penyakit dan penemuan obat dalam medis. Oleh karena itu, mereka adalah alat penting dalam kotak tools seorang data scientist.

Untuk algoritma genetika bekerja seperti yang diharapkan, perlu diselesaikan juga masalah rekombinasi antara kromosom terlebih dahulu.

Rekombinasi

Definisi kromosom biasanya menganggapnya sebagai array fixed-length yang berisi variabel biner:

Setiap bit dari variabel ini mewakili parameter atau karakteristik suatu jenis. Dengan cara ini, kita dapat menggambarkan individu memiliki set karakteristik biner tertentu secara eksklusif dalam hal kromosom. Kromosom kemudian memungkinkan representasi populasi yang berisi individual dengan berbagai tipe.

Kita dapat mewakili agen kompleks terdiri dari beberapa subsystem. Dalam kasus kebijakan reinforcement learning, contohnya, kromosom biasanya sesuai dengan sistem percepual atau pengontrol gerak agen.

Semua individu, masing-masing dengan kromosom sendiri, mulai beroperasi dalam lingkungan. Ketika mereka melakukannya, setiap individu menerima ukuran kemampuan (fitness) berdasarkan performanya. Kemudian, setelah kita hitung kemampuan untuk semua individu dalam populasi, kita lanjutkan dengan fase rekombinasi.

Pemilihan Berdasarkan Kemampuan

Kita memerlukan metode untuk mengidentifikasi orang tua yang kromosomnya akan di-rekombinasikan:

Metode ini perlu menggunakan kemampuan individu dalam populasi. Jika tidak, tidak ada pembelajaran antara satu generasi dan lainnya.

Ada dua kategori utama metode untuk menggunakan kemampuan dalam mendukung seleksi:

• Metode deterministik
• Metode stochastic

Metode deterministik melibatkan contoh pemilihan individu yang paling fit terhadap rekombinasi. Mereka biasanya tidak diakui karena cenderung mengembangkan populasi yang mencapai titik lokal dan kemudian berhenti evolusi.

Sebaliknya, kita dapat juga menggunakan metode stochastic untuk memilih orang tua. Metode yang paling ekstrem memilih individu secara acak dengan probabilitas uniform, sehingga sepenuhnya tidak mempertahankan kemampuan individu.

Sistem seleksi roulette wheel yang bagus adalah suatu sistem seleksi stokastik, di mana probabilitas pemilihan individu sebanding dengan kemampuan individunya. Sistem ini terinspirasi oleh roulettes dunia nyata, namun memiliki perbedaan penting darinya. Dalam roulette dunia nyata, semua slot mempunyai ukuran yang sama:

Dengan demikian, semua slot memiliki probabilitas yang sama untuk dipilih. Namun, kita dapat menerapkan versi berat dari roulette wheel. Dengan cara ini, individu yang lebih fit akan lebih cepat dipilih:

Sistem Seleksi Roulette

Akhirnya, kita dapat menggabungkan pertimbangan-pertimbangan di atas dan mengembangkan metode yang memenuhi syarat-syarat yang kita setting.

Dalam populasi dengan individu, untuk setiap kromosom dengan nilai kemampuan , kita hitung probabilitas sebagai berikut:

Kita dapat menggunakan sistem seleksi ini untuk memilih orang tua yang akan di-rekombinasikan.

Konklusi

Pada artikel ini, kita telah mempelajari cara melakukan seleksi gelanggang (roulette) dalam algoritma genetika.