BRACH AND BOUND SEARCH

BRACH AND BOUND SEARCH

Branch and bound merupakan metode yang membagi permasalahan menjadi subregion yang mengarah ke solusi (branching) dengan membentuk sebuah struktur pohon pencarian (search tree) dan melakukan pembatasan (bounding) untuk mencapai solusi optimal. Proses branch merupakan membangun semua cabang tree yang menuju solusi, sedangkan proses bound merupakan menghitung node dengan memperhatikan batas constraint.

Prosedur di dalam branch and bound dilakukan berulang secara rekursif hingga membentuk sebuah pohon pencarian (search tree) dan melakukan proses bounding dengan menentukan batas atas (upper bound) dan batas bawah (lower bound). Ketika tangkai pohon (node) dicabangkan, satu atau lebih node ditambahkan ke job yang ada di depannya. Pemilihan node untuk cabang yang memiliki jumlah job paling besar. Sebuah lower bound untuk makespan dihitung berdasarkan masing-masing node yang dihasilkan.

Dalam branch and bound terdapat tiga tahap dasar yaitu percabangan (branching), pembatasan (bounding), dan pengukuran (fathoming). Penjelasan ketiga tahap tersebut adalah sebagai berikut :

1.Percabangan (branching)

   Percabangan berhubungan dengan pemilihan submasalah yang belum dicabangkan dan

   memecahnya menjadi submasalah yang lebih kecil.
2. Pembatasan (bounding)
   Pembatasan dilakukan untuk menentukan suatu batas yang digunakan untuk melihat   

   seberapa baik solusi untuk suatu submasalah.
3. Pengukuran (fathoming)
   Pengukuran dilakukan untuk menentukan apakah suatu submasalah perlu untuk ditelusuri  

   lebih lanjut.

Algoritma Branch and Bound

Algoritma Branch and Bound mencari sejumlah solusi yang lengkap untuk masalah yang ada dengan hasil yang terbaik. Walaupun begitu, penggunaan satu per satu secara eksplisit tidak mungkin dilakukan dalam kaitan penambahan sejumlah solusi yang potensial. Penggunaan batas (bound) untuk fungsi yang akan dioptimalkan dikombinasikan dengan nilai solusi terbaik yang ada memungkinkan algoritma untuk mencari bagian-bagian dari sejumlah solusi secara implisit. Pada titik sembarang sepanjang proses solusi, status solusi yang berkenaan dengan pencarian sejumlah solusi dijelaskan oleh sekelompok ahli yang mempelajari dan belum seluruhnya dieksplorasi tetapi sejauh ini merupakan solusi terbaik yang ada saat ini. Pada awalnya hanya ada subset yaitu ruang solusi lengkap (complete solution space) dan solusi terbaik sejauh ini yang ditemukan baru 1 (satu). Subspace yang belum diperiksa direpresentasikan sebagai titik-titik dalam sebuah pohon pencarian yang dihasilkan secara dinamis, dimana awalnya hanya berisi root, dan setiap iterasi dari algoritma Branch and Bound klasik memproses satu titik. Iterasi memiliki tiga komponen utama yaitu pemilihan titik untuk diproses, kalkulasi batasan (bound), dan pencabangan. Seperti gambar di bawah ini.

Urutan dari pencarian ini dapat dipertukarkan sembarang sesuai dengan strategi yang dipilih untuk memilih node berikutnya yang akan diproses. Jika pemilihan subproblem berikutnya didasarkan pada nilai batas (bound) dari subproblem, maka operasi pertama dari iterasi setelah

pemilihan node adalah pencabangan (branching), yaitu pembagian ruang solusi dari node menjadi dua atau lebih subspace untuk diperiksa dalam sebuah iterasi sub rangkaian. Untuk setiap rangkaian, akan diperiksa apakah subspace terdiri dari satu solusi, yang kemudian dibandingkan Pencarian menggunakan algoritma Branch and Bound dengan solusi terbaik yang ada selama pencarian. Jika tidak, pembatasan fungsi untuk subspace dihitung dan dibandingkan dengan solusi terbaik yang diperoleh. Jika pencarian tidak dapat dilanjutkan dimana subspace

