nach oben

Natural Computing

Erschienen in:

01.09.2009

Natural strategies for search

verfasst von: Alec Banks, Jonathan Vincent, Keith Phalp

Erschienen in: Natural Computing | Ausgabe 3/2009

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In recent years a considerable amount of natural computing research has been undertaken to exploit the analogy between, say, searching a given problem space for an optimal solution and the natural process of foraging for food. Such analogies have led to useful solutions in areas such as optimisation, prominent examples being ant colony systems and particle swarm optimisation. However, these solutions often rely on well defined fitness landscapes that are not always be available in more general search scenarios. This paper surveys a wide variety of behaviours observed within the natural world, and aims to highlight general cooperative group behaviours, search strategies and communication methods that might be useful within a wider computing context, beyond optimisation, where information from the fitness landscape may be sparse, but new search paradigms could be developed that capitalise on research into biological systems that have developed over millennia within the natural world.

Vorheriger Artikel On the solution of trivalent decision problems by quantum state identification

Nächster Artikel On codeword design in metric DNA spaces

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

Anderson C, Franks NR (2001) Teams in animal societies. Behav Ecol 12(5):534–540CrossRef

Anderson C, Theraulaz G, Deneubourg JL (2002) Self-assemblages in insect societies. Insect Soc 49:99–110CrossRef

Atkinson RPD, Rhodes CJ, Macdonald DW, Anderson RM (2002) Scale-free dynamics in the movement patterns of jackals. OIKOS 98:134–140CrossRef

Bartumeus F, Catalan J, Fulco UL, Lyra ML, Viswanathan GM (2002) Optimizing the encounter rate in biological interactions: Lévy versus Brownian strategies. Phys Rev Lett 88:9, American Physical SocietyCrossRef

Bell WJ (1991) Searching behaviour: the behavioural ecology of finding resources. Chapman and Hall Animal Behaviour Series, Chapman and Hall, London

Benichou O, Coppey M, Moreau M, Suet P-H, Voituriez R (2005) Optimal search strategies for hidden targets. Phys Rev Lett 94:198101CrossRef

Boyer D, Miramontes O, Ramos-Fernandez G, Mateos JL, Cocho G (2004) Modeling the searching behavior of social monkeys. Physica A-Statis Mech Appl 342(1–2):329–335CrossRef

Burns JG (2005) Impulsive bees forage better: the advantage of quick, sometimes inaccurate foraging decisions. Anim Behav 70:e1–e5CrossRef

Butler MA (2005) Foraging mode of the chameleon. Bradypodian pumilum: a challenge to the sit-and-wait versus active forager paradigm? Biol J Linn Soc 84:797–808CrossRef

Charnov EL (1976) Optimal foraging, the marginal value theorem. Theor Popul Biol 9:2CrossRef

Colorni A, Dorigo M, Maniezzo V (1991) Distributed optimization by ant colonies. Proc European Conference on Artificial Life, Paris, France, pp 134–142

Cope JM, Fox CW (2003) Oviposition decisions in the seed beetle, Callosobruchus maculatus (Coleoptera: Bruchidae): effects of seed size on superparatism. J Stored Prod Res 39:355–365CrossRef

De Jong K (1975) An analysis of the behaviour of a class of genetic adaptive systems. PhD thesis, University of Michigan

De Meyer K, Bishop JM, Nasuto SJ (2003) Stochastic diffusion: using recruitment for search. Symposium on Evolvability & Interaction. 8–10th October 2003. Queen Mary. The University of London, UK

Dechaume-Moncharmont F-X, Dornhaus A, Houston AI, McNamara JM, Collins EJ, Franks NR (2006) The hidden cost of information in collective foraging. Proc Royal Soc B Biol Sci 1(1):1689

Dejean A, Le Breton J, Suzzoni JP, Orival J, Saux-Moreau C (2005) Influence of interspecific competition on the recruitment behavior and liquid food transport in the tramp ant species pheidole megacephala. Naturwissenschaften 92:324–327CrossRef

Delestrade A (1999) Foraging strategy in a social bird the alpine chough: effect of variation in quantity and distribution of food. Anim Behav 57:299–305CrossRef

Dobbs RC, Martin Te (1998) Variation in foraging behavior among nesting stages of female red-faced warblers. Condor 100:741–745, The Cooper Ornithological SocietyCrossRef

Dornhaus A, Chittka L (2004) Why do honey bees dance? Behav Ecol Sociobiol 55:395–401CrossRef

Dugatkin LA (1997) The evolution of cooperation. Bioscience 47(6):355 June 1997CrossRef

Etiene AS, Jeffery KJ (2004) Path integration in mammals. Hippocampus 14:180–192, Wiley-Liss IncCrossRef

Farina WM, Wainselboim AJ (2005) Trophallaxis within the dancing context: a behavioural and thermographic analysis in honeybees (Apis mellifera). Apidologie 36:43–47CrossRef

Fitzpatrick JW (1980) Foraging behavior of neotropical tyrant flycatchers. Condor 82:43–57, The Cooper Ornithological SocietyCrossRef

