Sejarah Algoritme Genetika

Algoritme Genetika

Algoritme Genetika pertama kali dikembangkan oleh John Holland dari Universitas Michigan pada tahun 1975. John Holland mengatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat dimodelkan dan diformulasikan dalam bentuk terminologi genetika. Algoritme genetika merupakan simulasi dari proses evolusi Darwin dan operasi genetika atas kromosom.

Pada dasarnya ada beberapa kondisi yang mempengaruhi proses evolusi yaitu, kemampuan organisme atau individu untuk melakukan reproduksi, keberadaan populasi individu yang dapat melakukan reproduksi, keberagaman individu dalam suatu populasi dan perbedaan kemampuan untuk bertahan. Individu yang lebih kuat (fit) akan memiliki tingkat kemampuan bertahan hidup dan reproduksi yang lebih tinggi jika dibandingkan dengan individu yang kurang kuat. Pada kurun waktu tertentu  atau lebih dikenal dengan istilah generasi, populasi secara keseluruhan akan lebih banyak memuat individu yang kuat.

Dalam struktur umum algoritma genetika teknik pencarian dilakukan sekaligus atas sejumlah solusi yang dikenal dengan istilah populasi. Individu yang terdapat pada suatu populasi disebut dengan kromosom. Kromosom adalah suatu solusi yang masih berupa simbol genetik. Populasi awal dibangun dengan pembangkitan secara acak, sedangkan populasi berikutnya adalah hasil dari proses genetika kromosom-kromosom melalui suatu iterasi yang disebut sebagai generasi.

Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat pengukur yang disebut dengan fungsi objektif atau (fitness function). Nilai fitness dari suatu kromosom mengandung nilai yang menunjukkan dari kualitas kromosom tersebut. Pada generasi berikutnya dikenal dengan sebutan keturunan atau (offspring) terbentuk dari gabungan 2 buah kromosom generasi sekarang yang berlaku sebagai orang tua atau induk dengan menggunakan operator-operator genetika sepert pindah silang (crossover) dan juga mutasi.

Populasi generasi yang baru dibentuk dengan cara melakukan seleksi nilai fitness dari kromosom orang tua dan nilai fitness dari kromosom offspring, serta mengeliminasi kromosom-kromosom lainnya yang tidak kuat, sehingga ukuran jumlah populasi pada setiap generasi konstan. Setelah melalui beberapa generasi, maka algoritme ini akan menuju konvergen (Engelbrecht 2007; Jong 2006).