Abstract
We present a model for the travelling salesman problem (TSP) solved using the ant colony optimisation (ACO), a bio-inspired mechanism that helps speed up the search for a solution and that can be applied to many other problems. The natural complexity of the TSP combined with the self-organisation and emergent behaviours that result from the application of the ACO make model-checking this system a hard task. We discuss our approach for modelling the ACO in a well-known probabilistic model checker and describe results of verifications carried out using our model and a couple of probabilistic temporal properties. These results demonstrate not only the effectiveness of the ACO applied to the TSP, but also that our modelling approach for the ACO produces the expected behaviour. It also indicates that the same modelling could be used in other scenarios.
Chapter PDF
Similar content being viewed by others
References
Olariu, S., Zomaya, A.: Handbook of Bioinspired Algorithms and Applications. Oxford University Press, Oxford (2007)
Heimfarth, T., Danne, K., Rammig, F.: An OS for Mobile Ad hoc Networks Using Ant Based Hueristic to Distribute Mobile Services. In: ICAS-ICNS, p. 77 (2005)
Janacik, P., Heimfarth, T., Rammig, F.: Emergent Topology Control Based on Division of Labour in Ants. In: AINA 2006, vol. 1, pp. 733–740 (2006)
Camazine, S., Deneubourg, J., Franks, N., et al.: Self-Organization in Biological Systems. Princeton University Press, Princeton (2001)
Lewes, G.: Problems of Life and Mind. Kessinger Publishing (2004)
De Wolf, T., Holvoet, T.: Emergence Versus Self-Organisation: Different Concepts But Promising When Combined Engineering. In: Brueckner, S.A., Di Marzo Serugendo, G., Karageorgos, A., Nagpal, R. (eds.) ESOA 2005. LNCS (LNAI), vol. 3464, pp. 1–15. Springer, Heidelberg (2005)
Vardi, M.: Automatic Verification of Probabilistic Concurrent Finite State Programs. In: 26th Annual Symp. on Found. of Comp. Sci., pp. 327–338 (1985)
Clarke, E.M., Grumberg, O., Peled, D.A.: Model Checking. The MIT Press, Cambridge (1999)
Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2006)
Dorigo, M., Gambardella, L.: Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Trans. on Evol. Comp. 1, 53–66 (1997)
Kwiatkowska, M., Norman, G., Parker, D.: PRISM: Probabilistic Symbolic Model Checker. In: Field, T., Harrison, P.G., Bradley, J., Harder, U. (eds.) TOOLS 2002. LNCS, vol. 2324, pp. 200–204. Springer, Heidelberg (2002)
Hansson, H., Jonsson, B.: A Logic for Reasoning About Time and Reliability. Formal Aspects of Computing 6, 512–535 (1994)
Ben-Ari, M., Manna, Z., Pnueli, A.: The Temporal Logic of Branching Time. Acta Informatica 20, 207–226 (1983)
Balasubramaniam, S., Botvich, D., Donnelly, et al.: Biologically Inspired Self-Governance and Self-Organisation for Autonomic Networks. In: 1st Intl. Conf. on Bio-Inspired Mod. of Net., Inform. and Comp. Sys., pp. 1–30 (2006)
Stauffer, A., Mange, D., Rossier, J., Vannel, F.: Bio-inspired Self-Organizing Cellular Systems. BioSystems 94, 164–169 (2008)
Cardelli, L.: Brane Calculi. In: Danos, V., Schachter, V. (eds.) CMSB 2004. LNCS (LNBI), vol. 3082, pp. 257–278. Springer, Heidelberg (2005)
Păun, G.: Computing with Membranes. Journal of Computing and System Sciences 61(1), 108–143 (2000)
Shang, G., Lei, Z., Fengting, Z., et al.: Solving Traveling Salesman Problem by Ant Colony Optimization Algorithm with Association Rule. In: 3rd Int. Conf. on Natural Computation, pp. 693–698 (2007)
Li, Y., Gong, S.: Dynamic Ant Colony Optimization for TSP. Int. J. Adv. Manuf. Technol. 22, 528–533 (2003)
Ugur, A., Aydin, D.: An Interactive Simulation and Analysis Software for Solving TSP using Ant Colony Optimization Algorithms. Adv. in Eng. Soft. 40, 341–349 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 IFIP
About this paper
Cite this paper
Duarte, L.M., Foss, L., Wagner, F.R., Heimfarth, T. (2010). Model Checking the Ant Colony Optimisation. In: Hinchey, M., et al. Distributed, Parallel and Biologically Inspired Systems. DIPES BICC 2010 2010. IFIP Advances in Information and Communication Technology, vol 329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15234-4_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-15234-4_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15233-7
Online ISBN: 978-3-642-15234-4
eBook Packages: Computer ScienceComputer Science (R0)