Abstract
Physarum polycephalum (true slime mold) has recently emerged as a fascinating example of biological computation through morphogenesis. Despite being a single cell organism, experiments have observed that through its growth process, the Physarum is able to solve various minimum cost flow problems. This paper analyzes a mathematical model of the Physarum growth dynamics. We show how to encode general linear programming (LP) problems as instances of the Physarum. We prove that under the growth dynamics, the Physarum is guaranteed to converge to the optimal solution of the LP. We further derive an efficient discrete algorithm based on the Physarum model, and experimentally verify its performance on assignment problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Chazelle, B.: Natural Algorithms. In: Proceedings of the 20th Symposium of Discrete Algorithms (2009)
Sumpter, D.: Collective Animal Behavior. Princeton University Press (2010)
Camazine, S., Deneubourg, J., Franks, N., Sneyd, J., Theraulaz, G., Bonabeau, E.: Self-Organization in Biological Systems. Princeton University Press (2003)
Tero, A., Takagi, S., Saigusa, T., Ito, K., Bebber, D., Fricker, M., Yumiki, K., Kobayashi, R., Nakagaki, T.: Rules for biological inspired adaptive network design. Science 327(5964), 439–442 (2010)
Nakagaki, T., Yamada, H., Toth, A.: Maze-solving by an amoeboid organism. Nature 407, 470 (2000)
Nakagaki, T., Tero, A., Kobayashi, R.: A mathematical model for adaptive transport network in path finding by true slime mold. Journal of Theoretical Biology 244(4), 553–564 (2007)
Miyaji, T., Ohnishi, I.: Physarum can solve the shortest path problem on Riemannian surface mathematically rigorously. International Journal of Pure and Applied Mathematics 47(3), 353–369 (2008)
Ito, K., Johansson, A., Nakagaki, T., Tero, A.: Convergence properties for the Physarum solver. arXiv:1101.5249v1 (2011)
Bonifaci, V., Mehlhorn, K., Varma, G.: Physarum can compute shortest paths. In: Proceedings of the 23th Symposium of Discrete Algorithms (2012)
Bertsimas, D., Tsitsiklis, J.: Introduction to Linear Optimization. Athena Scientific (1997)
Christiano, P., Kelner, J., Madry, A., Spielman, D., Teng, S.: Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Johannson, A., Zou, J. (2012). A Slime Mold Solver for Linear Programming Problems. In: Cooper, S.B., Dawar, A., Löwe, B. (eds) How the World Computes. CiE 2012. Lecture Notes in Computer Science, vol 7318. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30870-3_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-30870-3_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30869-7
Online ISBN: 978-3-642-30870-3
eBook Packages: Computer ScienceComputer Science (R0)