Mengenal Evolutionary Computation: Komputasi yang Meniru Evolusi Alam

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)

Secara umum, skema dari Evolutionary Algorithm bisa digambarkan dalam diagram alur sebagai berikut:

Gbr 1. Diagram alur skema Evolutionary Algorithm

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 2. 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 3. 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.