The Euclidean Steiner minimum tree
problem is a classical NP-hard combinatorial optimization problem.
Because of the intrinsic characteristic of the hard computability,
this problem cannot be solved accurately by efficient algorithms up
to now. Due to the extensive applications in real world, it is quite
important to find some heuristics for it. The stochastic diffusion
search algorithm is a newly population-based algorithm whose
operating mechanism is quite different from ordinary intelligent
algorithms, so this algorithm has its own advantage in solving some
optimization problems. This paper has carefully studied the
stochastic diffusion search algorithm and designed a cellular
automata stochastic diffusion search algorithm for the Euclidean
Steiner minimum tree problem which has low time complexity.
Practical results show that the proposed algorithm can find approving results
in short time even for the large scale size, while exact algorithms need to cost several hours.
ZHANG Jin (张 瑾), ZHAO Ya-liang (赵雅靓), MA Liang (马 良)
. Solving the Euclidean Steiner Minimum Tree Using Cellular
Stochastic Diffusion Search Algorithm[J]. Journal of Shanghai Jiaotong University(Science), 2011
, 16(6)
: 734
-741
.
DOI: 10.1007/s12204-011-1218-0
1 Gilbert E N, Pollak H O. Steiner minimal trees [J]. SIAM
Journal on Applied Mathematics, 1968, 16 (1): 1-29.
2 Maculan N, Michelon P, Xavier A E. The Euclidean
Steiner tree problem in Rn : A mathematical programming
formulation [J]. Annals of Operations Research, 2000,
96 (1-4): 209-220.
3 Du D Z, Hwang F K. The Steiner ratio conjecture of Gilbert and
Pollak is true [J]. Proceedings of the National Academy of
Sciences of the United States of America, 1990, 87 (23):
9464-9466.
4 Bishop J M, Torr P. Stochastic search network [C]//
Proceedings of the 1st IEE Conference on Artificial Neural
Networks. London, UK: IEE, 1989: 329-331.
5 de Meyer K. Foundations of stochastic diffusion search [D].
Berkshire, UK: Department of Cybernetics, University of Reading,
2004.
6 de Meyer K, Nasuto S J, Bishop M. Stochastic diffusion
search: Partial function evaluation in swarm intelligence
dynamic optimisation [C]// Stigmergic Optimization, Studies in
Computational Intelligence. Cambridge, USA: Springer-Verlag,
2006: 185-207.
7 Wang Li-fang, Zeng Jian-chao. A survey of stochastic
diffusion search [J]. Pattern Recognition and Artificial
Intelligence, 2008, 21 (3): 351-356 (in Chinese).
8 Zhu Gang, Ma Liang. Solving TSP by cellular ant
algorithm [J]. Computer Engineering and Applications, 2007,
43 (10): 79-80 (in Chinese).
9 Zhu Gang, Ma Liang. Cellular ant algorithm for function
optimization [J]. Journal of Systems Engineering, 2007,
22 (3): 305-308 (in Chinese).
10 Jin Hui-min, Ma Liang, Wang Zhou-mian. Fast
algorithms for finding optimal Euclidean Steiner tree [J].
Application Research of Computers, 2006, 23 (5): 60-62 (in
Chinese).
11 Jin Hui-min, Ma Liang, Wang Zhou-mian. Intelligent
optimization algorithms for Euclidean Steiner minimum tree problem
[J]. Computer Engineering, 2006, 32 (10): 201-203 (in Chinese).
