Perpustakaan Digital ITB

Topologi ring digunakan sebagai backbone pada jaringan optik karena dapat menghindari single-node failure. Topologi ring yang dirancang haruslah efisien untuk memperoleh Quality of Service (QoS) yang baik serta Capital Expenditure (CAPEX) yang rendah. Pada prinsipnya, perancangan topologi ring dapat dikategorikan ke dalam Traveling Salesman Problem (TSP) dan combinatorial optimization problem. Dalam combinatorial optimization, semakin besar skala TSP, maka semakin tinggi kompleksitasnya. Karena hal tersebut, TSP berskala besar sangatlah sulit untuk diselesaikan dalam waktu yang singkat. Algoritma yang paling mudah untuk menyelesaikan TSP adalah brute force. Brute force mampu memperoleh solusi optimal secara mutlak karena brute force akan mencoba semua kemungkinan kombinasi. Sayangnya, waktu komputasi brute force meningkat secara eksponensial seiring dengan bertambahnya skala TSP. Sampai saat ini, berbagai macam algoritma heuristic telah dikembangkan untuk menyelesaikan TSP, baik menggunakan pendekatan deterministik maupun probabilistik. Pendekatan deteministik dapat menyelesaikan TSP dalam satu kali pengujian (single cycle), namun waktu komputasi yang dibutuhkan sangatlah tinggi, khususnya menyelesaikan TSP berskala besar. Algoritma heuristic dengan pendekatan probabilistik dapat menyelesaikan TSP berskala besar dalam waktu yang acceptable. Sayangnya, solusi yang dihasilkan tidak stabil sehingga membutuhkan pengujian berulang kali (multi-cycle). Hal tersebut menyebabkan solusi yang dihasilkan menjadi tidak robust dan proses pencarian solusi dianggap tidak efisien. Beberapa contoh algoritma heuristic dengan pendekatan probabilistik antara lain Ant Colony Algorithm (ACO), Artificial Bee Intelligence (ABC), Simulated Annealing (SA), Genetic Algorithm (GA), dan Particle Swarm Optimization (PSO). Berdasarkan hal tersebut, diperlukan algoritma yang mampu memperoleh solusi optimal secara stabil dalam waktu komputasi yang acceptable dalam menyelesaikan TSP berskala besar. Penelitian ini mengembangkan algoritma heuristic yang diusulkan oleh Rokhayah dan Syambas (2020) dengan memodifikasi dua parameter kontrolnya, yaitu jumlah initial costs ( ) dan jumlah stored configurations ( ). Algoritma akan memulai konstruksi solusi dengan memilih links berdasarkan costs terendah. Pada iterasi berikutnya, setiap konfigurasi ring dikombinasikan dengan dua costs terendah dan belum terpilih. Apabila iterasi mencapai kelipatan tujuh, maka algoritma akan melakukan filter konfigurasi. Sebanyak konfigurasi dengan total cost terendah akan disimpan sedangkan sisanya akan dihapus. Pada iterasi terakhir, node terakhir pada setiap konfigurasi dihubungkan kembali dengan node awal sehingga terbentuklah topologi ring. Topologi ring dengan total cost terendah akan ditetapkan sebagai solusi optimal. Pada Rokhayah dan Syambas (2020), parameter bernilai 1. Karena hal tersebut, konfigurasi awal hanya mempertimbangkan cost terendah sehingga solusi masih belum optimal. Maka dari itu, penelitian ini memodifikasi parameter dengan nilai 2 dan 3 sehingga konfigurasi awal akan lebih bervariasi. Selain itu, parameter turut ditingkatkan guna menyimpan konfigurasi yang lebih bervariasi sehingga konfigurasi optimal tetap tersimpan sampai akhir iterasi. Parameter yang digunakan Rokhayah dan Syambas (2020) ialah 200, sedangkan parameter yang diuji pada penilitian ini ialah 200, 400, dan 600. Penelitian ini bertujuan untuk mengetahui parameter dan yang mampu memperoleh solusi optimal dalam waktu yang acceptable. Selain itu, penelitian ini akan memformulasikan space complexity yang tidak diformulasikan oleh penelitian sebelumnya. Metrik yang digunakan untuk mengevaluasi kinerja algoritma antara lain waktu komputasi dan tingkat kesalahan. Algoritma yang dijadikan sebagai pembanding ialah Rokhayah dan Syambas (2020) dan ACO. Hasil pengujian menunjukkan bahwa saat bernilai 600, 400, dan 200 masing-masing memperoleh rata-rata tingkat kesalahan sebesar 9.83%, 10.44%, dan 10.81%. saat bernilai 400 dan 200 masing-masing memperoleh rata- rata tingkat kesalahan sebesar 10.36% dan 10.86%. Rokhayah dan Syambas (2020) dan ACO memperoleh rata-rata tingkat kesalahan masing-masing sebesar sebesar 12.23% dan 19.88%. Waktu komputasi yang diperoleh pada sembarang saat bernilai 200, 400, dan 600 yaitu identik, 2 kali lebih tinggi, dan 3 kali lebih tinggi jika dibandingkan dengan Rokhayah dan Syambas (2020). Jika dibandingkan dengan ACO, waktu komputasi pada sembarang saat bernilai 200, 400, dan 600 yaitu 0.5 kali lebih rendah, identik, dan 0.5 kali lebih tinggi. Berdasarkan hasil yang telah diperoleh, parameter berdampak terhadap variasi konfigurasi. Semakin tinggi nilai , maka konfigurasi semakin bervariasi. Sedangkan parameter mempengaruhi penyimpanan konfigurasi saat terjadi filter konfigurasi. Semakin tinggi nilai , maka peluang terhapusnya konfigurasi optimal dapat diminimalkan. Maka dari itu, semakin tinggi parameter dan , maka semakin optimal konfigurasi ring yang diperoleh, namun waktu komputasi akan semakin tinggi.