Santa Fe Trail Problem
Keywords:
Santa Fe Trail, Evolutionary Computing etcAbstract
The Santa Fe Ant problem is conventional ideal problems that have been studied over the past two decades and is still being rigorously researched. Santa Fe Trail ant problem is well known for its reputation of being “hard” due to evolutionary computing methods not solving it at much higher effectiveness than random search. According to programmed set of instructions artificial ants search for food pallets in Santa Fe Trail. Various evolutionary algorithms have been implemented on this problem in these papers, which depicts various factors that are necessary to consider, while solving Santa Fe Trail using grammatical evolution. Algorithms such as Self Organizing Migrating Algorithm (SOMA), Simulating Annealing, Differential Evolution, Roulette Wheel, Monte Carlo, CGE, Novelty-based algorithms etc. These algorithms have been studied and their performance to solve Santa Fe Trail ant problem has been compared.
References
1. Zhou Y, Li LL, MingzhiMa. A complex-valued encoding bat algorithm for solving 0-1 knapsack problem. Springer Science +business media new york 2015; 12: 95-120.
2. Zamdborg L, Holloway DM et al. Forced evolution in Silico by articial transposons and their genetic operators: the ant navigation problem. Elsevier Inc 2015; 113: 88-110.
3. Azad A, Maria A, Rocha AC. Solving large 0-1 multidimensional knapsack problems by a new simplified binary Artificial swarm algorithm. Springer Inc 2015; 966: 110-130.
4. Berrero DF, Munoz P et al. On the statistical distribution of the expected run-time in population-based search algorithms. Springer Inc 2015; 102: 110-130.
5. Anibal-Lalla E, Stefenvob. A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem. Springer international publishing Switzerland 2015: 218-222.
6. Hamdan BI, Bashir H. A two stage Decomposition Approach for the TravellingSalesman Problem. Proceedings of the 2015 International Conference on Industrial Engineering and Operations Management Dubai, United Arab Emirates (UAE) 2015: 17.
7. Liu CY, Zou CM, Pie Wu. A task scheduling algorithm based on genetic algorithm and ant colony optimization in Cloud computing. 13th International Symposium on Distributed Computing and Applications to Business, Engineering and Science,China 2014: 68-72.
8. Herremans D, Sorenson K. FuX, an Android app that generates counterpoint. 2013IEEE Symposium on Computational Intelligence for Creativity and Affective Computing (CICAC) 2013: 48-55.
9. Sugiiea H, Mizano T. Santa fe trail problem solution using grammatical evolution. 2012 internal conference on industrial and intelligent information 2012;31.
10. Shen W, Xu B, Huang J. An improved genetic algorithm for 0-1 knapsack problems. Second Maya Hristekeva and DiptiShresta. Different Approaches to Solve the 0/1 Knapsack Problem 2008: 1-14.
11. Oplatkova Z, Zelinka I. Santa fe trail for artificial ant with analytical programming and three evolutionary algorithms. IEEE first Asia International Conference on modelling and simulation 2007: 1101-1130.
12. Dong YF, HuaGu J, Na-Li N et al. Combination of Gene tic, Algorithms and Ant algorithm for distribution network planning. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong 2007; 7: 999-1002. 13. Zamalloa M,Bordel G, Rodriguez L et al.Feature Selection Based on Genetic Algorithms for Speaker Recognition. Speaker and Language Recognition Workshop, IEEE Odyssey 2006: 557–564.
14. AndalJayalakshmi G, Sathiamoorthy S, Rajaram R. A Hybrid Genetic Algorithm – A New Approach to Solve Traveling Salesman Problem. International Journal of Computational Engineering Science 2006; 2: 339-355.
15. Langdon WB. The evolution of size in variable length representations. 1998 IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, USA, 5-9 May 1998.
16. Hristekeva M, Shresta D. Different Approaches to Solve the 0/1 Knapsack Problem 2008: 1-14.
17. Oplatkova Z, Zelinka I. Santa fe trail for artificial ant with analytical programming and three evolutionary algorithms. IEEE first Asia International Conference on modelling and simulation 2007: 1101-1130. 18. Dong YF, HuaGu J, Na-Li N et al. Combination of Genetic Algorithms and Ant algorithm for distribution network planning. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong 2007; 7: 999-1002.
19. Zamalloa M, Bordel G,Rodriguez L et al. Feature Selection Based on Genetic Algorithms for Speaker Recognition. Speaker and Language Recognition Workshop, IEEE Odyssey 2006: 557–564.
20. Jayalakshmi GA, Sathiamoorthy S, Rajaram R.A Hybrid Genetic Algorithm - A New Approach to Solve Traveling Salesman Problem. International Journal of Computational Engineering Science 2006; 2: 339 -355.
21. Langdon WB. The evolution of size in variable length representations. 1998 IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, USA, 5-9 May 1998.
22. Kushchu I. Genetic Programming and Evolutionary Generalization. IEEE Transactions On Evolutionary Computation 2002; 6: 5.
23. Vanneschi L, Tomassini M, Collard P et al. Negative slope coefficient: a measure to characterize genetic programming fitness landscapes. In Proceedings of the 9th European conference on Genetic Programming (EuroGP’06), Pierre Collet, Marco Tomassini, Marc Ebner, Steven Gustafson, and AnikóEkárt (Eds.). Springer-Verlag, Berlin, Heidelberg, 178-189.
24. Galván-López E, McDermott J, O’Neill M et al. Towards an understanding of locality in genetic programming. Proceedings of the 12th annual conference on Genetic and evolutionary computation 2010: 901-908.
25. McDermott J, Galván-Lopéz E, O’Neill M. A fine-grained view of GP locality with binary decision diagrams as ant phenotypes. In Proceedings of the 11th international conference on Parallel problem solving from nature: Part I (PPSN’10), Robert Schaefer, Carlos Cotta, JoannaKo?odziej, and Günter Rudolph (Eds.). SpringerVerlag, Berlin, Heidelberg 2010: 164-173.
26. Miller J,Thompson MJP. Cartesian Genetic Programming, Lecture Notes in Computer Science, 1802, 2000: 121132.
27. Jefferson D et al. Evolution as a theme in artificial life:The genesis/ tracker system. In Artificial Life II.
28. Langdon W. Fitness Causes Bloat in Variable Size Representations (CSRP-97-14) , Technical report 1997.
29. Langdon WB, Poli R. Why ants are hard. in Proc. 3rd Annual Conf.: Genetic Programming, Koza JR, Banzhaf W, Chellapilla K, Deb K, Dorigo M, Fogel DB, Garzon MH, Goldberg DE, Iba H, Riolo R, Eds., Madison, WI, 1998: 22–25.
30. Oplatkova Z, Zelinka I. Santafe trail for artificial ant with simulating annealing-preliminary study. IEEE first Asia International Conference on modelling and simulation 2008: 1111-1130.
31. Christensen S, Oppacher F. Solving the artificial ant on the Santa Fe trail problem in 20,696 fitness evaluations”,”GECCO ‘07: Proceedings of the 9th annual conference on Genetic and evolutionary computation 2007; 2: 1574 - 1579.
32. Wilson D, Kaur D. How Santa fe ants evolve. CornellUnive rsity international conference 2013: 92-103.
33. Sugiiea H,Mizano T. Santa fe trail problem solution using grammatical evolution. 2012 internal conference on industrial and intelligent information 2012: 31.
34. Doucette J, Heywood MI. Novelty based fitness:an evolution under the santafe trail. 13th European Conference, Euro GP 2010, Istanbul, Turkey 2010: 50-61.
2. Zamdborg L, Holloway DM et al. Forced evolution in Silico by articial transposons and their genetic operators: the ant navigation problem. Elsevier Inc 2015; 113: 88-110.
3. Azad A, Maria A, Rocha AC. Solving large 0-1 multidimensional knapsack problems by a new simplified binary Artificial swarm algorithm. Springer Inc 2015; 966: 110-130.
4. Berrero DF, Munoz P et al. On the statistical distribution of the expected run-time in population-based search algorithms. Springer Inc 2015; 102: 110-130.
5. Anibal-Lalla E, Stefenvob. A Biased Random-Key Genetic Algorithm for the Multiple Knapsack Assignment Problem. Springer international publishing Switzerland 2015: 218-222.
6. Hamdan BI, Bashir H. A two stage Decomposition Approach for the TravellingSalesman Problem. Proceedings of the 2015 International Conference on Industrial Engineering and Operations Management Dubai, United Arab Emirates (UAE) 2015: 17.
7. Liu CY, Zou CM, Pie Wu. A task scheduling algorithm based on genetic algorithm and ant colony optimization in Cloud computing. 13th International Symposium on Distributed Computing and Applications to Business, Engineering and Science,China 2014: 68-72.
8. Herremans D, Sorenson K. FuX, an Android app that generates counterpoint. 2013IEEE Symposium on Computational Intelligence for Creativity and Affective Computing (CICAC) 2013: 48-55.
9. Sugiiea H, Mizano T. Santa fe trail problem solution using grammatical evolution. 2012 internal conference on industrial and intelligent information 2012;31.
10. Shen W, Xu B, Huang J. An improved genetic algorithm for 0-1 knapsack problems. Second Maya Hristekeva and DiptiShresta. Different Approaches to Solve the 0/1 Knapsack Problem 2008: 1-14.
11. Oplatkova Z, Zelinka I. Santa fe trail for artificial ant with analytical programming and three evolutionary algorithms. IEEE first Asia International Conference on modelling and simulation 2007: 1101-1130.
12. Dong YF, HuaGu J, Na-Li N et al. Combination of Gene tic, Algorithms and Ant algorithm for distribution network planning. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong 2007; 7: 999-1002. 13. Zamalloa M,Bordel G, Rodriguez L et al.Feature Selection Based on Genetic Algorithms for Speaker Recognition. Speaker and Language Recognition Workshop, IEEE Odyssey 2006: 557–564.
14. AndalJayalakshmi G, Sathiamoorthy S, Rajaram R. A Hybrid Genetic Algorithm – A New Approach to Solve Traveling Salesman Problem. International Journal of Computational Engineering Science 2006; 2: 339-355.
15. Langdon WB. The evolution of size in variable length representations. 1998 IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, USA, 5-9 May 1998.
16. Hristekeva M, Shresta D. Different Approaches to Solve the 0/1 Knapsack Problem 2008: 1-14.
17. Oplatkova Z, Zelinka I. Santa fe trail for artificial ant with analytical programming and three evolutionary algorithms. IEEE first Asia International Conference on modelling and simulation 2007: 1101-1130. 18. Dong YF, HuaGu J, Na-Li N et al. Combination of Genetic Algorithms and Ant algorithm for distribution network planning. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong 2007; 7: 999-1002.
19. Zamalloa M, Bordel G,Rodriguez L et al. Feature Selection Based on Genetic Algorithms for Speaker Recognition. Speaker and Language Recognition Workshop, IEEE Odyssey 2006: 557–564.
20. Jayalakshmi GA, Sathiamoorthy S, Rajaram R.A Hybrid Genetic Algorithm - A New Approach to Solve Traveling Salesman Problem. International Journal of Computational Engineering Science 2006; 2: 339 -355.
21. Langdon WB. The evolution of size in variable length representations. 1998 IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, USA, 5-9 May 1998.
22. Kushchu I. Genetic Programming and Evolutionary Generalization. IEEE Transactions On Evolutionary Computation 2002; 6: 5.
23. Vanneschi L, Tomassini M, Collard P et al. Negative slope coefficient: a measure to characterize genetic programming fitness landscapes. In Proceedings of the 9th European conference on Genetic Programming (EuroGP’06), Pierre Collet, Marco Tomassini, Marc Ebner, Steven Gustafson, and AnikóEkárt (Eds.). Springer-Verlag, Berlin, Heidelberg, 178-189.
24. Galván-López E, McDermott J, O’Neill M et al. Towards an understanding of locality in genetic programming. Proceedings of the 12th annual conference on Genetic and evolutionary computation 2010: 901-908.
25. McDermott J, Galván-Lopéz E, O’Neill M. A fine-grained view of GP locality with binary decision diagrams as ant phenotypes. In Proceedings of the 11th international conference on Parallel problem solving from nature: Part I (PPSN’10), Robert Schaefer, Carlos Cotta, JoannaKo?odziej, and Günter Rudolph (Eds.). SpringerVerlag, Berlin, Heidelberg 2010: 164-173.
26. Miller J,Thompson MJP. Cartesian Genetic Programming, Lecture Notes in Computer Science, 1802, 2000: 121132.
27. Jefferson D et al. Evolution as a theme in artificial life:The genesis/ tracker system. In Artificial Life II.
28. Langdon W. Fitness Causes Bloat in Variable Size Representations (CSRP-97-14) , Technical report 1997.
29. Langdon WB, Poli R. Why ants are hard. in Proc. 3rd Annual Conf.: Genetic Programming, Koza JR, Banzhaf W, Chellapilla K, Deb K, Dorigo M, Fogel DB, Garzon MH, Goldberg DE, Iba H, Riolo R, Eds., Madison, WI, 1998: 22–25.
30. Oplatkova Z, Zelinka I. Santafe trail for artificial ant with simulating annealing-preliminary study. IEEE first Asia International Conference on modelling and simulation 2008: 1111-1130.
31. Christensen S, Oppacher F. Solving the artificial ant on the Santa Fe trail problem in 20,696 fitness evaluations”,”GECCO ‘07: Proceedings of the 9th annual conference on Genetic and evolutionary computation 2007; 2: 1574 - 1579.
32. Wilson D, Kaur D. How Santa fe ants evolve. CornellUnive rsity international conference 2013: 92-103.
33. Sugiiea H,Mizano T. Santa fe trail problem solution using grammatical evolution. 2012 internal conference on industrial and intelligent information 2012: 31.
34. Doucette J, Heywood MI. Novelty based fitness:an evolution under the santafe trail. 13th European Conference, Euro GP 2010, Istanbul, Turkey 2010: 50-61.
Published
2018-06-23