tidak berisi solusi yang optimal, keseluruhan subspace akan dibuang, selain itu subspace akan disimpan dalam kelompok node bersama-sama dengan batasannya (bound). Alternatif lainnya adalah dengan memulai menghitung batas (bound) dari node yang terpilih dan kemudian mencabangkannya jika diperlukan. Node-node yang dibuat kemudian disimpan bersamaan dengan batas dari node yang diproses. Pencarian berakhir saat tidak ada lagi bagian dari ruang solusi yang diperiksa, dan solusi optimal kemudian dicatat sebagai solusi terbaik.

Terminologi branch and bound

Dalam Branch and Bound terdapat metode untuk meminimalkan masalah dimana kasus maksimalisasi masalah dapat dikerjakan dengan cara yang sama. Masalahnya adalah meminimalkan fungsi f(x) dari variabel (x1 ... xn) sepanjang ruang solusi yang mungkin, S :

Fungsi f disebut fungsi objektif (objective function) dan dapat berupa berbagai tipe. Suatu kemungkinan solusi umumnya ditentukan oleh kondisi umum pada variabel, meskipun begitu variabel ini harus bukan bilangan bulat atau biner negatif dan batasan khusus menentukan struktur dari set yang mungkin. Pada satu kesempatan, satu set potensial, P, berisi S dimana f masih dibutuhkan. Fungsi g(x) diperlukan pada S (atau P) dengan g(x) _ f(x) untuk semua x dalam S (atau P). Baik P dan g sangat diperlukan pada konteks Branch and Bound. Pada gambar di bawah ini menjelaskan situasi dimana S dan P merupakan interval dari real.

Pengertian gambar : Hubungan antara fungsi bounding g dan fungsi objektif f pada satuan S dan P dari solusi yang potensial dan mungkin pada suatu masalah

Algoritma Branch and Bound digunakan untuk meminimalkan masalah. Oleh karena itu algoritma ini terdiri dari tiga komponen, yaitu :

1. Fungsi pembatas (bounding) : fungsi yang disediakan subspace dari ruang solusi dengan batas rendah untuk nilai solusi terbaik yang diperoleh dalam subspace.

2. Strategi seleksi : suatu strategi untuk memilih solusi subspace aktif untuk diperiksa dalam iterasi, dan

3. Aturan pencabangan (branching) : Suatu aturan yang diaplikasikan jika subspace setelah diperiksa tidak dapat dibatalkan, karena itu pembagian subspace kedalam dua atau lebih subspace untuk diperiksa dalam sub rangkaian iterasi.

Penerapan Algoritma Branch And Bound Pada Assigment Problem

Ada dua hal penting yang harus diidentifikasi di dalam algoritma branch and bound. Yang pertama adalah representasi masalah optimasi di dalam pohon uang status, lebih sederhananya adalah membuat pengertian state simpul pohon yang diasosiasikan dengan masalah optimasi tersebut. Yang kedua adalah menentukan fungsi nilai pembatas. Pada assignment problem proses branching dilakukan dengan memilih agent untuk mengerjakan setiap task. Apabila suatu agent sudah dipilih untuk melakukan suatu task, dia tidak boleh dipilih lagi untuk task berikutnya. Pemilihan task dilakukan secara bertahap. Simpul pada aras pertama merepresentasikan pemilihan task pertama, simpul ini didapatkan dengan megassign variable t1 dengan id agent yang mungkin, apabila ada n agent maka jumlah simpul pada aras pertama adalah n buah. Aras kedua merepresentasikan pemilihan task kedua, jumlah simpul pada aras ini adalah n-1, karena satu agent sudah dipilih untuk task sebelumnya. Begitu seterusnya sampai aras yang Solusi yang dihasilkan brupa tupple <t1,...,tn> Nilai batas suatu simpul didefinisikan dengan cost minimum yang paling mungkin apabila kita memilih agent yang bersesuaian dengan simpul tersebut.

C(X) = Σ c(k,l) + c(i,j) + rminj

