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.

                  9 Responses

                  1. mau nanya donk,,tau buku tentang evolutionary logarithm yg tulisanya bhs indonesia ga?soalnya smua buku yg saya dpt tntng itu bhs inggrs,,,mhon bantuanya,,trms

                    • maaf baru balas… saya bener2 sibuk banget gak sempet buka blog. Klo yang bahasa Indonesia sayangnya saya juga belum pernah dapet tuh

                  2. postingan yang sangat bermanfaat…🙂

                    maaf, saya mau tanya. sumber tulisan di atas dari buku mana? saya sedang nyari referensi tentang komputasi evolutionary buat TA. trimakasih.

                    • Terima kasih..🙂
                      Tulisan di atas saya ambil dari berbagai sumber, antara lain sebagai berikut:
                      – Denny Hermawanto. “Algoritma Genetika dan Contoh Aplikasinya”
                      – Baeck T., Fogel D.B., Michalewicz Z. (eds.). 2000. “Evolutionary computation, vol.1.. Basic algorithms and operators”. Institute of Physic Publishing.
                      – Engelbrecht, A.P. 2002. “Computational Intelligence, an Introduction”. John Wiley & Sons.
                      – Eiben A.E., Smith J.D. 2003. “Introduction to Evolutionary Computing”. Springer.
                      – Sivanandam, S.N., Deepa, S.N. 2008. “Introduction to Genetic Algorithms, Springer”. Springer.

                      Empat buku terakhir bisa didownload di gigapedia. Semoga membantu…

                  3. kunjungan balik…
                    salam kenal

                  Leave a Reply

                  Fill in your details below or click an icon to log in:

                  WordPress.com Logo

                  You are commenting using your WordPress.com account. Log Out / Change )

                  Twitter picture

                  You are commenting using your Twitter account. Log Out / Change )

                  Facebook photo

                  You are commenting using your Facebook account. Log Out / Change )

                  Google+ photo

                  You are commenting using your Google+ account. Log Out / Change )

                  Connecting to %s

                  %d bloggers like this: