Artificial Immune Algorithm for exams timetable

Tad Gonsalves; Rina Oishi

Tad Gonsalves Sophia University, Tokyo, Japan
Rina Oishi Faculty of Science & Technology, Sophia University, Tokyo

Keywords: Artificial Immune System, clonal algorithm, optimization, constrained optimization, time-tabling problems.

Abstract

The Artificial Immune System is a novel optimization algorithm designed on the resilient behavior of the immune system of vertebrates. In this paper, this algorithm is used to solve the constrained optimization problem of creating a university exam schedule and assigning students and examiners to each of the sessions. Penalties are imposed on the violation of the constraints. Abolition of the penalties on the hard constraints in the first stage leads to feasible solutions. In the second stage, the algorithm further refines the search in obtaining optimal solutions, where the exam schedule matches the preferences of the examiners.

Downloads

Download data is not yet available.

Author Biographies

Tad Gonsalves, Sophia University, Tokyo, Japan

Associate Professor, Inforamtion & Communications Dept., Faculty of Science & Technology

Rina Oishi, Faculty of Science & Technology, Sophia University, Tokyo

Department of Information and Communication Sciences

References

E.K. Burke and J.P. Newall. A multistage evolutionary algorithm for the timetable problem. IEEE Transactions on Evolutionary Computation, 3 (1):63 -74, 1999.

F. Melício, P. Caldeira, and A. Rosa. Solving real school timetabling problems with meta-heuristics. Proceedings of the 4th WSEAS International Conference on Applied Mathematics and Computer Science, 4:14-8, 2005.

Simon Kristiansen, Matias Sørensen, and Thomas R. Stidsen. Elective course planning. European Journal of Operational Research, 215(3):713-720, 2011.

Nelishia Pillay. A survey of school timetabling research. Annals of Operations Research, Springer, July 2014, Volume 218, Issue 1, pp 261-293.

B. McCollum. University timetabling: Bridging the gap between research and practice. In Proceedings of the 5th International Conference on the Practice and Theory of Automated Timetabling, pp.15-35. Springer, 2006.

R. Qu, E.K. Burke, B. McCollum, L.T.G. Merlot, and S.Y. Lee. A survey of search methodologies and automated system development for examination timetabling. Journal of Scheduling, 12(1):55-89, 2009.

Even, S., Itai, A., & Shamir, A. (1976). On the complexity of timetable and multicommodity flow problems. SIAM Journal

on Computing, 5, 691–703.

de Werra, D. (1997). The combinatorics of timetabling. European Journal of Operational Research, 96, 504–513.

Eikelder HM, Willemen RJ.Some complexity aspects of secondary school timetabling problems. Computer Science Practice and Theory of Automated Timetabling III. Lecture Notes in Computer Science, 2001; 2079:18–27.

Emma Hart, Jon Timmis, Application areas of AIS: The past, the present and the future, Applied Soft Computing 8 (2008)

–201.

de Castro L.N., Von Zuben, F.J.: Artificial immune systems: Part II—A survey of application. State Univ. Campinas, Campinas, Brazil, Tech. Rep. RT DCA 02/0065 (2000)

de Castro, L.N., Timmis, J.: Artificial Immune Systems: A New Computational Intelligence Approach. Springer-Verlag,

London (2002)

Timmis, J., Knight, T., de Castro L.N., Hart, E.: An Overview of artificial immune systems. In: Computation in Cells and

Tissues: Perspectives and Tools Thought. Natural Computation Series, Springer-Verlag, 51-86 (2004)

Ada, G.L., Nossal, G.: The Clonal Selection Theory. Scientific American, vol. 257, no.2, 50-57 (1987)

Dasgupta, D.: Advances in artificial immune systems. IEEE Comput. Intell. Mag., vol. 1, no. 4, 40-4 (2006)

Cauvery N K, Timetable Scheduling using Graph Coloring, International Journal of P2P Network Trends and TechnologyVolume1,

Issue 2- 2011, pp. 57-62.

E. K. Burke, D. G. Elliman, and R. Weare, A university timetabling system based on graph coloring and constraint

manipulation, Journal of Research on Computing in Education, 26, 1993.

Akhan Akbulut and Güray Y?lmaz, University Exam Scheduling System Using Graph Coloring Algorithm and RFID

Technology, International Journal of Innovation, Management and Technology, Vol. 4, No. 1, February 2013, pp. 66-72.

S.A. MirHassani, A computational approach to enhancing course timetabling with integer programming, Applied

Mathematics and Computation, Volume 175, Issue 1, 1 April 2006, pp. 814-822.

S Daskalaki, T Birbas, Efficient solutions for a university timetabling problem through integer programming, European

Journal of Operational Research, Volume 160, Issue 1, 1 January 2005, pp. 106-120.

Antony E. Phillips, Hamish Waterer, Matthias Ehrgott, David M. Ryan, Integer programming methods for large-scale

practical classroom assignment problems, Computers & Operations Research, Volume 53, January 2015, pp. 42–53.

J. Thompson and K. Dowsland, A robust simulated annealing based examination timetabling system, Computers and

Operations Research, vol. 25, pp. 637–648, 1998.

Chainate, W.; Thapatsuwan, P.; Pongcharoen, P., "Investigation on Cooling Schemes and Parameters of Simulated

Annealing for Timetabling University Courses," Advanced Computer Theory and Engineering, 2008. ICACTE '08.

International Conference on , vol., no., pp.200-204, 20-22 Dec. 2008

N. Pillay, W. Banzhaf, An informed genetic algorithm for the examination timetabling problem, Applied Soft Computing,

