Evolutionary Computation
Pengenalan dan Sejarah Singkat
Evolutionary computation merupakan suatu
wilayah ilmu komputer yang menggunakan pola pikir dari konsep dan prinsip dasar
dari evolusi alam, yaitu prinsip seleksi alam Darwinisme, sebagai inspirasi
dalam perancangan metode komputasi. Dalam proses seleksi alam, siap yang kuat
(yang bisa beradaptasi) dialah yang bisa bertahan. Ternyata ide ini telah
berkembang sejak tahun 1940an, jauh sebelum periode dimana komputer berkembang
pesat. Tahun 1948, Turing memperkenalkan istilah “genetical or
evolutionary search” dan tahun 1962 Bremermann melakukan eksperimen tentang
“optimisasi melalui evolusi dan kombinasi ulang (optimization through
evolution and recombination)” . Pada era tahun 1960an, tiga implementasi
ide dasar ini dikembangkan masing-masing di tempat berlainan. Di Amerika,
Fogel, Owens, dan Walsh memperkenalkan Evolutionary Programming,
sedangkan Holland (juga di Amerika) menyebut metodenya sebagai Genetic
Algorithm. Sementara itu di Jerman, Rechenberg dan Schwefel menemukan
metode Evolution Strategies. Selama lima belas tahun berikutnya,
metode tersebut dikembangkan secara terpisah, namun sejak awal tahun 1990an
ketiganya dipandang sebagai tiga jenis representasi (dialek) dari satu
teknologi yang diberi nama Evolutionary Computing. Di awal tahun
1990an juga bergabung dalam arus pemikiran ini suatu metode baru, yaitu Genetic
Programming, yang dipelopori oleh Koza.
Aplikasi dan Skema Umum
Algoritma yang mengikuti prinsip dasar
seleksi alam dikenal secara luas dengan sebutan Evolutionary Algorithm
(EA). Karena EA merupakan suatu metode komputasi yang bersifat generik dan
sangat fleksibel , EA bisa digunakan dalam berbagai aplikasi dan tujuan
berbeda. Aplikasi tersebut secara garis besar bisa dibagi dalam lima kategori,
yaitu:
1. Perencanaan (planning)
2. Perancangan (design)
3. Simulasi dan
identifikasi (simulation and identification)
4. Kontrol (control)
5. Pengelompokkan (classification)
Komponen Evolutionary Algorithm
Pada intinya, EA memproses suatu populasi
dari individual dimana setiap individual merupakan suatu kandidat solusi (candidate
solution) untuk permasalahan yang ingin dipecahkan. Pada setiap generasi,
individual dievaluasi berdasarkan suatu fungsi kesesuaian (fitness function).
Individual terbaik akan terpilih untuk proses reproduksi dan melanjutkan ke
proses kawin silang (crossover) dan mutasi untuk memproduksi keturunan (offspring)
atau candidate solution baru yang mewarisi sebagian sifat dari
induknya. Proses evolutionary dilakukan secara iteratif sampai kriteria
tertentu terpenuhi, misal jumlah iterasi tertentu terpenuhi atau solusi optimal
telah tercapai.
Dalam prosesnya, evolutionary algorithm
melibatkan komponen-komponen antara lain: individual, fitness function, metode
seleksi, operator genetik, dan populasi
Individual
Dalam evolutionary algorithm, individual
adalah kandidat solusi untuk permasalahan yang ingin dicari solusinya.
Karakteristik suatu individual diwakili oleh kromosom atau genome,
digambarkan dengan suatu pita gen, dimana setiap gen merupakan bagian kecil
dari kandidat solusi. Kromosom terdiri dari dua kelas, yaitu genotype dan phenotype.
Individual membentuk populasi. Individual merepresentasikan kemungkinan solusi
untuk masalah yang ditangani, dan biasanya juga disertakan informasi lainnya
seperti parameter strategi (strategy parameter) dan kesesuaian
individual (individual’s fitness).
Gbr 1. Contoh Representasi individual
Fitness Function
Fitness Function merupakan komponen yang
krusial dalam suatu evolutionary algorithm. Tujuan Fitness Function adalah
untuk memetakan representasi kromosom ke suatu nilai skalar. Fitness Function
digunakan untuk mengevaluasi seberapa baik suatu individual bisa digunakan
dalam memecahkan masalah yang dikehendaki, fitness function juga berperan untuk
menentukan individual mana yang akan bereproduksi dan sebagian materi
genetiknya (yaitu bagian dari candidate solutionnya) akan ‘diwariskan’ kepada
penerusnya/generasi berikutnya. Semakin besar kesesuaian (fitness) suatu
individual, semakin tinggi peluang individual tersebut terpilih untuk operasi
reproduksi, kawin silang (crossover), dan mutasi.
Idealnya, suatu fitness function bisa
mengukur kualitas suatu individu (candidate solution) seakurat mungkin, namun
desain dari fitness function juga akan memiliki batasan tentang processing
power, latar belakang pengetahuan, dan persyaratan yang ditentukan user.
Metode Seleksi
Metode seleksi yang dimaksud mencakup
mekanisme seleksi induk (parents) dan mekanisme seleksi survivor. Peran
pemilihan parents dalam EA adalah untuk membedakan antara
individual berdasarkan kualitasnya, dengan kata lain memberi kesempatan
individual yang lebih baik untuk menjadi parents bagi generasi
berikutnya. Semakin baik tingkat kesesuaian (dalam ukuran kualitas) suatu
individual, semakin tinggi peluang individual tersebut untuk terpilih.
Seperti pemilihan parents,
pemilihan survivor juga berperan berperan untuk membedakan individual
berdasarkan kualitasnya, perbedaannya hanya pada proses keduanya dilakukan pada
tahap yang berbeda. Pemilihan survivor dilakukan setelah proses penciptaan offspring dari parents terpilih.
Operator Genetik
Operator genetik berperan untuk
menciptakan individual baru dari individual lama (parents) atau tujuan
akhirnya adalah membangkitkan candidate solutions baru.
Operator genetik terbagi menjadi dua, yaitu mutasi dan rekombinasi. Rekombinasi
disebut juga sebagai kawin silang atau crossover. Macam-macam
crossover antara lain: one-point crossover, two-points crossover,
multi-point crossover, uniform crossover, three-parents crossover, crossover dengan reduced
surrogate, shuffle crossover, Precedence Preservative
Crossover (PPX), ordered crossover, Partially Matched
Crossover (PMX).
one-point crossover
|
two-point crossover
|
Uniform crossover
|
Three-parents crossover
|
Precedence Preservative Crossover (PPX)
|
Parent 1 : 4 2 | 1 3 | 6 5
Parent 2 : 2 3 | 1 4 | 5 6
Child 1 : 4 2 | 3 1 | 6 5
Child 2 : 2 3 | 4 1 | 5 6
Ordered crossover
|
|
String given:
Hasil Crossover:
Partially Matched Crossover (PMX)
|
|
Gbr 4. Contoh jenis-jenis crossover
Setelah operasi crossover, selanjutnya dilakukan operasi
mutasi. Mutasi berperan untuk mencegah algoritma terjebak dalam lokal minimum.
Terdapat beragam cara mutasi untuk tiap jenis representasi berbeda, yaitu
Flipping, interchanging, dan Reversing.
Populasi
Populasi memiliki peran sebagai
representasi dari segala kemungkinan solusi. Populasi merupakan kumpulan
individual atau populasi merupakan multiset dari genotypes. Genotypes adalah
sejumlah karakter yang diwariskan yang tetap terkandung dalam seluruh proses
reproduksi populasi.
Jika ukuran populasi kecil, agar tetap
mencakup sebagian besar dari search space, maka keragaman populasi
(population diversity) harus diperhatikan. Jika diperlukan, dalam EA
populasi bisa memiliki struktur spasial tambahan, yaitu dengan ukuran jarak
atau hubungan antar tetangga (neighbourhood relations). Untuk menjaga
keragaman populasi, operator mutasi sering disarankan menjadi solusi.
Evolutionary computing memiliki
kemampuan optimisasi yang powerful meski dengan ukuran populasi yang relatif
kecil (Glenn dan Payne, 1995). Dalam kasus populasi kecil, EA bisa ‘dipaksa’
untuk mengeksplorasi search space yang lebih besar, yaitu
dengan meningkatkan tingkat mutasi (mutation rate). Mutation
rate adalah peluang terjadinya mutasi selama replikasi DNA.
About the Author
0 comments