C(X) = cost minimum paling mungkin apabila kita

memilih agent i untuk task j. c(k,l) = fungsi biaya apabila agent k mengerjakan task l, dimana k adalah element dari himpunan agen A dan l[1..j-1]. c(i,j) = fungsi biaya apabila agent i mengerjakan task j. rmin = jumlah cost minimum dari task-task yang belum dikerjakan apabila kita memilih agent yang bersesuaian dengan simpul X.

Pohon ruang status static untuk assignment problem dengan n task dan n agent

Untuk mempermudah perumusan rminj, maka graf bipartite yang memodelkan assignment problem harus diubah bentuknya menjadi matriks ketetanggaan. Karena simpul graf pada himpunan yang sama tidak saling bertetanggaan maka kita tidak perlu membuat element matriks yang menyatakan bobot sisi simpul yang bertetanggaan tersebut. Pada setiap kasus assignment problem selalu ada 2 himpunan simpul graf, yaitu himpunan simpul agent dan himpunan simpul task. Dalam pembentukan matriks salah satu himpunan elementelementnya akan direpresentasikan dengan indeks baris matriks dan element-element himpunan lainnya akan direpresentasikan dengan indeks kolom matriks. Isi element matriks adalah bobot sisi antara simpul-simpul yang berada pada himpunan berbeda. Setelah matriks M tersebut terbentuk, barulah kita memulai proses branching. Untuk pemilihan agent pada task pertama nilai Σ c(k,l) adalah 0, jelas karena belum ada task yang dikerjakan sebelumnya. Kemudian kita akan menghitung rminj untuk setiap simpul, rminj dihitung dengan Rumus rminj = max{Ma(j+1) +Ma3+…+Man}, a element A, nilai a

untuk setiap kolom tidak boleh sama. Sebelum menghitung rminj kita harus merubah semua

element pada baris ke-i (apabila pada simpul tersebut yang dipilih agent i) dengan ∞, hal ini dilakukan agar agent ke-I tidak diperhitungkan lagi ketika mencari rminj. Ini sangat wajar mengingat setiap agent hanya boleh menerima task satu kali. Setelah itu barulah kita menghitung nilai C(X) dari simpul tersebut kemudian memasukkan simpul tersebut ke dalam antrian. Proses pengisian antrian terus dilakukan sampai semua anak dari simpul-E di generate, setelah itu barulah dilakukan pemilihan element-E yang baru. Simpul yang dipilih sebagai simpul-E adalah simpul yang memiliki nilai C(X) terkecil. Setelah itu simpul-E yang baru akan dibentuk sampai sebuah simpul solusi dimasukkan kedalam antrian dan simpul lainnya dinyatakan mati. Simpul dinyatakan mati apabila nilai batas dari simpul tersebut lebih besar dari simpul solusi. Agar lebih jelas penulis akan mencoba menyajikan pencarian solusi assignment problem ini dalam sebuah contoh kasus.

Contoh Kasus

Misalkan terdapat n orang dan n buah pekerjaan (job). Setiap orang akan di-assign dengan sebuah pekerjaan. Penugasan orang ke-i dengan pekerjaan ke-j membutuhkan biaya sebesar c(i,j). Bagaimana melakukan penugasan sehingga total biaya penugasan adalah

seminimal mungkin. Graf bipartite dari persoalan tersebut adalah sbb. :

Lingkaran kecil pada bagian kiri merupakan simpul orang(agent) dan pada bagian kanan merupakan simpul job(task), angka pada sisi merupakan nilai cost untuk

simpul tetangganya. Langkah awal adalah membuat matriks untuk graf tersebut. Indeks baris menyatakan simpul orang dan indeks kolom menyatakan simpul job. Matriks

ketetanggaanya adalah sbb. :

Job1 Job2 Job3 Job4

| 8       2       7      9 | Orang A

| 6       3       4      7 | Orang B

| 1      8        5      4 | Orang C

| 7      4        9      6 | Orang D

Simpul 1 atau simpul akar adalah simpul dummy, dalam assignment problem ini kita tidak perlu menghitung nilai batasnya. Selanjutnya kita akan langsung menghitung nilai

