Terminologi dan Operator GA

Download html download


3.1 Pendahuluan
Dalam algoritma genetika, individu dideklarasikan dengan angka biner atau beberapa set simbol yang diambil dari sebuah himpunan berhingga.Seperti memori komputer terdiri dari array bit, apa pun bisa disimpan dalam komputer dan juga dapat dikodekan dengan string sedikit. Masing-masing individu dikodekan dalam populasi dapat dilihat sebagai representasi, menurut sebuah encoding yang sesuai solusi khusus untuk masalah ini. Bab ini membahas terminologi dasar dan operator yang digunakan dalam Algoritma Genetika untuk mencapai solusi yang cukup baik.
3.2 Elemen Utama

Dua elemen yang berbeda dalam GA adalah individu dan populasi. Seorang individu adalah solusi

tunggal, sementara populasi adalah himpunan  individu saat ini terlibat dalam proses pencarian.

3.3 Individu

kelompok individu dapat menentukan 2 solusi, yaitu:

1. kromosom, yang merupakan informasi baku 'genetik' (genotipe).

2. fenotipe, yang merupakan ekspresif kromosom dalam model.

Gambar 3.1 Representasi Genotipe dan fenotipe

 Gambar 3.2 Representasi kromosom

          Sebuah kromosom yang dibagi disebut gen. Gen adalah representasi GA untuk faktor tunggal dan untuk faktor kontrol. Setiap faktor dalam set sesuai dengan gen dalam kromosom. Gambar 3.1 menunjukkan representasi genotipe a. Sebuah kromosom berisi informasi tentang solusi yang diwakilinya. Fungsi morfogenesis mengaitkan setiap genotipe dengan fenotipe. Artinya setiap kromosom menentukan satu solusi, tetapi itu tidak berarti bahwa setiap solusi dikodekan oleh tepat dalam satu kromosom. Fungsi morfogenesis setidaknya harus subjektif. Solusi setiap masalah harus sesuai dengan setidaknya satu kromosom, untuk memastikan bahwa ruang pencarian keseluruhan dapat dieksplorasi. Ketika fungsi morfogenesis yang mengaitkan setiap kromosom ke satu solusi tidak injective, kromosom yang berbeda dapat mengkodekan solusi yang sama. jika beberapa kromosom dapat mewakili fenotipe yang sama, arti dari setiap gen akan jelas tetapi tidak sesuai dengan karakteristik tertentu dari solusi yang diinginkan sehingga membingungkan. Kromosom dikodekan oleh bit string seperti pada gamvar 3.2.

3.4 Gen 
 
3.4 Gen
Gen adalah dasar "petunjuk" untuk membangun Generic Algoritma. Sebuah kromosom adalah urutan 
gen. Gen menggambarkan sebuah solusi untuk masalah. Bit string adalah representasi biner dari jumlah 
interval dari batas bawah. Sebuah gen adalah representasi GA untuk nilai faktor tunggal untuk faktor 
kontrol, dimana faktor kontrol harus memiliki batas atas dan batas bawah. Kisaran ini dapat dibagi 
menjadi jumlah interval yang dapat dinyatakan dengan bit string gen. Sebuah string sedikit panjang 'n' 
dapat mewakili interval (2n-1). Ukuran interval adalah (range) / (2n-1).   
 
Struktur dari setiap gen didefinisikan dalam parameter fenotipe. Parameter fenotip adalah petunjuk 
untuk pemetaan antara genotipe dan fenotipe. Hal ini juga dapat dikatakan sebagai pengkodean solusi 
set ke kromosom dan decoding kromosom untuk satu set solusi. Pemetaan antara genotipe dan fenotipe 
diperlukan untuk mengkonversi solusi set dari model menjadi bentuk yang GA. Dalam kromosom, gen 
yang direpresentasikan dapat dilihat dalam Gambar 3.3.
 
 


 

Gambar 3.3 Representasi sebuah gen


 
3.5 Fitness
Nilai Fitness dari individu dalam algoritma genetika adalah nilai fungsi obyektif untuk fenotipe. Untuk 
menghitung nilai Fitness,pertama kromosom harus diterjemahkan dan fungsi tujuan harus dievaluasi. 
Nilai Fitness tidak hanya menunjukkan seberapa baik solusi ini, tetapi juga sesuai dengan seberapa 
dekat kromosom untuk solusi optimal.

