Comparativa entre algoritmos Mono y Multi-objetivo aplicados al problema de calendarización de horarios universitarios

Autores/as

  • Moisés Emmanuel Romo Franco Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México
  • Juan Martín Carpio Valadez Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México
  • Lucero Ortíz-Aguilar Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México
  • Jorge Alberto Soria-Alcazar Universidad de Guanajuato, Guanajuato, Guanajuato, México
  • Héctor J. Puga Soberanes Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México
  • Carlos Lino Ramírez Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México
  • Luis Ernesto Mancilla Espinosa Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México

DOI:

https://doi.org/10.30973/progmat/2019.11.1/5

Palabras clave:

NSGA-II, Calendarización de Horarios Universitarios, Algoritmo Genético, Algoritmo Memético, Sistema Inmune

Resumen

La calendarización de tareas en las instituciones educativas tiene como objetivo que los estudiantes tomen sus asignaturas correspondientes apegándose a un conjunto de restricciones. En el presente trabajo se muestra que, utilizando un enfoque Multi-objetivo junto a la metodología API-CARPIO, se generan soluciones aceptables para el problema de calendarización de horarios. Las instancias de prueba provienen de datos reales del Instituto Tecnológico de León (ITL). Los resultados del algoritmo Multi-objetivo NSGAII y sus distintas configuraciones son comparados con los resultados de algoritmos Metaheurísticos, además con los resultados de un Experto Humano.

Biografía del autor/a

Moisés Emmanuel Romo Franco, Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México

ngeniero en Sistemas Computacionales, egresado en 2016 en el Instituto Tecnológico de León. Actualmente se encuentra cursando la Maestría en Ciencias de la Computación, en su segundo año en el Instituto Tecnológico de León. Actualmente se encuentra investigando y aplicando diferentes algoritmos Multiobjetivo para la generación del diseño de horarios. Sus áreas de interés son: Aplicación de Algoritmos Multiobjetivo y Visión por computadora

Juan Martín Carpio Valadez, Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México

Obtuvo el grado de Doctor en Ciencias (Óptica) del CIO en 1995. Su experiencia profesional incluye el CIO, ITESM campus León, Universidad Iberoamericana plantel León, y desde 1994 a la fecha el Instituto Tecnológico de León, en donde ocupó el cargo de Jefe del Depto. de Sistemas y Computación de 1999 a 2004, el cargo de Jefe de la División de Estudios de Posgrado e Investigación de 2004 a 2006. Ha participado como responsable y colaborador de varios proyectos de investigación, apoyados por CONCyTEG, COSNET y DGEST. Colaboró en la formación de recursos humanos a través de la dirección tesis de licenciatura (10), maestría (35) y doctorado (3). Actualmente es miembro del Sistema Nacional de Investigadores nivel I. Es miembro del Consejo de Posgrado y miembro del claustro del Doctorado Interinstitucional en Ciencias en Computación. Sus áreas de interés son: sistemas inteligentes, University Timetabling, Metaheurística, Hiperheurísticas. 

Lucero Ortíz-Aguilar, Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México

Ingeniero en Sistemas Computacionales, egresada en 2009 en el Instituto Tecnológico de León. Actualmente se encuentra cursando la Maestría en Ciencias de la Computación, en su segundo año en el Instituto Tecnológico de León. Actualmente se encuentra investigando y aplicando diferentes técnicas Metaheurísticas e Hiperheurísticas para la generación del diseño de horarios. Ha publicado artículos en el Congreso de la Mujer 2015, organizado por el CIO y en COMIA 2015 (Congreso Mexicano de Inteligencia Artificial), en relación a la aplicación de Metaheurísticas al diseño de horarios. Sus áreas de interés son: Técnicas de optimización combinatoria, Metaheurísticas, Hiperheurísticas y Visión por computadora.

Jorge Alberto Soria-Alcazar, Universidad de Guanajuato, Guanajuato, Guanajuato, México

Egresado como Ingeniero en sistemas computacionales por el instituto tecnológico de león en 2008, continúo su formación como Maestro en ciencias en Ciencias de la Computación por la misma casa de estudios egresando en 2010. Obtuvo el grado de Doctor en ciencias de la Computación por el Instituto Tecnológico de Tijuana B.C parte del Tecnológico Nacional de México en el 2015. El Dr Soria-Alcaraz cuenta trabajos publicados en el área nacional e internacional sobre los temas de Hiper-heurísticas, Timetabling así como Autonomus Search. Ha asistido a congresos nacionales e Internacionales a presentar trabajos acordes a estas áreas. Actualmente se desempeña como profesor investigador de tiempo completo en la División de Ciencias EconómicoAdministrativas de la Universidad de Guanajuato campus Guanajuato apoyando la carrera de Licenciatura en Sistemas de Información Administrativa. También pertenece al Sistema Nacional de Investigadores (SNI) con la distinción de Candidato a investigador Nacional.