batas simpul anak-anaknya.

• Simpul 2, t1 = A

Job1 Job2 Job3 Job4

| ∞     ∞      ∞      ∞ | Orang A

| 6       3      4       7 | Orang B

| 1       8      5        4 | Orang C

| 7       4      9        6 | Orang D

S(2) = Σ c(k,l) + c(A,1) + rminj = 0 + 8 + 11 = 19

Seterusnya kita coba untuk setiap anak yang mungkin, untuk job1 ini kita menemukan nilai S(X) terkecil yaitu 13 untuk X = 4. Pada simpul ke-4 nilai t1 bernilai C, berarti kita memilih orang C untuk job1. Matriksnya adalah sebagai berikut.

Job1 Job2 Job3 Job4

| 8       2       7       9 | Orang A

| 6       3       4       7 | Orang B

| ∞      ∞     ∞       ∞ | Orang C

| 7      4        9       6 | Orang D

Untuk selanjutnya kita akan mengeluarkan simpul 4 dari antrian dan men-expand simpul 4.

Setelah menentukan orang untuk job pertama kita akan menentukan untuk job kedua, pada tahap 2 ini orang yang sebelumnya sudah dipilih tidak boleh dipilih kembali. Karena untuk kali pertama kita akan me-expand simpul 4, maka simpul anak dari simpul 4 tidak boleh dibentuk dengan me-assign nilai t2 dengan C.

• Simpul 6, t2 = A

Job1 Job2 Job3 Job4

|  ∞    ∞      ∞      ∞ | Orang A

| 6       3      4       7 | Orang B

|  ∞    ∞     ∞       ∞ | Orang C

| 7      4       9        6 | Orang D

S(6) = Σ c(k,l) + c(A,2) + rminj = 1 + 2 + 10 = 13

Untuk S(7) diperoleh 16 dan S(8) = 17. Kemudian kita membandingkan S(X) yang kita peroleh pada tahap ini dengan S(X) pada tahap yang sebelumnya. X yang memiliki nilai S(X) terkecil adalah 6. Selanjutnya kita kita keluarkan simpul 6 dari atrian dan expand simpul 6.

• Simpul 9, t3 = B

Job1 Job2 Job3 Job4

| ∞ ∞ ∞ ∞ | Orang A

| ∞ ∞ ∞ ∞ | Orang B

| ∞ ∞ ∞ ∞ | Orang C

| 7  4  9   6 | Orang D

S(9) = Σ c(k,l) + c(B,3) + rminj = (1+2) + 4 + 6 = 13

Unruk S(10) kita peroleh 19, kemudian kita bandingkan lagi semua simpul pada antrian pada antrian, hasilnya simpul 9 memiliki nilai terkecil. Setelah itu kita keluarkan simpul 9 dari antrian dan kita expand simpul 9.

• Simpul 11, t4 = D

Job1 Job2 Job3 Job4

| ∞ ∞ ∞ ∞ | Orang A

| ∞ ∞ ∞ ∞ | Orang B

| ∞ ∞ ∞ ∞ | Orang C

| 0  0  0  0 | Orang D

S(11) = Σ c(k,l) + c(B,3) + rminj = (1+2+4) + 6 + 0 = 13

Simpul 11 ini adalah satu-satunya anak dari simpul 9 dan merupakan daun dari pohon ruang status untuk mengecek apakah telah didapat solusi optimum kita akan membandingkan nilai S(11) dengan semua S(X), X simpul pada antrian. Apabila tidak ada S(X) yang lebih kecil dari

S(11) maka kita matikan semua simpul pada antrian dan menyatakan bahwa solusi optimum telah ditemukan. Apabila masih ada S(X) yang lebih kecil kita harus meexpand simpul X tersebut sampai ditemukan solusi yang lebih optimum atau sampai semua simpul dalam antrian mati. Pada contoh kasus ini tidak ada simpul pada antrian yang memiliki nilai S(X) lebih kecil dari 13, sehingga kita menganggap bahwa solusi optimum sudah ditemukan. Solusi optimum tersebut dapat dinyatakan dengan tuple<C,A,B,D> dengan total cost = 13.

