Algoritme genetik
Algoritma genetika adalah teknik pencarian dalam ilmu komputer untuk menemukan solusi perkiraan untuk masalah optimasi dan pencarian. Algoritma genetika adalah kelas khusus dari algoritma evolusi yang menggunakan teknik yang terinspirasi oleh biologi evolusi seperti pewarisan, mutasi, seleksi alam dan rekombinasi (atau persilangan). Algoritma genetika pertama kali dikembangkan pada tahun 1970an oleh John Holland di New York, AS. Dia, murid-muridnya dan rekan-rekannya menerbitkan sebuah buku pada tahun 1975 berjudul “Adaptasi dalam Sistem Alam dan Buatan.”
Algoritme genetik biasanya diimplementasikan sebagai simulasi komputer di mana populasi representasi abstrak (disebut kromosom) dari solusi potensial (disebut unit) terhadap masalah optimasi berkembang menuju solusi yang lebih baik. Secara tradisional, solusi dalam format biner direpresentasikan sebagai string "0" dan "1", meskipun berbagai pengkodean juga dimungkinkan.Evolusi dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam generasi-generasi.
Dalam tiap generasi, kemampuan keseluruhan populasi dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang (current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru yang menjadi populasi sekarang (current) pada iterasi berikutnya dari algoritme.
Prosedur Algoritma Genetik
Algoritma genetika umum memerlukan definisi dua hal: (1) representasi genetik dari solusi, (2) fungsi kemampuan untuk mengevaluasinya.
Representasi defaultnya adalah array bit. Dengan cara yang sama, Anda dapat menggunakan array dengan tipe dan struktur lain. Alasan utama keakuratan representasi genetik ini adalah karena bagian-bagiannya dapat dengan mudah disusun karena ukurannya yang konstan, sehingga memudahkan operasi persilangan yang sederhana. Representasi panjang variabel juga digunakan, namun dalam kasus ini implementasi crossover lebih kompleks.Representasi pohon dipelajari dalam pemrograman genetik dan representasi bebas di HBGA.
Fungsi kapasitas ditentukan berdasarkan representasi genetik dan mengukur kualitas solusi yang disajikan. Fungsi kapasitas selalu bergantung pada masalahnya. Misalnya saja jika kita ingin memaksimalkan jumlah barang (benda) yang dapat ditampung dalam tas ransel dengan kapasitas tetap tertentu. Representasi solusinya dapat berupa bit array, dimana setiap bit merepresentasikan objek yang berbeda dan nilai bit (0 atau 1) menggambarkan apakah objek tersebut berada di dalam backpack atau tidak.Tidak semua representasi seperti itu berhasil karena ukuran benda tersebut mungkin melebihi kapasitas ransel.
Kapasitas solusi, jika direpresentasikan dengan benar, adalah jumlah dari nilai semua benda di dalam ransel, jika tidak maka akan menjadi 0. Dalam beberapa soal, mendefinisikan simbol kapasitas sulit atau tidak mungkin, sehingga IGA digunakan dalam kasus ini. .Setelah representasi genetik dan fungsi kebugaran ditentukan, algoritme genetika memproses inisialisasi acak populasi pada resolusi dan memperbaikinya dengan menerapkan operator mutasi, persilangan, dan seleksi berulang kali.
Secara sederhana, algoritme umum dari algoritme genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu:
- Membentuk suatu populasi individual dengan keadaan acak
- Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan
- Memilih individual dengan kecocokan yang tertinggi
- Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi
- Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang diinginkan
Sumber: id.wikipedia.org