Pengenalan Algoritma Genetik

Algoritma genetik adalah algoritma optimasi yang prinsipnya sama seperti teori evolusi atau "survival of the fittest". Dalam perhitungannya, hanya yang "fittest" yang mempunyai kesempatan untuk bertahan paling lama. Algoritma ini sangat sederhana dan acak tapi bisa sangat efisien untuk beberapa kasus. Flowchat dari algoritma adalah seperti pada gambar di bawah ini atau header pada postingan ini.

1. Initialization

Ini adalah fase dimana solusi untuk persoalan yang ingin diselesaikan diberikan secara acak sebanyak populasi yang dinginkan. Untuk memperjelas maksudnya, contoh algoritma genetik biasanya digunakan untuk mencari nilai parameter optimal untuk memaksimalkan atau meminimalkan suatu persamaan atau mencari konfigurasi yang paling optimal dalam suatu model.

2. Selection

Fase ini pada beberapa kasus atau user biasanya dilakukan setelah initialization (init), biasanya juga dilakukan setelah crossover. Jika dilakukan setelah init maka hanya populasi terbaik dan terpilih yang bisa melakukan crossover. Apa itu crossover akan dijelaskan setelah bagian ini. Selection adalah pemilihan untuk siapa yang bertahan berdasarkan fitness fuction yang hasilnya terbaik. Contoh populasi yang diberikan ada 100, maka jika kita melakukan selection dengan populasi yang bertahan adalah 30%, yang bertahan adalah 30 solusi dengan keluaran fitness function yang terbaik. Tujuh puluh sisanya di buang. Ftiness function adalah suatu fungsi untuk menentukan sebagus apa solusi yang ada di populasi sekarang. Contoh jika tujuannya adalah mencari nilai parameter suatu fungsi untuk mendapatkan nilai terkecil dari fungsi tersebut maka fitness functionnya adalah fungsi itu sendiri. Contoh lain jika ingin menentukan parameter terbaik suatu moel fisis maka fitness functionnya adalah nilai galat dari hasil prediksi model dan data observasi.

3. Crossover

Ini adalah fase pembentukan solusi baru berdsarkan 2 solusi yang sudah ada. Biasanya fase ini disebut juga sebagai fase breeding atau beranak. Ini mirip dengan pengkombinasian gen ibu dan ayah sehingga membentuk gen anak. Contoh ada 2 solusi dari populasi yang ingin di crossover seperti dibawah ini.

11011
10110

Maka gen anak atau solusi baru yang tercipta adalah

11010

dan

10111

atau yang lainnya tergantung bagaimana kita menyusun algoritma crossover yang diinginkan. yang terpenting adalah solusi baru yang tercipta adalah perpaduan dari 2 solusi lainnya yang ada pada populasi. Solusi di sini diberikan biner hanya untuk memperagakan seperti apa konsep crossover. Pada permasalahn yang sebenarnya, solusi bisa berbentuk nilai real, bulat, atau suatu option parameterisasi.

4. Mutation

Solusi yang baru tercipta punya kemungkinan kecil isinya akan berubah sedikit. Contoh gen atau solusi yang baru adalah

10111

Ini bisa termutasi sehingga akan menjadi

10110

atau

10011

atau kemungkinan lainnya. Di algoritma penerapannya, biasanya dilakukan generate angka random dan diberi threshold yang hanya kemungkinan kecil angka random tersebut memenuhinya. Jika terpenuhi maka fungsi mutation akan dilakukan.

Proses nomor 2, 3, dan 4 ini akan terus berulang sampai nilai dari fitnes function dari solusi terbaik yang kita punya sudah memuaskan atau sampai perulangan yang kita inginkan.

Untuk contoh penerapan algoritma genetik yang sebenarnya akan dibahas pada postingan selanjutnya agar bisa memahami dengan lebih baik lagi konsep yang dijelaskan pada pembahasan kali ini. Sekian.

referensi:
http://project7.ir/%D9%BE%D8%B1%D9%88%DA%98%D9%87-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%DA%98%D9%86%D8%AA%DB%8C%DA%A9-%D8%A8%D8%B1%D8%A7%DB%8C-%D8%A8%D9%87%D8%A8%D9%88%D8%AF-%D8%B4%D8%A8%DA%A9%D9%87-%D9%BE/, diakses pada 28 Agustus 2018
https://www.researchgate.net/figure/Genetic-Algorithm-Tree-Basic-steps-of-GA-selection-crossover-and-mutation_fig2_260377604, diakses pada 28 Agustus 2018
An Introduction to Genetic Algorithms, 2014, oleh Jenna Carr