JURNAL: STUDI PERBANDINGAN ANTARA ALGORITMA BIVARIATE MARGINAL DISTRIBUTION DENGAN ALGORITMA GENETIKA

Abstrak

Bivariate Marginal Distribution Algorithm merupakan perkembangan lebih lanjut dari Estimation of Distribution Algorithm. Algoritma heuristik ini mengenalkan pendekatan baru dalam melakukan rekombinasi untuk membentuk individu baru, yaitu tidak menggunakan proses crossover dan mutasi seperti pada Genetic Algorithm. Bivariate Marginal Distribution Algorithm menggunakan keterkaitan pasangan variabel dalam melakukan rekombinasi untuk membentuk individu baru. Keterkaitan antar variabel tersebut ditemukan selama proses optimasi berlangsung. Aplikasi yang dibuat dalam penelitian ini ditujukan untuk membandingkan kinerja Genetic Algorithm sederhana persilangan satu titik dengan Bivariate Marginal Distribution Algorithm pada kasus Onemax, Fungsi De Jong F2, dan Traveling Salesman Problem. Dari uji coba yang dilakukan, didapat hasil bahwa kinerja dari kedua algoritma tersebut dipengaruhi oleh parameter masing-masing dan juga besar ukuran populasi yang digunakan. Untuk kasus Onemax dengan ukuran masalah yang kecil, Genetic Algorithm lebih unggul dalam hal jumlah iterasi yang lebih sedikit dan waktu yang lebih cepat untuk mendapat hasil optimal. Namun, Bivariate Marginal Distribution Algorithm lebih unggul dalam hal hasil optimasi pada kasus Onemax dengan ukuran masalah yang lebih besar. Untuk Fungsi De Jong F2, Genetic Algorithm lebih unggul dari Bivariate Marginal Distribution Algorithm utamanya dalam hal jumlah iterasi dan waktu. Sedangkan untuk kasus Traveling Salesman Problem, Bivariate Marginal Distribution Algorithm dapat menunjukkan kinerja yang lebih baik dari Genetic Algorithm dalam hal hasil optimasi.

Kata kunci: heuristic algorithm, estimation of distribution algorithm, bivariate marginal distribution algorithm, genetic algorithm

Pendahuluan

Genetic Algorithm (GA) bekerja dengan rangkaian populasi yang berukuran tetap. Dari populasi yang ada, kromosom yang lebih baik akan lebih dipilih dibandingkan dengan kromosom yang buruk. Rangkaian baru dihasilkan dengan menggunakan rekombinasi/penyilangan operator dan mutasi. Rekombinasi populasi menggabungkan informasi yang terkandung di dalam dua kromosom sedangkan mutasi melakukan gangguan pada rangkaian kromosom untuk menjaga keanekaragaman populasi dan mengenalkan informasi baru. Proses ini diketahui dapat menyebabkan gangguan pada kromosom yang menyebabkan algoritma ini berpenampilan buruk pada masalah yang membutuhkan hasil optimum. Hal ini akhirnya menuntun pada pendekatan baru dalam melakukan rekombinasi yang dinamakan Estimation of Distribution Algorithm (EDA). EDA pertama kali diperkenalkan dalam lingkup Evolutionary Computation oleh Muehlenbein dan Paab (1996).

Peneliti: Chastine Fatichah

Untuk lebih lengkapnya silahkan download di link berikut: