Kecerdasan Buatan Pengantar Sistem Komputer 

Pengertian, struktur dan prosedur Algoritma Genetika

Pengertian

Merupakan teknik pencarian yang ada di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian. sering juga di artikan sebagai 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..

Aplikasi  Algoritma  Genetika

  1.  Algoritma Genetika ini dapat di gunakan di semua hal seperti bisnis, teknik maupun keilmuan
  2. Algoritma ini sangat tepat untuk menyelesaikan suatu masalah optimasi yang lebih kompleks dan sukar diselesaikan dengan menggunakan metode yang konvensional.
  3. Algoritma genetika banyak digunakan untuk penyelesaian masalah dengan multikriteria

Struktur Algoritma Genetika

1. Membangkitkan populasi awal.

Populasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi terdiri dari sejumlah kromosom-kromosom yang merepresentasikan solusi yang diinginkan.

2. Pembentukan generasi baru.

Dalam pembentukan tersebut digunakan tiga operator, yaitu operator reproduksi/seleksi, crossover dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru.

3. Evaluasi solusi.

Pada proses ini akan dilakukan evaluasi setiap populasi dengan menghitung nilai fitness dari setiap kromosom dan akan terus melakukan evaluasinya sampai terpenuhi kriteria berhenti. Tetapi kalau samapai akhir kriteria belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah 2. Beberapa kriteria berhenti yang sering digunakan antara lain:

a. Berhenti pada generasi tertentu.

b. Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah.

c. Berhenti bila sampai n generasi tidak didapatkan nilai fitness yang lebih tinggi.

Prosedur Algoritma Genetika

Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan, yaitu :

  1.  Representasi genetik dari penyelesaian,
  2.  Fungsi kemampuan untuk mengevaluasinya.

Operator-Operator Algoritma Genetika

  1. Operasi Evolusi = proses seleksi (selection)
  2. Operasi Genetika  = pindah silang (crossover) dan mutasi (mutation)

Siklus algoritma genetika

Siklus Algoritma Genetika oleh David Goldberg mengalami revisi agar dapat menyesuaikan algoritma genetika saat ini. berikut ini merupakan siklus dari algoritma genetika :

Siklus algoritma sebelum direvisi

siklus algoritma genetika

Siklus algoritma genetika setelah direvisi

revisi siklus algoritma genetiaka

Komponen-komponen utama algoritma genetika

Ada beberapa komponen utama dalam algoritma genetika, yaitu:

1.Teknik Pengkodean

Teknik pengkodean adalah  bagaimana  mengkodekan  gen  dari  kromosom dan variabel. Gen  biasanya dipresentasikan ke dalam  bentuk  bit, bilangan  real,  elemen  program atau  representasi  lainnya.  yang  dapat diimplementasikan untuk operator genetika. Dengan demikian kromosom dapat direpresentasikan dengan menggunakan:

⊕ String bit  : 10011 dst.

⊕ Array bilangan real : 65.65, -67.98, 77.34 dst.

⊕ Elemen permutasi : E2, E10, E5 dst

⊕ Daftar aturan : R1, R2, R3 dst.

⊕ Elemen program : pemrograman genetika

2. Membangkitkan Populasi Awal

Membangkitkan populasi awal adalah proses membangkitkan sejumlah individu  suatu solusi harus benar-benar diperhatikan dalam membangkitan setiap individunya secara  acak  atau  melalui  prosedur  tertentu. Beberapa cara teknik pembangkitan populasi awal. antara lain:

a. Random Generator

Inti dari cara ini yaitu  melibatkan  pembangkitan  bilangan  random  untuk  nilai setiap gen  sesuai  dengan  representasi  kromosom  yang  digunakan.  Berikut ini merupakan rumus untuk pembangkitan cara random generator :

  IPOP = round{random(Nipop, Nbits)}

Keterangan :

IPOP  =  Gen  yang  berisi  pembulatan  dari  bilangan  random yang dibangkitkan sebanyak  Nipop (Jumlah populasi) X Nbits (Jumlah Gen dalam tiap kromosom).

b. Pendekatan Nilai Tertentu (Memasukkan Nilai Tertentu dalam Gen)

Untuk cara ini bekerja dengan memasukkan nilai-nilai tertentu ke dalam gen dari populasi awal  yang sebelumnhya telah dibentuk.

c. Permutasi Gen

Cara permutasi Gen yaitu dengan  cara  pembangkitan  populasi  awal, biasanya cara ini menggunakan permutasi  Josephus  dalam  permasalahan kombinatorial  seperti  TSP.

3. Seleksi

Seleksi digunakan untuk memilih individu-individu mana saja yang akan dipilih untuk  proses  kawin  silang  dan  mutasi. Hal ini dilakukan untuk mendapatkan calon induk yang baik. berikut beberapa metode seleksi, yaitu :

a. Seleksi dengan Mesin Roulette

⊕ Metode seleksi dengan  mesin  roulette  ini  merupakan  metode  yang  paling sederhana dan sering dikenal dengan nama stochastic sampling with replacement. Cara kerja metode ini adalah sebagai berikut:

⊕ Dihitung nilai fitness dari masing-masing individu (fi, dimana i adalah individu ke-1 s/d ke-n)

⊕ Dihitung total fitness semua individu

⊕ Dihitung probabilitas masing-masing individu

⊕ Dari probabilitas tersebut, dihitung jatah masing-masing individu pada angka 1 sampai 100

⊕ Dari bilangan random yang dihasilkan, ditentukan individu mana yang terpilih dalam proses seleksi

b. Seleksi dengan turnamen

Pada metode ini, ditetapkan suatu nilai untuk individu-individu yang dipilih secara random dari suatu populasi. Individu yang terbaik dari kelompok ini akan diseleksi sebagai induk.  Parameter  yang dapat digunakan pada metode ini adalah ukuran tour yang bernilai antara 2 sampai dengan N ( N merupakan jumlah individu dalam suatu populasi).

4. Pindah Silang (Crossover)

Crossover (pindah  silang)  adalah suatu operator  dari  algoritma  genetika  yang akan melibatkan  dua induk untuk membentuk kromosom  baru. Pindah silang akan menghasilkan titik  baru  dalam  ruang  pencarian  yang  siap  untuk  diuji. berikut ini aliran pindah silang (crossover)

crossover

5. Mutasi

 Berikut ini proses alur mutasi :

proses alur mutasi

Demikian artikel terkait materi kuliah yang berjudul “Pengertian, struktur dan prosedur Algoritma Genetika”. Untuk dapat mendapatkan materi terkait kecerdasan Buatan secara lengkap, dapat didownload melalui link berikut Matkul AI.  Semoga bermanfaat

Related posts

Leave a Comment