Jika kadang-kadang fungsi fitness yang diperoleh dengan kombinasi sederhana dari kriteria yang 

berbeda dapat memberikan hasil yang baik, maka kriteria dapat dikombinasikan dengan cara yang 

konsisten. Tapi, untuk masalah yang lebih rumit dapat dipertimbangkan dari teori optimasi multikriteria.

3.6 Populasi 

Sebuah populasi adalah kumpulan individu. Sebuah populasi terdiri dari sejumlah individu yang diuji, 

serta parameter fenotip yang mendefinisikan individu dan beberapa informasi tentang ruang pencarian. 

Dua aspek penting dari populasi yang digunakan dalam Algoritma Genetika adalah: 

1. Generasi populasi awal. 

2. ukuran populasi.

 

 
Gambar 3.4 Populasi 


 
Ukuran populasi tergantung pada kompleksitas masalah. Dalam kasus kode biner kromosom, setiap bit 
diinisialisasi secara acak dengan nilai nol atau satu. Tapi mungkin ada kasus di mana inisialisasi 
populasi dilakukan dengan beberapa solusi yang dikenal lebih baik. Populasi yang besar membutuhkan 
lebih banyak biaya komputasi, memori dan waktu. Populasi menjadi kombinasi dari berbagai kromosom 
yang diwakili seperti pada Gambar. 3.4. Dengan demikian populasi di atas terdiri dari empat kromosom.
3.7 Struktur Data 
Struktur data utama dalam GA adalah kromosom, fenotipe, nilai-nilai fungsi tujuan dan nilai-nilai 
Fitness. Hal ini sangat mudah diimplementasikan menggunakan MATLAB sebagai alat numerik. 
Seluruh populasi kromosom dapat disimpan dalam satu array dan diberikan jumlah individu dan 
panjang representasi genotipe mereka. Demikian pula, variabel desain, atau fenotipe yang diperoleh 
dengan menerapkan beberapa pemetaan dari representasi kromosom ke ruang desain dapat disimpan 
dalam array tunggal. Pemetaan yang sebenarnya tergantung pada skema decoding yang digunakan. 
Nilai-nilai fungsi tujuan dapat skalar atau vectorial dan tentu sama dengan nilai-nilai fitness. nilai 
fitness yang berasal dari fungsi objek menggunakan skala atau peringkat fungsi dan dapat disimpan 
sebagai vektor. 


3.8 Strategi Pencarian
 Proses pencarian terdiri dari inisialisasi populasi dan kemudian berkembang biak dari individu baru 
sampai kondisi penghentian dipenuhi. Ada beberapa tujuan untuk proses pencarian, salah satunya 
adalah untuk menemukan optima global. Selalu ada kemungkinan bahwa iterasi berikutnya dalam 
pencarian akan menghasilkan solusi yang lebih baik. Dalam beberapa kasus, proses pencarian bisa 
berjalan selama bertahun-tahun dan tidak menghasilkan solusi lebih baik. Tujuan lain adalah 
konvergensi lebih cepat.  
 
3.9 Encoding
Encoding adalah proses yang mewakili gen individu. Proses ini  dapat dilakukan dengan menggunakan 
bit, angka, pohon, array, daftar atau benda lainnya. encoding  terutama tergantung pada pemecahan 
masalah. Sebagai contoh, seseorang dapat mengkodekan nomor  langsung dalam bentuk real atau 
integer.




 
3.9.1 Binary Encoding 
Cara yang paling umum dari encoding adalah string biner, yang akan diwakili seperti pada Gambar. 3.5.
Setiap kromosom mengkodekan biner (bit) string. Setiap bit dalam string dapat mewakili karakteristik 
dari solusi. oleh karena itu setiap bit string adalah solusi tetapi belum tentu solusi terbaik. Kemungkinan
lain adalah bahwa seluruh string dapat mewakili angka. Biner string dikodekan dengan 1 dan 0 yang 
banyak digunakan. Panjang string yang digunakan tergantung pada akurasi.
 

 
Gambar 3.5 Binary Encoding


 
• Integer direpresentasikan dengan tepat
• jumlah bilangan real yang terbatas dapat direpresentasikan
• Jumlah bilangan real direpresentasikan meningkat sepanjang string
 
