Mengenal Lebih Dalam tentang Algoritma Genetika

Algoritma genetika merupakan salah satu metode metaheuristik yang digunakan untuk berbagai masalah optimasi.

Dalam ilmu komputer dan matematika, metaheuristik adalah metode tingkat tinggi untuk menemukan, menghasilkan, atau memilih heuristik (algoritma pencarian parsial) yang dapat memberikan solusi yang baik untuk masalah optimasi, terutama dengan informasi yang tidak lengkap atau terbatas kapasitas komputasinya.

Mengenal Lebih Dalam tentang Algoritma Genetika

Algoritma genetika dapat digunakan dalam machine learning, misalnya, untuk "menyetel" (mengoptimalkan) parameter meta untuk jaringan saraf tiruan, atau untuk regresi linier.

Di artikel ini kita akan mengenal lebih dalam mengenai algoritma genetika. Simak, ya!

Daftar Isi

Pengertian Algoritma Genetika

Algoritma genetika adalah algoritma pencarian heuristik adaptif yang terinspirasi oleh proses seleksi alam dan genetika. Metode ini melakukan pencarian acak yang dilengkapi dengan data historis untuk mengarahkan pencarian ke wilayah dengan kinerja yang lebih baik dalam ruang solusi.

Sumber: generativedesign.org

Algoritme ini pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Hasil penemuannya ini ditulis pada buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritma genetika biasanya dipakai untuk menghasilkan solusi berkualitas tinggi untuk masalah optimasi dan masalah pencarian. Kita dapat menerapkan algoritma genetika untuk memecahkan berbagai masalah optimasi yang tidak cocok jika menggunakan algoritma optimasi standar.

Algoritma ini didasarkan pada proses seleksi alamiah yang dikenal dengan proses evolusi. Dalam proses evolusi, individu yang bisa beradaptasi dengan lingkungannya akan tetap bertahan hidup dan menghasilkan keturunan melalui proses perkembangbiakan dan melibatkan perubahan gen dari waktu ke waktu.

Dengan kata lain, algoritma genetika mensimulasikan "survival of the fittest" di antara individu dari generasi berturut-turut untuk memecahkan masalah. Setiap generasi terdiri dari populasi individu dan setiap individu mewakili titik dalam ruang pencarian dan solusi yang mungkin. Setiap individu direpresentasikan sebagai string karakter/bilangan bulat/float/bit. String ini diibaratkan seperti sebuah kromosom dalam istilah biologi.

Cara Kerja Algoritma Genetika

Berikut adalah langkah per langkah cara kerja algoritma genetika:

Membuat populasi awal secara acak
Kemudian algoritma genetika membuat urutan populasi baru. Pada setiap tahapnya algoritma menggunakan individu pada generasi saat ini untuk membentuk populasi berikutnya. Untuk menghasilkan populasi, algoritma melakukan kerja sbb:

Memberi skor tiap-tiap anggota dari populasi saat ini dengan menghitung nilai kecocokan, Nilai ini disebut sebagai raw fitness score.
Melakukan penskalaan dari raw fitness score dan mengubahnya menjadi rentang nilai yang lebih baik. Nilai hasil penskalaan ini disebut dengan expectation value.
Memilih anggota atau parent berdasarkan nilai expectation value tersebut
Beberapa individu pada populasi saat ini dengan nilai kecocokan terbaik akan dipilih sebagai elite. Individu elite ini diteruskan ke populasi berikutnya.
Kemudian parent membentuk children yang dihasilkan melalui proses pengubahan acak pada salah satu parent. Pengubahan ini disebut sebagai mutation. Selain mutation, pembentukan children dapat dilakukan dengan menggabungkan entri vektor dari parent. Proses ini disebut sebagai crossover.
Mengganti populasi saat ini dengan children tersebut untuk membentuk generasi berikutnya.

Algoritma akan berhenti ketika salah satu kriteria penghentian terpenuhi.
Algoritma kemudian mengambil langkah-langkah yang dimodifikasi untuk batasan linier dan integer
Setelah itu, algoritma melakukan modifikasi lanjutan untuk batasan nonlinier.

Keunggulan Algoritma Genetika

Algoritma genetika memiliki kelebihan sebagai berikut:

Algoritma genetika dapat diandalkan (robust)
Menyediakan optimasi pada ruang berskala besar
Tidak akan rusak jika terdapat noise atau terjadi perubahan input.
Lebih cepat dan lebih efisien dibandingkan dengan metode tradisional.
Memiliki kemampuan paralel yang sangat baik.
Mengoptimalkan fungsi kontinu dan diskrit dan juga masalah multi-objective.
Berguna ketika ruang pencarian sangat besar dan ada banyak parameter yang terlibat.
Dapat memberikan daftar solusi yang baik, bukan hanya satu solusi saja.

Kekurangan Algoritma Genetika

Berikut kelemahan dari algoritma genetika:

Tidak cocok untuk semua masalah, terutama masalah yang sederhana dan yang tersedia informasi turunannya.
Untuk beberapa masalah, nilai kecocokan dihitung berulang kali yang secara komputasi cukup 'mahal'.
Bersifat stokastik, yakni tidak ada jaminan pada optimalitas atau kualitas solusi.
Jika tidak diimplementasikan dengan benar, algoritma genetika mungkin tidak konvergen ke solusi optimal.

Penutup

Sebagai kesimpulan, algoritma genetika adalah algoritma machine learning untuk memecahkan masalah optimasi terbatas dan tidak terbatas yang didasarkan pada seleksi alam, proses yang mendorong evolusi biologis. Algoritma genetika secara berulang-ulang memodifikasi populasi individual hingga menemukan daftar solusi yang optimal.

Jika suka dengan artikel seperti ini, Anda bisa mengunjungi rubrik Machine Learning atau membaca artikel lainnya mengenai "Analisis Regresi: Kegunaan dan Jenis-jenisnya".

Referensi:

Trivusi