Persilangan dalam Algoritma Genetika

Persilangan dalam Algoritma Genetika

Persilangan (crossover) adalah salah satu metode yang bisa digunakan untuk membentuk individu baru dalam algoritma genetika. Dalam metode ini, perlu diperhatikan peluang persilangan yang ditetapkan oleh perancang sistem. Peluang ini menentukan jumlah anak yang dapat dibentuk menggunakan persilangan dalam sebuah populasi. Sebagai contoh, apabila terdapat 100 individu dalam sebuah populasi dengan peluang persilangan sebesar 25%, berarti diharapkan terdapat 25 individu baru yang diperoleh menggunakan metode persilangan.

Untuk memperoleh solusi dari sebuah permasalahan, dapat dilakukan crossover selama beberapa generasi. Dalam setiap generasi, peluang persilangan harus senantiasa diperhatikan. Ada kalanya sebuah solusi dapat dicapai setelah menerapkan algoritma genetika selama 10 generasi. Ada pula permasalahan yang dapat diselesaikan setelah dilakukan proses repoduksi selama 50 atau bahkan 100 generasi.

Dalam persilangan, dipilih dua individu dari generasi saat ini yang berfungsi sebagai orang tua (parents). Selanjutnya, dilakukan persilangan berdasarkan salah satu metode dari 4 metode yang ada, yaitu persilangan satu titik (single-point crossover), persilangan banyak titik (multi-point crossover), persilangan seragam (uniform crossover), dan persilangan permutasi (permutation crossover). Pada kesempatan ini, akan dibahas dua jenis persilangan pertama terlebih dahulu.

Baca juga:

  1. Ā Metode Roda Roulette untuk Seleksi Orang Tua
  2. Stochastic Universal Sampling Pada Algoritma Genetika
  3. Seleksi Orang Tua dengan Metode Seleksi Lokal
  1. Persilangan satu titik (single-point crossover)Pilihlah bilangan acak yang akan menentukan posisi persilangan. Kromosom yang berada di sebelah kanan posisi tersebut akan saling dipersilangkan,sehingga membentuk dua individu baru. Contoh:
  • Induk 1 = 1 0 1 0 0 1 1 0
  • Induk 2 = 0 1 0 1 0 1 0 0Posisi persilangan = 3
  • Anak 1 = 1 0 1 | 1 0 1 0 0
  • Anak 2 = 0 1 0 | 0 0 1 1 0
  1. Persilangan banyak titik (multi-point crossover)Persilangan ini mirip dengan persilangan jenis pertama. Hanya saja, terdapat beberapa titik yang dijadikan sebagai acuan lokasi persilangan. Contoh:
  • 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 1Posisi persilangan = 2, 6, 10
  • Anak 1 = 0 1 | 0 1 0 0 | 1 0 1 1 | 0 1
  • Anak 2 = 1 1 | 1 1 0 0 | 0 0 1 1 | 1 0

Itulah dua jenis persilangan yang pertama. Menarik kan? Dua jenis persilangan berikutnya — yaitu persilangan seragam (uniform crossover) dan persilangan permutasi (permutation crossover) — akan dibahas pada artikel berikutnya. Insya Allah. Kedua jenis persilangan terebut pun tidak kalah menarik dengan kedua persilangan di atas. Agar tidak ketinggalan, pastikan Anda tetap mengikuti artikel di AutomationID.