ALGORITMA OPTIMASI PROBABILISTIK DAN DETERMINISTIK

A Hasad
Program Studi Teknik Elektronika
Fakultas Teknik, Universitas Islam 45 (UNISMA)
Jl. Cut Meutia No. 83 Bekasi 17113
Telp. +6221-88344436, Fax. +6221-8801192
Website: andihasad.com, Email: andihasad@yahoo.com

Dalam kehidupan sehari-hari, kita akan mudah menemukan permasalahan dari algoritma optimasi. Salah satu contohnya adalah bagaimana menyusun jadwal perkuliahan  sehingga tidak bentrok ruangan, dosen, maupun mahasiswa dengan distribusi yang adil dan semaksimal mungkin memenuhi kebutuhan semua pihak. Untuk menyelesaikan berbagai permasalahan seperti itu, para ahli telah mengelompokkan berbagai algoritma ke dalam kelompok Algoritma Optimasi (AO). Setiap algoritma memiliki kelebihan dan kekurangan masing-masing dalam menyelesaikan suatu masalah, karena tidak ada satupun algoritma yang berlaku umum dan bisa digunakan untuk menyelesaikan semua jenis masalah. Olehnya itu, diperlukan kemampuan memilih AO yang paling tepat (sesuai) untuk menyelesaikan masalah yang dihadapi.

Para ahli mengelompokkan AO ke dalam dua kelompok, seperti yang diperlihatkan pada Gambar 1, yaitu :

1. AO  Deterministik
2. AO  Probabilistik

Gambar 1  Pengelompokan Algoritma Optimasi

Perbedaan yang mendasar dari kedua kelompok tersebut adalah pada setiap langkah eksekusi di dalam AO Deterministik, hanya terdapat  satu jalan untuk diproses, jika tidak ada jalan maka algoritma dianggap selesai. Dengan demikian AO ini selalu menghasilkan solusi yang tetap untuk suatu input yang diberikan. Algoritma ini biasanya digunakan untuk masalah yang ruang solusinya tidak terlalu besar, sedangkan AO Probabalistik  digunakan untuk menyelesaikan  ruang masalah dengan ruang solusi yang sangat besar, bahkan tak terbatas. Algoritma Probabilistik berusaha menemukan solusi yang “bagus” tanpa melebihi batasan waktu yang telah ditentukan. Solusi yang “bagus” belum tentu yang paling optimal, namun sudah dapat diterima oleh user. Contohnya menyelesaikan masalah  TSP (Travelling Salesman Problem) untuk jutaan lokasi, maka akan memerlukan 1000 tahun komputasi jika diselesaikan dengan AO Deterministik . Jika kita menginginkan solusi dalam satu hari maka solusi menggunakan AO Deterministik tidak mungkin dilakukan. Namun jika ada AO Probabilistik yang bisa memberikan solusi yang “bagus” (sedikit lebih besar daripada solusi paling minimum, tetapi bisa diterima oleh kita) dalam waktu satu hari,  maka kita bisa menggunakan algoritma tersebut.

Selengkapnya mengenai Algoritma Optimasi dan Aplikasinya … download [pdf]

Referensi :

Hasad A. 2011. Algoritma Optimasi dan Aplikasinya, Sekolah Pascasarjana IPB, Bogor.

Suyanto. 2010. Algoritma Optimasi Deterministik atau Probabistik, Graha Ilmu, Yogyakarta.