RING TOPOLOGY DESIGN USING HEURISTIC ALGORITHM BASED ON A DETERMINISTIC APPROACH

• Main Author: Soebagja Budiana, Mochamad
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/79084
• Institution: Institut Teknologi Bandung

Ring topology is used as the backbone in an optical network to avoid single-node failure. The design of ring topology must be efficient to obtain good Quality of Service (QoS) and low Capital Expenditure (CAPEX). In principle, the design of ring topology is categorized into Traveling Salesman Problem (TSP) and combinatorial optimization problems. In combinatorial optimization problems, the larger the TSP scale, the higher the complexity. Thus, solving large-scale TSP in an acceptable time is very difficult. The easiest way to solve TSP is using a brute force algorithm. Brute force can obtain the absolute optimal solution because brute force will try every single combination. Unfortunately, the computational time of brute force will increase exponentially as the TSP scale increases. Hitherto, various kinds of heuristic algorithms have been developed to solve TSP using deterministic or probabilistic approaches. The deterministic approach can solve the TSP in one trial (single cycle). However, the computational time is very high, especially for solving large- scale TSP. The heuristic algorithm with a probabilistic approach can solve large-scale TSP within an acceptable time. However, the solution of the probabilistic approach is unstable, so it requires several trials (multi-cycles). That causes the probabilistic approach solution to be not robust and the solution construction process is inefficient. Some of the heuristics based on the probabilistic approach are Ant Colony Algorithm (ACO), Artificial Bee Intelligence (ABC), Simulated Annealing (SA), Genetic Algorithm (GA), and Particle Swarm Optimization (PSO). Based on these problems, an algorithm that can obtain stable and optimal solutions with low computational time for solving large-scale TSP is needed. This research develops a heuristic algorithm proposed by Rokhayah and Syambas (2020) by modifying two control parameters, which are the initial link numbers ( ) and the stored configurations ( ). This algorithm starts the solution construction by choosing the links with the lowest costs. For the next iteration, each ring configuration is combined with the two lowest costs and has not been chosen yet. If the iteration reaches a multiple of seven, this algorithm filters the configurations. This algorithm keeps as many as configurations whereas the rest iv will be removed. On the last iteration, the last node on each configuration is connected to the initial node forming a ring topology. The ring topology with the lowest total cost will be chosen as an optimal solution. On Rokhayah and Syambas (2020), the parameter value is 1. This causes the initial links is only consider the lowest cost, so the solution is still not optimal. Therefore, this research is modifying the and parameters with 2 and 3 so that the initial configurations will be more varied. The y parameter is also increased to store more configurations, so the optimal configuration remains stored until the last of the iteration. On Rokhayah and Syambas (2020), the parameter used is 200, whereas in this research are 200, 400, and 600. The objectives of this research are to determine the best of and parameter values to achieve the optimal solution within an acceptable time. In addition, this research formulates the space complexity which is not formulated in previous research. The metrics used to evaluate the performance are computational time and error rate. The comparison algorithms in this research are ACO and Rokhayah and Syambas (2020). The results show that when is 600, 400, and 200 obtaining an average error rate of 9.83%, 10.44%, and 10.81%, respectively. when and obtaining an average error rate of 10.36% and 10.86%, respectively. Rokhayah and Syambas (2020) and ACO obtained an average error rate of 12.23% and 19.88%, respectively. Compared to Rokhayah and Syambas (2020), the computational time obtained by any when is 200, 400, and 600 is identical, 2 times higher, and 3 times higher, respectively. If the computational time is compared to ACO, any when is 200, 400, and 600 is 0.5 times lower, identical, and 0.5 times higher, respectively. Based on the results, the parameter affects the configuration variations. The higher the value, the more diverse the configurations are. Therefore, the probability of obtaining an optimal solution is increased. Meanwhile, the parameter affects the combination storage when the configuration filter occurs. The higher the value, the probability of losing the optimal configuration can be minimized. Therefore, the higher the and parameters, the ring configuration will be more optimal, but the computational time will be longer.