Fogel LJ, Owens AJ and Walsh MJ (1964) On the evolution of artificial intelligence. In: Proceedings of 5th national symposium on human factors in engineering, IEEE, San Diego, CA, pp 63–76

Freake MJ (2001) Homing behavior in the sleepy lizard (Tiliqua rugosa): the role of visual cues and the parietal eye. Behav Ecol Sociobiol 50:563–569

Freeman MC, Grossman GD (1992) Group foraging by a stream minnow: shoals or aggregations? Anim Behav 44:393–403CrossRef

Fresneau D (1985) Individual foraging and path fidelity in a ponerine ant. Insectes Sociaux Paris 32(2):109–116CrossRef

Friedberg RM (1958) A learning machine: Part I. IBM J, pp 2–13

Fruergaard-Pedersen R (2006). Optimal demining using a swarm of low-cost robotic units. Phd Thesis, Department of Computer Science – Daimi, Faculty of Science, University of Aarhus, Denmark

Gil M, De Marco RJ (2005) Olfactory learning by means of trophallaxis in Apis mellifera. J Exp Biol 208:271–280CrossRef

Gordon DM (2003) The organization of work in social insect colonies. Complexity 8(1):43–46CrossRef

Grassé PP (1959) La reconstruction du nid et les coordinations interindividuelles chez bellicositermes natalensis et cubitermes sp La theorie de la stigmergie: essai d’interpretation du comportament des termites constructeurs. Insects Sociaux 6:41–81CrossRef

Hauser MD (1992) Costs of deception: cheaters are punished in rhesus monkeys (Macaca mulatta). Proc Natl Acad Sci USA 89:12137–12139 CrossRef

Hill S, Burrows MT, Hughes RN (2000) Increased turning per unit distance as an area-restricted search mechanism in a pause-travel predator, juvenile plaice, foraging for buried bivalves. J Fish Biol 56:1497–1508CrossRef

Holland JH (1962) Outline for a logical theory of adaptive systems. J Assoc Comput Mach 3:297–314

Holland JH (1975) Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbour

Holland OE, Melhuish C (1999) Stigmergy, self-organization, and sorting in collective robots. Artif Life 5:(2) 173–202

Iwasa Y, Higashi M, Yamamura N (1981) Prey distribution as a factor determining the choice of optimal foraging strategy. Am Nat 117:710–723CrossRefMathSciNet

Kennedy J, Eberhart RC (1995) Particle swarm optimization. In: Proceedings on IEEE international conference neural networks, Piscataway, NJ, pp 1942–1948

Koza J (1992) Genetic programming: on the programming of computers by means of natural selection. MIT Press, Cambridge, MAMATH

Krakauer DC, Rodríguez-Gironés MA (1995) Searching and learning in a random environment. J Theor Biol 177:417–419CrossRef

Marchand D, McNeil JN (2004) The importance of behavioural plasticity for maximizing foraging efficiency in Frugivorous Lepidopteran Larvae. J Insect Behav 17:5CrossRef

Marthaler D, Bertozzi A, Schwartz I (2004) Lévy searches based on a priori information: the biased Lévy walk. UCLA CAM Report, (04–50), 2004

Maschwitz U, Steghaus-Kovac S, Gaube R, Hänel H (1989). A South East Asian ponerine ant of the genus Leptogenys (Hym.,Form.) with army ant life habits. Behav Ecol Sociobiol 24:305–316 CrossRef

Maynard Smith J (1982) Evolution and the theory of games. Cambridge University Press, Cambridge

Menzel R, Brandt R, Gumbert A, Komischke B, Kunze J (2000) Two spatial memories for honeybee navigation. Proc Royal Soc Lond B Biol Sci 267, 961–968

Merkle T, Rost M, Alt W (2006) Egocentric path integration models and their application to desert arthropods. J Theor Biol 240:385–399CrossRefMathSciNet

Minsky M (1986) The society of mind. Simon and Schuster, New York

Mittelstaedt H (2000) Triple-loop model of path control by head direction and place cells. Biol Cybern 83:261–270CrossRef

Monmarche N, Venturini G, Slimane M (2000) On how Pachycondyla apicalis ants suggest a new search algorithm. Future Gener Comp Syst 16:937–946CrossRef

Morrison ML, With KA, Timossi IC. Milne KA (1987) Composition and temporal variation of flocks in the Sierra Nevada. The Condor 89:739–1450 (The Cooper Ornithological Society)CrossRef

Motro U, Shmida A (1995) Near-far search–an evolutionary stable search strategy. J Theor Biol 173:15–22CrossRef

Müller M, Wehner R (1994) The hidden spiral: systematic search and path integration in desert ants, Cataglyphis fortis. J Compar Physiol A: Neuroethol, Sensory, Neural, Behav Physiol. 175(5)

Nishimura K (1999) Exploration of optimal giving-up time in uncertain environment: a sit-and-wait forager. J Theor Biol 199:321–327CrossRef

O’Brien JW, Browman HI, Evans BI (1990) Search strategies of foraging animals. Am Scient 78:152–160