Volume 10, Issue 2, March 2010, pp. 457-467.

Cuupic, M.; Golub, M.; Jakobovic, D. Exam timetabling using genetic algorithm, Information Technology Interfaces, 2009.

ITI '09. Proceedings of the ITI 2009 31st International Conference on Year: 2009, pp. 357 - 362

Nothegger, C.; Mayer, A.; Chwatal, A.; Raidl, G. Solving the post enrolment course timetabling problem by ant colony

optimisation. Ann. Oper. Res. 2012, 194, 325–339.

Qarouni-Fard, D.; Najafi-Ardabili, A.; Moeinzadeh, M.-H. Finding Feasible Timetables with Particle Swarm Optimization,

th International Conference on Innovations in Information Technology, IIT '07, 2007, pp. 387 - 391

Shiau, D.F. A hybrid particle swarm optimization for a university course scheduling problem with flexible preferences.

Expert Syst. Appl. 2011, 38, 235–248.

Ho, I.S.F.; Safaai, D.; Zaiton, M., A Combination of PSO and Local Search in University Course Timetabling Problem.

International Conference on Computer Engineering and Technology, ICCET '09, 2009, Volume: 2, pp. 492 – 495.

Ayob, M.; Jaradat, G., Hybrid Ant Colony systems for course timetabling problems, 2nd Conference on Data Mining and

Optimization, DMO '09, 2009, pp. 120 – 126.

Rakesh P. Badoni, D.K. Gupta, Pallavi Mishra, A new hybrid algorithm for university course timetabling problem using

events based on groupings of students. Computers & Industrial Engineering, Volume 78, December 2014, pp. 12-25.

Timmis, J., Neal, M., Knight, T.: AINE: Machine Learning Inspired by the Immune System. IEEE Transactions on

Evolutionary Computation (2002)

de Castro L.N., Timmis, J.: An artificial immune network for multimodal function optimization. In: Proc. IEEE Congress

on Evolutionary Computation, vol. 1, 699-674 (2002)

de Castro L.N., Von Zuben, F.J.: Learning and optimization using the clonal selection principle. IEEE Trans. Evol.

Comput., vol. 6, no. 3, 239-251 (2002)

Glickman, M; Balthrop, J; Forrest, S, A Machine Learning Evaluation of an Artificial Immune System, Evolutionary

Computation, vol.13, no.2, pp.179-212, June 2005.

Hofmeyr, S; Forrest, S, Architecture for an Artificial Immune System, Evolutionary Computation , vol.8, no.4, pp.443-473,

Dec. 2000

O. Nasraoui, C. Rojas, C. Cardona, A framework for mining evolving trends in web data streams using dynamic learning

and retrospective validation, Comput. Networks 50, July 10, 2006, pp. 1425–1429.

Deng, J., Jiang, Y., Mao, Z.: An Artificial Immune Network Approach for Pattern Recognition, Third International

Conference on Natural Computation, ICNC 2007, vol. 3, 635-640, Haikou (2007)

de Castro L.N., Von Zuben, F.J.: aiNet: An artificial immune network for data analysis. In: Data Mining: A Heuristic

Approach, H.A. Abbass, R.A. Sarker, and C.S. Newton (eds). Idea Group Publishing, USA, pp. 231-259 (2001)

de Castro L.N., Von Zuben, F.J.: Learning and optimization using the clonal selection principle. IEEE Trans. Evol.

Comput., vol. 6, no. 3, 239-251 (2002).

Timmis, J., Neal, M., Hunt, J. E.:An artificial immune system for data analysis. Biosystem, vol. 55, no. 1/3, 143-150 (2000)

Timmis, J., Neal, M., Knight, T.: AINE: Machine Learning Inspired by the Immune System. Published in IEEE

Transactions on Evolutionary Computation (2002).

Sanjoy Das, Min Gui, Anil Pahwa, Artificial Immune Systems for Self-Nonself Discrimination: Application to Anomaly

Detection. Advances of Computational Intelligence in Industrial Systems Studies in Computational Intelligence Volume

, 2008, pp. 231-248.

Hua Yang, Tao Li, Xinlei Hu, Feng Wang, and Yang Zou, A Survey of Artificial Immune System Based Intrusion

Detection. The Scientific World Journal Volume 2014 (2014), Article ID 156790, 11 pages.

http://dx.doi.org/10.1155/2014/156790

Tad Gonsalves: CLONALG for improving software development cost models, Advances in Computer Science &

Engineering; Nov. 2012, Vol. 9 Issue 2, pp.133-151.

Weiwei Zhang; Yen, G.G.; Zhongshi He, Constrained Optimization Via Artificial Immune System, IEEE Transactions on

Cybernetics, 2014, Volume: 44, Issue: 2, pp.185 – 198.

de Mello Honorio, L.; Leite da Silva, A.M.; Barbosa, D.A., A Cluster and Gradient-Based Artificial Immune System

Applied in Optimization Scenarios, IEEE Transactions on Evolutionary Computation, 2012, Volume: 16, Issue: 3, pp.301 –

de Castro L.N., Timmis, J.: An artificial immune network for multimodal function optimization. In: Proc. IEEE Congress

on Evolutionary Computation, vol. 1, 699-674 (2002)

Tad Gonsalves and Yu Aiso, Multi-modal Optimization using a Simple Artificial Immune Algorithm, ICCGI2012, 2012.

Malim, M.R.; Khader, A.T.; Mustafa, A., An immune-based approach to university course timetabling: Immune network algorithm. International Conference on Computing & Informatics, ICOCI '06, 2006, pp. 1 – 6.