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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Biology of the Physarum polycephalum Plasmodium: Preliminaries for Unconventional Computing Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Slime Mould Inspired Applications on Graph-Optimization Problems

verfasst von : Xiaoge Zhang, Cai Gao, Yong Deng, Zili Zhang

Erschienen in: Advances in Physarum Machines

Verlag: Springer International Publishing

Einloggen

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

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.

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 Physarum Learner: A Slime Mold Inspired Structural Learning Approach
Nächstes Kapitel Cellular Automata Models Simulating Slime Mould Computing
Literatur
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.
Bonifaci, V., Mehlhorn, K., Varma, G.: Physarum can compute shortest paths. J. Theor. Biol. 309, 121–133 (2012)MathSciNetCrossRef
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.
Rescigno, A.: Optimally balanced spanning tree of the star network. IEEE Trans. Comput. 50(1), 88–91 (2001)MathSciNetCrossRef
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.
Warburton, A.: Approximation of pareto optima in multiple-objective, shortest-path problems. Oper. Res. 35(1), 70–79 (1987)MathSciNetCrossRefMATH
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
Metadaten
Titel
Slime Mould Inspired Applications on Graph-Optimization Problems
verfasst von
Xiaoge Zhang
Cai Gao
Yong Deng
Zili Zhang
Copyright-Jahr
2016
Buch
Advances in Physarum Machines

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

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

Copyright-Jahr: 2016

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

Premium Partner

    Bildnachweise