Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Biology of the Physarum polycephalum Plasmodium: Preliminaries for Unconventional Computing Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Slime Mould Inspired Applications on Graph-Optimization Problems

Authors : Xiaoge Zhang, Cai Gao, Yong Deng, Zili Zhang

Published in: Advances in Physarum Machines

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Since the appearance of slime mould-inspired network design applications, it has attracted the attention of many researchers from all over the world. In this chapter, we provide an overview of a variety of slime mould-inspired applications on graph-optimization problems. We will focus more on the mathematical model inspired by slime mould, develop a novel Energy Propagation model, and also covers its applications to many graph optimization problems. Some examples of such applications include Shortest Path Tree Problem (SPT), Supply Chain Network Design (SCNP), Maze Problem and Multi-source Multi-sink Minimum Cost Flow Problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Physarum Learner: A Slime Mold Inspired Structural Learning Approach
next chapter Cellular Automata Models Simulating Slime Mould Computing
Literature
1.
Adamatzky, A.: Growing spanning trees in plasmodium machines. Kybernetes 37(2), 258–264 (2008)
2.
Adamatzky, A.: Physarum Machines: Computers from Slime Mould, vol. 74. World Scientific (2010)
3.
Adamatzky, A.: Bioevaluation of World Transport Networks. World Scientific (2012)
4.
Adamatzky, A.: The world’s colonization and trade routes formation as imitated by slime mould. Int. J. Bifurcat. Chaos 22(08) (2012)
5.
Adamatzky, A.: Slime mould computes planar shapes. Int. J. Bio-Inspired Comput. 4(3), 149–154 (2012)CrossRef
6.
Adamatzky, A., Alonso-Sanz, R.: Rebuilding Iberian motorways with slime mould. Biosystems 105(1), 89–100 (2011)CrossRef
7.
Adamatzky, A., Martínez, G.J., Chapa-Vergara, S.V., Asomoza-Palacio, R., Stephens, C.R.: Approximating Mexican highways with slime mould. Nat. Comput. 10(3), 1195–1214 (2011)MathSciNetCrossRef
8.
Adamatzky, A., Schubert, T.: Slime mold microfluidic logical gates. Mater. Today 17(2), 86–91 (2014)CrossRef
9.
Adamatzky, A., Yang, X.-S., Zhao, Y.-X.: Slime mould imitates transport networks in China. Int. J. Intell. Comput. Cybern. 6(3), 232–251 (2013)MathSciNetCrossRef
10.
Adamatzky, A.I.: Route 20, autobahn 7, and slime mold: approximating the longest roads in USA and Germany with slime mold on 3-D terrains. IEEE Trans. Cybern. 44(1), 126–136 (2014)CrossRef
11.
Aono, M., Hara, M., Aihara, K.: Amoeba-based neurocomputing with chaotic dynamics. Commun. ACM 50(9), 69–72 (2007)CrossRef
12.
Aono, M., Zhu, L., Hara, M.: Amoeba-based neurocomputing for 8-city traveling salesman problem. Int. J. Unconventional Comput. 7(6), 463–480 (2011)
13.
Bauer, R., Wagner, D.: Batch dynamic single-source shortest-path algorithms: an experimental study. In: Vahrenhold, J. (ed.) SEA 2009. LNCS, vol. 5526, pp. 51–62. Springer, Heidelberg (2009)
14.
Bauer, F., Varma, A.: Distributed algorithms for multicast path setup in data networks. IEEE/ACM Trans. Networking (TON) 4(2), 181–191 (1996)CrossRef
15.
Baumgarten, W., Ueda, T., Hauser, M.J.: Plasmodial vein networks of the slime mold physarum polycephalum form regular graphs. Phys. Rev. E 82(4), 046113 (2010)CrossRef
16.
Becker, M.: Design of fault tolerant networks with agent-based simulation of physarum polycephalum. In: 2011 IEEE Congress on Evolutionary Computation (CEC), pp. 285–291. IEEE (2011)
17.
Bell, M.G., Iida, Y.: Transportation Network Analysis (1997)
18.
Bingfeng, S., Ziyou, G.: Modeling Network Flow and System Optimization for Traffic and Transportation System (in Chinese). China Communications Press (2013)
19.
Bi, Z., Zhang, W.: Flexible fixture design and automation: review, issues and future directions. Int. J. Prod. Res. 39(13), 2867–2894 (2001)CrossRef
20.
21.
Bu, D., Zhao, Y., Cai, L., Xue, H., Zhu, X.E.A.: Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Res. 31(9), 2443–2450 (2003)
22.
23.
Chen, H., Tseng, P.: A low complexity shortest path tree restoration scheme for IP networks. IEEE Commun. Lett. 14(6), 566–568 (2010)CrossRef
24.
Deng, Y., Chen, Y., Zhang, Y., Mahadevan, S.: Fuzzy dijkstra algorithm for shortest path problem under uncertain environment. Appl. Soft Comput. 12(3), 1231–1237 (2012)CrossRef
25.
26.
Dreyfus, S.E.: An appraisal of some shortest-path algorithms. Oper. Res. 17(3), 395–412 (1969)CrossRefMATH
27.
Ernst, A.T., Horn, M., Kilby, P., Krishnamoorthy, M.: Dynamic scheduling of recreational rental vehicles with revenue management extensions. J. Oper. Res. Soc. 61(7), 1133–1143 (2010)CrossRefMATH
28.
Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Incremental algorithms for the single-source shortest path problem. Found. Softw. Technol. Theoret. Comput. Sci. 113–124 (1994)
29.
Gao, C., Lan, X., Zhang, X., Deng, Y.: A bio-inspired methodology of identifying influential nodes in complex networks. PloS ONE 8(6), e66732 (2013)CrossRef
30.
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002)MathSciNetCrossRefMATH
31.
Glover, F., Klingman, D.D., Phillips, N.V., Schneider, R.F.: New polynomial shortest path algorithms and their computational attributes. Manage. Sci. 31(9), 1106–1128 (1985)MathSciNetCrossRefMATH
32.
Guimera, R., Danon, L., Diaz-Guilera, A., Giralt, F., Arenas, A.: Self-similar community structure in a network of human interactions. Phys. Rev. E 68(6), 065103 (2003)CrossRef
33.
Gunji, Y.-P., Shirakawa, T., Niizato, T., Yamachiyo, M., Tani, I.: An adaptive and robust biological network based on the vacant-particle transportation model. J. Theor. Biol. 272(1), 187–200 (2011)CrossRef
34.
Hale, T.S., Huq, F., Hipkin, I., Tucker, C.: A methodology for estimating expected distances between nodes on a network. J. Oper. Res. Soc. 64(3), 439–445 (2012)CrossRef
35.
Houbraken, M., Demeyer, S., Staessens, D., Audenaert, P., Colle, D., Pickavet, M.: Fault tolerant network design inspired by physarum polycephalum. Nat. Comput. 12(2), 277–289 (2013)MathSciNetCrossRef
36.
Huang, H.-J., Lam, W.H.: Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues. Transp. Res. Part B: Methodol. 36(3), 253–273 (2002)CrossRef
37.
Huynh, V.-N., Nakamori, Y.: A satisfactory-oriented approach to multiexpert decision-making with linguistic assessments. IEEE Trans. Syst. Man Cybern. Part B: Cybern. 35(2), 184–196 (2005)CrossRef
38.
39.
Jones, J., Adamatzky, A.: Material approximation of data smoothing and spline curves inspired by slime mould. Bioinspiration Biomimetics (2014)
40.
Jones, J., Adamatzky, A.: Computation of the travelling salesman problem by a shrinking blob. Nat. Comput. 13(1), 1–16 (2014)MathSciNetCrossRef
41.
Kasai, S., Aono, M., Naruse, M.: Amoeba-inspired computing architecture implemented using charge dynamics in parallel capacitance network. Appl. Phys. Lett. 103(16), 163703 (2013)CrossRef
42.
Laporte, G.: A concise guide to the traveling salesman problem. J. Oper. Res. Soc. 61(1), 35–40 (2010)CrossRefMATH
43.
Liu, H.X., He, X., He, B.: Method of successive weighted averages (mswa) and self-regulated averaging schemes for solving stochastic user equilibrium problem. Netw. Spat. Econ. 9(4), 485–503 (2009)MathSciNetCrossRefMATH
44.
Liu, L., Song, Y., Zhang, H., Ma, H., Vasilakos, A.: Physarum optimization: a biology-inspired algorithm for the Steiner tree problem in networks. IEEE Trans. Comput. (2013). doi:10.​1109/​TC.​2013.​229
45.
Masi, L., Vasile, M.: A multi-directional modified physarum solver for discrete decision making. In: Bioinspired Optimization Methods and their Applications. BIOMA 2012 (2012)
46.
Masi, L., Vasile, M.: Optimal multi-objective discrete decision making using a multidirectional modified Physarum Solver. In: EVOLVE 2012 International Conference, 2012
47.
Miranda-Moreno, L.F., Nosal, T.: Weather or not to cycle. Transp. Res. Rec.: J. Transp. Res. Board 2247(1), 42–52 (2011)CrossRef
48.
Misra, S., Oommen, B.J.: Dynamic algorithms for the shortest path routing problem: learning automata-based solutions. IEEE Trans. Syst. Man Cybern. Part B: Cybern. 35(6), 1179–1192 (2005)CrossRef
49.
Miyaji, T., Ohnishi, I.: Physarum can solve the shortest path problem on riemannian surface mathematically rigorously. Int. J. Pure Appl. Math. 47(3), 353–369 (2008)MathSciNetMATH
50.
Murthy, I., Sarkar, S.: Stochastic shortest path problems with piecewise-linear concave utility functions. Manage. Sci. 44(11-Part-2), S125–S136 (1998)
51.
Nagurney, A.: Supply chain network economics: dynamics of prices, flows and profits. Edward Elgar Publishing (2006)
52.
Nagurney, A.: A system-optimization perspective for supply chain network integration: the horizontal merger case. Transp. Res. Part E: Logistics Transp. Rev. 45(1), 1–15 (2009)CrossRef
53.
Nagurney, A., Nagurney, L.S.: Sustainable supply chain network design: a multicriteria perspective. Int. J. Sustain. Eng. 3(3), 189–197 (2010)CrossRefMATH
54.
Nagurney, A., Woolley, T.: Environmental and cost synergy in supply chain network integration in mergers and acquisitions. In: Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems, pp. 57–78. Springer, 2010
55.
Nagurney, A., Dong, J., Zhang, D.: A supply chain network equilibrium model. Transp. Res. Part E: Logistics Transp. Rev. 38(5), 281–303 (2002)CrossRef
56.
Nakagaki, T., Yamada, H., Tóth, Á.: Intelligence: Maze-solving by an amoeboid organism. Nature 407(6803), 470–470 (2000)CrossRef
57.
Nakagaki, T., Yamada, H., Toth, A.: Path finding by tube morphogenesis in an amoeboid organism. Biophys. Chem. 92(1), 47–52 (2001)CrossRef
58.
Nakagaki, T., Iima, M., Ueda, T., Nishiura, Y., Saigusa, T., Tero, A., Kobayashi, R., Showalter, K.: Minimum-risk path finding by an adaptive amoebal network. Phys. Rev. Lett. 99(6), 68104 (2007)CrossRef
59.
Narváez, P., Siu, K., Tzeng, H.: New dynamic SPT algorithm based on a ball-and-string model. IEEE/ACM Trans. Networking 9(6), 706–718 (2001)CrossRef
60.
Newman, M.E.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3), 036104 (2006)MathSciNetCrossRef
61.
Nguyen, S., Pallottino, S., Scutella, M.G.: A new dual algorithm for shortest path reoptimization. Transportation and Network Analysis: Current Trends: Miscellanea in honor ofMichael Florian, vol. 63, 221 (2002)
62.
Perlman, R.: A comparison between two routing protocols: OSPF and IS-IS. IEEE Netw. 5(5), 18–24 (1991)CrossRef
63.
64.
65.
Royset, J.O., Carlyle, W.M., Wood, R.K.: Routing military aircraft with a constrained shortest-path algorithm. Mil. Oper. Res. 14(3), 31–52 (2009)CrossRef
66.
Sharma, N., Arkatkar, S.S., Sarkar, A.K.: Study on heterogeneous traffic flow characteristics of a two-lane road. Transport 26(2), 185–196 (2011)CrossRef
67.
Shirakawa, T., Adamatzky, A., Gunji, Y.-P., Miyake, Y.: On simultaneous construction of Voronoi diagram and Delaunay triangulation by Physarum polycephalum. Int. J. Bifurcat. Chaos 19(09), 3109–3117 (2009)CrossRef
68.
Stephenson, S.L., Stempen, H., Hall, I.: Myxomycetes: A Handbook of Slime Molds. Timber Press Portland, Oregon (1994)
69.
Taleizadeh, A.A., Niaki, S.T.A., Wee, H.-M.: Joint single vendor-single buyer supply chain problem with stochastic demand and fuzzy lead-time. Knowl.-Based Syst. 48, 1–9 (2013)CrossRef
70.
Tero, A., Kobayashi, R., Nakagaki, T.: Physarum solver: a biologically inspired method of road-network navigation. Phys. A 363(1), 115–119 (2006)CrossRef
71.
Tero, A., Kobayashi, R., Nakagaki, T.: A mathematical model for adaptive transport network in path finding by true slime mold. J. Theor. Biol. 244(4), 553–564 (2007)MathSciNetCrossRef
72.
Tero, A., Takagi, S., Saigusa, T., Ito, K., Bebber, D.P., Fricker, M.D., Yumiki, K., Kobayashi, R., Nakagaki, T.: Rules for biologically inspired adaptive network design. Science 327(5964), 439–442 (2010)MathSciNetCrossRefMATH
73.
Tsompanas, M., Sirakoulis, G., Adamatzky, A.: Evolving transport networks with cellular automata models inspired by slime mould. IEEE Trans. Cybern. (2013)
74.
Tsuda, S., Aono, M., Gunji, Y.-P.: Robust and emergent physarum logical-computing. Biosystems 73(1), 45–55 (2004)CrossRef
75.
Verter, V., Kara, B.Y.: A path-based approach for hazmat transport network design. Manage. Sci. 54(1), 29–40 (2008)CrossRef
76.
77.
Watanabe, S., Tero, A., Takamatsu, A., Nakagaki, T.: Traffic optimization in railroad networks using an algorithm mimicking an amoeba-like organism, Physarum plasmodium. BioSystems 105(3), 225–232 (2011)CrossRef
78.
Watts, D.J., Strogatz, S.H.: Collective dynamics of small-worldnetworks. Nature 393(6684), 440–442 (1998)CrossRef
79.
Whiting, J.G., de Lacy Costello, B.P., Adamatzky, A.: Slime mould logic gates based on frequency changes of electrical potential oscillation. Biosystems 124, 21–25 (2014)
80.
Willms, A.R., Yang, S.X.: An efficient dynamic system for real-time robot-path planning. IEEE Trans. Syst. Man Cybern. Part B: Cybern. 36(4), 755–766 (2006)CrossRef
81.
Wu, K., Nagurney, A., Liu, Z., Stranlund, J.K.: Modeling generator power plant portfolios and pollution taxes in electric power supply chain networks: A transportation network equilibrium transformation. Transp. Res. Part D: Transp. Environ. 11(3), 171–190 (2006)CrossRef
82.
Xiao, T., Yu, G., Sheng, Z., Xia, Y.: Coordination of a supply chain with one-manufacturer and two-retailers under demand promotion and disruption management decisions. Ann. Oper. Res. 135(1), 87–109 (2005)MathSciNetCrossRefMATH
83.
Xu, Y., Qu, R.: Solving multi-objective multicast routing problems by evolutionary multi-objective simulated annealing algorithms with variable neighbourhoods. J. Oper. Res. Soc. 62(2), 313–325 (2011)CrossRef
84.
Zachary, W.: An information flow modelfor conflict and fission in small groups1. J. Anthropol. Res. 33(4), 452–473 (1977)CrossRef
85.
Zhang, X., Liu, Q., Hu, Y., Chan, F.T., Mahadevan, S., Zhang, Z., Deng, Y.: An adaptive amoeba algorithm for shortest path tree computation in dynamic graphs (2013). arXiv:​1311.​0460
86.
Zhang, X., Huang, S., Hu, Y., Zhang, Y., Mahadevan, S., Deng, Y.: Solving 0–1 knapsack problems based on amoeboid organism algorithm. Appl. Math. Comput. 219(19), 9959–9970 (2013)MathSciNetMATH
87.
Zhang, X., Zhang, Y., Zhang, Z., Mahadevan, S., Adamatzky, A., Deng, Y.: Rapid Physarum algorithm for shortest path problem. Appl. Soft Comput. 23, 19–26 (2014)CrossRef
88.
89.
Zhang, X., Adamatzky, A., Yang, X.-S., Yang, H., Mahadevan, S., Deng, Y.: A Physarum-inspired approach to optimal supply chain network design at minimum total cost with demand satisfaction (2014). arXiv:​1403.​5345
90.
Zhao, M., Yang, Y.: Bounded relay hop mobile data gathering in wireless sensor networks. IEEE Trans. Comput. 61(2), 265–277 (2012)MathSciNetCrossRefMATH
91.
Ziyou, G., Yifan, S.: A reserve capacity model of optimal signal control with user-equilibrium route choice. Transp. Res. Part B: Methodol. 36(4), 313–323 (2002)CrossRef
Metadata
Title
Slime Mould Inspired Applications on Graph-Optimization Problems
Authors
Xiaoge Zhang
Cai Gao
Yong Deng
Zili Zhang
Copyright Year
2016
Book
Advances in Physarum Machines

Print ISBN: 978-3-319-26661-9

Electronic ISBN: 978-3-319-26662-6

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-26662-6_26

Premium Partner

    Image Credits