Papaj DR, Rausher MD (1983) Individual variation in host location by phytophagous insects. In: Ahmad S (ed) Herbivorous Insects, Host-Seeking Behavior and Mechanisms. pp 77–124

Passino KM (2002) Biomimicry of bacterial foraging for distributed optimisation and control. IEEE Cont Syst Magazine, June 2002, pp 52 –67

Pianka ER (1966) Convexity, desert lizards, and spatial heterogeneity. Ecology 47:1055–1059CrossRef

Pyke GH (1978) Optimal foraging: movement patterns of bumblebees between inflorescences. Theor Popul Biol 13:72–98CrossRef

Ramos-Fernández G, Mateos JL, Miramontes O, Cocho G, Larralde H, Ayala-Orozco B (2004) Lévy walk patterns in the foraging movements of spider monkeys (Ateles geoffroyi). Behav Ecol Sociobiol 55:223CrossRef

Rechenberg I (1965) Cybernetic solution path of an experimental problem. Royal Aircraft Establishment, Library Translation No. 1122

Reed HC, Landolt PJ (2000) Application of alarm pheromone to targets by southern yellowjackets (Hymenoptera: Vespidae). Fla Entomol 83(2):193–196CrossRef

Sandia National Laboratories (2001) Developing technologies for asymmetrical warfare and homeland defense. Sandia Technology vol 3, no 2. Sandia National Laboratories. Albuquerque, USA

Secor SM (1994) Ecological significance of movements and activity range for the sidewinder, Crotalus cerastes. Copeia 1994(3):631–645CrossRef

Schmickl T, Crailsheim K (2006) Trophallaxis among swarm-robots: a biologically inspired strategy for swarm robotics. BioRob 2006, The First IEEE/RAS-EMBS International Conference on Biomedical Robotics and Biomechatronics, 2006. February 20–22, 2006, pp 377–382

Skutelsky O (1995) Flexibility in foraging tactics of Buthus Occitanus scorpions as a response to above-ground activity of termites. J Arachnol 23:46–47

Stahl JC, Sagar PM (2000) Foraging strategies if southern Buller’s albatrosses Diomedea b. bulleri breeding on The Snares, New Zealand. J Royal Soc NZ 30(3):299–318

Steinmetz I, Schmolz E, Ruther J (2003) Cuticular lipids as trail pheromone in a social wasp. Proc Royal Soc London B 270:385–291CrossRef

Stevens JR, Cushman FA, Hauser MD (2005) Evolving the psychological mechanisms for cooperation. Annu Rev Ecol Evol Syst 36:499–518CrossRef

Viswanathan GM, Buldyrev SV, Havlin S, Da Luz MGE, Raposo EP, Stanley HE (1999) Optimizing the success of random searches. Nature 401:911–914CrossRef

Viswanathan GM, Afanasyev V, Buldyrev SV, Havlin S, da Luz MGE, Raposo EP, Stanley HE (2001) Lévy flights search patterns of biological organisms. Physica A 295:85–88CrossRefMATH

Viswanathan GM, Bartumeus F, Buldyrev SV, Catalan J, Fulco UL, Havlin S, da Luz MGE, Lyra ML, Raposo EP, Stanley HE (2002) Lévy flight random searches in biological phenomena. Physica A 314:208–213CrossRefMathSciNetMATH

Von Frisch K (1967) The dance language and orientation of bees. Harvard University Press. Cambridge, Massachusetts, USA

Vladusich T, Hemmi JM, Zeil J (2006) Honeybee odometry and scent guidance. J Exp Biol 209:1367–1375CrossRef

Waddington KD (1980) Flight patterns of foraging bees relative to density of artificial flowers and distribution of nectar. Oecologia (Berl) 44:199–204CrossRef

Waibel M, Floreano D, Magnenat S, Keller L (2006) Division of labour and colony efficiency in social insects: effects of interactions between genetic architecture, colony kin structure and rate of perturbations. Proc Royal Soc B 273, 1815–1823

Ward P, Zahavi A (1973) The importance of certain assemblages of birds as ‘information centres’ for food finding. Ibis 117:517–534CrossRef

Wiess MR, Papaj DR (2003) Colour learning in two behavioural contexts: how much can a butterfly keep in mind? Anim Behav 65:425–434CrossRef

Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1(1):67–82CrossRef

Wright J, Stone RE, Brown N (2003) Communal roosts as structured information centres in the raven, Corvus corax. J Anim Ecol 72:1003–1014CrossRef

Zamon JE (2001) Seal predation on salmon and forage fish schools as a function of tidal currents in the San Juan Islands, Washington, USA. Fish Oceanogr 10(4):353–366CrossRef

Titel: Natural strategies for search
verfasst von: Alec Banks
Jonathan Vincent
Keith Phalp
Publikationsdatum: 01.09.2009
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2009
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-008-9087-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2009

Foundations of r-contiguous matching in negative selection for anomaly detection

A new problem for rule following

Abstract geometrical computation 3: black holes for classical and analog computing

General relativistic hypercomputing and foundation of mathematics

Information processing with structured excitable medium

On the solution of trivalent decision problems by quantum state identification

Premium Partner