Membuat AI dalam Game Flappy Bird | Implementasi Algoritma Genetika dan Aplikasi Model Pelatihan Multilayer Perceptron

Implementasi algoritma genetika bisa dikatakan berhasil dalam penanganan suatu aplikasi yang kompleks. Hal ini karena melibatkan banyak objektif dan fungsi optimasi yang tidak terdefinisi dengan baik. Misalnya, desain sirkuit analog dan optimalisasi antena ruang-lahir yang dikembangkan menggunakan Algoritma genetika.

Algoritma optimisasi sederhananya dapat dibagi menjadi tiga kelas: algoritma pemrograman matematika, heuristik, dan metaheuristik. Algoritma pemrograman matematika memiliki fondasi yang paling ketat, dan dimungkinkan untuk membuktikan bahwa algoritma tersebut benar-benar konvergen, algoritma ini memeriksa apakah solusi yang diusulkan mendekati setidaknya optimum lokal, dan untuk memperkirakan tingkat konvergensi. Algoritma metaheuristik gunakan metafora, biasanya berasal dari bidang yang tidak terkait untuk didefinisikan sebagai algoritma pemilihan. Simulated annealing, ant colony, bee swarm, harmony search adalah contoh dari algoritma yang berasal dari berbagai bidang ilmu komputer.

Algoritma genetika adalah teknik pencarian metaheuristik kecerdasan buatan yang berasal dari teori evolusi biologis organisme oleh Darwin. Adapun banyak metode metaheuristik lainnya, banyak penelitian membahas tentang algoritma genetika dikarenakan kurangnya fondasi matematika secara inti dan konkret.

A. Masalah Optimasi

Banyak masalah dalam kehidupan nyata tidak memiliki rumus dan teknik untuk menghitung hasil secara tepat karena jumlah generik yang sangat banyak. Algoritma genetika berjalan pada sebuah populasi solusi yang pasti dan mengembangkannya menggunakan metode yang terinspirasi oleh teori Darwin dalam biologi. Artikel ini akan membahas perbedaan antara algoritma genetika dengan metode lain dan juga melakukan beberapa percobaan untuk memperkirakan efektivitas algoritma genetika.

Setiap permasalahan pada algoritma genetika membutuhkan fungsi kebugaran yang mengukur kualitas atas solusi menuju optimasi masalah.

B. Terminologi

Pada algoritma genetika, populasi dari solusi kandidat (phenotypes) dikembangkan ke arah solusi yang lebih baik dari masalah optimisasi. Setiap solusi kandidat diwakili oleh kromosom yang merupakan sekumpulan gen yang dapat mengubah mutasi dan crossover. Satu set kromosom baru, juga dikenal sebagai generasi yang dibentuk menggunakan tanggul seleksi.

Populasi: Jumlah individu hadir dengan kromosom yang sama panjang. Dengan kata lain, mereka adalah satu set solusi pasti untuk masalah optimisasi.

Genom: Bagian dari kromosom. Nilai masing-masing gen berpengaruh pada kualitas dari sebuah solusi.

Kromosom: Satu set genom. Kromosom merupakan solusinya dalam bentuk gen.

Selection: Populasi generasi berikutnya akan mempertahankan sebagian solusi terbaik pada generasi sebelumnya sehingga sifat-sifat terbaiknya akan dipertahankan.

Mutation: Mengubah genom dalam kromosom.

Crossover: Mencampur dua individu untuk menghasilkan pasangan baru keturunan yang memiliki sifat keduanya

C. Operator Genetik

Encoding dan Decoding

Teknik encoding sangat tergantung pada masalah. Secara umum, encoding adalah urutan setiap gen yang memiliki efek pada solusi. Decoding berfungsi menerjemahkan kromosom ke solusi masalah optimisasi. Encoding merupakan metode untuk membersihkan data sebelum memasukkannya ke dalam operator genetik.

Selection

Proses seleksi utamanya bertanggung jawab untuk memastikan kelangsungan hidup individu yang paling cocok. Solusi terbaik akan dipertahankan di generasi berikutnya.

Metode pemilihan roda roulette

Pemilihan proporsional kebugaran, juga dikenal sebagai pemilihan roda roulette, adalah operator genetik yang digunakan dalam algoritma genetika dengan memilih solusi secara potensial untuk rekombinasi. Dalam metode ini, setiap gen memiliki kemungkinan untuk dipilih sebagai generasi selanjutnya.

Metode pemilihan kebugaran terbaik

Dalam metode seleksi ini, individu-individu terbaik dengan kebugaran tertinggi dipilih. Metode ini merupakan pertukaran antara keanekaragaman populasi dan rata-rata kebugaran populasi dimana keragaman menurun dan kebugaran rata-rata meningkat dibandingkan dengan metode pemilihan roda roulette.

Mutation

Mutation digunakan untuk mempertahankan keragaman genetik dari satu generasi populasi kromosom ke generasi berikutnya. Hal ini merupakan analogi untuk mutasi biologis. Tujuan mutasi dalam GA adalah melestarikan dan memperkenalkan keragaman. Mutasi harus memungkinkan algoritma dapat keluar dari minimum lokal dengan mencegah populasi kromosom menjadi begitu mirip satu sama lain, sehingga dapat memperlambat atau bahkan menghentikan evolusi. Mutasi dapat dilakukan dengan rumus atau secara acak.

Crossover

Crossover betujuan memisahkan individu induk dan menggabungkannya kembali. Titik crossover dapat dipilih secara acak untuk meningkatkan keragaman populasi baru.

Multi-point crossover merupakan crossover sederhana dengan lebih dari satu posisi di mana proses crossover akan terjadi.

Selebihnya mengenai masalah tersebut dijelaskan pada code dan paper berikut.