Muhammad Fikri-1610953025: Klasifikasi Algoritma Genetika

Algoritma genetika (Algen) berupa langkah-langkah pencarian solusi masalah yang didasari mekanisma seleksi alam dan genetika alami. Banyak teknik pencarian yang dalam penggunaannya membutuhkan informasi yang banyak agar dapat bekerja dengan baik. Sedangkan Algen lebih sederhana hanya membutuhkan Objective Function untuk melakukan pencarian efektif dengan lebih baik dan struktur yang lebih baik.

[KEMBALI KE MENU UTAMA]

DAFTAR ISI

1. Simple Genetic Algorithm

2. Paralell and Distributed Genetic Algorithm (PGA and DGA)

3. Adaptive Genetic Algorithm
4. Referensi

1. Simple Genetic Algorithm (SGA) [Kembali]

Mekanisme dari Simple Genetic Algorithms (SGA) sangat sederhana yang terdiri atas 3 operasi. Yaitu :
a.reproduksi
b.penyilangan
c.mutasi

Prosedur standar dari SGA adalah :
-Cetak populasi secara acak
-Pilih induk (menggunakan fitness function)
-Metode seleksi : roulette wheel, tournamet, demetic
-Silang kromosom induk
-Mutasi kromosom keturunan
-Tambah keturunan kembali kepada pool

SGA sangat berguna dan efisien ketika
-Ruang pencarian besar, kompleks atau sulit dimengeri
-Tidak tersedia analisa matematis
-Metode pencarian tradisional gagal

2. Paralell and Distributed Genetic Algorithm (PGA and DGA)[kembali]

SGA yang dieksekusi secara paralel disebut PGA. Tujuannya adalah mengurangi waktu eksekusi. PGA bisa digunakan dengan mudah pada jaringan heterogren komper atau pada mainframes parallel. Semua algoritma mencoba untuk menyelesaikan tugas yang sama dan ketika pekerjaan tersebut selesai maka akan muncul individu yang terbaik dari yang terbaik. Ini merupakan cara yang paling populer meskipun ada banyak cara yang lain. Cara ini tidak bergantung pada yang lain sehingga dapat bekerja secara parallel.

Dalam pelaksanaannya, PGA bergantung pada :

-Bagaimana fitness dievaluasi dan mutasi diaplikasikan

-Bagaimana seleksi diaplikasi secara lokal atau global

-Subpopulasi single atau multiple yang digunakan

-Jika multiple populasi digunakan maka bagaimana individu bertukar

Terdapat beberapa metode PGA. Setiap Metode memiliki kelebihannya masing-masing. Berikut bagian-bagian dari metode PGA :

-independent PGA

-migration PGA

-partition PGA

-segmentation PGA

-segmentation-migration PGA

2.1 Master-Slave Parallelization [kembali]

Algoritma ini menggunakan sebuah populasi dan evaluasi terhadap setiap indivu diselesaikan secara parallel. Sebagaimana terlihat pada gambar

Master bertugas untuk menampung populasi dan slave mengevaluasi fitness. Metode ini mudah digunakan dan efisien ketika evaluasi membutuhkan pertimbangan komputasi. Berikut algoritma yang digunakan

2.2 Fine Grained Parallel GAs (Cellular GAs) [kembali]

Kata sellular digunakan karena mirip seperti sel automata dengan stochastic transition rules. Fitness dievaluasi secara serentak. Berikut algoritma yang digunakan

2.3 Multiple-Deme Parallel GAs (Distributed GAs or Coarse Grained GAs) [kembali]

Metode ini lebih canggih. Metode ini lebih dikenal sebagai Distributed GAs. Berikut merupakan algoritma yang digunakan

2.4 Hierarchical Parallel Algorithms [kembali]

Ini merupakan metode yang menggabungkan metode Multiple-Deme Parallel dengan master-slave atau fine-grained. Gabungan metode tersebut menyebabkan kelebihan masing-masing metode saling melengkapi sehingga performanya meningkat. Berikut Algoritmanya:

2.5 Hybrid Genetic Algorithm (HGA) [kembali]

Metode ini didesain dengan variasi crossover (persilangan).

Algoritma tersebut bekerja sebagai berikut :

2.5.a. Crossover [kembali]

Operator crossover menggunakan "edge map" yang digunakan untuk menampung informasi tentang semua koneksi masuk dan keluar dari city. Karena jarak antar kota adalah sama, maka setiap kota akan memiliki setidakny 2 atau 4 edge associations ( 2 dari setiap induk). Algoritmanya sebagai berikut :

2.5.b Inititalization Heuristics (IH) [kembali]

Metode ini hanya bisa diaplikasikan pada TSP. Metode ini memindahkan kota bergantung pada letak koordinatnya pada x dan y. Perjalanan ini merepresentasikan linked-list. Berikut algoritmanya:

2.5.c RemoveSharp Algorithm [kembali]

Metode ini menghapus sisi-sisa tertentu yang tumbuh pada perjalanan yang mengganggu. Algoritmanya sebagai berikut :

2.5.d LocalOpt Algorithm [kembali]

Metode ini akan memilih q pada kota (Sp+0, Sp+1,...,Sp+q-1) dari perjalanan dan akan memindahkan kota Sp+1, Sp+2, ...,Sp+q-2 pada jarakn minimal antara kota Sp+0 dan Sp+q-1 dengan mencari perpindahan yang paling mungkin.

3. Adaptive Genetic Algorithm [kembali]

Pada metode ini, ukuran populasi, kemungkinan penyilangan, atau kemungkinan mutasi divariasikan ketika AG sedang berlangsung. Variasi sederhananya seperti berikut :

-Perubahan mutasi berganting pada perubahan populasi

-Semakin lama populasi tidak berubah, semakin tinggi kemungkinan mutasi dilaksanakan

Algoritmany sebagai berikut