Model Checking the Ant Colony Optimisation

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.
Document type :
Conference papers
Mike Hinchey; Bernd Kleinjohann; Lisa Kleinjohann; Peter A. Lindsay; Franz J. Rammig; Jon Timmis; Marilyn Wolf. 7th IFIP TC 10 Working Conference on Distributed, Parallel and Biologically Inspired Systems (DIPES) / 3rd IFIP TC 10 International Conference on Biologically-Inspired Collaborative Computing (BICC) / Held as Part of World Computer Congress (WCC) , Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-329, pp.221-232, 2010, Distributed, Parallel and Biologically Inspired Systems. 〈10.1007/978-3-642-15234-4_22〉
Liste complète des métadonnées

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01054497
Contributor : Hal Ifip <>
Submitted on : Thursday, August 7, 2014 - 11:08:01 AM
Last modification on : Friday, December 1, 2017 - 1:09:51 AM
Document(s) archivé(s) le : Wednesday, November 26, 2014 - 1:25:37 AM

File

papermodel.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Lucio Mauro Duarte, Luciana Foss, Flávio Rech Wagner, Tales Heimfarth. Model Checking the Ant Colony Optimisation. Mike Hinchey; Bernd Kleinjohann; Lisa Kleinjohann; Peter A. Lindsay; Franz J. Rammig; Jon Timmis; Marilyn Wolf. 7th IFIP TC 10 Working Conference on Distributed, Parallel and Biologically Inspired Systems (DIPES) / 3rd IFIP TC 10 International Conference on Biologically-Inspired Collaborative Computing (BICC) / Held as Part of World Computer Congress (WCC) , Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-329, pp.221-232, 2010, Distributed, Parallel and Biologically Inspired Systems. 〈10.1007/978-3-642-15234-4_22〉. 〈hal-01054497〉

Share

Metrics

Record views

191

Files downloads

180