Algoritma Genetika (GENETIC ALGORITHM) Lanjutan..

Definisi & Sejarah Singkat

Algoritma genetik adalah teknik pencarian di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. Algoritma genetik adalah kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)

Algoritma Genetik pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in Natural and Artificial Systems" pada tahun 1975.

Algoritma Genetik khususnya diterapkan sebagai simulasi komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional, solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. 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 algoritma.

Penjelasan Istilah

• Algoritma genetika dimulai dari himpunan kandidat solusi yang dihasilkan secara acak. Himpunan solusi ini dikenal dengan istilah populasi.
• Setiap individu yang terdapat dalam satu populasi disebut dengan istilah kromosom, yangmerupakan representasi dari sebuah solusi.
• Sebuah kromosom dinyatakan dengan rangkaian dari simbol (string). 
• Pada algoritma genetika, Populasi awal dibentuk secara acak sedangkan populasi berikutnya merupakan hasil evolusi Kromosom - kromosom dalam suatu iterasi yang berkelanjutan, yang disebut dengan istilah generasi.
• Kromosom-kromosom yang terbentuk selanjutnya diperoleh dari operasi yang dilakukan pada kromosom induk (parent) yang ada didalam populasi, dikenal dengan istilah anak (offspring). 
• Kromosom offspring dapat terbentuk dengan melakukan penyilangan (crossover) dari dua parent yang menghasilkan kombinasi dari dua kromosom.
• Pada setiap generasi, kromosom akan melalui proses seleksi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. 
• Nilai fitness dari suatu kromosom menunjukan kualitas kromosom dalam populasi tersebut. Generasi baru akan dibentuk dengan menyeleksi nilai fitness dari kromosom parent dan kromosom offspring, serta menolak kromosom - kromosom yang tidak cukup fit sehingga ukuran populasi (jumlah kromosom dalam suatu populasi) konstan.

Prosedur Algoritma Genetika

Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan:
(1) representasi genetik dari penyelesaian,
(2) fungsi kemampuan untuk mengevaluasinya.

Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan representasi bentuk bebas diselidiki di dalam HBGA. 

Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda (objek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang tetap. Representasi penyelesaian mungkin berbentuk larik bits, dimana tiap bit mewakili objek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah objek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini valid, karena ukuran objek dapat melebihi kapasitas ransel. Kemampuan penyelesaian adalah jumlah nilai dari semua objek di dalam ransel jika representasi itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini digunakan IGA. 

Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan, algoritma genetik akan memproses inisialisasi populasi penyelesaian secara acak, dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator-operator mutasi, persilangan, dan seleksi. 

Secara sederhana, algoritma umum dari algoritma 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 o Selain crossover, kromosom baru juga dapat terbentuk dengan melakukan modifikasi suatu kromosom yang disebut dengan istilah mutasi.

FLOWCHART ALGORITMA GENETIKA

   

Operator Operator Genetika

Operator-operator ini digunakan pada parent untuk melahirkan new generation. Operator-operator tersebut adalah: binary (crossover) operator yang memilih dua parent yang akan melahirkan new generation yang identik terhadap keduanya, dan unary (mutation) operator yang mengambil satu individu untuk dimodifikasi menjadi bentuk selayaknya sebuah individu.

1. Operator crossover. Operator dasar GA adalah crossover yang mengkombinasikan dua individu dengan harapan akan melahirkan individu yang lebih baik. Menurut Michalewicz (1996), ada 3 (tiga) teknik crossover pada TSP yaitu :

• Partially-Mapped Crossover (PMX),
• Order Crossover (OX),
• Cycle Crossover (CX),

2. Operator mutasi. Mutasi memperkenalkan materi genetika baru kepada populasi GA untuk menjaga keragaman dan menjelajahi wilayah baru. Beberapa operator mutasi yang umum digunakan adalah sebagai berikut :

• Uniform mutation
• Non-uniform mutation

Algoritma Genetika untuk menyelesaikan Travelling Salesman Problem

Langkah – Langkah Algoritma Genetika secara umum

Inisialisasi P1 sebagai populasi awal, kemudian dievaluasi berdasarkan nilai fitness terbesar.

1. Nilai fitness terbesar disimpan sebagai solusi sementara pada variabel solusi. 
2. Inisialisai P2 sebagai pasangan populasi P1. Jika terdapat individu pada P2 yang chromosomenya identik dengan individu pada P1 pada indeks yang sama, maka akan dilakukan proses mutasi kemudian diurut berdasarkan nilai fitnessnya. 
3. Nilai fitness terbesar pada P2 dibandingkan dengan nilai fitness yang sudah terdapat pada variabel solusi, jika nilai fitness solusi pada P2 tersebut lebih besar, maka nila fitness pada variabel solusi digantikan oleh individu. 
4. Mutasi terjadi pada P2 jika individu pada P2 yang indeksnya sama pada individu P1 memiliki chromosome yang identik. 
5. Dilakukan proses crossover antara P1 dan P2 menghasilkan NG. 
6. Mutasi terjadi pada NG, jika terdapat individu yang nilai fitnessnya sama. 
7. Evaluasi populasi NG 
8. Nilai fitness solusi pada NG dibandingkan dengan nilai fitness pada variabel solusi. Jika individu terbaik pada NG nilai fitnessnya lebih besar dibandingkan dengan nilai fitness solusi, maka akan digantikan sebagai variabel solusi. 
9. Jumlah NG yang dihasilkan diambil seluruhnya untuk dijadikan sebagai populasi awal untuk reproduksi berikutnya.