SIMULASI PENENTUAN LINTASAN TERPENDEK PADA COMPLETE GRAPH DENGAN MENGGUNAKAN ANT COLONY OPTIMIZATION ALGORITHM

Abstract

ABSTRAK

Ant Colony Optimization Algorithm merupakan suatu metodologi yang dihasilkan berdasarkan pengamatan terhadap perilaku semut. Ant Colony Optimization Algorithm berfungsi untuk menemukan solusi dalam permasalahan pencarian lintasan terpendek dengan berdasarkan nilai probabilistic dan dengan bantuan semut buatan yang terdapat pada algoritma ini. Penelitian ini bertujuan untuk membangun suatu program simulasi lintasan terpendek pada complete graph . Data jarak pada simulasi ini ditentukan secara random dengan ketentuan nilai 0 – 100. Simulasi yang dilakukan adalah perhitungan algoritma menggunakan nilai parameter dengan kondisi pheromone awal yang berbeda-beda. Parameter pada Ant Colony Optimization Algorithm diatur dengan nilai alpha = 1, beta = 2, nilai kondisi pheromone awal = 0.0001 untuk simulasi pertama, nilai alpha = 1, beta = 2, kondisi pheromone awal = 1 untuk simulasi kedua, dan nilai alpha = 1, beta = 5, kondisi pheromone awal = 0.00000001 untuk simulasi ketiga. Hasil simulasi menunjukkan bahwa semakin besar nilai kondisi pheromone awal yang digunakan maka semakin besar pula nilai temporary yang dihasilkan. Meskipun dengan kondisi pheromone awal berbeda, namun lintasan terpendek yang didapatkan dengan data jarak yang digunakan pada penelitian ini adalah sama yaitu 15 – 14 – 1 – 3 – 20 – 12 – 16 – 6 – 18 – 10 – 9 – 13 – 11 – 7 – 8 – 4 – 2 – 17 – 5 – 19 dengan panjang 613 (dalam km).

Kata kunci: Ant Colony Optimization Algorithm, Complete Graph, Simulasi, Lintasan Terpendek.

ABSTRACT

Ant Colony Optimization Algorithm is a methodology generated based on observations of ant behavior. Ant Colony Optimization Algorithm serves to find solutions in the problem of finding the shortest path based on probabilistic value and with the help of artificial ants found in this algorithm. This study aims to build a shortest path simulation program on the complete graph . The distance data in this simulation is determined randomly with terms 0 - 100. The simulation performed is the algorithm calculation using parameter values with different initial pheromone conditions. The parameters in Ant Colony Optimization Algorithm are set with the value of alpha = 1, beta = 2, initial pheromone condition value = 0.0001 for the first simulation, alpha = 1, beta = 2, initial pheromone = 1 for second simulation, and alpha = 1 , beta = 5, initial pheromone conditions = 0.00000001 for the third simulation. Simulation results show that the greater the initial pheromone condition used, the greater the temporary value generated. Although the initial pheromone conditions were different, the shortest path obtained with the distance data used in this study was the same, that was 15 – 14 – 1 – 3 – 20 – 12 – 16 – 6 – 18 – 10 – 9 – 13 – 11 – 7 – 8 – 4 – 2 – 17 – 5 – 19 with length 613 (in km).

Keywords: Ant Colony Optimization Algorithm, Complete Graph, Simulation, Shortest Path.