Ami Riana, Hermawan Syahputra

Simulasi Lintasan Terpendek pada Graf Komplit Menggunakan Ant Colony Optimization Algorithm

Introduction

Simulasi lintasan terpendek pada graf komplit menggunakan ant colony optimization algorithm. Simulasi lintasan terpendek pada graf komplit K_20 menggunakan Ant Colony Optimization (ACO). Menguji parameter fheromon berbeda untuk temukan jalur optimal.

Abstract

This study aims to build a shortest path simulation program on the complete graph K_20. The data of distance in this simulation was determined randomly with the provision of a value of 0-100. The simulation conducted was an algorithm calculation used parameter values with different initial pheromone conditions. The parameters in the Ant Colony Optimization Algorithm are set with alpha = 1, beta = 2, the initial pheromone condition = 0,0001 for the first simulation; alpha = 1, beta = 2, initial pheromone = 1 for the second simulation; and alpha value = 1, beta = 5, initial pheromone condition = 0,00000001 for the third simulation. The simulation results showed that if the value of the initial pheromone condition used gets greater, the value of the temporary output gets greater. Even though the initial pheromone condition was different, the shortest path obtained with distance data used in this study is the same, namely 15-14-1-3-20-12-16-6-18-10-9-13-11-7-8-4-2-17-5-19 with length 613 (in kilometers). [THE SHORTEST PATH SIMULATION IN COMPLETE GRAPHS USING THE ANT COLONY OPTIMIZATION ALGORITHM](J. Sains Indon., 42(2): 44-51, 2018)Keywords:Ant Colony Optimization Algorithm, Complete Graph, Shortest Path

Review

The paper, "Simulasi Lintasan Terpendek pada Graf Komplit Menggunakan Ant Colony Optimization Algorithm," explores the application of the Ant Colony Optimization (ACO) algorithm to solve the shortest path problem within a complete graph. The primary objective of this study is to build a simulation program to identify the shortest path on a K_20 complete graph, a common benchmark problem in graph theory and combinatorial optimization. The use of ACO is well-suited for such problems, aiming to demonstrate its capabilities in efficiently navigating complex graph structures to find optimal or near-optimal solutions. The methodology involved setting up a K_20 complete graph where edge distances were randomly assigned values between 0 and 100. The core of the experimental design centered on running the ACO algorithm with three distinct sets of parameter values, specifically varying the initial pheromone conditions. The first simulation used alpha=1, beta=2, and initial pheromone=0.0001; the second maintained alpha=1, beta=2, but increased initial pheromone to 1; and the third configuration featured alpha=1, beta=5, with an extremely low initial pheromone of 0.00000001. This systematic variation aimed to investigate the sensitivity of the ACO algorithm to different initial pheromone levels. The simulation results showed that an increase in the initial pheromone condition correlated with a greater "temporary output value," although the specific nature and significance of this output would benefit from further elaboration. Critically, despite these variations in initial pheromone and the observed change in temporary output, the ACO algorithm consistently converged on the *same* shortest path for the given random distance data. This path, explicitly detailed as 15-14-1-3-20-12-16-6-18-10-9-13-11-7-8-4-2-17-5-19, yielded a length of 613 kilometers. This finding suggests a robustness in the ACO algorithm's ability to identify a stable solution across a range of initial pheromone settings for this specific graph instance, demonstrating its consistent performance in finding *a* shortest path. For future work, comparing this result with exact methods or other heuristics could provide valuable insight into the optimality and efficiency of the discovered path.

Full Text

Comments

You need to be logged in to post a comment.