Héctor J. Puga Soberanes, Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México

Héctor J. Puga Soberanes se graduó de Licenciatura en Físico Matemáticas, en el Instituto Politécnico Nacional en 1993. Obtuvo el grado de Maestría en Ciencias (Óptica) en 1995, egresado del Centro de Investigaciones en Óptica, A. C. (CIO), obteniendo el titulo por parte de la Universidad de Guanajuato. Obtuvo el grado de Doctor en Ciencias (Óptica), egresado del CIO, obteniendo el titulo por parte de la Universidad de Guanajuato en 2002. Cuenta con publicaciones internacionales, en congresos internacionales y nacionales. Ha participado como responsable y colaborador de varios proyectos de investigación, apoyados por CONCyTEG, COSNET y DGEST. A colaborado en la formación de recursos humanos a través de la dirección tesis de licenciatura (3) y Maestría (4) Actualmente es miembro del Sistema Nacional de Investigadores nivel I. Profesor con perfil deseable (Promep) de Agosto de 2005 a la fecha. Sus áreas de interés son: Metrología, Hiperheurísticas y sistemas inteligentes.

Carlos Lino Ramírez, Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México

Profesor Investigador y jefe de la División de Estudios de Posgrado e Investigación (DEPI) del Instituto Tecnológico de León, en el programa de Maestría en Ciencias en Ciencias de la Computación desde Noviembre del 2010. Doctorado en Arquitectura y Tecnología de los Sistemas Informáticos por la Universidad Politécnica de Valencia, España (2012). Maestro en Ciencias en Ciencias Computacionales por el Instituto Tecnológico de León (1999). Ingeniero en Sistemas Computacionales por el Instituto Tecnológico de León (1996). Ha sido subdirector del Instituto Tecnológico de León (2006-2007), jefe del departamento de Sistemas y Computación del Instituto Tecnológico de León (2004-2006), jefe del área de redes en el Sistema Avanzado de Bachillerato y Educación Superior (1999-2001). Ha presentado sus trabajos de investigación en diversos congresos internacionales en España, Italia, Alemania y México. Sus áreas de investigación son Inteligencia de Ambiente, Algoritmos de Encaminamiento y Redes de Sensores Inalámbricas.

Luis Ernesto Mancilla Espinosa, Tecnológico Nacional de México-Instituto Tecnológico de León, León, Guanajuato, México

Luis Ernesto Mancilla Espinosa recibió su BS grado en comunicación e ingeniería electrónica de la Escuela Superior de Ingeniería Eléctrica del Instituto Politécnico Nacional en 1975. El obtuvo el grado de Maestro en ciencias de la Computación del Instituto Tecnológico de León en 1999 y su posgrado en ingeniería especializada en Mecatrónica del Centro de Investigación y desarrollo tecnológico en Querétaro, Qro. Sus líneas de interés cubren la Mecatrónica, Inteligencia Artificial, Software de computadora e Ingeniería en Software.

Citas

Jorge A, S., Martin, C. J., & Hugo, T. Diseño de Horarios Mediante Algoritmos Genético. Décima Primera Reunión de Otoño de Potencia, Electrónica y Computación del IEEE, SI ROPEC, Morelia. 2009.

Aguilar, L. D. M. O., Valadez, J. M. C., Soberanes, H. J. P., González, C. L. D., Ramírez, C. L., & Alberto Soria-Alcaraz, J. Comparativa de algoritmos bioinspirados aplicados al problema de calendarización de horarios. Research in Computing Science. 2015, vol 94, 33-43.

Soria-Alcaraz J., A., Martín, C., Héctor, P., & Sotelo-Figueroa, M. A. Comparison of metaheuristic algorithms with a methodology of design for the evaluation of hard con-straints over the course timetabling problem. Berlin, Heidelberg: Springer Berlin Heidel-berg. 2013, pp. 289–302. Avariable from: https://doi.org/10.1007/978-3-642-33021-6_23

