Struktur Umum Algoritma Genetika

Algoritma genetika memberikan suatu pilihan bagi penentuan nilai parameter dengan meniru cara reproduksi genetik, pembentukan kromosom baru serta seleksi alami seperti terjadi pada mahluk hidup.

Struktur Umum Algoritma Genetika

Struktur umum algoritma genetik dapat diilustrasikan dalam diagram alir berikut ini:

Inisialisasi populasi awal dilakukan untuk menghasilkan solusi awal dari suatu permasalahan algoritma genetika. Inisialisasi ini dilakukan secara acak sebanyak jumlah kromosom/populasi yang diinginkan. Selanjutnya dihitung nilai fitness dan seterusnya dilakukan seleksi dengan menggunakan metode roda roullete, tournament atau ranking. Kemudian dilakukan perkawinan silang (crossover) dan mutasi. Setelah melalui beberapa generasi maka algoritma ini akan berhenti sebanyak generasi yang diinginkan.

Karakteristik Algoritma Genetika

Goldberg (1989) mengemukakan bahwa algoritma genetika mempunyai karakteristik-karakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain yaitu:

1. AG bekerja dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dan bukan parameter itu sendiri. Sebagai contoh untuk mendapatkan minimum dari fungsi  f(x)=y=x4+2x3+5, AG tidak secara langsung mencari nilai x atau y, tetapi terlebih dahulu merepresentasikan x dalam bentuk string biner.
2. AG melakukan pencarian pada sebuah populasi dari sejumlah individu-individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu.
3. AG merupakan informasi fungsi objektif (fitness), sebagai cara untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi.
4. AG menggunakan aturan-aturan transisi peluang, bukan aturan-aturan deterministik.

Parameter yang digunakan pada algoritma genetika adalah:

1. Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai.
2. Populasi jumlah individu yang dilibatkan pada setiap generasi
3. Probabilitas terjadinya persilangan (crossover) pada suatu generasi
4. Probabilitas terjadinya mutasi pada setiap individu.
5. Jumlah generasi yang akan dibentuk yang menentukan lama dari penerapan AG

Sebagaimana halnya proses evolusi di alam, suatu algoritma genetika yang sederhana umumnya terdiri dari tiga operator yaitu : operator reproduksi, operator crossover (persilangan) dan operator mutasi.

Langkah-langkah Algoritma Genetika

Struktur umum dari suatu algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut:

1. Pengkodean
   Pengkodean disini meliputi pengkodean gen dan kromosom.
2. Inisialisasi populasi awal
   Membangkitkan sejumlah kromosom (sesuai dengan ukuran populasi) untuk dijadikan anggota populasi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan.
3. Evaluasi nilai fitnes
   Setiap kromosom pada populasi dihitung nilai fitnessnya berdasarkan fungsi fitness. Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut. Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti.
4. Pembentukan kromosom baru
   1. Seleksi
      Memilih sejumlah kromosom yang akan menjadi kromosom calon parent
   2. Crossover
      Mengkombinasikan dua kromosom parent (induk) berdasar nilai probabilitas crossovernya untuk menghasilkan offspring
   3. Mutasi
      Mengubah sejumlah gen berdasar nilai probabilitas mutasinya untuk menghasilkan kromosom baru.
   4. Update Generasi
      Membaharui kromosom yang terdapat dalam populasi.
   5. Pengecekan faktor pemberhenti
      Jika memenuhi dari salah satu dari kondisi untuk berhenti, maka siklus algoritma genetika berhenti. Proses evolusi bisa dihentikan berdasarkan beberapa kondisi, misalnya ketika:
      1. evolusi telah mencapai jumlah generasi maksimum yang diizinkan,
      2. terdapat suatu individu yang telah memiliki fitness tertentu yang diharapkan,
      3. keberagaman populasi telah mencapai tingkat minimum yang diizinkan,
      4. dalam beberapa generasi tertentu, tidak ada peningkatan nilai fitness yang diharapkan.

Sebelum algoritma genetika dilakukan, ada dua hal   penting yang harus dilakukan yaitu pendefinisian kromosom yang merupakan suatu solusi yang masih berbentuk simbol dan fungsi fitness atau fungsi obyektif. Dua hal ini berperan penting dalam algoritma genetika untuk menyelesaikan suatu masalah.

Berbagi :