Discriminant Analysis as a Function of Predictive Learning to Select Evolutionary Algorithms in Intelligent Transportation System

Authors: Jorge A. Ruiz-Vanoye, Ocotlán Díaz-Parra, Alejandro Fuentes-Penna, Daniel Vélez-Díaz, Edith Olaco García

Abstract:

In this paper, we present the use of the discriminant analysis to select evolutionary algorithms that better solve instances of the vehicle routing problem with time windows. We use indicators as independent variables to obtain the classification criteria, and the best algorithm from the generic genetic algorithm (GA), random search (RS), steady-state genetic algorithm (SSGA), and sexual genetic algorithm (SXGA) as the dependent variable for the classification. The discriminant classification was trained with classic instances of the vehicle routing problem with time windows obtained from the Solomon benchmark. We obtained a classification of the discriminant analysis of 66.7%.

Keywords: Intelligent transportation systems, data-mining techniques, evolutionary algorithms, discriminant analysis, machine learning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1123579

References:

[1] Huberty, C.J., Applied Discriminant Analysis, Wiley Interscience, New York, 1994.
[2] Rascón Chávez, O., Introduction of descriptive statistics. Editorial UNAM, 1983.
[3] Fisher, R.A., The use of multiple measurements in taxonomic problems. Annals of Eugenics Vol. 7, 1936, 179-188.
[4] Kantardzicv, M.M., Data mining: Concepts, Models, Methods, and Algorithms. Wiley IEEE Press, 2002.
[5] Mitchell, M., An Introduction to Genetic Algorithms. MIT Press, England, 1998.
[6] Rechenberg, I., Evolution Strategy, Frommann-Holzboog, Stuttgart, 1994
[7] Fogel, L., Owens, A., Walsh, M., Artificial intelligence through simulated evolution. Wiley, 1966.
[8] Cramer, N., A representation for the adaptive generation of simple sequential programs. In Proceedings of the International Conference on Genetic Algorithms and their Applications, 183-187, 1985.
[9] Koza, J.R. Genetic Programming: On Programming Computers by Means of Natural Selection and Genetics. MIT Press, Cambridge, MA, 1992.
[10] Holland, J.H., Adaptation in Natural and Artificial Systems. University of Michigan Press. Ann Arbor, 1975.
[11] Lederberg J., Tatum, E.L., “Novel Genotypes in mixed Cultures of Biochemical Mutants of Bacteria”. Cold Spring Harbor Symposia of Quantitative Biology Vol. 11, 1946.
[12] Cook, S.A., “The Complexity of Theorem Proving Procedures”, Proceedings of 3rd ACM Symposium on Theory of Computing, pp. 151-158, Shaker Heights, Ohio, United States, May 03–05, 1971, ACM, New York, NY, USA
[13] Garey, M.R. and Johnson, D.S., Computers and Intractability, a Guide to the Theory of NP-completeness. W. H. Freeman and Company, New York, 1979.
[14] Toth, P. and Vigo, D., The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, 2001.
[15] Solomon, M.M., “Algorithms for Vehicle Routing and Scheduling Problems with Time Window Constrains”, Operations Research Vol. 35 No. 2, pp. 254-265, 1987.
[16] Sussman, J.M., Perspectives on Intelligent Transportation Systems (ITS), Springer Verlag, 2005, ISBN: 978-0-387-23257-7
[17] Fink, E., “How to Solve it Automatically, Selection among Problem-solving Methods”. Proceedings of the Fourth International Conference on AI Planning Systems AIPS'98, pp. 128-136, 1998.
[18] Cruz-Reyes, L., Classification of heuristics algorithms for the solution of Bin Packing Problem, Ph. D Thesis. Centro Nacional de Investigación y Desarrollo Tecnológico, 2004.
[19] Soares, C. and Brazdil, P., “Zoomed Ranking, Selection of Classification Algorithms Based on Relevant Performance Information”, Principles of Data Mining in Knowledge Discovery 4th European Conference (PKDD 2000), LNAI 1910, Springer Verlag, Berlin Heidelberg New York, pp. 126-135, 2000.
[20] Blanton, J. and Wainwright, R.L., “Multiple Vehicle Routing with Time and Capacity Constrainst using Genetic Algorithms”, Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, pp. 452-459, 1993.
[21] Thangiah, S.R., “Genetic Algorithms, Tabu Search and Simulated Annealing Methods for Vehicle Routing Problems with Time Windows”, Practical Handbook of Genetic Algorithms: Complex Structures. L. Chambers Ed. CRC Press, 1998.
[22] Michie, D., Spiegelhalter, D.J. and Taylor, C.C., Machine Learning, Neural and Statistical Classification. Publisher Ellis Horwood, 1994.
[23] Affenzeller, M., “New Generic Hybrids Based Upon Genetic Algorithms”, Advances in Artificial Intelligence. In IBERAMIA 2002, Lecture Notes in Artificial Intelligence 2527, Springer-Verlag, pp. 329-339, 2002.
[24] Dantzing, G.B. and Ramser, J.H., “The truck Dispatching Problem”. Management Science Vol. 6 No. 80, 1959.
[25] Lis, J., Eiben, A., “A Multi-Sexual Genetic Algorithm for Multi-Objective Optimization”, Proceedings of 1996 International Conference on Evolutionary Computing, IEEE, T. Fukuda, and T. Furuhashi (editors), Nagoyo, Japan, 1996, 59-64
[26] Wagner, S. and Affenzeller, M., “HeuristicLab: A Generic and Extensible Optimization Environment”, Adaptive and Natural Computing Algorithms. Springer, Computer Science, pp. 538-541, 2005.
[27] SPSS, Inc. Headquarters, Chicago, Illinois. http://www.spss.com/es/