Genetic Algorithm [ GA ]

PENDAHULUAN

        Algoritma Genetika sebagai cabang dari algoritma evolusi merupakan metode adaptive yang biasa yang digunakan untuk memecahkan suatu pencarian nilai dalam sebuah masalah optimasi. Algoritma ini didasarkan pada proses genetik yang ada dalam mahkluk hidup , yaitu perkembangan generasi dalam sebuah populasi yang alami, secara lambat laun mengikuti prinsip seleksi alam "siapa yang kuat", dia yang bertahan (survive). Dengan meniru teori evolusi ini, algoritma genetika dapat digunakan untuk mencari solusi permasalahan-permasalahan dalam dunia nyata.

        peletak prinsip dasar sekaligus pencipta algoritma genetika adalah John Holland. Algoritma genetika menggunakan analogi secara langsung dari kebiasaan yang alami yaitu seleksi alam . Algoritma ini bekerja dengan sebuah populasi terdiri dari individu-individu , yang masing-masing individu mempresentasikan sebuah solusi yang mungkin bagi persoalan yang ada. Dalam kaitan ini, individu dilambangkan dengan sebuah nilai fitness yang akan digunakan untuk mencari solusi terbaik dari persoalan yang ada. Sebelum Algoritma genetika dapat dijalankan, maka sebuah kode yang sesuai (representatif) untuk persoalan harus dirancang. Untuk ini maka titik solusi dalam ruang permasalahan dikodekan dalam bentuk kromosom/string yang terdiri dari komponen genetik terkecil yaitu gen. Dengan teorievolusi dan teori genetika, didalam penerapan Algoritma Genetika akan melibatkan beberapa operator, yaitu :

• Operasi Evolusi yang melibatkan proses seleksi (selection) di dalamnya.
• Operasi genetika yang melibatkan operator pindah silang (crossover) dan mutasi (mutation).

untuk memeriksa hasil optimasi , kita membutuhkan fungsi fitness yang menandakan gambaran hasil(solusi) yang sudah dikodekan. selama berjalan, induk harus digunakan untuk reproduksi, pindah silang dan mutasi untuk menciptakan keturunan . Jika Algoritma genetika didesain secara baik, populasi akan mengalami konvergensi dan akan di dapatkan sebuah solusi yang optimum.

TEKNIK PENGKODEAN

     Teknik pengkodeanadalah bagaimana mengkodekan gen dari kromosom, dimana gen merupakan bagian dari kromosom. satu gen biasanya akan mewakili satu variabel.

     gen dapat dipresentasikan dalam bentuk : bit, bilangan real, daftar aturan, elemen permutasi, elemen program atau representasi lainnya yang dapat di implementasikan untuk operator.

     Dengan demikian kromsom dapat direpresentasikan dengan menggunakan : 

• string bit                  : 10011 dst.
• Array bilangan real  : 65.65,-67.98,77.34 dst
• Elemen permutasi    : E2, E10,E5 dst
• Daftar aturan           : R1,R2,R3 dst
• Elemen program      : pemrograman genetika
• struktur lainnya

Struktur Umum Algoritma Genetika

Beberapa hal yang harus dilakukan dalam algoritma genetika adalah:

• Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.
• Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan.
• Menentukan proses pembangkitan populasi awal.
• Menentukan proses seleksi yang akan digunakan
• Menentukan proses perkawinan silang (cross-over) dan mutasi gen yang akan dilakukan

a. Definisi individu

Individu menyatakan salah satu solusi yang mungkin. Individu bisa dikatakan sama dengan kromosom, yang merupakan kumpulan gen. Gen ini bisa biner, float, dan kombinatorial. Beberapa definisi penting yang perlu diperhatikan adalah sebagai berikut:

• Genotype (Gen), sebuah nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu       dalam satu kesatuan gen yang dinamakan kromosom. Dalam algoritma genetika, gen ini bisa berupa nilai biner, float, integer maupun karakter, atau kombinatorial.
• Allele, nilai dari gen.
• Kromosom, gabungan gen-gen yang membentuk nilai tertentu.
• Individu, menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi yang mungkin dari permasalahan yang diangkat
• Populasi, merupakan sekumpulan individu yang akan diproses bersama dalam satu siklus proses evolusi.
• Generasi, menyatakan satu siklus proses evolusi atau satu iterasi di dalam algoritma genetika.

Pada gambar berikut diilustrasikan perbedaan dari istilah-istilah di atas.

Misalnya di dalam TSP individu menyatakan jalur yang ditempuh, dalam penentuan nilai maksimal dari F(x,y) individu menyatakan nilai (x,y). Pada gambar berikut diilustrasikan 2 kemungkinan jalur yang ditempuh dalam TSP dan bagaimana representasinya dalam individu.

b. Definisi Fitness

Nilai fitness adalah nilai yang menyatakan baik tidaknya suatu solusi (individu). Nilai fitness ini yang dijadikan acuan dalam mencapai nilai optimal dalam algoritma genetika. Algoritma genetika bertujuan mencari individu dengan nilai fitness yang paling tinggi.

Dalam TSP, karena TSP bertujuan meminimalkan jarak, maka nilai fitnessnya adalah inversi dari total jarak dari jalur yang didapatkan. Cara melakukan inversi bisa menggunakan rumus 1/x atau 100000-x, dimana x adalah total jarak dari jalur yang didapatkan.

 Diagram Alir Algoritma Genetika

Algoritma genetika secara umum dapat diilustrasikan dalam diagram alir yang dapat dilihat pada gambar berikut.

1. Populasi awal

Proses ini merupakan proses yang digunakan untuk membangkitkan populasi awal secara random sehingga didapatkan solusi awal.

2. Evaluasi fitness

Proses ini merupakan proses untuk mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti.

3. Seleksi

Proses seleksi merupakan proses untuk menentukan individu-individu mana saja yang akan dipilih untuk dilakukan crossover.

4. Crossover

Proses crossover ini merupakan proses untuk menambah keanekaragaman

string dalam satu populasi.

5. Mutasi

Mutasi merupakan proses mengubah nilai dari satu atau beberapa gen dalam suatu kromosom.

6. Kriteria berhenti

kriteria berhenti merupakan kriteria yang digunakan untuk menghentikan proses algoritma genetika.

7. Hasil

Hasil merupakan solusi optimum yang didapat algoritma genetika.