Korean Management Science Review (경영과학)

The Korean Operations Research and Management Science Society (한국경영과학회)
권호 표지

A Nodes Set Based Hybrid Evolutionary Strategy on the Rectilinear Steiner Tree Problem

점집합을 개체로 이용한 직각거리 스타이너 나무 문제의 하이브리드 진화 전략에 관한 연구

  • 양병학 (경원대학교 산업정보시스템공학과)
  • Published : 2006.05.01
Download PDF
⟨ Previous Next ⟩

Abstract

The rectilinear Steiner tree problem (RSTP) is to find a minimum-length rectilinear interconnection of a set of terminals in the plane. It is well known that the solution to this problem will be the minimal spanning tree(MST) on some set Steiner points. The RSTP is known to be NP-complete. The RSTP has received a lot of attention in the literature and heuristic and optimal algorithms have been proposed. A key performance measure of the algorithm for the RSTP is the reduction rate that is achieved by the difference between the objective value of the RSTP and that of the MST without Steiner points. A hybrid evolutionary strategy on RSTP based upon nodes set is presented. The computational results show that the hybrid evolutionary strategy is better than the previously proposed other heuristic. The average reduction rate of solutions from the evolutionary strategy is about 11.14%, which is almost similar to that of optimal solutions.

Keywords

References

  1. Back, Thomas, Evolutionary Algorithm in Theory and Practice, Oxford University Press, 1996
  2. Barreiros, J., 'An Hierarchic Genetic Algorithm for Computing (near) Optimal Euclidean Stein Steiner Trees,' Workshop on Application of hybrid Evolutionary Algorithms to NP-Complete Problems, Chicago, 2003
  3. Beasley, J.E., 'OR-Library：Distributing Test Problems by Electronic Mail,' Journal of the Operational Research Society, Vol.41 (1990), pp.1069-1072 https://doi.org/10.1057/jors.1990.166
  4. Beasley, J.E., 'A Heuristic for Euclidean and Rectilinear Steiner Problems,' European Journal of Operational Research, Vol.58 (1992), pp.284-292 https://doi.org/10.1016/0377-2217(92)90214-T
  5. Borah, M. and R.M. Owens, 'An Edge-Based Heuristic for Steiner Routing,' IEEE Trans. on Computer Aided Design, Vol. 13(1994), pp.1563-1568 https://doi.org/10.1109/43.331412
  6. France, R.L., 'A Note on the Optimum Location of New Machines in Existing Plant Layouts,' J. Industrial Engineering, Vol.14 (1963), pp.57-59
  7. Ganley, J.L., 'Computing Optimal Rectilinear Steiner Trees：A Survey and Experimental Evaluation,' Discrete Applied Mathematics, Vol.90(1999), pp.161-171 https://doi.org/10.1016/S0166-218X(98)00089-4
  8. Garey, M.R. and D.S. Johnson, 'The rectilinear Steiner Tree Problem is NP-complete,' SIAM Journal on Applied Mathematics, Vol.32(1977) pp.826-834 https://doi.org/10.1137/0132071
  9. Hanan, M., 'On Steiner's Problem with Rectilinear Distance,' SLAM Journal on Applied Mathematics, Vol.14(1966), pp.255-265 https://doi.org/10.1137/0114025
  10. Hesser, J., R. Manner, O. Stucky, 'Optimization of Steiner Trees using Genetic Algorithms,' Proceedings of the Third International Conference on Genetic Algorithm, (1989), pp.231-236
  11. Ho, J.M., G. Vijayan, and C.K. Wong, 'New Algorithm for the Rectilinear Steiner Tree Problem,' IEEE Trans. on Computer Aided Design, Vol.9(1990), pp.185-193 https://doi.org/10.1109/43.46785
  12. Hwang, F.K., 'An O(n logn) Algorithm for Suboptimal Rectilinear Steiner Trees,' IEEE Transaction son Circuits and Systems, Vol.26(1979), pp.75-77 https://doi.org/10.1109/TCS.1979.1084551
  13. Joseph, J. and F.C. Harris, 'A Genetic Algorithm for the Steiner Minimal Tree Problem,' Procedings of Inernational Conference on Intelligent Systems, 1996
  14. Julstrom, B.A., 'Encoding Rectilinear Trees as Lists of Edges,' Proceedings of the 16th ACM Symposium on Applied Computing, (2001), pp.356-360
  15. Kahng, A.B. and B. Robins, 'A New Class of Iterative Steiner Tree Heuristics with Good Performance,' IEEE Trans. on Computer Aided Design, Vol.11(1992), pp. 893 https://doi.org/10.1109/43.144853
  16. Lee, J.L., N.K. Bose, and F.K. Hwang, 'Use of Steiner's Problem in Suboptimal Routing in Rectilinear Metric,' IEEE Transaction son Circuits and Systems, Vol.23(1976), pp.470-476 https://doi.org/10.1109/TCS.1976.1084243
  17. Soukup, J. and W.F. Chow, 'Set of Test Problems for the Minimum Length Connection Networks,' ACM/SIGMAP Newsletter, Vol.15(1973), pp.48-51
  18. Wakabayashi, S., 'A Genetic Algorithm for Generating a Set of Rectilienar Steiner Trees in VLSI Interconnection Layout,' Information processing Society of Japan Journal, Vol.43, No.5, 2002
  19. Warme, D.M., P. Winter, and M. Zachariasen, 'Exact Algorithms for Plane Steiner Tree Problems : A Computational Study,' In： D.Z. Du, J.M. Smith and J.H. Rubinstein (eds.)：Advances in Steiner Tree, Kluser Academic Publishers (1998)
  20. Warme, D.M., http://www.group-w-inc.com/~warme/research