Komponen Algoritma Genetika

Bagikan ke :

Tweet

Ada beberapa komponen algoritma genetika yang perlu diketahui sebelum pembuatan program diantaranya yaitu:

A. Teknik Pengkodean

Teknik pengkodean adalah bagaimana mengodekan gen dari kromosom, dimana gen merupakan bagian dari kromosom. Satu gen biasanya akan mewakili satu variable. Agar dapat diproses melalui algoritma genetik, maka alternatif solusi tersebut harus dikodekan terlebih dahulu kedalam bentuk kromosom. Masing-masing kromosom berisi sejumlah gen yang mengodekan informasi yang disimpan didalam kromosom. Gen dapat direpresentasikan dalam bentuk bit, bilangan real, daftar aturan, elemen permutasi, elemen program atau representasi lainnya yang dapat diimplementasikan untuk operator genetika.

algoritma genetika

B. Pengertian Individu

Individu menyatakan salah satu solusi yang mungkin. Individu dapat dikatakan sama dengan kromosom, yang merupakan kumpulan gen. Beberapa definisi penting yang perlu diperhatikan dalam membangun penyelesain masalah menggunakan algoritma genetika. Istilah-istilah tersebut dapat disebutkan sebagai berikut (Berlianty & Arifin 2010):

1. Kromosom, merupakan tempat penyimpanan informasi gentika. Di dalam algoritma genetika pada umumnya string dianalogikan sebagai kromosom.
2. Genotype(struktur), kombinasi satu atau beberapa kromosom yang membentuk fungsi kerja suatu organisme. Interaksi sekumpulan kromosom disenut dengan genotype. Di dalam algoritma gentika struktur dianalogikan sebagai genotype.
3. Phenotype (set parameter), interaksi di dalam struktur terjadi karena adanya proses transformasi kode-kode genetika. Modifikasi ini disebut phenotype. Phenotype tersebut merupakan representasi set parameter masalah yang sedang dihadapi. Representasi kode dapat berupa numerik atau non numerik.
4. Genes, suatu kromosom yang dibentuk oleh beberapa gen.
5. Alleles (feature value), suatu feature yang memiliki nilai feature tertentu yang disebut dengan allele.
6. Locus (positioning), letak gen dalam suatu kromosom. Setiap featurememiliki urutan posisi di dalam string.

Hal-hal yang harus dilakukan dalam Algoritma Genetika yaitu:

1. Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.
2. Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah individu baik-tidaknya solusi yang didapat.
3. Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random-walk.
4. Menentukan proses seleksi yang akan digunakan.
5. Menentukan proses perkawinan silang (cross-over) dan mutasi gen yang akan digunakan. 

Hal penting yang harus diketahui dalam pemakaian Algoritma genetika:

1. Algoritma Genetika adalah algoritma yang dikembangkan dari proses pencarian solusi menggunakan pencarian acak, ini terlihat pada proses pembangkitan populasi awal yang menyatakan sekumpulan solusi yang dipilih secara acak.
2. Algoritma Genetika bekerja dengan bilangan acak pada kromosom awal, sehingga memungkinkan kromosom terbaik tidak terlibat dalam proses.
3. Algoritma genetika menggunakan pembangkit bilangan random dalam setiap pemilihan kromosom, baik induk, proses persilangan, maupun mutasi.
4. Solusi yang dihasilkan belum tentu merupakan solusi yang optimal, karena sangat dipengaruhi oleh bilangan acak yang dibangkitkan.

C. Membangkitkan Populasi Awal

Kebanyakan metode optimasi klasik memasukkan urutan deterministik dan komputasi berdasarkan gradien atau turunan dengan orde lebih tinggi dari fungsi objektif. Metode ini diterapkan pada titik tunggal dalam space search. Pendekatan point to point ini dapat menyebar pada lokal optimal. Algoritma genetika menampilkan mutiple directional search dengan menjaga populasi dari solusi potensial (Berlianty & Arifin 2010).

Membangkitkan populasi awal adalah proses membangkitkan sejumlah individu secara acak atau melalui procedure tertentu. Ukuran untuk populasi tergantung pada masalah yang akan diselesaikan dan jenis operator genetika yang akan diimplementasikan. Setelah ukuran populasi ditentukan, kemudian dilakukan pembangkitan populasi awal. 