Kesimpulan

Algoritma branch and bound merupakan algoritma yang sering gunakan untuk menyelesaikan optimasi. Algortima branch and bound menggunakan skema BFS yang lebih pintar, yaitu menggunakan fungsi pembatas bound untuk menentukan simpul-E yaitu simpul yang akan di-expand berikutnya. Kasus terburuk dari algoritma ini sama seperti exchaustive search yaitu n!, namun hal ini sangat jarang terjadi karena algoritma menggunakan bantuan fungsi pembatas dalam pencarian solusi. Assigment problem salahsatu masalah dasar pada bidang optimasi kombinatorial, selain branch and bound banyak algoritma lain yang dapat digunakan untuk mencari solusi optimum dari masalah ini. Ketepatan solusi optimum yang diperoleh dari algoritma branch and bound, sangat tergantung pada formula fungsi pembatas yang dipilih. Bagaimanapun juga formula itu dipilih hanya berdasarkan insting dan pengalaman, sehingga algoritma ini terkadang tidak memberikan hasil yang benar-benar optimal. Namun apabila aspek waktu lebih dipentingkan daripada ketepatan hasil, algoritma ini bisa menjadi pilihan dalam menyelesaikan masalah optimasi.

Pengertian A* Search

·         A* pencari menggunakan kedua path biaya dan nilai-nilai heuristik
            biaya (p) adalah biaya jalan p.
            h (p) memperkirakan dari biaya dari akhir p untuk suatu tujuan.

·          Misalkan f (p) = biaya (p) + h (p).
            f (p) memperkirakan biaya total jalur pergi dari node awal
            untuk tujuan melalui p.

A* Aearch Algorithm

A* adalah campuran dari terendah-biaya pertama dan Best-Pertama pencarian. Ini memperlakukan perbatasan sebagai prioritas antrian diperintahkan oleh f (p). Selalu memilih node di perbatasan dengan terendah Diperkirakan jarak total.

Analsis Of A*

Mari kita berasumsi bahwa biaya busur secara ketat positif.
Kelengkapan: ya.

Kompleksitas waktu: O (bm)
heuristik bisa benar-benar informatif dan tepi biaya semua bisa sama, yang berarti bahwa A? melakukan hal yang sama hal sebagai BFS

Kompleksitas ruang: O (bm)
seperti BFS, A? mempertahankan perbatasan yang tumbuh dengan ukuran pohon

Optimalitas: ya.

Optimality Of A*

Jika A* mengembalikan solusi, bahwa solusi dijamin akan optimal,

·         selama faktor percabangan terbatas

·         Biaya busur non-negatif

·         h (n) adalah meremehkan panjang jalan terpendek dari n ke node tujuan.

Why Is A* Optimal?

·         Asumsikan untuk kontradiksi bahwa beberapa  jalan lain sebenarnya
jalan terpendek untuk tujuan

·         Pertimbangkan saat sebelum p dipilih dari perbatasan.
Beberapa bagian dari jalan juga akan di perbatasan, mari kita sebut ini
path parsial

·         Karena p diperluas sebelum , f (p)? f ().

·         Karena p adalah tujuan, h (p) = 0. demikian
biaya (p)? biaya () + h ().

·         Karena h adalah diterima, biaya () + h ()? biaya () untuk setiap
jalan p0 untuk tujuan yang memanjang

·         Dengan demikian biaya (p)? biaya () untuk setiap p0 jalan lain ke tujuan. ini
bertentangan asumsi kita bahwa  adalah jalan terpendek.

Optimal Eficiency Of A*

·         Bahkan, kita dapat membuktikan sesuatu yang lebih kuat tentang A* : dalam akal (mengingat heuristik tertentu yang tersedia) ada algoritma pencarian bisa berbuat lebih baik!

·         Optimal Efisiensi: Di antara semua algoritma optimal yang dimulai dari node awal yang sama dan sama-sama menggunakan heuristik h​​, A* memperluas jumlah minimal