Asratian, A. S., de Werra, D. A generalized class–teacher model for some Timetabling problems. University of Technology, Department of Engineering Sciences and Mathematics, Mathematical Science. Mathematics, European Journal of Operational Research. 2002, pp. 531–542. Avariable from: https://doi.org/10.1016/S0377-2217(01)00342-3.

Deng, X., Zhang, Y., Kang, B., Wu, J., Sun, X., & Deng, Y. An application of genetic algorithm for university course timetabling problem. In Control and Decision Conference (CCDC). 2011, Chinese, pp. 2119-2122, Avariable from: https://doi.org/10.1109/CCDC.2011.5968555.

Mahiba, A.A. & Durai, C.A.D. Genetic algorithm with search bank strategies for university course timetabling problem. Procedin Engineering. 2012, vol. 38, pp. 253– 263. https://doi.org/10.1016/j.proeng.2012.06.033

Soria-Alcaraz, J. A., Carpio, J. M., Puga, Hé., Melin, P., Terashima-Marn, H., Reyes, L. C. & Sotelo-Figueroa, M. A. Castillo, O., Melin, P.; Pedrycz, W. & Kacprzyk, J. Generic Memetic Algorithm for Course Timetabling. In: ITC2007 Recent Advances on Hybrid Approaches for Designing Intelligent Systems, Springer. 2014, vol. 547, pp. 481–492. https://doi.org/10.1007/978-3-319-05170-3_33

Nguyen, K., Lu, T., Le, T., & Tran, N. Memetic algorithm for a university course timetabling problem. In Informatics in Control, Automation and Robotics. 2011, pp. 67–71. Avariable from: https://doi.org/10.1007/978-3-642-25899-2_10.

Joudaki, M., Imani, M., & Mazhari, N. Using improved Memetic algorithm and local search to solve University Course Timetabling Problem (UCTTP). Doroud, Iran: Islamic Azad University. 2010.

Frausto-Solís, J., Alonso-Pecina, F., & MoraVargas, J. An efficient simulated annealing algorithm for feasible solutions of course timetabling. In Mexican International Conference on Artificial Intelligence. Springer. 2008, pp. 675–685. https://doi.org/10.1007/978-3-540-88636-5_64

Thepphakorn, T., Pongcharoen, P., & Hicks, C. An ant colony based timetabling tool. International Journal of Production Economics. 2014, vol. 149, pp. 131–144. Avariable from: https://doi.org/10.1016/j.ijpe.2013.04.026.

Soria-Alcaraz, J., Ochoa, G., Swan, J., Carpio, M., Puga, H., & Burke, E. Effective learning hyper-heuristics for the course timetabling problem. European Journal of Operational Research. 2014, pp. 77–86. Avariable from: https://doi.org/10.1016/j.ejor.2014.03.046.

Carrasco, M. P., & Pato, M. V. A multiobjective genetic algorithm for the class/teacher timetabling problem. In International Conference on the Practice and Theory of Automated Timetabling. 2000, pp. 3- 17. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44629-X_1

Datta, D., Deb, K., & Fonseca, C. Multiobjective evolutionary algorithm for university class timetabling problem. Evolutionary Scheduling. 2007, pp.197-236. https://doi.org/10.1007/978-3-540-48584-1_8

Azadeh, A., Gholizadeh, H., & Jeihoonian, M. A multi-objective optimisation model for university course timetabling problem using a mixed integer dynamic non-linear programming. International Journal of Services and Operations Management. 2013, 15(4), 467- 481. https://doi.org/10.1504/IJSOM.2013.054886

Movahhedfar, N., Ranjbar, M., Salari, M., & Rostami, S. Memetic and scatter search metaheuristic algorithms for a multiobjective fortnightly university course timetabling problem: a case study. Journal of Industrial and Systems Engineering. 2013, Vol 6.

Wolpert, H., Macready, G. No free lunch Theorems for Search. Technical report, The Santa Fe Institute. 1996, vol. 1.

Conant-Pablos, S. E., Magaña-Lozano, D. J., Terashima-Marín, H. Pipelining memetic algorithms, constraint satisfaction, and local search for course timetabling. MICAI Mexican international conference on artificial intelligence. 2009, vol. 1, 408–419. https://doi.org/10.1007/978-3-642-05258-3_36

