Penyelesaian Maximum Flow Problem dengan Algoritma Cloning-Based Setya Widodo, Purwanto, dan Subanji Universitas Negeri Malang E-mail:
[email protected] ABSTRAK: Skripsi ini membahas tentang permasalahan Maximum Flow. Permasalahan ini yaitu mencari aliran maksimum yang dapat mengalir melewati suatu jaringan atau network dengan satu titik asal dan satu titik tujuan dengan menggunakan algoritma Cloning-Based yang dalam penelitian yang dilakukan sebelumnya oleh Novi Tri Nurhantini di tahun 2010 algoritma ini digunakan untuk menyelesaikan Travelling Salesman Problem. Dari penelitian diperoleh penyelesaikan permasalahan Maximum Flow dengan Algoritma Cloning-Based menghasilkan solusi sebaik pada Travelling Salesman Problem dengan metode Djikstra sebagai pembanding karena metode ini memiliki langkah yang hampir sama.
Kata Kunci: Maximum flow, Algoritma Cloning-based ABSTRACT: This thesis discuss about Maximum Flow Problem. This problem is problem of looking for Maximum Flow which could flow through the network with a source and a sink by Cloning-Based algorithm which is on Novi Tri Nurhantini’s research on 2010 is able to solve Travelling Salesman Problem well. Therefore, we proposed solving Maximum Flow Problem with Cloning-Based algorithm whether it will produce solution as well as on Travelling Salesman Problem by Djikstra method as the comparer because it has the step that almost the same. . Key Words: Maximum flow, Cloning-based algorithm
Dalam kehidupan sehari-hari Teori graph, khususnya maximum flow problem, dapat digunakan dalam pendistribusian produk dari pusat ke cabang dengan mengetahui jumlah kendaraan maksimal yang dikirimkan sekali periode pengiriman sehingga tidak menyebabkan kemacetan jalan, terutama di kota-kota besar. Penyelesaian maximum flow problem akan menjadi mudah dan efektif jika menggunakan algoritma Banyak penelitian yang telah dilakukan oleh berbaai praktisi pendidikan maupun mahasiswa dalam penyelesaian masalah maximum flow. Salah satunya adalah skripsi berjudul “Aplikasi Seleksi klon pada Travelling Salesman Problem” yang ditulis oleh Novi Tri Nurhantini tahun 2010 yang membahas tentang bagaimana Algoritma Cloning-Based dapat menyelesaikan permasalahan dalam Travelling Salesman Problem. Sehingga memicu gagasan utuk menerapkan aplikasi ini dalam permasalahan maximum flow problem dengan langkah yang hampir sama. Berikutnya yaitu skripsi yang berjudul “Penerapan Model Maksimum Flow dalam Teori Graph pada Lalu Lintas Kendaraan” yang ditulis oleh Rosyidah tahun 2006 yang membahas penerapan model maximum flow pada lalulintas kendaraan dengan kapasitas terbesar dari suatu titik asal ke titik tujuan yang telah ditentukan. Dari beberapa kajian dan manfaat yang telah dijelaskan, maka penelitian ini mengambil judul “Penyelesaian Maximum Flow Problem dengan Algoritma Cloning-Based”. Judul ini dipilih karena penulis mengaplikasikan dan mengimplementasikan penyelesaian maximum flow problem
dengan menggunakan Algoritma Cloning-Based. Berdasarkan latar belakang, penulisan ini mempunyai tujuan yaitu untuk (1) Untuk mengetahui langkahlangkah penyelesaian maximum flow problem dengan menggunakan Algoritma Cloning-Based. (2) Untuk mengetahui analisa hasil dari penyelesaian maximum flow problem dengan menggunakan Algoritma Cloning-Based. Pada tubuh manusia sistem kekebalan berfungsi untuk mendeteksi masuknya benda asing atau patogen ke dalam tubuh seperti virus, bakteri yang dapat mengganggu kestabilan tubuh. Sistem kekebalan tubuh tidak dapat mendeteksi secara langsung adanya patogen yang masuk ke dalam tubuh, tetapi dapat dideteksi melalui bagian dari patogen yang disebut dengan antigen. Jika terdeteksi adanya patogen, sistem kekebalan tubuh bertugas untuk mengeleminasinya dari tubuh. Agar proses eliminasi patogen berlangsung dengan baik dan benar, sistim kekebalan tubuh harus mampu untuk membedakan antara antigen pada patogen yang selanjutnya disebut dengan nonself-antigen dengan antigen yang dimiliki sel-sel tubuh yang disebut dengan self-antigen. Sel-sel kekebalan tubuh yang fungsinya khusus mendeteksi adanya patogen adalah limfosit. Ada dua tipe limfosit yaitu B-cells dan T-cells. Kedua tipe limfosit mempunyai molekul pada permukaan sel-nya, yang disebut sebagai receptor, yang berfungsi untuk mengikat molekul antigen dari patogen. Receptor dari Tcells disebut dengan TCR sedangkan receptor B-cell disebut dengan BCR atau biasa dikenal dengan antibody (Sasongko,2008). HASIL Hasil temuan didasarkan pada tujuan yakni untuk mengetahui langkahlangkah penyelesaian maximum flow problem dengan menggunakan Algoritma Cloning-Based dan untuk menganalisa hasil dari penyelesaian maximum flow problem dengan menggunakan Algoritma Cloning-Based. Langkah-langkah Algoritma Cloning-based Langkah-langkah menyelesaikan permasalahan dengan menggunakan algoritma Cloning-Based pada Maximum Flow Problem dengan mengadopsi dari langah untu TSP: 1. Suatu agen bergerak melalui satu salah sisi dari titik asal dan kemudian mengkloning ke titik lain yang belum terlewati. Ketika suatu agen telah sampai pada suatu kota dan tidak mampu membentuk rute hingga mencapai kota tujuan atau afinitasnya kurang dari afinitas minimal, maka akan memicu seleksi positif dan kota hasil kloning tadi dan rute yang dihasilkan sebelumnya dimatikan (solusi tidak berguna). Sebaliknya, jika tidak maka agen pada kota yang tadi akan mengkloning dirinya dan hasil kloning ini akan mendapat salinan dari kota-kota yang telah dikunjungi oleh agen pendahulunya. Langkah diatas adalah langkah penerapan dalam Travelling Salesman Problem, untuk permasalahan dalam Maximum Flow Problem terdapat perbedaan yaitu pada suatu agen dari salah satu sisi sumber dan tidak mampu membentuk rute untuk mencapai kota tujuan maka akan memicu seleksi positif dan kota hasil kloning tadi dan rute yang dihasilkan sebelumnya dimatikan(solusi tidak berguna).
2. Setelah semua kota terlewati maka agen kembali ke kota awal dan proses kloning selesai. Tetapi pada Maximum Flow Problem agen yang telah mencapai kota tujuanlah yang tidak akan mengkloning dirinya dan proses kloning selesai. 3. Ketika semua rute terbentuk dengan afinitas kurang dari atau sama dengan afinitas minimal, maka akan memicu seleksi negatif dan akan dipilih rute yang nilai afinitasnya terbesar(rute lain yang tidak berguna dihancurkan). Tetapi pada Maximum Flow Problem ketika semua agen telah mencapai kota tujuan yang melalui satu sisi yang sama yang terhubung dengan titik awal maka akan memicu seleksi negatif dan akan dipilih rute yang memiliki bobot terbesar dan rute lain yang tidak berguna dihancurkan.
Penerapan Algoritma Cloning-based Berikut contoh penerapan algoritma Cloning-based dalam graph G A 6
5 S
T
7 6
4 B
Gambar 1. Network N Langah 1: sisi S – A Didapatkan lintasan S – A – T seperti pada graph berikut. A 6
5 S
T
7 6
4 B
Dengan bobot minimumnya adalah: Min{5,6} = 5 Jadi dari sisi S – A diperoleh maximum flow-nya sebesar 5. Langkah 2: sisi S – B Dari titik B agen mengkloning dirinya menjadi 2 yaitu menuju ke titik A dan T. Dari titik A agen langsung menuju titik T karena tidak ada sisi yang menuju ke titik lain selain T. sehingga diperoleh lintasan sebagai berikut. 1. S – B – A – T dengan bobot minimum:
Min{6, 7, 1} = 1 2. S – B – T dengan bobot minimum: Min{6, 4} = 4 Berdasarkan lintasan yang diperoleh diatas dengan seleksi negatif diperoleh lintasan S – B – T dengan bobot minimum 4. Karena sisi bobot S – B belum nol maka lintasan yang tersisa yang melalui sisi tersebut adalah S – B – A – T dengan bobot minimum 1 dan diperoleh jaringan sisa sebbagai berikut. A 0
0 S
T
6 1
0 B
Sisi bobot S – B belum nol tetapi tidak ada lintasan yang tersisa yang melalui sisi tersebut yang menuju ke titik tujuan sehingga memicu seleksi positif sehingga agen dimatikan. Jadi dari langkah-langkah diatas diperoleh lintasan dan maximum flow-nya seagai berikut. 1. S – A – T dengan bobot minimum 6. 2. S – B – T dengan bobot minimum 4. 3. S – B – A – T dengan bobot minimum 1. Jadi besar maximum flow yang diperoleh adalah 11. Kelebihan algoritma cloning-based 1. Algoritma cloning-based tidak terlalu banyak memerlukan persyaratan matematika dalam penyelesaian proses optimasi. 2. Operasi cloning dari algoritma cloning-based sangat efektif untuk mengobservasi posisi global secara acak. 3. Algoritma cloning-based mempunyai fleksibelitas untuk diimplementasikan secara efisien pada problematika tertentu. PEMBAHASAN Pembahasan didasarkan pada hasil temuan mengenai penyelesaian dan analisis terhadap algoritma Cloning-based dalam maximum flow. Berikut pembahasan dari masing-masing subbab. Deskripsi Algoritma Cloning-based Analogi antara sistem kekebalan tubuh dan masalah optimasi adalah sebagai berikut. Response dari sistem imun merepresentasikan solusi dan antigen merepresentasikan masalah yang harus diselesaikan. Lebih tepatnya, Sel B adalah sebagai agen-agen buatan yang menjelajahi dan mengeksplorasi lingkungan buatan. Patogen adalah sebagai masalah optimasi, dalam kasus ini, masalah optimasi digambarkan oleh antigen pada patogen. Mekanisme seleksi positif dan
seleksi negatif digunakan untuk mengontrol perbanyakan agen dengan mengeliminasi solusi yang buruk atau tidak berguna. Jadi, aturan seleksi positif dan seleksi negatif dapat dipertimbangkan sebagai mekanisme yang tidak hanya memilih solusi yang tepat, tetapi juga mengatur jumlah populasi agen yang tumbuh pada proses kloning. Tabel Analogi Sistem Kekebalan Tubuh pada Masalah Optimasi Sumber: Bakhouya, 2006 Sistem Kekebalan Tubuh Patogen
Respon Tubuh Sel-B Clonal Selection Seleksi Positif dan Seleksi Negatif
Masalah Optimasi Permasalahan (dalam hal ini graph kota dimana tiap titik(kota) digambarkan sebagai antigen) Solusi Agen pencari Menciptakan agen pencari baru untuk menjelajahi kota Penyeleksian agen yang buruk/tidak berguna untuk membunuh dirinya sendiri (apoptosis)
Penerapan Algoritma Cloning-based Pada Maximum Flow Problem masalah lingkungan buatannya adalah sebagai berikut:
Titik merepresentasikan tiap kota, yang dianalogikan sebagai antigen pada patogen. Sel B adalah agen pencari yang bergerak dari satu kota ke kota tetangganya dan dapat mengkloning dirinya atau menghancurkan dirinya sendiri berdasarkan kriteria seleksi positif dan seleksi negatif. Kapasitas jalan dianalogikan sebagai daya afinitas yang dipunyai Sel B untuk merangsang respon dari tubuh terhadap patogen. Solusi dari permasalahan dianalogikan sebagai afinitas terbesar yang dibutuhkan sampai tubuh merespon adanya patogen.
Secara formal, misalkan C={a, …., z} adalah himpunan kota-kota, A={(x,y):x,y ∈C} adalah ujung-ujung dari sisi tersebut dan δ(x,y) adalah kapasitas jalan antara x, y ∈ C. Seleksi positif terjadi jika kota tidak membangun rute dan tidak mencapai kota tujuan. Sedangkan seleksi negatif terjadi apabila semua agen telah menyelesaikan perjalanannya maka agen yang membentuk rute dengan afinitas paling besar akan menjadi solusi sedangkan agen yang tidak dapat membentuk rute dengan jumlah afinitas lebih besar atau sama dengan afinitas minimal setelah melalui suatu titik untuk menuju ke titik tujuan akan dimatikan dan rute yang telah terbentuk dihapus.
Keunggulan Algoritma Cloning-based dibanding metode Djikstra Analisis Data Berikut ini adalah hasil perbandingan antara hasil perhitungan dengan menggunakan Algoritma Cloning-Based secara manual dengan perhitungan menggunakan program dari masalah-masalah pada gambar 4.1, gambar 4.2 dan gambar 4.3 dan hasil perbandingan algoritma Cloning-Based dengan Metode Djikstra
Gambar 1.
Gambar 2.
Gambar 3. Tabel perbandingan hasil uji coba Hasil manual Cloning-Based (max flow)
Hasil manual Djikstra (max flow)
Gambar 1
0,4
0,4
Gambar 2
15
13
Gambar 3
7
7
Dari perbandingan hasil perhitungan pada tabel terlihat bahwa hasil yang diberikan oleh Algoritma Cloning-Based lebih optimal dari pada metode Djikstra.
SIMPULAN DAN SARAN Kesimpulan Dari hasil perhitungan manual dan perhitungan melalui program serta analisis terhadap permasalahan penyelesaian maximum flow dengan menggunakan algoritma cloning-based, dapat disimpulkan bahwa : Berdasarkan penjelasan di bab 3 diperoleh perbedaan hasil perhitungan manual antara lagoritma Cloning-Based dan metode Djikstra terdapat perbedaaan seperti yang terlihat pada Tabel 5.1 berikut. Tabel Perbandingan hasil manual antara Algoritma Cloning-Based dan metode Djikstra Permasalahan Graph terhubung pada Gambar 3.1 Graph terhubung pada Gambar 3.12 Graph terhubung pada Gambar 3.20
Cloning-Based (max flow)
Djikstra (max flow)
0,4
0,4
15
13
7
7
Dari Tabel terlihat bahwa pada Graph permasalahan algortima Cloning-Based lebih optimal dari metode Djikstra yaitu pada graph terhubung pada Gambar 3.12, yaitu Algoritma Cloning-Based menghasilkan maximum flow sebesar 15 sedangkan metode Djikstra sebesar 13.Pembuatan program sebagai alat bantu perhitungan sangat memudahkan sales dalam menentukan rute perjalanan yang lebih cepat. Program ini mampu menyelesaikan masalah maximum-flow dengan jumlah titik yang banyak dan memberikan solusi rute maximum flow yang dibutuhkan dengan cepat. Saran Alat bantu program ini masih perlu dikembangkan lebih lanjut yaitu untuk pemilihan titik sisi awal secara random karena pada program ini pemilihan sisi awal sesuai urutan index titik. Penambahan variabel yang diteliti misalnya variabel kemacetan, lebar ruas jalan, dan hari kerja akan semakin membuat hasil akhir dari perhitungan semakin baik, baik itu perhitungan secara manual maupun perhitungan menggunakan alat bantu.
DAFTAR PUSTAKA Hayati, Izza, dkk. 2010. Penyelesaian Maximum Flow Problem Pada Distribusi Semen di PT. Jawa Berkat Utama. Laporan. Universitas Negeri Malang. Johnsonbaugh, Richard. 2001. Discrete Mathematics. Chicago: De Paul Martina, Inge. 2004. 36 Jam Belajar Komputer. Pemrograman Borland Delphi 7. Penerbit Elex Media Komputindo. Munir, Rinaldi. 2006. Diktat Kuliah IF2251 Strategi Algoritmik. Penerbit ITB Nurhantini, Tri Novi. 2010. Aplikasi Seleksi Klon pada Travelling Salesman Problem. Skripsi. Universitas Negeri Malang. Sasongko, Budi Pranoto. 2001. Cloning-Based Algorithm Dan Aplikasinya Dalam Travelling Salesperson Problem. Bandung: ITB. UniversityWilson, Robin J. dan John J. Watkins. 2001. Graph an Introductory Approach. Canada: John Willey & Sons.
Malang, Desember 2012 Penulis
Pembimbing I
Prof. Drs. Purwanto, Ph. D. M. Si NIP 19591222198502 1 006 Pembimbing II
Dr. Subanji, M. Si NIP 19710605 199802 1 001
Mahasiswa
Setya Widodo NIM. 908312409126
