BAB 2 LANDASAN TEORI 2.1
Constraint Satisfaction Problem
2.1.1 Pengertian Dasar Constraint adalah batasan dalam pengertian yang paling sederhana. Dalam kehidupan sehari-hari, mungkin sering didengar kalimat seperti berikut: pekerjaan itu harus selesai sebelum jam 10 malam, seorang guru cuma dapat mengajar maksimal tiga kelas dalam sehari, persegi panjang harus berada di sebelah kiri dari lingkaran. Seseorang dapat melakukan apa saja dalam hal ini kecuali melanggar constraint, misalnya dia dapat menggeser persegi panjang ke mana saja sepanjang persegi panjang itu ada di sebelah kiri lingkaran, dia dapat mengajar kelas sebanyak mungkin asal jangan lebih dari tiga untuk hari apa saja, dia dapat menyelesaikan pekerjaan kapan saja asal sebelum jam 10 malam. Dari kehidupan sehari-hari ini definisi constraint dibuat sedikit lebih ilmiah. Constraint adalah relasi logis di antara beberapa variabel, yang masing-masing mengambil sebuah nilai dalam sebuah domain. Jadi constraint itu membatasi nilai yang dapat diambil oleh variabel tersebut. Dalam contoh guru mengajar kelas sebanyak mungkin asal jangan lebih dari tiga untuk hari apa saja, variabelnya adalah jumlah kelas yang diambil guru, domain-nya adalah bilangan asli, batasannya adalah variabel yang bersangkutan tidak boleh lebih dari tiga. Constraint sering digunakan dalam percakapan sehari-hari jika dilihat definisi paragraf di atas. Umumnya orang jarang menyelesaikan masalah dengan satu constraint seperti dalam contoh di atas, tetapi masalah-masalah yang ada biasanya disertai dengan koleksi constraint yang jarang berkaitan. Hal ini tentu saja memperumit masalah. Sebelumnya penyebutan masalah dengan constraint ini distandarkan. Komunitas internasional memberi nama constraint satisfaction problem kepada masalah dengan constraint ini. Masalah optimalisasi penjadwalan pekerjaan termasuk constraint satisfaction problem, tepat-
7 nya constraint satisfaction optimization problem. Perbedaan constraint satisfaction problem dengan constraint satisfaction optimization problem akan dibahas nantinya. Dari sini juga dapat diambil pengertian dari penyelesaian terhadap constraint satisfaction problem. Penyelesaian dari constraint satisfaction problem adalah pemberian nilai terhadap semua variabel dari domain masing-masing variabel yang berkaitan di mana semua constraint dipenuhi. Dalam contoh guru mengajar kelas sebanyak mungkin asal jangan lebih dari tiga untuk hari apa saja, penyelesaian dari constraint satisfaction problem ini adalah variabel yang bersangkutan (jumlah kelas yang diambil guru) mendapat nilai 1 atau 2 atau 3 karena nilai 1 atau 2 atau 3 berada pada domain variabel itu (bilangan asli) dan tidak melanggar constraint (tidak boleh lebih dari tiga). Untuk menyelesaikan masalah constraint satisfaction problem, diperlukan constraint programming. Constraint programming adalah pembelajaran sistem komputasi berdasarkan constraint. Ide utama dari constraint programming ini adalah menyelesaikan masalah dengan menyatakan constraint (kondisi, sifat, kebutuhan) yang harus dipenuhi oleh solusi. Dengan kata lain, constraint programming adalah pendekatan alternatif terhadap pemrograman yang berisikan permodelan suatu masalah sebagai himpunan kebutuhan (constraint) yang berurutan diselesaikan metode umum ataupun spesifik untuk domain (Krzysztof Apt, 2005, p1). 2.1.2 Definisi Formal Constraint Satisfaction Problem Berikut adalah definisi formal dari hal-hal yang berhubungan dengan constraint satisfaction problem. Definisi 1. Sebuah Domain berisikan nilai yang dapat diambil oleh sebuah variabel. Sebuah domain itu bersifat khusus untuk sebuah variabel. Jadi masing-masing variabel itu memiliki domain-nya masing-masing. Kesepakatan umum memberi huruf kapital D untuk menyebut domain. Berikut adalah contoh untuk domain dari variabel x. (nilai x) ∈ Dx
8 Domain dalam constraint satisfaction problem seringnya memiliki anggota bilangan bulat. Anggota sebuah domain boleh saja bukan numerik. Hal yang dapat menjadi anggota dari sebuah domain adalah simbol. Contoh anggota domain yang bukan numerik adalah nama bulan dalam satu tahun. Anggota domain-nya adalah Januari, Februari, Maret, April, Mei, Juni, Juli, Agustus, September, Oktober, November, dan Desember. Definisi 2. Sebuah label adalah pemberian nilai dari domain sebuah variabel ke variabel itu. Jika ingin memberi nilai v ke variabel x digunakan notasi <x,v>. Tentunya v ∈ Dx . Definisi 3. Kumpulan label adalah tupel dari label. Kumpulan label digunakan untuk menyatakan pemberian nilai-nilai ke variabel yang jumlahnya lebih dari satu. Digunakan notasi tupel (<x1 , v1 ><x2 , v2 >. . .<xn , vn >) untuk menyatakan kumpulan label dari pemberian v1 , v2 , . . . , vn pada x1 , x2 , . . . , xn . Karena kumpulan label adalah tupel, urutan dari label pada representasi ini menjadi tidak signifikan. Dengan kata lain, (<x, a>
) dianggap sama seperti kumpulan label (<x, a>), (<x, a>), dan lain-lain. Di samping itu, adalah penting untuk mengingat bahwa tupel tidak memiliki anggota yang sama. Sebuah constraint pada sebuah himpunan variabel membatasi nilai yang dapat diambil secara bersamaan. Menurut konsep, sebuah constraint dapat dilihat sebagai sebuah himpunan yang memiliki semua kumpulan label yang valid pada variabel yang bersangkutan (Edward Tsang, 1996, p7). Walaupun begitu, pada kenyataannya di lapangan, constraint dapat dinyatakan dengan banyak cara, contohnya, fungsi, pertidaksamaan, matriks, dan lain-lain. Definisi 4.
9 Sebuah constraint menurut konsep adalah sebuah himpunan kumpulan label pada variabel yang berkaitan. Digunakan Cs untuk menyatakan constraint pada himpunan variabel S. Bila ada masalah, solusi tentu ingin dicari. Dalam constraint satisfaction problem, sebelum solusi constraint satisfaction problem secara matematika dibahas, akan dibahas pengertian pemenuhan constraint. Sebenarnya pemenuhan constraint adalah relasi binari antara sebuah label atau sebuah kumpulan label dengan sebuah constraint. Definisi 5. Jika variabel-variabel dari kumpulan label X adalah sama dengan variabel-variabel dari elemen kumpulan label pada constraint C, maka X memenuhi-constraint C jika dan hanya jika X adalah elemen dari C: memenuhi-constraint( (<x1 , v1 ><x2 , v2 >. . . <xk , vk >), Cx1 ,x2 ,...,xk ) ≡ (<x1 , v1 ><x2 , v2 >. . . <xk , vk >) ∈ Cx1 ,x2 ,...,xk Memenuhi constraint juga didefinisikan antara label dan constraint unari. Definisi 6. memenuhi-constraint(<x, v>, Cx ) ≡ (<x, v>) ∈ Cx Jika dikatakan kumpulan label L memenuhi constraint C, itu artinya jika C adalah sebuah constraint pada variabel x1 , x2 , . . . , xk atau subset-nya, maka label pada variabel itu dalam L adalah valid sepanjang C dipenuhi. Untuk contohnya, () memenuhi constraint Cc,d jika dan hanya jika () adalah anggota Cc,d : Cc,d = . . ., (), . . . Setelah berbagai hal yang merupakan bagian dari constraint satisfaction problem itu sudah didefinisikan, pekerjaan mendefinisikan constraint satisfaction problem itu menjadi
10 mudah. Sebelumnya untuk menyegarkan ingatan, dalam bahasa umum constraint satisfaction problem adalah sebuah masalah dengan sebuah himpunan variabel dengan jumlah berhingga, masing-masing diasosiasikan dengan sebuah domain dengan jumlah anggota berhingga juga, dan sebuah himpunan constraint yang membatasi nilai yang dapat diambil oleh variabel-variabel ini secara bersamaan. Berikut diberikan definisi formal dari constraint satisfaction problem. Definisi 7. Sebuah constraint satisfaction problem adalah sebuah himpunan dengan tiga variabel: (Z, D, C) di mana Z = sebuah himpunan dari variabel-variabel dengan jumlah berhingga x 1 , x2 , . . . , x n ; D = sebuah fungsi yang memetakan setiap variabel pada Z ke sebuah himpunan dari objek-objek: D : Z → himpunan objek-objek dengan jumlah berhingga (jenis apa pun). Disebut Dxi sebagai himpunan dari objek-objek yang dipetakan dari xi oleh D. Objek-objek ini adalah nilai-nilai yang mungkin bagi xi dan himpunan Dxi sebagai domain xi ; C = sebuah himpunan constraint yang berhingga (yang memiliki kemungkinan kosong) atas sebuah subset variabel-variabel di Z. Dengan kata lain, C adalah sebuah himpunan atas kumpulan label. Digunakan csp(P) untuk menyatakan P adalah constraint satisfaction problem. Cx1 ,x2 ,...,xk membatasi himpunan kumpulan label yang x1 , x2 , . . . , dan xk yang dapat diambil secara bersamaan. Sebagai contoh, jika variabel x hanya dapat mengambil nilai a, b dan c, maka ditulis Cx = (<x, a>), (<x, b>), (<x, c>). Perhatikan perbedaan antara
11 Cx dan Dx : Cx adalah sebuah himpunan kumpulan label sementara Dx adalah sebuah himpunan nilai. Nilai x yang mungkin juga harus memenuhi constraint selain Cx . Hal itu berarti walaupun <x, a> memenuhi Cx , a mungkin bukan nilai yang valid bagi x untuk keseluruhan masalah. Untuk mendapatkan label yang valid, <x, a> mesti memenuhi semua constraint yang mengandung constraint x, contohnya Cx,y , Cx,y,z , dan lain-lain. Berikut adalah pengertian matematika dari solusi atas constraint satisfaction problem. Definisi 8. Sebuah tupel solusi atas sebuah constraint satisfaction problem adalah kumpulan label yang semua anggotanya memenuhi semua constraint: ∀csp((Z, D, C)): ∀x1 , x2 , . . . , xn ∈ Z: ∀v1 ∈ Dx1 , v2 ∈ Dx2 , . . . , vn ∈ Dxn : tupel solusi((<x1 , v1 > <x2 , v2 > . . . <xn , vn >), (Z, D, C)) ≡ ((Z = x1 , x2 , . . . , xn ) ∧ (∀C ∈ C: memenuhi-constraint((<x1 , v1 > <x2 , v2 > . . . <xn , vn >), C))) Sebuah constraint satisfaction problem disebut memiliki penyelesaian jika memiliki tupel solusi. Tergantung dari kebutuhan aplikasinya, constraint satisfaction problem dapat dikategorikan menjadi beberapa kategori sebagai berikut. 1. Constraint satisfaction problem di mana yang dicari adalah solusi yang mana saja. 2. Constraint satisfaction problem di mana yang dicari adalah semua solusi. 3. Constraint satisfaction problem di mana yang dicari adalah solusi yang optimal, di mana optimal itu didefinisikan menurut kebutuhan pengguna. 2.2
Pencarian Sistematis
2.2.1 Generate and Test Sebenarnya siapa pun dapat menyelesaikan constraint satisfaction problem yang mana pun. Caranya gampang sekali. Mencoba semua kombinasi nilai ke variabel-variabel yang
12 ada. Cari ini dijamin dapat memperoleh sebuah solusi, jika ada, atau membuktikan bahwa masalah ini tidak bisa dipecahkan. Oleh karena itu, algoritma ini dipastikan dapat mencari semua solusi dengan lengkap. Untuk constraint satisfaction problem yang sederhana tentu saja ini tidak menjadi masalah. Tetapi constraint satisfaction problem adalah masalah NPhard. Artinya seiring dengan meningkatnya jumlah variabel pada constraint satisfaction problem, jumlah kombinasi yang harus dicoba meningkat secara kuadrat. Menghabiskan waktu yang sangat lama untuk mencoba semua kombinasi bahkan walaupun dibantu komputer dengan spesifikasi yang canggih dalam menghitungnya. Jadi kebanyakan waktu dalam riset constraint programming dihabiskan dalam mencari algoritma pencarian yang efisien. Dari riset ini muncul beberapa algoritma pencarian sistematis. Algoritma generate and test memang tidak efisien tapi algoritma ini menjadi dasar dari pengembangan algoritma pencarian sistematis lainnya. Oleh karena itu, untuk memahami algoritma pencarian sistematis lainnya, perlu dipahami terlebih dahulu algoritma generate and test. Sebelum algoritma generate and test ini dibahas, ada baiknya pencarian kombinasi nilai ke variabel-variabel itu divisualisasikan ke dalam bentuk pohon. Visualisasi pencarian kombinasi nilai bagi variabel-variabel akan memudahkan pemahaman algoritma pencarian sistematis yang mana pun dalam constraint programming. Misalnya ada constraint satisfaction problem sebagai berikut. Constraint satisfaction problem ini terdiri dari tiga variabel, a, b, dan c. Da untuk constraint satisfaction problem ini adalah {1, 2, 3} sedangkan Db -nya {1, 2} dan Dc -nya {1, 2}. Dalam gambar 2.2, pencarian solusinya mulai dari variabel a. Karena jumlah anggota Da adalah 3 maka ada 3 jalan dari titik yang paling atas (solusinya mulai dicari dari variabel a). Titik yang ditandai dengan ∗ mewakili status pencarian. Artinya dalam konteks gambar ini adalah diputuskan (setidaknya untuk sementara) untuk memberi nilai 1 ke variabel a dan sedang mempertimbangkan nilai apakah yang akan diberikan ke variabel b. Algoritma generate and test dapat dibayangkan sebagai algoritma depth-first search yang paling dasar. Dalam konteks gambar pohon ini, algoritmanya dimulai dengan nilai a paling kiri yaitu 1, kemudian nilai b paling kiri yaitu 1, kemudian nilai c paling kiri yaitu 1.
13
Gambar 2.1: Ruang pencarian untuk csp(Z, D, C) dengan urutan (a, b, c) di mana Z = {a, b, c}, Da = {1, 2, 3}, Db = {1, 2}, dan Dc = {1, 2} Setelah semua variabel diberi nilai, barulah algoritma ini menguji apakah kombinasi nilai ini memenuhi semua constraint yang ada. Jika tidak, dicoba nilai variabel yang terakhir kali diberi nilai (c) yang lain, yaitu 2 . Ujilah lagi. Jika tidak, karena semua nilai untuk variabel c untuk kumpulan label () sudah dicoba, maka dicoba nilai untuk variabel b berikutnya. Begitu seterusnya. Jumlah kombinasi yang dicoba oleh algoritma ini sama dengan ukuran produk Cartesian semua domain variabel. Seperti yang sudah dijelaskan, algoritma generate and test ini sangat tidak efisien karena algoritma ini menghasilkan banyak pemberian nilai ke variabel-variabel yang ditolak pada fase uji coba. Sebagai tambahan, generator seakan-akan tidak peduli dengan pemberian nilai yang memiliki konflik dan terus memberikan nilai yang lain tanpa memandang konflik. Singkatnya, algoritma ini merupakan generator yang buta. Dapat dipastikan algoritma ini tidak berguna pada hampir semua masalah constraint satisfaction problem karena kebanyakan masalah constraint satisfaction problem bersifat eksponensial. Contohnya pada masalah pewarnaan tiga warna pada n verteks. Ada 3n kemungkinan pewarnaan. Untuk n lebih besar daripada 20, mengiterasi semua kemungkinan berada di luar jangkau-
14 an (Brian Hayes, 2003, p13). Ada yang dapat dilakukan untuk meningkatkan pendekatan algoritma ini. 2.2.2 Backtracking Algoritma ini adalah algoritma yang paling umum dan paling banyak dipakai dalam aplikasi penghitungan untuk constraint satisfaction problem.
Pada dasarnya back-
tracking secara perlahan-lahan mencoba mengembangkan kumpulan label yang masih belum lengkap untuk beberapa variabel, menuju ke kumpulan label yang lengkap, dengan secara berulang-ulang memilih nilai bagi variabel yang lain yang konsisten dengan solusi yang masih belum lengkap ini.
Algoritma backtracking ada-
lah pendekatan brute-force yang sudah diperbaiki, yang secara sistematik mencari sebuah solusi atas sebuah masalah di antara semua pilihan yang ada (Eitan Gurari, http://www.cse.ohio-state.edu/˜gurari/course/cis680/cis680Ch19.html, 1999). Berikut ini adalah alur algoritma ini. Variabel yang diperiksa sekarang diberi nilai tertentu. Label ini diperiksa kecocokannya dengan semua label yang sudah masuk dalam tupel solusi. Jika label ini tidak cocok dengan label-label yang sudah ada di tupel solusi, maka label ini akan ditolak, dan label yang lain akan dicoba. Pada kasus di mana semua label sudah ditolak, label yang masuk ke tupel solusi terakhir kalinya dianggap tidak cocok lagi, dan ditolak. Memeriksa label yang masuk ke tupel solusi terakhir kali disebut backtrack. Proses ini berlanjut sampai semua variabel sudah diberi label atau tidak ada lagi label yang bisa di-backtrack, yakni dalam hal semua label untuk variabel pertama sudah ditolak. Pada kasus terakhir ini, constraint satisfaction problem dianggap tidak memiliki penyelesaian. Pada backtracking ini, tidak ada usaha untuk menggunakan constraint selain pada saat memeriksa kekonsistenan label untuk variabel yang sedang diperiksa dengan kumpulan label yang sudah ada di dalam tupel solusi. Proses ini adalah pencarian yang sangat melelahkan di mana secara sistematis dieksplorasi seluruh ruang pencarian. Proses ini sama dengan generate and test, bersifat lengkap dan semua hasil yang didapatkannya memenuhi
15 constraint. Tidak ada usaha untuk mengurangi sebagian ruang pencarian. Contoh berikut akan memperjelas algoritma backtracking dan perbedaannya dengan generate and test. Ada sebuah constraint satisfaction problem yang terdiri dari 3 variabel, yaitu a dengan Da = {1, 2, 3, 4}, b dengan Db = {1, 2, 3, 4}, dan c dengan Dc = {4, 5, 6}. Constraint-nya adalah Ca,b = a < b dan Ca,b,c = a + b = c. Pencarian solusi dimulai dari variabel a. Diberikan nilai 1 untuk a. Pada saat ini label akan diperiksa apakah melanggar constraint yang ada. Tapi karena tidak ada constraint unari untuk a maka pencarian bergerak ke tingkat yang lebih dalam, yaitu tingkat di mana variabel b berada. b diberi nilai 1. Pada saat ini label diperiksa apakah konsisten dengan kumpulan label yang sudah ada dalam tupel solusi () dan constraint unari untuk b jika ada. Label tidak konsisten dengan kumpulan label () karena melanggar constraint Ca,b . Maka dicari nilai yang lain untuk b, yaitu 2. Seperti biasa label ini akan diperiksa apakah konsisten dengan kumpulan label (). Hasilnya adalah konsisten. Pencarian pun bergerak ke tingkat yang paling dalam, yaitu tingkat di mana variabel c berada. c diberi nilai, yaitu 4. Pada saat ini label akan diperiksa apakah konsisten dengan kumpulan label (,). Ternyata tidak karena melanggar constraint Ca,b,c . Maka diberikan nilai yang lain untuk c. Dapat dilihat tidak ada satu pun nilai dari Dc yang konsisten dengan kumpulan label (,). Maka pencarian melakukan backtrack seperti yang terlihat pada gambar 2.3. Label terakhir dari kumpulan label (,) yaitu ditolak dan nilai yang lain diberikan untuk b. Dapat dilihat perbedaan backtracking dengan generate and test di mana pencarian dengan metode generate and test memberi nilai ke semua variabel terlebih dahulu sebelum memeriksa apakah pemberian nilai ini memenuhi constraint atau tidak. Sementara itu pencarian dengan metode backtracking memeriksa apakah pemberian nilai itu memenuhi constraint yang ada pada saat setiap variabel diberi nilai.
16
Gambar 2.2: Contoh constraint satisfaction problem di mana terjadi backtrack 2.3
Konsistensi Constraint
2.3.1 Pengertian Dasar Nama lain konsistensi constraint adalah problem reduction. Intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan. Sekarang ini sudah diketahui teknik konsistensi ini sangat penting dalam penyelesaian constraint satisfaction problem yang berat sehingga semua aplikasi komersial penyelesaian constraint satisfaction problem menggunakan teknik konsistensi ini sebagai langkah dasar (Christian Bessière; Jean-Charles Régin, 2001, p1). Sejarah konsistensi constraint dapat ditelusuri dari peningkatan efisiensi program pengenalan gambar oleh peneliti di intelejensi semu. Pengenalan gambar melibatkan pemberian label kepada semua garis pada gambar dengan cara yang konsisten. Jumlah kombinasi pemberian label pada garis yang memungkinkan dapat menjadi sangat besar, sementara hanya sedikit yang konsisten. Teknik konsistensi dengan efektif membuang semua pemberian nilai yang tidak konsisten pada tahap awal. Dengan demikian memperpendek pencarian untuk pemberian nilai yang konsisten. Untuk mengilustrasikan teknik konsistensi ini akan diberikan sebuah contoh constraint
17
Gambar 2.3: Graf menggambarkan constraint satisfaction problem yang sangat sederhana. Anggap A < B adalah constraint antara variabel A dengan domain DA = {3..7} dan variabel B dengan domain DB = {1..5}. Dengan jelas tampak bahwa untuk sebagian nilai pada DA tidak ada nilai yang konsisten di DB yang memenuhi constraint A < B dan sebaliknya. Nilai yang demikian dapat dibuang dari domain yang berkaitan tanpa kehilangan solusi apa pun. Reduksi itu aman. Didapatkan domain yang tereduksi DA = {3, 4} dan DB = {4, 5}. Perhatikan bahwa reduksi ini tidak membuang semua pasangan yang tidak konsisten. Sebagai contoh kumpulan label (,) masih dapat dihasilkan dari domain, tetapi untuk setiap nilai A dari DA adalah mungkin untuk mencari nilai B yang konsisten dan sebaliknya. Walaupun teknik konsistensi ini jarang digunakan sendirian untuk menghasilkan solusi (walaupun dapat), teknik konsistensi ini membantu menyelesaikan constraint satisfaction problem dalam beberapa cara. Teknik konsistensi ini dapat dipakai sebelum pencarian maupun pada saat pencarian. Constraint sering direpresentasikan dengan gambar graf (gambar 2.4) di mana setiap verteks mewakili variabel dan busur antar dua verteks mewakili constraint binari yang mengikat variabel-variabel yang dihubungkan dengan busur tersebut. Constraint unari diwakilkan dengan busur melingkar. 2.3.2 Konsistensi Verteks Teknik konsistensi yang paling sederhana adalah konsistensi verteks.
18 Definisi 9. Sebuah constraint satisfaction problem adalah konsisten secara verteks jika dan hanya jika untuk semua variabel semua nilai di domain-nya memenuhi constraint unari untuk variabel yang bersangkutan. ∀csp((Z, D, C)) : konsisten-verteks((Z, D, C)) ≡ (∀x ∈ Z : (∀v ∈ Dx : memenuhi-constraint(<x, v>, Cx ))) Konsistensi verteks sering disebut juga dengan konsistensi-1. Angka 1 ini mewakili constraint unari yang harus dipenuhi oleh semua variabel. Jika domain DX untuk variabel X memiliki nilai a yang tidak memenuhi constraint unari untuk variabel X, maka pemberian nilai a ke X akan mengakibatkan kegagalan langsung. Oleh karena itu ketidakkonsistenan secara verteks dapat dihapuskan dengan membuang semua nilai dari domain DX untuk variabel X yang tidak memenuhi constraint unari pada X (Roman Barták, 2005, p15). 2.3.3 Konsistensi Busur Jika constraint satisfaction problem yang ada sudah menjadi konsisten secara verteks, maka constraint unari dapat dihapus. Setelah konsisten secara verteks, maka pekerjaan yang tersisa adalah memastikan konsisten secara busur. Busur melambangkan constraint binari. Dua variabel dikatakan konsisten secara busur jika untuk setiap nilai dari domain variabel pertama dapat ditemukan nilai dari domain variabel kedua dan label ini memenuhi constraint untuk kedua variabel tersebut.
Definisi 10. Pasangan variabel (x, y) sebuah csp(Z, D, C) adalah konsisten secara busur jika dan
19 hanya jika setiap nilai a di domain x yang memenuhi constraint pada x, ada nilai dari domain y yang memenuhi constraint pada y dan konsisten dengan label <x, a>: ∀csp((Z, D, C)) : ∀x, y ∈ Z : konsisten-busur((x, y), (Z, D, C)) ≡ (∀a ∈ Dx : memenuhi-constraint((<x, a>, Cx ) ⇒ ∃b ∈ Dy : (memenuhi-constraint((), Cy )) ∧ memenuhi-constraint((<x, a>, , Cx,y ))) Dari definisi, jelas bahwa busur (Vi , Vj ) dapat dibuat konsisten dengan menghapus nilai-nilai di domain dari Vi di mana tidak ada nilai yang berkaitan di domain Dj sehingga constraint binari antara Vi dan Vj dipenuhi (perhatikan bahwa menghapus nilai-nilai tersebut tidak menghapus solusi yang mana pun dari constraint satisfaction problem yang bersangkutan). Sebuah constraint satisfaction problem dikatakan konsisten secara busur jika setiap nilai pada setiap domain memiliki dukungan di domain yang lain. Membuat masalah constraint satisfaction problem konsisten secara verteks sering dilakukan di tahap prapemrosesan: mengurangi ukuran beberapa domain biasanya membuat masalah menjadi lebih mudah dipecahkan (Barbara M. Smith, 1995, p5). Untuk membuat setiap busur dari graf constraint konsisten, atau dengan kata lain untuk membuat suatu constraint satisfaction problem konsisten secara busur, adalah tidak cukup untuk melakukan penghapusan nilai-nilai yang tidak konsisten secara busur untuk suatu variabel di domain hanya sekali saja. Ketika domain dari Vi sudah dikurangi anggotanya, maka setiap busur (Vi , Vj ) yang sudah pernah diotak-atik harus diperiksa lagi, karena beberapa anggota dari domain untuk Vi mungkin tidak konsisten lagi dengan anggota domain variabel-variabel yang diperiksa kekonsistenannya secara busur terhadap variabel Vi . Untuk mengatasi masalah ini, dikembangkan algoritma AC-1 yang pada dasarnya mengulang pemeriksaan kekonsistenan antara dua variabel terus-menerus sampai tidak ada domain mana pun yang berubah. Berikut adalah dari algoritma AC-1. REVISI adalah algoritma biasa yang mengkonsistenkan dua variabel secara busur.
20
Algoritma AC-1 prosedur AC-1(G) Q <- (Vi,Vj) di busur(G), i#j ulang UBAH <- salah untuk setiap busur(Vi,Vj) di Q lakukan UBAH <- REVISI(Vi,Vj) atau UBAH akhir untuk sampai bukan (UBAH) akhir prosedur AC-1
Dapat diperhatikan bahwa untuk menerapkan teknik konsistensi busur ini, constraint satisfaction problem yang ada diubah menjadi constraint satisfaction problem binari (constraint satisfaction problem yang semua constraint-nya binari atau unari). Jika ada constraint yang melibatkan tiga variabel atau lebih, constraint yang bersangkutan mesti dipisahkan menjadi beberapa constraint binari atau unari. Kekurangan dari algoritma ini adalah tidak begitu efisien karena setiap revisi sukses dari satu busur pada suatu iterasi memaksa semua busur untuk direvisi lagi pada iterasi berikutnya, walaupun hanya sebagian kecil dari mereka yang dipengaruhi oleh revisi ini. Kekurangan dari algoritma AC-1 ditutupi oleh algoritma AC-3 yang melakukan revisi kembali hanya bagi busur-busur yang memiliki kemungkinan dipengaruhi oleh revisi sebelumnya. Algoritma AC-3 prosedur AC-3(G) Q <- (Vi,Vj) pada busur(G), i#j ketika Q tidak kosong lakukan pilih dan hapus busur (Vk,Vm) dari Q jika REVISI(Vk,Vm) maka Q <- Q bergabung {(Vi,Vk) bilamana (Vi,Vk) di busur(G), i#k, i#m} akhir jika akhir ketika akhir prosedur AC-3
21
Gambar 2.4: Graf constraint yang konsisten secara busur tetapi tidak mempunyai solusi Ketika algoritma AC-3 merevisi busur untuk kedua kalinya, algoritma ini menguji pasangan nilai yang sudah diketahui (dari iterasi sebelumnya) apakah konsisten atau tidak konsisten dan mana yang tidak terpengaruhi oleh reduksi domain. Ide utama dari algoritma AC-3 berdasarkan konsep dukungan. Nilai didukung jika ada nilai yang cocok di domain setiap variabel lainnya. Ketika sebuah nilai V dibuang dari domain variabel X, adalah tidak perlu untuk memeriksa semua constraint binari CY,X . Tepatnya, nilai-nilai dalam DY dapat diabaikan jika tidak memerlukan V untuk dukungan. Walaupun sudah mencapai tahap konsisten secara busur yang mengakibatkan banyak ketidakkonsistenan dibuang dari graf constraint , tidaklah cukup untuk mendapatkan solusi. Jika ukuran domain masing-masing variabel menjadi satu, maka constraint satisfaction problem tepat mempunyai satu solusi yang didapatkan dengan memberikan nilai ke masing-masing variabel dari domain masing-masing. Hal ini berlaku juga untuk konsistensi verteks. Jika ada domain yang menjadi kosong, maka constraint satisfaction problem-nya tidak mempunyai solusi. Lain daripada itu, solusinya tidak pasti. Contoh berikut (gambar 2.5) menunjukkan bahwa graf constraint konsisten secara busur tetapi tidak ada satu pun label yang memenuhi semua constraint.
2.4
Optimalisasi Dalam Constraint Satisfaction Problem
2.4.1 Pengertian Dasar Pada bagian sebelumnya, sudah dibahas teknik-teknik untuk menyelesaikan constraint satisfaction problem di mana semua solusinya sama baiknya. Pada permasalahan seperti optimalisasi penjadwalan pekerjaan di industri, beberapa solusi adalah lebih baik daripada
22 solusi lainnya. Pada kasus lainnya, pemberian nilai kepada variabel-variabel yang sama mengakibatkan harga yang berbeda. Tugas dari permasalahan ini adalah untuk mencari solusi yang paling optimal di mana keoptimalan suatu solusi itu didefinisikan oleh fungsi yang spesifik untuk aplikasi. Masalah ini biasa disebut sebagai constraint satisfaction optimization problem untuk membedakan dengan constraint satisfaction problem biasa. Semua masalah optimalisasi yang dipelajari di riset operasional adalah constraint satisfaction problem pada pengertian umum, di mana constraint umumnya adalah numerik. Definisi 11. Sebuah constraint satisfaction optimization problem didefinisikan sebagai constraint satisfaction problem dengan fungsi optimalisasi f yang memetakan setiap tupel solusi ke sebuah nilai numerik: (Z, D, C, f ) di mana (Z, D, C, f ) adalah constraint satisfaction problem, dan jika S adalah himpunan tupel solusi dari (Z, D, C), maka f : S → nilai numerik Diberikan sebuah tupel solusi T , f (T ) disebut sebagai nilai f dari T . Tugas dalam constraint satisfaction optimization problem adalah untuk mencari tupel solusi nilai f yang optimal (minimal atau maksimal) yang ditentukan oleh fungsi f optimalisasi yang spesifik untuk aplikasi. Constraint yang umum disebut hard constraints, sementara fungsi f disebut soft constraints. Penamaan ini menggambarkan bahwa hard constraints harus dipenuhi, sementara soft constraints memiliki preferensi terhadap beberapa solusi (yang mempunyai nilai tinggi/rendah) dari yang lainnya (yang mempunyai nilai lebih rendah/lebih tinggi) (Anonim, http://en.wikipedia.org/wiki/Constraint_optimization, 2006). Masalah alokasi sumber daya di penjadwalan adalah constraint satisfaction optimization problem. Pada banyak masalah penjadwalan, mencari solusi yang mana pun tidaklah cukup baik. Seseorang mungkin ingin mencari cara yang paling ekonomis dalam mengalokasikan sumber daya ke pekerjaan-pekerjaan, atau mengalokasi mesin ke
23 pekerjaan-pekerjaan, memaksimalkan beberapa kualitas yang bisa diukur dari hasil keluaran. Masalah-masalah ini adalah constraint satisfaction optimization problem. Untuk mencari solusi yang paling optimal, seseorang mungkin harus mencari semua solusi terlebih dahulu, dan kemudian membandingkan nilai f mereka. Sebagian dari ruang pencarian dapat dipotong jika seseorang dapat membuktikan bahwa solusi yang lebih optimal dari solusi sebelumnya tidak berada di dalamnya. Hal ini berarti tidak ada solusi yang berada di dalamnya atau nilai f pada setiap solusi di ruang pencarian yang dipotong itu tidak lebih optimal dari solusi yang sudah didapatkan (sub-optimal). 2.4.2 Branch and Bound Untuk menyelesaikan masalah constraint satisfaction optimization problem, digunakan fungsi f untuk memandu pencarian. Branch and bound, yang merupakan algoritma pencarian umum dalam pencarian solusi optimal, menggunakan fungsi f . Di sini tetap digunakan tupel solusi untuk menyebut kumpulan label yang memberikan nilai kepada semua variabel yang memenuhi constraint. Perlu diperhatikan bahwa tupel solusi di sini tidak harus mengacu kepada solusi optimal pada constraint satisfaction optimization problem. Branch and bound adalah teknik yang terkenal pada riset operasi dan intelejensi semu. Teknik ini didasarkan pada fungsi heuristik yang baik dalam memperkirakan nilai terbaik (’terbaik’ menurut fungsi optimalisasi) pada semua verteks di bawah cabang yang sedang diperiksa pada pohon pencarian (Edward Tsang, 1996, p301). Jika fungsi heuristiknya bagus, seseorang dapat memotong ruang pencarian yang di dalamnya tidak terdapat solusi optimal. Oleh karena itu, walaupun branch and bound tidak mengurangi kompleksitas algoritma pencarian, tapi teknik ini dapat menjadi lebih efisien daripada backtracking saja. Untuk menerapkan branch and bound pada constraint satisfaction optimization problem, seseorang memerlukan sebuah fungsi heuristik h yang memetakan semua kumpulan label CL ke sebuah nilai numerik (h : CL → angka). Nilai ini disebut nilai h dari kumpulan label. Supaya fungsi h dapat diterima, nilai h dari setiap kumpulan label CL harus lebih besar (lebih kecil) dari nilai f dari setiap tupel solusi pada masalah maksimalisasi
24 (minimalisasi). Sebuah variabel global, yang disebut sebagai bound, akan diinisialisasi minus tak terhingga pada masalah maksimalisasi. Teknik ini mencari solusi dengan kelakuan depthfirst. Teknik ini menggunakan backtracking. Ketika sebuah label ingin ditambahkan ke kumpulan label, nilai h dari kumpulan label yang ada (berikut label yang baru masuk itu) dihitung. Jika nilai h ini lebih kecil dari bound pada masalah maksimalisasi, maka cabang tempat kumpulan label berada dipotong. Ketika sebuah tupel solusi ditemukan, nilai f dihitung. Nilai f akan menjadi nilai bound jika dan hanya jika lebih besar dari bound yang sudah ada pada masalah maksimalisasi. Ketika nilai f ini lebih besar dari bound, maka solusi yang baru ditemukan akan dimasukkan ke kumpulan solusi terbaik sampai saat ini. Setelah pencarian selesai, tupel solusi yang terakhir didapatkan dapat dianggap sebagai solusi yang paling optimal. Prosedur Branch_and_Bound di bawah ini memberikan langkah-langkah dalam menerapkan strategi branch and bound depth-first dalam menyelesaikan constraint satisfaction optimization problem, di mana nilai f maksimum diperlukan. Masalah minimalisasi dapat dihadapi seperti masalah maksimalisasi dengan menggantikan semua nilai f dan h dengan negasi nilai mereka. Untuk membuat prosedur menjadi lebih sederhana, prosedur ini hanya mengembalikan satu tupel solusi yang mempunyai nilai f optimal; tupel solusi lainnya yang mempunyai nilai f yang sama diabaikan.
25 Algoritma Branch_and_Bound prosedur Branch_and_Bound(Z,D,C,f,h) BOUND ← minus tak terhingga BEST_S_SO_FAR ← NIL BNB(Z,,D,C,f,h) kembalikan (BEST_S_SO_FAR) akhir prosedur Branch_and_Bound prosedur BNB(BELUM_LABEL, KUMPULAN_LABEL,D,C,f,h) jika (BELUM_LABEL={}) maka jika (f(KUMPULAN_LABEL) > BOUND) maka BOUND ← f(KUMPULAN_LABEL) BEST_S_SO_FAR ← KUMPULAN_LABEL selain jika (h(KUMPULAN_LABEL) > BOUND) maka pilih variabel x dari BELUM_LABEL ulangi pilih nilai v dari Dx hapus v dari Dx jika (KUMPULAN_LABEL + <x,v> memenuhi constraint) maka BNB(BELUM_LABEL-x, KUMPULAN_LABEL + <x,v>, D, C, f, h) akhir jika sampai (Dx ={}) akhir jika akhir jika akhir prosedur BNB
Efisiensi dari branch and bound ditentukan oleh dua faktor: kualitas fungsi heuristik dan apakah bound yang ’bagus’ ditemukan pada tahap awal. Pada masalah maksimalisasi, jika nilai h adalah selalu memperkirakan lebih tinggi dari nilai f , maka perkiraan menjadi lebih dekat ke nilai f (contohnya, semakin kecil nilai h tanpa lebih kecil dari nilai f ), lebih besar kemungkinannya bagian yang cukup besar dari ruang pencarian dipotong. Sebuah cabang akan dipotong oleh branch and bound jika nilai h dari verteks yang sedang diperika lebih rendah dari bound (pada masalah maksimalisasi). Ini berarti bahkan jika dengan fungsi heuristik diperbaiki, branch and bound akan memotong proporsi yang berbeda dari ruang pencarian jika cabang diurutkan secara berbeda, karena batas yang
26 berbeda akan ditemukan di bawah cabang yang berbeda. Gambar 2.6 menunjukkan sebuah contoh dari constraint satisfaction optimization problem. Semua dari lima variabel x1 , x2 , x3 , dan x4 mempunyai domain numerik. Nilai f dari sebuah kumpulan label adalah total perkalian dari semua nilai yang diambil variabelvariabel ini. Tugasnya adalah mencari tupel solusi dengan nilai f maksimum. Khusus contoh constraint satisfaction optimization problem ini hanya diperlukan solusi tunggal sehingga nilai h yang sama dengan bound akan dipotong juga.
Gambar 2.5: Contoh constraint satisfaction optimization problem yang sederhana Gambar 2.7 menunjukkan ruang yang dijelajahi oleh backtracking sederhana. Setiap verteks pada gambar 2.7 mewakili sebuah kumpulan label, dan setiap cabang mewakili pemberian sebuah nilai ke variabel yang belum mendapatkan nilai. Variabel-variabel diasumsikan untuk diperiksa dengan urutan: x1 , x2 , x3 , dan x4 . Gambar 2.8 menunjukkan ruang yang dicari oleh branch and bound dengan urutan pencarian yang sama dengan backtracking. Nilai h untuk sebuah verteks dihitung ketika nilai yang diberikan sejauh ini ditambahkan dengan nilai maksimal dari variabel yang belum diberi nilai. Sebagai contoh, nilai h dari (<x1 ,3>,<x2 ,2>) adalah 3 * 2 (nilai yang diberikan sejauh ini) dikalikan dengan 4 * 4 (nilai maksimum yang dapat diberikan ke x3 dan x4 ), yaitu 16. Menurut prosedur Branch_and_Bound yang dijelaskan sebelumnya, bound diinisialisasi ke minus tak terhingga. Ketika verteks untuk (<x1 ,2><x2 ,3><x3 ,4><x4 ,2>) dicapai, bound diberi nilai (2 * 3 * 4 * 2 =) 48. Nilai bound ini tidak memiliki efek bagi setengah kiri dari pohon pencarian. Ketika verteks (<x1 ,3><x2 ,2><x3 ,3>) diperiksa, nilai h (yaitu
27
Gambar 2.6: Ruang pencarian yang dijelajahi oleh backtracking sederhana dalam constraint satisfaction optimization problem
Gambar 2.7: Ruang pencarian yang dijelajahi oleh branch and bound dalam constraint satisfaction optimization problem
28
Gambar 2.8: Ruang pencarian yang dijelajahi oleh branch and bound dalam constraint satisfaction optimization problem ketika bound yang bagus ditemukan pada tahap awal pencarian 48) ditemukan sama nilainya dengan bound (yaitu 48). Maka dari itu, cabang di bawah verteks (<x1 ,3><x2 ,2><x3 ,3>) dipotong. Setelah pemotongan ini, pencarian bergerak ke cabang berikutnya. (<x1 ,3><x2 ,2><x3 ,4><x4 ,2>) kemudian ditemukan dan disimpulkan sebagai solusi yang paling optimal. Pada gambar 2.8, 15 verteks dijelajahi, dengan perbandingan 17 verteks pada gambar 2.7. Gambar 2.9 menunjukkan pentingnya menemukan bound yang lebih ketat pada tahap awal. Pada gambar 2.9, urutan pencariannya adalah x1 , x4 , x2 , dan x3 dengan urutan nilai domain dimulai dari yang paling besar. Solusi optimal ditemukan setelah 6 verteks dijelajahi. Bound 96 digunakan untuk memotong cabang di bawah (<x1 ,2><x4 ,2>) (yang nilai h-nya 48). Hanya 11 verteks yang dijelajahi pada gambar 2.9.
