Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Consensus Theory for Cognitive Agents’ Unstructured Knowledge Conflicts Resolving in Management Information Systems Kapitel lesen Erstes Kapitel lesen

2019 | OriginalPaper | Buchkapitel

Local Termination Criteria for Swarm Intelligence: A Comparison Between Local Stochastic Diffusion Search and Ant Nest-Site Selection

verfasst von : Andrew O. Martin, J. Mark Bishop, Elva J. H. Robinson, Darren R. Myatt

Erschienen in: Transactions on Computational Collective Intelligence XXXII

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Stochastic diffusion search (SDS) is a global Swarm Intelligence optimisation technique based on the behaviour of ants, rooted in the partial evaluation of an objective function and direct communication between agents. Although population based decision mechanisms employed by many Swarm Intelligence methods can suffer poor convergence resulting in ill-defined halting criteria and loss of the best solution, as a result of its resource allocation mechanism, the solutions found by Stochastic Diffusion Search enjoy excellent stability.
Previous implementations of SDS have deployed stopping criteria derived from global properties of the agent population; this paper examines new local SDS halting criteria and compares their performance with ‘quorum sensing’ (a termination criterion naturally deployed by some species of tandem-running ants). In this chapter we discuss two experiments investigating the robustness and efficiency of the new local termination criteria; our results demonstrate these to be (a) effectively as robust as the classical SDS termination criteria and (b) almost three times faster.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel The Ins and Outs of Network-Oriented Modeling: From Biological Networks and Mental Networks to Social Networks and Beyond
Nächstes Kapitel Towards Large-Scale Optimization of Iterated Prisoner Dilemma Strategies
Fußnoten
1
The simplifying assumption is that, by considering only the mean transition of agents between different clusters of agents, rather than the full probability distribution (as investigated in [51]), a sufficiently accurate model of SDS may be obtained.
 
2
It should be emphasised that this analogy is provided simply to illustrate the communication and feedback mechanisms at the heart of a stochastic diffusion search, and not as a heuristic to be employed by a group of hungry conference delegates.
 
3
The material in Sect. 6 was included at the suggestion of one of the reviewers of this manuscript; it forms a much extended and adapted version of the ‘practical’ analysis of SDS behaviour first presented by Myatt et al. in [48].
 
4
Thus multiple testing is very similar to the repeated metrics strategy deployed by real scouts in nest selection, albeit in the latter case scouts assess potential nest sites across a number of metrics using a weighted additive strategy [27].
 
5
Standard SDS has previously been shown to be a global search algorithm [51] - it will eventually converge to the global best solution in a given search space; by removing agents form the swarm, relative to standard SDS the number of potential agents remaining available for explore-exploit behaviour is reduced.
 
6
To facilitate the use of homogenous performance metrics, we assume that in a population of k agents, k single asynchronous updates corresponds to one standard synchronous iteration cycle.
 
7
\(\beta \) defines a “uniform random noise” hypothesis; an aggregate of all the possible hypotheses an agent could have other than the putative solution hypothesis.
 
8
These parameters define a problem analogous to the search space being infinitely large, wherein the only way an agent can adopt the ‘best’ solution is to receive it via diffusion from an active agent.
 
