Algoritma Branch & Bound

Algoritma Branch & Bound adalah salah satu algoritma yang digunakan untuk persoalan optimasi, yaitu dengan meminimalkan atau memaksimalkan suatu fungsi objektif, yang tidak melanggar batasan (constraints) persoalan. 

Algoritma Branch & Bound menggambarkan suatu persoalan sebagai simpul – simpul, dan memecahkan permasalahan dengan memproses simpul – simpul tersebut. 

Algoritma Branch & Bound merupakan gabungan dari algoritma Breadth First Search (BFS) dan Least Cost Search. Karakteristik algoritma Branch & Bound adalah sebagai berikut: 

• Setiap simpul diberi sebuah nilai cost: ĉ(i) = nilai taksiran termurah ke simpul status tujuan yang melalui simpul status i. ĉ(i) menyatakan batas bawah (lower bound) dari ongkos pencarian solusi dari status i. 
• Simpul berikutnya yang akan di-ekspan tidak lagi berdasarkan urutan pembangkitannya, tetapi simpul yang memiliki cost yang paling kecil (Least Cost Search) – pada kasus minimalisasi.

    Sesuai dengan namanya yaitu algoritma Branch & Bound, algoritma ini mengekspan simpul – simpul solusi sehingga didapatkan seluruh percabangan dari simpul solusi (branch), lalu matikan/batasi simpul yang sekiranya tidak menuju ke simpul solusi (bound). 

    Terdapat dua informasi tambahan yang diperlukan dalam penyelesaian persoalan dengan Branch & Bound: 

• Untuk setiap simpul pada pohon ruang status, diperlukan suatu cara penentuan batas (bound) nilai terbaik fungsi objektif pada setiap solusi yang mungkin, dengan menambahkan komponen pada solusi sementara yang direpresentasikan simpul. 
• Nilai dari solusi terbaik sejauh proses terakhir.

Prinsip Pencarian Solusi pada Algoritma B&B

• Skema BFS = skema FIFO (First In First Out).
• Tinjau kembali persoalan 4-ratu yang diselesaikan dengan skema BFS (murni).

Gambar 7.1 Pohon ruang status yang terbentuk untuk persoalan 4-Ratu dengan metode BFS

• Solusi pertama dicapai pada simpul 30, yaitu X = (2, 4, 1, 3). Dengan skema BFS murni / FIFO, kita harus memperluas dulu simpul 12, simpul 15, dan simpul 16 sebelum memperluas simpul 22 yang melahirkan simpul solusi, yaitu simpul 30.
• Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost).
• Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound).
• Simpul hidup yang menjadi simpul-E ialah simpul yang mempunyai nilai batas terkecil (strategi  pencarian berdasarkan biaya terkecil (least cost search).
• Untuk setiap simpul X, nilai batas ini dapat berupa [HOR78]:

(a)    Jumlah simpul dalam upapohon X yang perlu  dibangkitkan sebelum simpul solusi ditemukan, atau

(b)     Panjang lintasan dari simpul X ke simpul solusi terdekat (dalam upapohon X ybs)

Misal digunakan ukuran (b):

• Pemberian nilai batas seperti pada persoalan N-Ratu di atas adalah nilai batas yang ideal, karena letak simpul solusi diketahui.
• Pada umumnya, untuk kebanyakan persoalan, letak simpul solusi tidak diketahui, karena itu, dalam prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan.
• Fungsi heuristik untuk menghitung taksiran cost:

        = ongkos untuk simpul i

            = ongkos mencapai simpul i dari akar

       = ongkos mencapai simpul tujuan dari simpul i.

• Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki minimum.

Berikut adalah algoritma global Branch & Bound: 

1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node), maka solusi telah ditemukan. Berhenti. 
2. Jika Q kosong, tidak ada solusi. Berhenti. 
3. Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyai ĉ(i) paling kecil. Jika terdapat beberapa simpul i yang memenuhi, pilih satu secara sembarang. 
4. Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, berhenti. Jika simpul i bukan simpul solusi, maka bangkitkan semua anak – anaknya. Jika i tidak mempunyai anak, kembali ke langkah 2. 
5. Untuk setiap anak j dari simpul I, hitung ĉ(j), dan masukkan semua anak – anak tersebut ke dalam Q.
6. Kembali ke langkah 2

Algoritma Branch & Bound memiliki fungsi pembatas yang bertujuan untuk memangkas jalur yang dianggap tidak lagi mengarah ke solusi. 

Kriteria pemangkasan secara umum: 

• Nilai simpul tidak lebih baik dari nilai terbaik sejauh ini. 
• Simpul tidak merepresentasikan solusi yang ‘feasible’ karena ada batasan yang dilanggar.Solusi yang ‘feasible’ pada simpul tersebut hanya terdiri atas satu titik → tidak ada pilihan lain.

Nama            : Ghazali

NPM             : 19312188

Kelas             : IF 19 D

Fakultas         : http://ftik.teknokrat.ac.id/

Universitas    : https://teknokrat.ac.id/