3.9.2 Octal Encoding 
Encoding ini menggunakan string yang terdiri dari bilangan oktal (0-7)
 

 
Gambar 3.6 Octal encoding


 
3.9.3 Hexadecimal Encoding
Encoding ini menggunakan string yang terdiri dari bilangan heksa desimal (0-9,A-F)
 

 
Gambar 3.7 Hexadecimal encoding 


 
3.9.4 Permutation Encoding (Real Number Coding)
Setiap kromosom terdiri dari string angka, yang direpresentasikan secara berurutan. Dalam permutasi 
encoding, setiap kromosom adalah string integer / nilai-nilai nyata, yang mewakili angka secara 
berurutan. Permutasi encoding hanya berguna untuk mencari permasalahan. Bahkan untuk masalah 
pada tipe crossover dan koreksi mutasi harus dilakukan untuk meninggalkan kromosom yang konsisten 
(yaitu, memiliki urutan nyata di dalamnya).
 

 

Gambar 3.8 Permutation encoding




 
3.9.5 Value Encoding 
Dalam value encoding, setiap kromosom adalah string dari beberapa nilai. Nilai bisa apa saja yang 
terhubung ke masalah, nomor form, bilangan real atau karakter untuk beberapa objek yang rumit.
 

 
                                                    Gambar 3.9 Value encoding

Di sisi lain, encoding ini sering diperlukan untuk mengembangkan metode crossover yang baru dan 
mutasi khusus untuk masalah.  
3.9.6 Tree Encoding 
Encoding ini terutama digunakan untuk pengembangan ekspresi program untuk pemrograman genetik. 
Setiap kromosom adalah pohon dari beberapa objek seperti fungsi dan perintah dari bahasa 
pemrograman.  
3.10 Breeding
Dalam proses ini, proses pencarian menciptakan individu baru yang diharapkan lebih

sehat. Siklus breeding terdiri dari tiga langkah yaitu:

• Memilih orang tua.
• Menyilangkan orang tua untuk membuat individu baru (keturunan atau anak - anak).
• Mengganti individu tua dalam populasi dengan yang baru.

3.10.1 Seleksi
Seleksi adalah proses memilih dua orang tua dari populasi untuk disilangkan. Gambar tersebut. 3.10


menunjukkan proses seleksi dasar. Seleksi adalah metode yang secara acak mengambil kromosom dari 

populasi sesuai dengan fungsi evaluasi mereka. Semakin tinggi fungsi fitness, semakin banyak 

kesempatan seorang individu harus dipilih. Tekanan seleksi didefinisikan sebagai sejauh mana individu 

yang lebih baik. tekanan seleksi ini mendorong GA untuk meningkatkan nilai fitness populasi selama 

beberapa generasi berturut-turut. Tingkat konvergensi GA sangat ditentukan oleh besarnya tekanan 

seleksi, dengan tekanan seleksi yang lebih tinggi sehingga tingkat konvergensi yang lebih tinggi.



 

 Gambar 3.10 Seleksi 





3.10.1.1 Seleksi Roulette Wheel

Seleksi Roulette adalah salah satu teknik seleksi GA tradisional. Operator reproduksi yang umum 

digunakan adalah operator reproduksi proporsional di mana string dipilih dengan probabilitas sebanding 

dengan nilai fitness. Prinsip seleksi roulette adalah pencarian linear melalui roda roulette dengan slot 

pada roda tertimbang sebanding dengan nilai fitness individu.

Proses Roulette dijelaskan di atas juga dapat dijelaskan sebagai berikut: Nilai yang diharapkan dari 

seorang individu adalah bahwa nilai fitness dibagi dengan nilai fitness yang sebenarnya dari populasi. 

Setiap individu ditugaskan pada roda roulette, ukuran sebanding dengan nilai fitness individu. roda 

berputar N kali, di mana N adalah jumlah individu dalam populasi. Pada setiap putaran, individu di 