Ortiz, L. Diseño de horarios de Alumnos y Maestros mediante Técnicas de Soft Computing, para una Institución Educativa. Master’s thesis, Instituto Tecnológico de León. 2015.

Carpio-Valadez, J.M.: Integral Model for optimal assignation of academic tasks. In: Encuentro de investigacion en ingenieria electrica, ENVIE, Zacatecas. 2006, pp. 78–83.

Soria-Alcaraz, J. A., Martin, C., Héctor, P., Hugo, T., Laura, C. R., & Sotelo-Figueroa, M. A. Methodology of design: A novel generic approach applied to the course timetabling problem. In Soft Computing Applications in Optimization, Control, and Recognition. 2013, pp. 287–319. Avariable from: https://doi.org/10.1007/978-3-642-35323-9-12.

Ortiz-Aguilar, L. D. M., Carpio, M., SoriaAlcaraz, J. A., Puga, H., Díaz, C., Lino, C., & Tapia, V. Training OFF-Line Hyperheuristics For Course Timetabling Using K-Folds Cross Validation. En la revista programación matemática y software. 2016. https://doi.org/10.30973/progmat/2016.8.3/1

D. B. Fogel, Evolutionary Computation. The Fossil Record. Selected Readings on the History of Evolutionary Algorithms., New York, 1998.

Glover, F., Laguna, M., & Martí, R. Scatter Search, to appear in Theory and Applications of Evolutionary Computation: Recent Trends, A. Ghosh and S. Tsutsui. 1999.

Goldberg, D. E. Genetic Algorithms in Search, Optimization and Machine Learning. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1989, 1st edition.

M. Mitchell, An Introduction To Genetic Algorithms, London England: The MIT Press, 1998.

Talbi, E. Metaheuristics: From design to implementation. US: Wiley. 2009.

Azuaje, F.: Review of “Artificial immune systems: A new computational intelligence approach. Journal Neural Networks. 2003, vol. 16, no.8, Elsevier, pp. 1229–1229.

Molina, J. Problema de Optimización de rutas de vehículos con aspectos medioambientales. Master’s thesis, Universidad de Sevilla. 2013.

Safaei, N., Banjevic, D., & Jardine, A. K. Multi-objective simulated annealing for a maintenance workforce scheduling problem: a case study. In Simulated annealing. InTech. 2008.

Arfken, G. Métodos matemáticos para físicos (No. 510 A7Y 1970). 1981.

Srinivas, N. and Deb, K.: Multi-Objective function optimization using non-dominated sorting genetic algorithms. Evolutionary Computation. 1994, 2(3), pp. 221-248.

Deb, K., Agrawal, S. ,Pratap, A. , Meyarivan, T. : A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature. 2000, pp. 849-858. https://doi.org/10.1007/3-540-45356-3_83

Cortés, A. Comparación de dos algoritmos metaheurísticos en la solucion Multi-objetivo de un modelo particular de la cadena de suministros. Master’s thesis, Instituto Tecnológico de León. 2010.

Escobar, A. Optimización Multi-objetivo. Universidad Tecnológica de Pereida – Colombia. PDF Presentation. 2014.

Arranz de la Peña, J. Algoritmos genéticos. Madrid: Universidad Carlos III. 2009.

Srinivas, M. & Patnaik, L. M. Genetic algorithms: A survey. Computer.1994, 27(6), 17-26. https://doi.org/10.1109/2.294849

Derrac, J., García, S.: A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence. In Swarm and Evolutionary Computation. 2011. https://doi.org/10.1016/j.swevo.2011.02.002

Descargas

Publicado

28-02-2019

Cómo citar

Romo Franco, M. E., Carpio Valadez, J. M., Ortíz-Aguilar, L., Soria-Alcazar, J. A., Puga Soberanes, H. J., Lino Ramírez, C., & Mancilla Espinosa, L. E. (2019). Comparativa entre algoritmos Mono y Multi-objetivo aplicados al problema de calendarización de horarios universitarios. Programación matemática Y Software, 11(1), 36–47. https://doi.org/10.30973/progmat/2019.11.1/5

Número

Vol. 11 Núm. 1 (2019): Febrero de 2019

Sección

Artículos

Licencia

Derechos de autor 2019 Programación Matemática y Software

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.

Usted es libre de:

Compartir — compartir y redistribuir el material publicado en cualquier medio o formato.
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente.

Bajo las siguientes condiciones:

Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso.
  Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia.

Artículos más leídos del mismo autor/a