Genetic Algorithm

Genetic Algorithm (GA) adalah bagian dari Evolutionary Algorithm yaitu suatu algoritma yang mencontoh proses evolusi alami dimana konsep utamanya adalah individu-individu yang paling unggul akan bertahan hidup, sedangkan individu-individu yang lemah akan punah[1]. Keunggulan individu-individu ini diuji melalui suatu fungsi yang dikenal sebagai fitness function. Fitness dalam GA didefinisikan sebagai gambaran kelayakan suatu solusi terhadap suatu permasalahan. Fitness Function akan menghasilkan suatu nilai fitness value yang akan menjadi referensi untuk proses GA selanjutnya. Secara umum, proses GA ditunjukan pada Gambar 1

Proses GA dimulai dengan menentukan populasi awal initial population yang terdiri dari beberapa kromosom yang disusun oleh beberpa gen yang merupakan representasi dari kandidat-kandidat solusi dari suatu masalah. Kandidat-kandidat terbaik akan dipilih melalui proses selection, berdasarkan fitness value yang telah dihitung untuk setiap kromosom dalam populasi. Kandidat – kandidat terpilih dari proses ini adalah individu-individu yang akan mengisi mating pool yaiu suatu set dimana dua parents akan dibentuk dari sini. Dalam Evolutionary Algorithm prinsip bertahan muncul karena adanya proses reproduksi. Turunan offspring yang dihasilkan akan membawa sifat gen orangtuanya (parents) , oleh sebab itu parents dipilih dari mating pool yang merupakan kumpulan kandidat-kandidat terbaik dari suatu populasi. Dengan demikian turunan yang dihasilkan adalah turunan yang memiliki sifat unggul dari kedua orang tuanya.

GA adalah salah satu algoritma yang digunakan untuk proses optimisasi. Dalam optimisasi, kondisi optimal solusi-solusi yang diperoleh adalah target utama yang akan dicapai. Namun dalam algoritma optimisasi, kondisi optimum lokal local optimum sering terjadi. Optimum lokal adalah suatu kondisi dimana algoritma mencapai nilai tertinggi atau terendah pada beberapa nilai kandidat solusi. Hal ini berlawanan dengan kondisi optimum global (global optimum) yaitu algoritma mencapai niai teringgi atau terendah untuk seluruh kandidat solusi dalam suatu masalah tertentu. Optimum lokal dapat terjadi salah satunya diakibatkan oleh populasi mencapai format konvergensi terlalu dini premature convergence. Menurut Rajeev dan Krisnamoorthy [2] kriteria tercapainya konvergensi adalah apabila sekitar 80% atau 85 % dari jumlah kromosom memiliki nilai gen yang sama. Salah satu cara untuk mencegah masalah prematur dini ini adalah dengan mempertahankan keragaman kromosom dari suatu populasi. Dalam GA, keragaman kromosom dari suatu populasi dapat dipertahankan dengan mengimplementasikan operator crossover dan mutasi (mutation).

Crossover adalah suatu operator rekombinasi yang bertujun untuk memperloleh individu yang lebih baik. Operator crossover melakukan rekombinasi dari set parents yang akan dipilih secara acak dari mating pool yang telah terbentuk dari proses seleksi. Crossover akan menghasilkan satu set turunan offspring yang keragamannya akan tetap dipertahankan dengan proses selanjutnya yaitu mutasi. Pada operator mutasi, keragaman akan dipertahankan dengan menukar salah satu atau lebih gen dalam kromosom dengan nilai kebalikannya. Sebagai contoh, jika kromosom kita memiliki nilai biner 0 dan 1 maka jika secara acak titik mutasi yang terpilih memiliki nilai 1, nilai ini akan ditukar menjadi nilai 0 atau sebaliknya. Hasil dari operator mutasi ini adalah turunan baru yang selanjutnya akan kembali diuji pada funsi fitness untuk melihat kelayakan populasi baru dari hasil proses GA ini sebagai kandidat solusi dari masalah yang diberikan. Proses pengujian fitness, seleksi,crossover dan mutasi akan dilakukan secara berulang sedemikian hingga telah dipenuhi salah satu kontrol perulangan proses GA berikut yaitu iterasi, konvergensi atau nilai fitness.

References
[1] Andries P Engelbrecht. Fundamentals of computational swarm intelligence. John Wiley & Sons, 2006.
[2] S Rajeev and CS Krishnamoorthy. Discrete optimization of structures using genetic algorithms. Journal of structural engineering, 1992.