Literatur
1.
Aleksander, I., Stonham, T.J.: Guide to pattern recognition using random access memories. Comput. Digit. Tech. 2(1), 29–40 (1979)CrossRef
2.
Al-Rifaie, M.M., Bishop, J.M.: Stochastic diffusion search review. J. Behav. Robot. 4(3), 155–173 (2013)
3.
Anoop, K., Sumana, A.: Response to a change in the target nest during ant relocation. J. Exp. Biol. 218(6), 887–92 (2015)CrossRef
4.
Arthur, W.B.: Inductive reasoning and bounded rationality (The El Farol Problem). Amer. Econ. Rev. 84, 406–411 (1994)
5.
Back, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, Oxford (1996)MATH
6.
Beattie, P.D., Bishop, J.M.: Self-localisation in the ‘SENARIO’ autonomous wheelchair. J. Intell. Robot. Syst. 22, 255–267 (1998)CrossRef
7.
Bishop, J.M.: Stochastic Searching Networks. In: Proceedings of 1st IEE International Conference on Artificial Neural Networks. IEE Conference Publication (313), pp. 329–331. IEE, London (1989)
8.
Bishop, J.M.: Anarchic techniques for pattern classification. Ph.D. thesis, Reading University, UK (1989)
9.
Bishop, J.M., Torr, P.H.S.: The stochastic search network. In: Linggard, R., Myers, D.J., Nightingale, C. (eds.) Neural Networks for Images, Speech and Natural Language. Chapman Hall, New York (1992)
10.
11.
Bishop, J.M., Andrew, O.M., Robinson, E.J.H.: Local termination criteria for stochastic diffusion search: a comparison with the behaviour of ant nest-site selection. In: Nguyen, N., Iliadis, L., Yannis, M., Bogdan, T. (eds.) Computational Collective Intelligence. Lecture Notes in Computer Science, vol. 9875, pp. 474–486. Springer, Heidelberg (2016). https://​doi.​org/​10.​1007/​978-3-319-45243-2_​44CrossRef
12.
Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, Oxford (1999)MATH
13.
Bonabeau, E., Dorigo, M., Theraulaz, G.: Inspiration for optimisation from social insect behaviour. Nature 406, 3942 (2000)CrossRef
14.
Cao, T.T.: High social density increases foraging and scouting rates and induces polydomy in Temnothorax ants. Behav. Ecol. Sociobiol. 67(11), 1799–1807 (2013)CrossRef
15.
Carroll, C.R., Janzen, D.H.: Ecology of foraging by ants. Annu. Rev. Ecol. Syst. 4, 231–257 (1973)CrossRef
16.
Chadab, R., Rettenmeyer, C.: Mass recruitment by army ants. Science 188, 1124–1125 (1975)CrossRef
17.
Deneubourg, J.L., Pasteels, J.M., Verhaeghe, J.C.: Probabilistic behaviour in ants: a strategy of errors? J. Theor. Biol. 105(2), 259–271 (1983)CrossRef
18.
Dornhaus, A., Franks, N.R., Hawkins, R.M., Shere, H.N.S.: Ants move to improve: colonies of Leptothorax albipennis emigrate whenever they find a superior nest site. Anim. Behav. 67(5), 959–963 (2004)CrossRef
19.
Dornhaus, A., Holley, J.A., Pook, V.G., Worswick, G., Franks, N.R.: Why do not all workers work? Colony size and workload during emigrations in the ant Temnothorax albipennis. Behav. Ecol. Sociobiol. 63(1), 43–51 (2008)CrossRef
20.
Dorigo, M., Maniezzo, V., Colorni, A.: Positive feedback as a search strategy, Dipartimento di Elettronica e Informatica, Politecnico di (1991)
21.
Dorigo, M.: Optimisation, learning and natural algorithms. Politecnico di Italy, Milano (1992)
22.
Dorigo, M., Caro, G.D., Gambardella, L.M.: Ant algorithms for discrete optimisation. Artif. Life 5(2), 137–172 (1999)CrossRef
23.
Franklin, E.L.: The journey of tandem running: the twists, turns and what we have learned. Insectes Sociaux 61, 1–8 (2014)CrossRef
24.
Franks, N.R., Dornhaus, A., Metherell, B., Nelson, T., Lanfear, S.A., Symes, W.: Not everything that counts can be counted: ants use multiple metrics for a single nest trait. Proc. R. Soc. Lond. Ser. B 273, 165–169 (2006)
25.
Franks, N.R., Hooper, J.W., Dornhaus, A., Aukett, P.J., Hayward, A.L., Berghoff, S.M.: Reconnaissance and latent learning in ants. Proc. R. Soc. Lond. Ser. B 274(1617), 1505–1509 (2007)
26.
Franks, N.R., et al.: Moving targets: collective decisions and flexible choices in house-hunting ants. Swarm Intell. 1(2), 81–94 (2007)CrossRef
27.
Franks, N.R., Mallon, E.B., Bray, H.E., Hamilton, M.J., Mischler, T.C.: Strategies for choosing between alternatives with different attributes: exemplified by house-hunting ants. Anim. Behav. 65, 215–223 (2003)CrossRef
28.
Frank, N.R., et al.: How ants use quorum sensing to estimate the average quality of a fluctuating resource. Sci. Rep. 5, 11890 (2015)CrossRef
29.
Goldberg, D.: Genetic Algorithms in Search, Optimisation and Machine Learning. Addison Wesley, Reading (1989)MATH
30.
Goodman, L.J., Fisher, R.C.: The Behaviour and Physiology of Bees. CAB International, Oxon (1991)
31.
Grech-Cini, E.: Locating facial features. Ph.D. dissertation, University of Reading, Reading UK (1995)
32.
33.
Holland, J.H.: Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor (1975)
34.
Fan, H., Hua, Z., Li, J.J., Yuan, D.: Solving a shortest path problem by ant algorithm. In: Proceedings of 2004 International Conference on Machine Learning and Cybernetics, vol. 5, pp. 3174–3177 (2004)
35.
Krieger, M.J., Billeter, J.B., Keller, L.: Ant-like task allocation and recruitment in cooperative robots. Nature 406(6799), 992–995 (2000)CrossRef
36.
Iosifescu, M.: Finite Markov Processes and Their Applications. Wiley, Chichester (1980)MATH
37.
Kennedy, J., Eberhart, R.C., Shi, Y.: Swarm Intelligence. Morgan Kauffman, San Francisco (2001)
38.
Kennedy, J., Eberhart, R.C.: Particle swarm optimisation. In: Proceedings of the IEEE International Conference on Neural Networks IV, pp. 1942–1948 (1995)
39.
Kramer, B.H., Scharf, I., Foitzik, S.: The role of per-capita productivity in the evolution of small colony sizes in ants. Behav. Ecol. Sociobiol. 68(1), 41–53 (2013)CrossRef
40.
De Meyer, K.: Explorations in stochastic diffusion search: soft and hardware implementations of biologically inspired spiking neuron stochastic diffusion networks. Technical report KDM/JMB/2000-1. University of Reading, Reading UK (2000)
41.
42.
De Meyer, K., Nasuto, S.J., Bishop, J.M.: Stochastic diffusion optimisation: the application of partial function evaluation and stochastic recruitment. In: Abraham, A., Grosam, C., Ramos, V. (eds.) Stigmergic Optimisation. SCI, vol. 31, pp. 185–207. Springer, Heidelberg (2006). https://​doi.​org/​10.​1007/​978-3-540-34690-6_​8CrossRef
43.
Kurvers, R.H.J.M., Wolf, M., Krause, J.: Humans use social information to adjust their quorum thresholds adaptively in a simulated predator detection experiment. Behav. Ecol. Sociobiol. 68(3), 449–456 (2014)CrossRef
44.
Miller, M.B., Bassler, B.L.: Quorum sensing in bacteria. Annu. Rev. Microbiol. 55(1), 165–199 (2001)CrossRef
45.
Mitrus, S.: The cavity-nest ant Temnothorax crassispinus prefers larger nests. Insectes Sociaux 62(1), 43–49 (2015)CrossRef
46.
Moglich, M., Maschwitz, U., Holldobler, B.: Tandem calling: a new kind of signal in ant communication. Science 186(4168), 1046–1047 (1974)CrossRef
47.
Mugford, S.T., Mallon, E.B., Franks, N.R.: The accuracy of Buffon’s needle: a rule of thumb used by ants to estimate area. Behav. Ecol. 12, 655–658 (2001)CrossRef
48.
Myatt, D.M., Bishop, J.M., Nasuto, S.J.: Minimum stable convergence criteria for stochastic diffusion search. Electron. Lett. 22(40), 112–113 (2004)CrossRef
49.
Myatt, D., M., Nasuto, S.J., Bishop J.M., : Alternative recruitment strategies for SDS. In: Proceedings of AISB06: Symposium on Exploration vs. Exploitation in Naturally Inspired Search, Bristol, UK, pp. 181–187 (2006)
50.
Nasuto, S.J.: Analysis of resource allocation of stochastic diffusion search. Ph.D. dissertation. University of Reading, Reading UK (1999)
51.
Nasuto, S.J., Bishop, J.M.: Convergence of the stochastic diffusion search. Parallel Algorithms Appl. 14, 89–107 (1999)CrossRef
52.
Nasuto, S.J., Bishop, J.M., Lauria, S.: Time complexity of stochastic diffusion search. In: Heiss, M. (ed) Proceedings of International ICSC/IFAC Symposium on Neural Computation, Vienna (1998)
53.
54.
Nasuto, S.J., Bishop, J.M., De Meyer, K.: Communicating neurons: a connectionist spiking neuron implementation of stochastic diffusion search. Neurocomputing 72(4–6), 704–712 (2008)
55.
Nasuto, S.J., Bishop, J.M.: Steady state resource allocation analysis of the stochastic diffusion search. Biol. Inspired Cogn. Arch. 12, 65–76 (2015)
56.
Neumaier, A.: Complete search in continuous global optimisation and constraint satisfaction. In: Isereles, A. (ed.) Acta Numerica 2004. Cambridge University Press, Cambridge UK (2004)
57.
Pratt, S.C.: Behavioural mechanisms of collective nest-site choice by the ant Temnothorax curvispinosus. Insectes Sociaux 52, 383–392 (2005)CrossRef
58.
Pratt, S.C.: Quorum sensing by encounter rates in the ant Temnothorax albipennis. Behav. Ecol. 16, 488–496 (2005)CrossRef
59.
Pratt, S.C., Mallon, E.B., Sumpter, D.J.T., Franks, N.R.: Quorum sensing, recruitment, and collective decision-making during colony emigration by the ant Leptothorax albipennis. Behav. Ecol. Sociobiol. 52(2), 117–127 (2002)CrossRef
60.
Pratt, S.C., Pierce, N.E.: The cavity-dwelling ant Leptothorax curvispinosus uses nest geometry to discriminate among potential homes. Anim. Behav. 62, 281–287 (2001)CrossRef
61.
Pratt, S.C., Sumpter, D.J.T., Mallon, E.B., Franks, N.R.: An agent-based model of collective nest site choice by the ant Temnothorax albipennis. Anim. Behav. 70, 1023–1036 (2005)CrossRef
62.
63.
Robinson, E.J.H., Franks, N.R., Ellis, S., Okuda, S., Marshall, J.A.R.: A simple threshold rule is sufficient to explain sophisticated collective decision-making. PLoS One 6, e19981 (2011)CrossRef
64.
Robinson, E.J.H., Smith, F.D., Sullivan, K.M.E., Franks, N.R.: Do ants make direct comparisons? Proc. Royal Soc. B 276, 2635–2641 (2009)CrossRef
65.
Sasaki, T., Colling, B., Sonnenschein, A., Boggess, M.M., Pratt, S.C.: Flexibility of collective decision making during house hunting in Temnothorax ants. Behav. Ecol. Sociobiol. 69, 707–714 (2015)CrossRef
66.
Sasaki, T., Pratt, S.C.: Emergence of group rationality from irrational individuals. Behav. Ecol. 22(2), 276–281 (2011)CrossRef
67.
Seeley, T.D.: The Wisdom of the Hive. Harvard University Press, Cambridge (1995)
68.
Seeley, T.D., Visscher, P.K.: Quorum sensing during nest-site selection by honeybee swarms. Behav. Ecol. Sociobiol. 56, 594–601 (2004)CrossRef
69.
Seeley, T.D., Visscher, P.K., Schlegel, T., Hogan, P.M., Franks, N.R., Marshall, J.A.R.: Stop signals provide cross inhibition in collective decision-making by honey bee swarms. Science 335, 108–111 (2012)CrossRef
70.
Stroeymeyt, N., Robinson, E.J.H., Hogan, P.M., Marshall, J.A.R., Giurfa, M., Franks, N.R.: Experience-dependent flexibility in collective decision-making by house-hunting ants. Behav. Ecol. 22(3), 535–542 (2011)CrossRef
71.
Sueur, C., Deneubourg, J.L., Petit, O.: Sequence of quorums during collective decision making in macaques. Behav. Ecol. Sociobiol. 64, 1875–1885 (2010)CrossRef
72.
Sumpter, D.J.T., Pratt, S.C.: Quorum responses and consensus decision making. Proc. R. Soc. B 364(1518), 743–753 (2009)
73.
Ward, A.J.W., Sumpter, D.J.T., Couzin, I.D., Hart, P.J.B., Krause, J.: Quorum decision-making facilitates information transfer in fish shoals. Proc. Nat. Acad. Sci. 105(19), 6948–6953 (2008)CrossRef
74.
Whitaker, R.M., Hurley, S.: An agent based approach to site selection for wireless networks. In: Proceedings of 2002 ACM Symposium on Applied Computing (Madrid), pp. 574–577. ACM, New York (2002)
75.
Wilson, E.O.: Communication by tandem running in the ant genus Cardiocondyla. Psyche 66(3), 29–34 (1959)CrossRef
76.
Wilson, E.O.: Chemical communication among workers of the fire ant Solenopsis saevissima (Fr. Smith) 1. The organisation of mass-foraging. Anim. Behav. 10, 134–147 (1962)CrossRef
Metadaten
Titel
Local Termination Criteria for Swarm Intelligence: A Comparison Between Local Stochastic Diffusion Search and Ant Nest-Site Selection
verfasst von
Andrew O. Martin
J. Mark Bishop
Elva J. H. Robinson
Darren R. Myatt
Copyright-Jahr
2019
Verlag
Springer Berlin Heidelberg
Buch
Transactions on Computational Collective Intelligence XXXII

Print ISBN: 978-3-662-58610-5

Electronic ISBN: 978-3-662-58611-2

Copyright-Jahr: 2019

DOI
https://doi.org/10.1007/978-3-662-58611-2_3

Neuer Inhalt

    Bildnachweise