Penyelesaian permasalahan maximum flow dengan menggunakan pendekatan algoritma viral systems

Abstract

Permasalahan maximum flow merupakan permasalahan untuk mencari besar penugasan aliran pada suatu jaringan kerja sehingga aliran yang sampai ke suatu tujuan menjadi maksimal. Semakin banyak titik yang harus dilewati maka akan semakin banyak pula kemungkinan solusi yang ada sehingga menyebabkan permasalahan maximum flow sulit diselesaikan dengan cara manual. Beberapa metode optimasi seperti metode Ford-Fulkerson hanya sesuai diterapkan untuk kasus dengan jumlah titik sedikit. Hal inilah yang menyebabkan munculnya pendekatan dengan metode heuristik, seperti Genetic Algorithm. Viral Systems (VS) merupakan salah satu metode heuristik yang dapat digunakan untuk menyelesaikan permasalahan kombinatorial dari skala sedang hingga besar. VS terinspirasi oleh performansi kerja virus dalam menginfeksi sel. Penelitian dilakukan untuk membuat model algoritma VS yang sesuai dengan permasalahan maximum flow, membandingkan performansi VS dengan Genetic Algorithm, dan mengetahui parameter-parameter apa saja yang berpengaruh terhadap kasus yang diuji. Dalam algoritma VS, virus akan menyerang sel yang memiliki genome yang merupakan kode matematis dari solusi yang akan dicari. Genome terdiri dari beberapa gen yang berisi angka dimana angka tersebut merupakan titik yang akan dilalui. Jika ada n buah titik yang harus dilewati maka akan terbentuk n gen. Gen pertama dalam genome merupakan angka prioritas titik source sedangkan gen terakhir merupakan angka prioritas titik sink. Terdapat dua macam replikasi virus yaitu litik dan lisogenik. Model algoritma VS diimplementasikan terhadap 7 kasus. Kasus 1 terdiri dari 11 buah titik, kasus 2 dan 3 terdiri dari 25 buah titik dan digunakan untuk mengetahui performansi algoritma VS, kasus 4 terdiri dari 20 titik merupakan kasus implementasi maximum flow di dunia nyata, kasus 5 dan 7 terdiri dari 74 titik, dan kasus 6 terdiri dari 59 titik. Kasus 5, 6, dan 7 akan digunakan untuk pengujian parameter penelitian algoritma VS. Model algoritma VS yang telah dibuat berhasil menemukan hasil yang optimal. VS menghasilkan solusi yang sama baiknya dengan metode Genetic Algorithm. Parameter-parameter penelitian VS yang berpengaruh terhadap kasus 5 adalah parameter pi, untuk kasus 6 adalah parameter plt, pi, pr, LNR0, dan LIT0, dan untuk kasus 7 adalah plt, pi, LNR0, dan LIT0.