×

Biomimicry of social foraging bacteria for distributed optimization: Models, principles, and emergent behaviors. (English) Zbl 1031.92038

Summary: We explain the social foraging behavior of E. coli and M. xanthus bacteria and develop simulation models based on the principles of foraging theory that view foraging as optimization. This provides us with novel models of their foraging behavior and with new methods for distributed nongradient optimization. Moreover, we show that the models of both species of bacteria exhibit the property identified by Grunbaum that postulates that their foraging is social in order to be able to climb noisy gradients in nutrients. This provides a connection between evolutionary forces in social foraging and distributed nongradient optimization algorithm designs for global optimization over noisy surfaces.

MSC:

92D50 Animal behavior
90C90 Applications of mathematical programming
92D15 Problems related to evolution

Software:

avida
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] STEPHENS, D. W., and KREBS, J. R., Foraging Theory, Princeton University Press, Princeton, New Jersey, 1986.
[2] ALCOCK, J., Animal Behavior: An Evolutionary Approach, Sinauer Associates, Sunderland, Massachusetts, 1998.
[3] BELL, W. J., Searching Behavior: The Behavioral Ecology of Finding Resources, Chapman and Hall, London, England, 1991.
[4] GRUNBAUM, D., Schooling as a Strategy for Taxis in a Noisy Environment, Evolutionary Ecology, Vol. 12, pp. 503–522, 1998. · doi:10.1023/A:1006574607845
[5] BONABEAU, E., DORIGO, M., and THERAULAZ, G., Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, New York, NY, 1999. · Zbl 1003.68123
[6] ADAMI, C., Introduction to Artificial Life, Springer Verlag, New York, NY, 1998. · Zbl 0902.68198
[7] RESNICK, M., Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds, MIT Press, Cambridge, Massachusetts, 1994.
[8] LEVY, S., Artificial Life: A Report from the Frontier where Computers Meet Biology, Vintage Books, New York, NY, 1992.
[9] ARIN, S., DENEUBOURG, J. L., GOSS, S., and PASTEELS, J. M., Functional Self-Organization Illustrated by Interest Traffic in Ants: The Case of the Argentine Ant, Biological Motion, Lecture Notes in Biomathematics, Edited by W. Alt and G. Hoffmann, Springer Verlag, Berlin, Germany, Vol. 89, pp. 533–547, 1990.
[10] PARRISH, J. K., and HAMNER, W. M., Editors, Animal Groups in Three Dimensions, Cambridge University Press, Cambridge, England, 1997.
[11] CAMAZINE, S., et al., Self-Organization in Biological Systems, Princeton University Press, Princeton, New Jersey, 2001.
[12] PASSINO, K. M., Biomimicry of Bacterial Foraging for Distributed Optimization and Control, IEEE Control Systems Magazine, 2002 (to appear). · Zbl 1031.92038
[13] STEVENS, A., Simulations of the Gliding Behavior and Aggregation of Myxobacteria, Biological Motion, Lecture Notes in Biomathematics, Edited by W. Alt and G. Hoffmann, Springer Verlag, Berlin, Germany, Vol. 89, pp. 548–555, 1990.
[14] STEVENS, A., A Stochastic Cellular Automaton, Modeling Gliding and Aggregation of Myxobacteria, SIAM Journal on Applied Mathematics, Vol. 61, pp. 172–182, 2000. · Zbl 0992.92005 · doi:10.1137/S0036139998342053
[15] MADIGAN, M. T., MARTINKO, J. M., and PARKER, J., Biology of Microorganisms, 8th Edition, Prentice Hall, Upper Saddle River, New Jersey, 1997.
[16] NEIDHARDT, F. C., INGRAHAM, J. L., and SCHAECHTER, M., Physiology of the Bacterial Cell: A Molecular Approach, Sinauer Associates, Sunderland, Massachusetts, 1990.
[17] ALBERTS, B., BRAY, D., LEWIS, J., RAFF, M., ROBERTS, K., and WATSON, J. D., Molecular Biology of the Cell, 2nd Edition, Garland Publishing, New York, NY, 1989.
[18] BERG, H. C., and BROWN, D. A., Chemotaxis in Escherichia coli Analyzed by Three-Dimensional Tracking, Nature, Vol. 239, pp. 500–504, 1972. · doi:10.1038/239500a0
[19] BERG, H. C., Motile Behavior of Bacteria, Physics Today, Vol. 53, pp. 24–29, 2000. · doi:10.1063/1.882934
[20] SEGALL, J. E., BLOCK, S. M., and BERG, H. C., Temporal Comparisons in Bacterial Chemotaxis, Proceedings of the National Academy of Sciences, Vol. 83, pp. 8987–8991, 1986. · doi:10.1073/pnas.83.23.8987
[21] BERG, H. C., Random Walks in Biology, New Expanded Edition, Princeton University Press, Princeton, New Jersey, 1993.
[22] BUDRENE, E. O., and BERG, H. C., Dynamics of Formation of Symmetrical Patterns by Chemotactic Bacteria, Nature, Vol. 376, pp. 49–53, 1995. · doi:10.1038/376049a0
[23] BLAT, Y., and EISENBACH, M., Tar-Dependent and-Independent Pattern Formation by Salmonella Typhimurium, Journal of Bacteriology, Vol. 177, pp. 1683–1691, 1995.
[24] BUDRENE, E. O., and BERG, H. C., Complex Patterns Formed by Motile Cells of Escherichia coli, Nature, Vol. 349, pp. 630–633, 1991. · doi:10.1038/349630a0
[25] WOODWARD, D. E., TYSON, R., MYERSCOUGH, M. R., MURRAY, J. D., BUDRENE, E. O., and BERG, H. C., Spatio-Temporal Patterns Generated by Salmonella Typhimurium, Biophysical Journal, Vol. 68, pp. 2181–2189, 1995. · doi:10.1016/S0006-3495(95)80400-5
[26] ARMITAGE, J. P., Bacterial Tactic Responses, Advances in Microbial Physiology, Vol. 41, pp. 229–290, 1999. · doi:10.1016/S0065-2911(08)60168-X
[27] SHAPIRO, J. A., Multicellularity: The Rule, Not the Exception, Bacteria as Multicellular Organisms, Edited by J. A. Shapiro and M. Dworkin, Oxford University Press, New York, NY, pp. 14–49, 1997.
[28] LOSICK, R., and KAISER, D., Why and How Bacteria Communicate, Scientific American, Vol. 276, pp. 68–73, 1997. · doi:10.1038/scientificamerican0297-68
[29] SHIMKETS, L. J., and DWORKIN, M., Myxobacterial Multicellularity, Bacteria as Multicellular Organisms, Edited by J. A. Shapiro and M. Dworkin, Oxford University Press, New York, NY, pp. 220–244, 1997.
[30] REICHENBACH, H., Biology of the Myxobacteria: Ecology and Taxonomy, Myxobacteria II, Edited by M. Dworkin and D. Kaiser, American Society for Microbiology, Washington, DC, pp. 13–62, 1993.
[31] KOCH, A. and WHITE, D., The Social Lifestyle of Myxobacteria, BioEssays, Vol. 20, pp. 1030–1038, 1998. · doi:10.1002/(SICI)1521-1878(199812)20:12<1030::AID-BIES9>3.3.CO;2-Z
[32] KOCH, A. L., The Strategy of Myxococcus xanthus for Group Cooperative Behavior, Antonie van Leeuwenhoek, Vol. 73, pp. 299–313, 1998. · doi:10.1023/A:1001554700039
[33] NAWA, N. E., and FURUHASHI, T., Fuzzy System Parameters Discovery by Bacterial Evolutionary Algorithm, IEEE Transactions on Fuzzy Systems, Vol. 5, pp. 608–616, 1999. · doi:10.1109/91.797983
[34] BERTSEKAS, D. P., Nonlinear Programming, Athena Scientific Press, Belmont, Massachusetts, 1995.
[35] LUENBERGER, D. G., Linear and Nonlinear Programming, Addison-Wesley, Reading, Massachusetts, 1984. · Zbl 0571.90051
[36] MCBRIDE, M. J., HARTZELL, P., and ZUSMAN, D. R., Motility and Tactic Behavior of Myxococcus xanthus, Myxobacteria II, Edited by M. Dworkin and D. Kaiser, American Society for Microbiology, Washington, DC, pp. 285–305, 1993.
[37] SHAPIRO, J. A., Bacteria as Multicellular Organisms, Scientific American, Vol. 258, pp. 62–69, 1988.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.