An anticipation mechanism for the shortest path problem based on Physarum polycephalum. (English) Zbl 1337.90075
Summary: In this paper, we put forward an anticipation mechanism for the existing Physarum-inspired shortest path finding method. The Physarum-based shortest path finding model can be implemented by an iterative algorithm and has wide applications in many fundamental network optimization problems. In this paper, we mainly focus on the Physarum-inspired shortest path tree model. Normally, we stop the program when the difference between two consecutive iterations is less than a predefined threshold. However, we do not know how to set the specific value for the threshold variable. In order to find out the optimal solution, we need to set the threshold as a very small number. This in turn will consume a lot of time. From this point of view, this algorithm lacks an efficient and reliable mechanism to judge when the optimal solution will be found. In this paper, we introduce an anticipation mechanism to address this issue. Numerical examples are used to demonstrate its reliability and efficiency.
MSC:
| 90C35 | Programming involving graphs or networks |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
| 92C80 | Plant biology |
References:
| [1] | DOI: 10.1007/s00114-007-0276-5 · doi:10.1007/s00114-007-0276-5 |
| [2] | Adamatzky Andrew, Physarum Machines: Computers from Slime Mould 74 (2010) · doi:10.1142/7968 |
| [3] | DOI: 10.1142/8482 · doi:10.1142/8482 |
| [4] | DOI: 10.1109/TNB.2011.2181978 · doi:10.1109/TNB.2011.2181978 |
| [5] | DOI: 10.1142/S0218127410027568 · doi:10.1142/S0218127410027568 |
| [6] | DOI: 10.1108/03684921111169440 · doi:10.1108/03684921111169440 |
| [7] | DOI: 10.1080/03081079.2013.776206 · Zbl 1286.93002 · doi:10.1080/03081079.2013.776206 |
| [8] | DOI: 10.1142/S0219525912500348 · doi:10.1142/S0219525912500348 |
| [9] | DOI: 10.1007/s11047-011-9255-z · doi:10.1007/s11047-011-9255-z |
| [10] | DOI: 10.1073/pnas.1305049110 · doi:10.1073/pnas.1305049110 |
| [11] | DOI: 10.1016/j.jtbi.2012.06.017 · doi:10.1016/j.jtbi.2012.06.017 |
| [12] | DOI: 10.1016/j.ins.2010.02.022 · doi:10.1016/j.ins.2010.02.022 |
| [13] | DOI: 10.1109/TIA.2008.2002171 · doi:10.1109/TIA.2008.2002171 |
| [14] | DOI: 10.1371/journal.pone.0066732 · doi:10.1371/journal.pone.0066732 |
| [15] | DOI: 10.1080/0305215X.2013.772603 · doi:10.1080/0305215X.2013.772603 |
| [16] | DOI: 10.1007/978-4-431-54394-7_2 · doi:10.1007/978-4-431-54394-7_2 |
| [17] | DOI: 10.1103/PhysRevLett.99.068104 · doi:10.1103/PhysRevLett.99.068104 |
| [18] | DOI: 10.1038/35035159 · doi:10.1038/35035159 |
| [19] | DOI: 10.1016/S0301-4622(01)00179-X · doi:10.1016/S0301-4622(01)00179-X |
| [20] | DOI: 10.1016/j.eswa.2014.03.002 · doi:10.1016/j.eswa.2014.03.002 |
| [21] | DOI: 10.1080/03081079.2012.695902 · Zbl 1277.68154 · doi:10.1080/03081079.2012.695902 |
| [22] | DOI: 10.1016/j.jtbi.2006.07.015 · doi:10.1016/j.jtbi.2006.07.015 |
| [23] | DOI: 10.1126/science.1177894 · Zbl 1226.90021 · doi:10.1126/science.1177894 |
| [24] | DOI: 10.1371/journal.pone.0089231 · doi:10.1371/journal.pone.0089231 |
| [25] | Yang Xin-She, Amir Hossein Gandomi, and Mehmet Karamanoglu (2013) |
| [26] | DOI: 10.1080/00207543.2013.793425 · doi:10.1080/00207543.2013.793425 |
| [27] | DOI: 10.1016/j.eswa.2013.07.054 · doi:10.1016/j.eswa.2013.07.054 |
| [28] | DOI: 10.1016/j.ssci.2012.12.003 · doi:10.1016/j.ssci.2012.12.003 |
| [29] | Zhang Xiaoge, IJUC 10 (1) pp 143– (2014) |
| [30] | DOI: 10.1016/j.asoc.2014.05.032 · doi:10.1016/j.asoc.2014.05.032 |
| [31] | DOI: 10.1088/1748-3182/9/3/036006 · doi:10.1088/1748-3182/9/3/036006 |
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.