Teknik dalam pembangkitan populasi awal ini ada beberapa cara, diantaranya adalah sebagai berikut:

1. Seperti pada metode random seach, pencarian solusi dimulai dari suatu titik uji tertentu. Titik uji tersebut dianggap sebagai alternative solusi yang disebut sebagai populasi.
2. Random Generator adalah melibatkan pembangkitan bilangan random untuk nilai setiap gen sesuai dengan representasi kromosom yang digunakan.
3. Pendekatan tertentu (memasukan nilai tertentu kedalam gen) Cara ini adalah dengan memasukan nilai tertentu kedalam gen dari populasi awal yang dibentuk.
4. Permutasi Gen Cara ini adalah penggunaan permutasi josephus dalam permasalahan kombinatorial seperti TSP.

D. Fungsi fitness

Suatu individu atau kromosom dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran performasinya.Fungsi yang digunakan untuk mengukur nilai kecocokan atau derajat optimalitas suatu kromosom disebut dengan fitness function.Nilai yang dihasilkan dari fungsi tersebut menandakan seberapa optimal solusi yang diperoleh. Nilai yang dihasilkan oleh fungsi fitness merepresentasikan seberapa banyak jumlah persyaratan yang dilanggar, sehingga dalam kasus penjadwalan perkuliahan semakin kecil jumlah pelanggaran yang dihasilkan maka solusi yang dihsilkan akan semakin baik.

E. Seleksi

Setiap kromosom yang terdapat dalam populasi akan melalui proses seleksi untuk dipilih menjadi orang tua. Sesuai dengan teori Evolusi Darwin maka kromosom yang baik akan bertahan dan menghasilkan keturunan yang baru untuk generasi selanjutnya. Ada beberapa metode seleksi, yaitu:

1. Seleksi Roulette Wheel Model seleksi ini merupakan model yang paling besar variansinya. Munculnya individu superior sering terjadi pada model ini, sehingga perlu strategi lain menangani hal ini.
2. Seleksi Rangking Seleksi ini memperbaiki proses seleksi yang sebelumnya yaitu roulette wheel karena pada seleksi tersebut kemungkinan selain satu kromosom mempunyai nilai fitness yang mendominasi hingga 90% bisa terjadi.Sehingga nilai fitness yang lain akan mempunyai kemungkinan yang sangat kecil untuk terpilih. Seleksi rangking dipakai untuk mengatasi masalah di atas, pertama-tama, diurutkan seluruh kromosom berdasarkan bagus-tidaknya solusi berdasarkan nilai fitness-nya.Setelah diurutkan, kromosom terburuk diberi nilai fitness baru sebesar 1, kromosom kedua terburuk diberi nilai fitness baru sebesar 2, dan seterusnya.Kromosom terbaik diberi nilai fitness baru sebesar n dimana n adalah banyak kromosom dalam suatu populasi.
3. Seleksi Steady State Metode ini tidak banyak digunakan dalam proses seleksi karena dilakukan dengan mempertahankan individu yang terbaik. Pada setiap generasi, akan dipilih beberapa kromosom-kromosom yang memiliki nilai fitness terburuk akan digantikan dengan offspring yang baru. Sehingga pada generasi selanjutnya akan terdapat beberapa populasi yang dipertahankan.
4. Seleksi Turnamen Merupakan metode seleksi lainnya yang didasari fenomena alamiah seperti turnamen antar individu dalam populasi.Dilakukan dengan memilih secara acak beberapa kromosom dari populasi. Individu-individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk.
5. Truncation Random Metode ini lebih mudah diterapkan jika dibandingkan dengan metode Roulette Wheel, pemilihan kromosom dilakukan secara acak tetapi tidak semua kromosom mendapatkan kesempatan tersebut, hanya kromosom terbaik saja yang berpeluang.

Semoga Bermanfaat

Eko Saputro

Saya ini cuma Mahasiswa Informatika Biasa yang amburadul dan masih sangat jauh dari kata sempurna. Selain itu juga Tidak Puas dengan Keadilan Kampus. Tapi tetep semangat dan saya yakin kesuksesan tidak dengan IPK (alasan lama).