ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR THE MIXED CHINESE POSTMAN PROBLEM

Hiroshi Masuyama, Tetsuo Ichimori, Toshihiko Sasama

2006

Abstract

The well known Chinese Postman Problem has many applications, and this problem has been proved to be NP-hard in graphs where directed and non-directed edges are mixed. In this paper, in order to investigate the salient feature of orthogonal design, we designed a genetic algorithm adopting an orthogonal crossover seoperation to solve this (mixed Chinese Postman) problem and evaluate the salient ability. The results indicate that for problems of small sizes, the orthogonal genetic algorithm can find near-optimal solutions within a moderate number of generations. We confirmed that the orthogonal design shows better performance, even for graph scales where simple genetic algorithms almost never find the solution. However, only the introduction of orthogonal design is not yet effective for the Chinese Postman Problem of practical size where a solution can be obtained in less than 104 generations. This paper concludes that the optimal design scale of orthogonal array to this mixed Chinese Postman Problem does not conform to the same scale as the multimedia multicast routing problem.

References

  1. Thimbleby, H., 2003. The directed Chinese postman problem. In Software - Practice & Experience, Vol.33, No.11, pp.1081-1096.
  2. Zhang, Q. and Leung, Y., 1999. An orthogonal genetic algorithm for multimedia multicast routing. In IEEE Trans. on Evolutionary Computation, Vol.3, No.1, pp.53-62, April.
  3. Fang, K.T. and Wang, Y., 1994, Number-Theoretic Methods in statistics. New York, Chapman & Hall.
  4. Wu, Q., 1978. On the optimality of orthogonal experimental design. In Acta Mathematicae Sinica, Vol.1, No.4, pp.283-299.
  5. Sasama, T., Masuyama, H. and Ichimori, T., 2002. On Fault Tolerance of Hypercubes using Subcubes. In Int. Journal of Reliability, Quality and Safety Engineering, Vol.9, No.2, pp.151-161.
  6. Leung, Y., Li, G. and Xu, Z., 1998. A Genetic Algorithm for the Multiple Destination Routing Problem. In IEEE Trans. on Evolutionary Computation, Vol.2, No.4.
  7. Zhang, Q. and Leung, Y., 1999. An Orthogonal Genetic Algorithm for Multimedia Multicast Routing. In IEEE Trans. on Evolutionary Computation, Vol.3, No.1.
  8. Edmond, J. and Johnson, E., 1979. Matching, Euler tours, and the Chinese postman. In Mathematical Programming, No.5, pp.538-554.
  9. Pearn, W. L., and Liu, C. M., 1995. Algorithms for the Chinese postman problem on mixed networks. In Computers & Operations Research, Vol.22, No.5, pp.479-489, May.
  10. Frederickson, G.N., 1979. Approximation algorithms for some postman problems. In J. Assoc. Comput. Mach. Vol.26, pp.538-554.
Download


Paper Citation


in Harvard Style

Masuyama H., Ichimori T. and Sasama T. (2006). ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR THE MIXED CHINESE POSTMAN PROBLEM . In Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT, ISBN 978-972-8865-69-6, pages 39-45. DOI: 10.5220/0001314600390045


in Bibtex Style

@conference{icsoft06,
author={Hiroshi Masuyama and Tetsuo Ichimori and Toshihiko Sasama},
title={ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR THE MIXED CHINESE POSTMAN PROBLEM},
booktitle={Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT,},
year={2006},
pages={39-45},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001314600390045},
isbn={978-972-8865-69-6},
}


in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT,
TI - ON ABILITY OF ORTHOGONAL GENETIC ALGORITHMS FOR THE MIXED CHINESE POSTMAN PROBLEM
SN - 978-972-8865-69-6
AU - Masuyama H.
AU - Ichimori T.
AU - Sasama T.
PY - 2006
SP - 39
EP - 45
DO - 10.5220/0001314600390045