bawah penanda roda ini dipilih berada di barisan orangtua untuk generasi berikutnya.
konvergensi lambat tapi mencegah konvergensi yag terlalu cepat. Hal ini juga membuat tekanan
peringkat. Yang terburuk memiliki nilai fitness 1 dan yang terbaik memiliki nilai fitness N. Hasilnya 
sedikit lebih mengganggu daripada seleksi sebelumnya.


3.10.1.2 Seleksi Acak

Teknik ini secara acak memilih orang tua dari populasi. Dalam hal gangguan kode genetik, seleksi acak 


3.10.1.3 Seleksi Peringkat
Seleksi peringkat merupakan saat populasi dan setiap kromosom menerima nilai fitness berdasarkan 
ketika varians fitness rendah. Cara lainnya yaitu :


1.     Pilih sepasang individu secara acak. Menghasilkan nomor acak, R, antara 0 dan 1. Jika R < r 
      menggunakan individu pertama sebagai orang tua. Jika R ≥ r kemudian menggunakan
 individu kedua sebagai orang tua. Ini diulang untuk memilih orang tua kedua. 
Nilai r adalah parameter untuk metode ini.
2.     Pilih dua individu secara acak. Individu dengan evaluasi tertinggi menjadi orangtua.
 Ulangi untuk 
      menemukan orang tua kedua. 

 
3.10.1.4 Seleksi Turnamen

Individu terbaik dari turnamen adalah satu dengan nilai fitness tertinggi, yang merupakan pemenang 

Nu. Turnamen dan pemenang tersebut kemudian dimasukkan ke dalam kolom persilangan. Kompetisi 

turnamen diulang sampai kolom persilangan menghasilkan keturunan yang baru diisi. Perbedaan nilai 

fitness memberikan tekanan seleksi, yang mendorong GA untuk meningkatkan nilai fitness gen berhasil.

Metode ini lebih efisien dan mengarah ke solusi optimal.

3.10.1.5 Seleksi Boltzmann

Metode ini mensimulasikan proses pendinginan lambat dari logam cair untuk mencapai nilai fungsi 

minimum dalam masalah minimisasi. Dalam seleksi Boltzmann suhu terus bervariasi mengontrol laju 

seleksi sesuai jadwal yang telah ditetapkan. suhu mulai keluar tinggi, yang berarti tekanan seleksi 

rendah. Suhu diturunkan secara bertahap, yang secara bertahap meningkatkan tekanan seleksi, sehingga 

memungkinkan GA untuk mempersempit lebih dekat ke bagian terbaik dari ruang pencarian dengan 

tetap menjaga tingkat yang sesuai keanekaragaman. Suhu logaritmik penurunan ditemukan berguna 

untuk konvergensi tanpa terjebak ke keadaan minimal lokal. Tapi untuk mendinginkan sistem ke 

keadaan ekuilibrium membutuhkan waktu.









3.10.1.6 Stochastic Universal Sampling

Stochastic Universal Sampling memberikan nol bias dan menyebar minimum. Individu dipetakan ke 

segmen bersebelahan dengan garis, sehingga segmen masing-masing individu sama dengan ukuran 

fitness yang persis seperti dalam seleksi roulette-wheel. pointer di sini sama spasi ditempatkan di atas 

garis, sebanyak individu yang akan dipilih. Pertimbangkan NPointer jumlah individu yang akan dipilih, 

maka jarak antara pointer 1 / NPointer dan posisi pointer pertama diberikan oleh sejumlah secara acak 

dalam rentang [0, 1 / NPointer].
 



 Gambar 3.11 Stochastic Universal Sampling



 
3.10.2 Crossover (Rekombinasi)

Crossover adalah proses mengambil dua solusi orangtua dan memproduksi anak dari mereka. Setelah 

proses seleksi (reproduksi), populasi dicapai dengan individu yang lebih baik. Reproduksi membuat 

klon dari string yang bagus tetapi tidak membuat yang baru. Operator Crossover diterapkan pada kolom 

persilangan dengan harapan bahwa hal itu menciptakan keturunan yang lebih baik
Crossover adalah operator rekombinasi yang keluar dalam tiga langkah:


i. Operator reproduksi memilih secara acak sepasang dua string individu untuk disilangkan.
ii. Sebuah situs lintas dipilih secara acak di sepanjang panjang string. 
iii. Akhirnya, nilai-nilai posisi tertukar antara dua string sepanjang situs lintas