Multi Objective ACO
Multi-objective optimization (MOO) merupakan metode optimisasi di mana beberapa objective atau tujuan harus dioptimisasi secara bersamaan (Angus & Woodward, 2009). Umumnya pada MOO tidak ada solusi terbaik yang bisa memenuhi seluruh objective secara bersamaan, sehingga biasanya ada beberapa solusi yang dihasilkan yang disebut dengan pareto-optimal (Marler & Arora, 2010). Untuk memilih satu solusi dari pareto-optimal biasanya memerlukan proses lebih lanjut dengan menyerahkannya kepada pihak pengambil keputusan. Gambar 1 memperlihatkan contoh solusi-solusi yang dihasilkan dimana titik-titik berwarna oranye merupakan alternatif solusi optimal yang dihasilkan, atau biasa disebut dengan non-dominated solution atau pareto-optimal.
Gambar 1 Contoh diagram Pareto pada MOO
Multi-objective Ant Colony Optimization (MOACO) merupakan penerapan ACO dalam menyelesaikan permasalahan multi-objective. Sebelum lebih jauh ada baiknya dipahami terlebih dulu cara kerja algoritma ACO. Ant Colony Optimization (ACO) merupakan algoritma yang dibuat pertama kali oleh Marco Dorigo pada tahun 1996. Pada awalnya ACO diimplementasikan untuk memecahkan pencarian jalur terpendek pada kasus Traveling Salesman Problem (TSP). Pada prinsipnya algoritma ACO menirukan cara kerja semut yang melakukan perjalanan dari satu titik tujuan menuju ke titik tujuan lainnya dengan memilih jalur yang paling pendek. Gambar 2 berikut merupakan ilustrasi dari cara kerja algoritma ACO dalam hal pemilihan jalur yang paling pendek (Dorigo et al., 1996)
Gambar 2 Ilustrasi cara kerja algoritma ACO
Pada Gambar 2, bagian a menunjukkan dua kemungkinan jalur yang dapat dilalui oleh semut namun kedua jalur tersebut memiliki jarak yang berbeda. Di mana jarak dari titik H ke D dan D ke B adalah 1 (d=1) dan jarak dari titik D ke C dan C ke B adalah 0.5 (d=0.5). Bagian b menunjukkan waktu perjalanan pertama (t=0) di mana belum ada feromon pada setiap jalur, sehingga peluang memilih jalur yang ada sama besarnya. Lalu bagian c menunjukkan waktu kedua di mana pada jalur yang lebih pendek kadar feromonnya lebih kuat karena sudah dilalui lebih banyak semut dalam waktu yang sama dibanding dengan jalur yang lebih panjang. Sehingga jalur yang lebih pendek memiliki peluang lebih besar dipilih untuk dilalui.
Beberapa penelitian yang sudah pernah dilakukan misalnya untuk meminimalkan pemborosan resource dan penggunaan tenaga listrik pada penempatan virtual machine di cloud computing (Gao, Guan, Qi, Hou, & Liu, 2013), serta proses pengambilan keputusan menggunakan teknik Analytic Hierarchy Process (AHP), di mana matriks-matriks yang digunakan dalam perhitungan AHP tersebut harus konsisten namun tetap memiliki standar deviasi yang rendah setelah mengalami modifikasi (Girsang, Tsai, & Yang, 2016).
Salah satu metode MOACO adalah Bi-criterion Ant yang digunakan untuk pemecahan masalah dengan dua objective function yang saling bertolak belakang (Iredi, Merkle, & Middendorf, 2001). Metode Bi-criterion Ant dalam pemilihan kandidat node dapat dirumuskan menggunakan persamaan berikut
Di mana Tij (t) adalah feromon untuk objective function yang pertama dan Tij'(t) adalah feromon untuk objective function yang kedua. Begitu juga dengan yang merupakan informasi nij (t) heuristic untuk objective function yang pertama dan merupakan informasi nij(t)’ heuristic untuk objective function yang kedua. Sedangkan lambda dapat dirumuskan menggunakan persamaan berikut.
lambda= (k-1)/(m-1)
Di mana k adalah semut ke-k. Lalu m adalah jumlah semut yang digunakan.
Referensi
Angus, D., & Woodward, C. (2009). Multiple objective ant colony optimisation. Swarm Intelligence2, 3(1), 69–85.
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26(1), 1–13.
Girsang, A. S., Tsai, C.-W., & Yang, C.-S. (2016). Rectifying the Inconsistent Fuzzy Preference Matrix in AHP Using a Multi-Objective BicriterionAnt. Neural Processing Letters, 44(2), 519–538.
Gao, Y., Guan, H., Qi, Z., Hou, Y., & Liu, L. (2013). A multi-objective ant colony system algorithm for virtual machine placement in cloud computing. Journal of Computer and System Sciences, 79, 1230–1242.
Iredi, S., Merkle, D., & Middendorf, M. (2001). Bi-Criterion Optimization with Multi Colony Ant Algorithms. In International Conference on Evolutionary Multi-Criterion Optimization EMO 2001: Evolutionary Multi-Criterion Optimization (pp. 359–372).
Marler, R. T., & Arora, J. S. (2010). The weighted sum method for multi-objective optimization: new insights. Structural and Multidisciplinary Optimization, 41(6), 853–862.