Bayesian Optimization Algorithm

Pengantar
Dewasa ini, penelitian untuk menemukan metode optimisasi yang secara eksplisit mampu memodelkan solusi yang baik telah banyak dilakukan. Salah satu hasil penelitian itu adalah metode Bayesian Optimization Algorithm (BOA) atau Algoritma Optimisasi Bayesian. BOA merupakan salah satu algoritma yang menggunakan estimasi distribusi dari data multinomial pada jaringan Bayesian untuk men-generate solusi baru.
BOA masih memiliki keterkaitan dengan Population Incremental Learning Algorithm dan Univariate Marginal Distribution Algorithm. BOA berkaitan juga dengan Algoritma Genetika serta algoritma evolusioner lain yang terinspirasi oleh teori evolusi dalam biologi yang menekankan pada seleksi alam.

Strategi
Dalam BOA, informasi yang ada tentunya akan diproses. Pemrosesan informasi pada BOA bertujuan untuk membangun model probabilistik yang mendeskripsikan relasi antar komponen solusi yang sesuai dalam ruang permasalahan. Untuk mencapai tujuan ini, harus dilakukan pengulangan proses pembuatan dan pengambilan sampel dari jaringan Bayesian yang terdiri atas dependensi bersyarat, independensi, serta probabilitas bersyarat antar komponen pada solusi.

Jaringan Bayesian
Jaringan bayesian biasa digunakan untuk memodelkan data multionomial baik untuk variabel diskrit maupun kontinu. Jaringan ini meng-encode hubungan antar variabel yang ada pada data yang dimodelkan, serta mampu merepresentasikan struktur masalah. Kegunaan jaringan ini yaitu untuk mendeskripsikan data dan men-generate objek baru dari variabel dengan properti yang mirip dengan yang ada pada data yang diberikan.
Dalam pembangunan jaringan Bayesian, setelah sebuah jaringan terbangun, kandidat solusi yang ada sekarang akan dibuang. Selanjutnya, model akan men-generate kandidat solusi yang baru. Proses ini akan terus berulang hingga model menemukan prototype dari solusi.
Tiap node pada jaringan berkorespondensi dengan 1 posisi pada string yang merepresentasikan solusi (Xi berkorespondensi dg posisi ke-i pada string). Hubungan antar variabel direpresentasikan oleh edge yang menghubungkan node-nodenya. Edge pada jaringan ini dapat bersifat directed (memiliki arah) maupun undirected (tidak memiliki arah). Namun, yang dibahas disini yang jaringan yang sifatnya directed, dan berada pada domain diskrit.
Jaringan Bayesian yang terbuka (acyclic) dengan edge yang directed melambangkan distribusi probabilitas joint. Hal ini dapat dirumuskan dengan:
Bayesian
dimana X = (X0, … , Xn-1) adalah variable vektor, ∏Xi adalah himpunan induk Xi pada jaringan (himpunan node yang adjacent dengan Xi), dan p(Xi | ∏Xi) adalah probabilitas bersyarat dari Xi yang disyaratkan oleh variabel ∏Xi. Distribusi ini dapat digunakan untuk men-generate objek baru menggunakan probabilitas marginal dan bersyarat dalam data set yang dimodelkan.
Ada dua komponen dasar dari jaringan Bayesian, yaitu:

  1. Scoring metric, sebagai ukuran kemampuan jaringan untuk memodelkan data. Untuk menghitungnya biasa digunakan Bayesian Dirichlet Metric (BD) atau K2 Metric.
  2. Algoritma pencarian untuk mendapatkan nilai scoring metric tertinggi. Biasanya digunakan algoritma Greedy yang sederhana atau algoritma Stockhastic.

Mekanisme Umum
BOA mengembangkan populasi dari kandidat solusi ke permasalahan optimasi yang diberikan. Populasi awal di-generate secara acak dan diperbaharui dalam sejumlah iterasi menggunakan 2 operator, yaitu:

  • Seleksi : ambil solusi baik, buang solusi buruk
  • Variasi : bangun jaringan Bayesian sebagai model dari solusi yang menjanjikan setelah seleksi

Berikutnya, kandidat solusi yang baru di-generate dengan melakukan sampling pada jaringan Bayesian yang telah dibangun. Sejumlah solusi baru akan dimasukkan ke dalam populasi untuk menggantikan sejumlah kandidat solusi yang lama. Iterasi selanjutnya akan dilakukan hingga kriteria terminasi dipenuhi. Dalam kasus ini, ada 3 kriteria terminasi, yaitu: ditemukan solusi yang maksimum, ditemukan pola yang konvergen, atau iterasi telah mencapai batas yang ditentukan.

Mekanisme umum algoritma BOA dapat digambarkan sebagai pada gambar di bawah ini:
Ilustrasi BOA

Pseudocode
1. Set t = 0, generate populasi awal P(0)
2. Pilih himpunan string yang menjanjikan S(t) dari P(t)
3. Bangun jaringan B menggunakan metric dan constraint yang dipilih
4. Generate himpunan string baru O(t) sesuai distribusi joint yang di-encode oleh B
5. Buat populasi baru P(t+1) dengan menggantikan string pada P(t) dengan O(t), set t = t + 1
6. Jika kriteria terminasi belum ditemukan, kembali ke langkah 2

Perbandingan dengan Algoritma Genetika
Perbandingan hasil uji coba permasalahan 3-deceptive, trap-5, dan 6-bipolar dapat dilihat pada gambar di bawah ini.
Perbandingan Kinerja BOA dengan GA

Penerapan
BOA dirancang dan telah diujicobakan pada permasalahan yang berbasis string biner. Paling sering digunakan untuk merepresentasikan permasalahan optimisasi fungsi biner, misalnya untuk One Max.

REFERENSI
1. Brownlee, Jason (2011). Clever Algorithms: Nature-Inspired Programming Recipes
2. Pelikan, Martin (2009). Bayesian optimization algorithm (BOA), [online] http://www.cs.umsl.edu/~pelikan
3. Pelikan, Martin, David E. Goldberg, and Erick Cant´u-Paz (1998), BOA: The Bayesian Optimization Algorithm

NB:
Ini adalah tugas yang saya buat untuk mata kuliah Sistem Intelijen. Masih paham dengan kulitnya saja, belum bisa jika harus merambah ke implementasi. -_-

Download artikel ini dalam versi pdf

8 thoughts on “Bayesian Optimization Algorithm

    • iya dipublish aja.. wkwkwk..
      tadinya sih malah mau saya publish semua, soalnya kan dokumennya saya yang gabungin >:)
      tapi dipikir2 lagi, jadi gak enak.. akhirnya publish bagian saya aja… hehehe.. unyuuuuuuuuuuuu :p

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s