Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem
Traveling salesman problem (TSP) is an optimization problem in determining the optimal route of a number of nodes that will only be passed once with the initial node as the final destination. One method for solving TSP is the Ant Colony Optimization (ACO) Algorithm. ACO is inspired by ant behaviour...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Program Studi Teknik Informatika Universitas Trilogi
2020-12-01
|
| Series: | JISA (Jurnal Informatika dan Sains) |
| Subjects: | |
| Online Access: | https://trilogi.ac.id/journal/ks/index.php/JISA/article/view/704 |
| _version_ | 1811208111963242496 |
|---|---|
| author | Alda Larasati Anindya Ketut Bayu Yogha Bintoro Silvester Dian Handy Permana |
| author_facet | Alda Larasati Anindya Ketut Bayu Yogha Bintoro Silvester Dian Handy Permana |
| author_sort | Alda Larasati Anindya |
| collection | DOAJ |
| description | Traveling salesman problem (TSP) is an optimization problem in determining the optimal route of a number of nodes that will only be passed once with the initial node as the final destination. One method for solving TSP is the Ant Colony Optimization (ACO) Algorithm. ACO is inspired by ant behaviour in searching for food, where ants produce pheromones to find food sources and make a route from the colony to food that will be followed by other ants. However ACO has not been considered as the optimal method for resolving TSP. This is because ACO has several shortcomings in the computational process. Comparisons between pheromones are not yet clear, and slow computing time causes the results of ACO to be not optimal. To correct these deficiencies, modifications will be made to the ACO. Modifications are made by changing some values in the ACO, such as adjusting the number of ants by the node automatically, changing the value in the pheromone renewal, and adding value to the construction of the solution. The outcome of this research is the modification of ACO did not provide shorter computing time with a more accurate final value, thus did not provide an optimal solution. The test results in this study found that the average computation time for the last iteration of each test was 0.54 second, and for the 10 iteration computation time obtained an average of 5.54 second for four tests. The amount of memory used in four tests in this study was 440.11 mb for 10 iterations. |
| first_indexed | 2024-04-12T04:17:15Z |
| format | Article |
| id | doaj.art-122388c616ec45648cdb695de5634c82 |
| institution | Directory Open Access Journal |
| issn | 2776-3234 2614-8404 |
| language | English |
| last_indexed | 2024-04-12T04:17:15Z |
| publishDate | 2020-12-01 |
| publisher | Program Studi Teknik Informatika Universitas Trilogi |
| record_format | Article |
| series | JISA (Jurnal Informatika dan Sains) |
| spelling | doaj.art-122388c616ec45648cdb695de5634c822022-12-22T03:48:22ZengProgram Studi Teknik Informatika Universitas TrilogiJISA (Jurnal Informatika dan Sains)2776-32342614-84042020-12-0132424810.31326/jisa.v3i2.704496Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman ProblemAlda Larasati Anindya0Ketut Bayu Yogha Bintoro1Silvester Dian Handy Permana2Universitas TrilogiUniversitas TrilogiUniversitas TrilogiTraveling salesman problem (TSP) is an optimization problem in determining the optimal route of a number of nodes that will only be passed once with the initial node as the final destination. One method for solving TSP is the Ant Colony Optimization (ACO) Algorithm. ACO is inspired by ant behaviour in searching for food, where ants produce pheromones to find food sources and make a route from the colony to food that will be followed by other ants. However ACO has not been considered as the optimal method for resolving TSP. This is because ACO has several shortcomings in the computational process. Comparisons between pheromones are not yet clear, and slow computing time causes the results of ACO to be not optimal. To correct these deficiencies, modifications will be made to the ACO. Modifications are made by changing some values in the ACO, such as adjusting the number of ants by the node automatically, changing the value in the pheromone renewal, and adding value to the construction of the solution. The outcome of this research is the modification of ACO did not provide shorter computing time with a more accurate final value, thus did not provide an optimal solution. The test results in this study found that the average computation time for the last iteration of each test was 0.54 second, and for the 10 iteration computation time obtained an average of 5.54 second for four tests. The amount of memory used in four tests in this study was 440.11 mb for 10 iterations.https://trilogi.ac.id/journal/ks/index.php/JISA/article/view/704ant colony optimizationaco modificationtraveling salesman problem |
| spellingShingle | Alda Larasati Anindya Ketut Bayu Yogha Bintoro Silvester Dian Handy Permana Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem JISA (Jurnal Informatika dan Sains) ant colony optimization aco modification traveling salesman problem |
| title | Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem |
| title_full | Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem |
| title_fullStr | Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem |
| title_full_unstemmed | Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem |
| title_short | Modification of Ant Colony Optimization Algorithm to Solve the Traveling Salesman Problem |
| title_sort | modification of ant colony optimization algorithm to solve the traveling salesman problem |
| topic | ant colony optimization aco modification traveling salesman problem |
| url | https://trilogi.ac.id/journal/ks/index.php/JISA/article/view/704 |
| work_keys_str_mv | AT aldalarasatianindya modificationofantcolonyoptimizationalgorithmtosolvethetravelingsalesmanproblem AT ketutbayuyoghabintoro modificationofantcolonyoptimizationalgorithmtosolvethetravelingsalesmanproblem AT silvesterdianhandypermana modificationofantcolonyoptimizationalgorithmtosolvethetravelingsalesmanproblem |