Ant Colony Optimization with Environment changes: an Application to GPS Surveying

• Autorzy: Antonio Mucherino , Stefka Fidanova , Maria Ganzha
• Języki publikacji: EN

Abstrakty

EN

We propose a variant on the well-known Ant Colony Optimization (ACO) general framework where we introduce the environment to play an important role during the optimization process. Together with diversification and intensification, the environment is introduced with the aim of avoiding the search to get stuck at local optima. In this work, the environment is simulated by means of the Logistic map, that is used in ACO for perturbing the update of the pheromone trails. Our preliminary experiments show that our environmental ACO (eACO), with variable environment, outperforms the standard ACO on a set of instances of the GPS Surveying Problem (GSP).(original abstract)

Słowa kluczowe

EN

Global Position System (GPS); Geodesy; Logistic map

PL

Global Position System (GPS); Geodezja; Odwzorowanie logistyczne

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2015
• Tom: 5
• Strony: 495--500

Twórcy

autor

Antonio Mucherino

• University of Rennes 1, Rennes, France

autor

Stefka Fidanova

• University of Sofia, Sofia, Bulgaria

autor

Maria Ganzha

• Polish Academy of Science, Warsaw, Poland

Bibliografia

• V. Atanassova, S. Fidanova, I. Popchev, P. Chountas, Generalized Nets, ACO-Algorithms and Genetic Algorithm. In: "Monte Carlo Methods and Applications", K.K. Sabelfeld, I. Dimov, De Gruyter, 39-46, 2012.
• T. Bektas, The Multiple Traveling Salesman Problem: an Overview of Formulations and Solution Procedures, Omega 34(3), 209-219, 2006.
• L. Chen, K. Aihara, Chaotic Simulated Annealing by a Neural Network Model with Transient Chaos, Neural Networks 8(6), 915-930, 1995.
• P. Dare, Optimal Design of GPS Networks: Operational Procedures, PhD Thesis, School of Surveying, University of East London, UK, 1995.
• P. Dare, H.A. Saleh, GPS Network Design: Logistics Solution using Optimal and Near-Optimal Methods, Journal of Geodesy 74, 467-478, 2000.
• M. Dorigo, M. Birattari, Ant Colony Optimization. In: "Encyclopedia of Machine Learning", C. Sammut, G.I. Webb (Eds.), Springer, 36-39, 2010.
• K. Falconer, Fractal Geometry: Mathematical Foundations and Applications, Wiley, 400 pages, 2013.
• S. Fidanova, Hybrid Heuristics Algorithms for GPS Surveying Problem, Lecture Notes in Computer Science 4310, Proceedings of the 6th International Conference on Numerical Methods and Applications, T. Boyanov, S. Dimova, K. Georgiev, G. Nikolov (Eds.), 239-248, 2007.
• S. Fidanova E. Alba, G. Molina, Memetic Simulated Annealing for GPS Surveying Problem, Lecture Notes in Computer Science 5434, Proceedings of the 4th International Conference on Numerical Analysis and Its Applications, S. Margenov, L.G. Vulkov, J. Waśniewski (Eds.), 281-288, 2009.
• S. Fidanova, E. Alba, G. Molina, Hybrid ACO Algorithm for the GPS Surveying Problem, Lecture Notes in Computer Science 5910, Proceedings of Large Scale Scientific Computing, I. Lirkov, S. Margenov, J. Waśniewski (Eds.), 318-325, 2010.
• B. Hofmann-Wellenhof, H. Lichtenegger, J. Collins, Global Positioning System: Theory and Practice, Springer, 326 pages, 1993.
• R. Horst, P.M. Pardalos, Handbook of Global Optimization, Springer, 879 pages, 1995.
• J.B. Kruskal, On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proceedings of the American Mathematical Society 7(1), 48-50, 1956.
• A. Leick, GPS Satellite Surveying, 3rd edition, Wirley, 464 pages, 2004.
• L. Liberti, C. Lavor, N. Maculan, A. Mucherino, Euclidean Distance Geometry and Applications, SIAM Review 56(1), 3-69, 2014.
• T.E. Malliavin, A. Mucherino, M. Nilges, Distance Geometry in Struc- tural Biology: New Perspectives. In: "Distance Geometry: Theory, Methods and Applications", A. Mucherino, C. Lavor, L. Liberti, N. Maculan (Eds.), Springer, 329-350, 2013.
• A. Mucherino, O. Seref, Modeling and Solving Real Life Global Optimization Problems with Meta-Heuristic Methods. In: "Advances in Modeling Agricultural Systems", Springer Optimization and Its Applications 25, P.J. Papajorgji, P.M. Pardalos (Eds.), 403-420, 2008.
• C.H. Papadimitriou, The Euclidean Travelling Salesman Problem is NP- complete, Theoretical Computer Science 4(3), 237-244, 1977.
• M. Rani, R. Agarwal, Generation of Fractals from Complex Logistic Map, Chaos, Solitions and Fractals 42, 447-452, 2009.
• H.A. Saleh, P. Dare, Effective Heuristics for the GPS Survey Network of Malta: Simulated Annealing and Tabu Search Techniques, Journal of Heuristics 7, 533-549, 2001.
• H.A. Saleh, P. Dare, Heuristic Methods for Designing a Global Positioning System Surveying Network in the Republic of Seychelles, The Arabian Journal for Science and Engineering 26(1B), 74-93, 2002.
• T. Stutzle, H.H. Hoos, MAX-MIN Ant System; In: "Future Generation Computer Systems", vol. 16, M. Dorigo, T. Stutzle, G. Di Caro (Eds.), 889-914, 2000.
• E-G. Talbi, Metaheuristics: From Design to Implementation, Wiley, 624 pages, 2009.
• P. Teunissen, A. Kleusberg, GPS for Geodesy, 2nd edition, Springer, 650 pages, 1998.
• P-F. Verhulst, A Note on the Law of Population Growth, Correspondence Mathematiques et Physiques 10, 113-121, 1938 (in French).
• D. Yang, G. Li, G. Cheng, On the Efficiency of Chaos Optimization Algorithms for Global Optimization, Chaos, Solitions and Fractals 34, 1366-1375, 2007

Identyfikatory

DOI

10.15439/2015F33