Persilangan dalam Algoritma Genetika (Bagian 2)

Pada artikel yang lalu, telah dipaparkan dua jenis persilangan dalam algoritma genetika. Pada kesempatan ini, akan dilanjutkan dua jenis persilangan lain yang juga sering diaplikasikan dalam algoritma ini.

Sebagaimana dua jenis persilangan sebelumnya, kedua persilangan ini dapat dilakukan setelah terpilih dua individu yang berperan sebagai orang tua (parents). Hal tersebut dapat dilakukan dengan menggunakan metode roda roulette, stochastic universal sampling, ataupun seleksi lokal. Selanjutnya, persilangan diwujudkan dengan mengikuti salah metode berikut ini.

  1. Persilangan seragam (uniform crossover)

    Pada metode ini, perancang terlebih dahulu membentuk mask bit yang berfungsi sebagai pembanding dalam membuat anak. Perancang menentukan aturan yang harus dipatuhi dalam proses reproduksi pada algortima genetika. Contoh:

    Orang tua

  • Induk 1 = 0 1 1 1 0 0 1 0 1 1 1 0
  • Induk 2 = 1 1 0 1 0 0 0 0 1 1 0 1

    Mask bit

  • Sampel 1 = 1 0 0 1 1 1 0 0 1 1 0 1
  • Sampel 2 = 0 1 1 0 0 0 1 1 0 0 1 0

    Aturan

  • Anak 1 akan dihasilkan dari induk 1 jika bit mask bernilai 1
  • Anak 1 akan dihasilkan dari induk 2 jika bit mask bernilai 0
  • Anak 2 dihasilkan dengan aturan yang berkebalikan dengan aturan untuk anak 1

    Dengan demikian, anak yang dihasilkan yaitu

  • Anak 1 = 0 1 0 1 0 0 0 0 1 1 0 0
  • Anak 2 = 1 1 1 1 0 0 1 0 1 1 1 1
  1. Persilangan dengan permutasi (permutation crossover)

    Pertama kali, lakukanlah persilangan langsung pada sebagian kromosom. Selanjutnya, buat pasangan persilangan terhadap kromosom yang saling dipersilangkan. Selanjutnya, pada kromosom tersisa, lakukan persilangan sesuai dengan pasangan persilangan yang telah dibentuk sebelumnya. Contoh:

  • Induk 1 = 1 2 3 | 4 5 6 7 | 8 9
  • Induk 2 = 4 5 3 | 1 8 7 6 | 9 2
  • Anak 1 = x x x | 1 8 7 6 | x x
  • Anak 2 = x x x | 4 5 6 7 | x x

    Pasangan persilangan yang terbentuk yaitu 1-4, 8-5, 7-6, 6-7. Dengan demikian, ketika ditemukan nilai kromosom seperti pada pasangan tersebut, lakukan persilangan langsung dengan pasangannya. Pada contoh di atas, individu yang terbentuk menjadi

  • Anak 1 = 4 2 3 | 1 8 7 6 | 5 9
  • Anak 2 = 1 8 3 | 4 5 6 7 | 9 2

***

Tidak lupa, ketika melakukan persilangan, senantiasa perhatikan peluang persilangan. Peluang ini menentukan banyaknya persilangan yang dapat dilakukan dalam sebuah populasi. Peluang persilangan 25% dalam populasi yang terdiri dari 100 individu berarti peluang dihasilkannya 25 individu baru dari hasil persilangan.

Pada akhirnya, persilangan pada algoritma genetika mengingatkan kita pada persilangan biologis. Keduanya pun sama-sama dilakukan untuk menghasilkan generasi terbaik, yang diharapkan dapat menjadi solusi terbaik pula untuk menyelesaikan permasalahan yang ada. Anda dapat melihat benang merahnya?