ecms_neu_mini.png

Digital Library

of the European Council for Modelling and Simulation

 

Title:

Evolutionary Ruin And Stochastic Recreate:

A Case Study On The Exam Timetabling Problem

Authors:

Jingpeng Li, Rong Qu, Yindong Shen

Published in:

 

(2012).ECMS 2012 Proceedings edited by: K. G. Troitzsch, M. Moehring, U. Lotzmann. European Council for Modeling and Simulation. doi:10.7148/2012 

 

ISBN: 978-0-9564944-4-3

 

26th European Conference on Modelling and Simulation,

Shaping reality through simulation

Koblenz, Germany, May 29 – June 1 2012

 

Citation format:

Li, J., Qu, R., & Shen, Y. (2012). Evolutionary Ruin And Stochastic Recreate: A Case Study On The Exam Timetabling Problem. ECMS 2012 Proceedings edited by: K. G. Troitzsch, M. Moehring, U. Lotzmann (pp. 347-353). European Council for Modeling and Simulation. doi:10.7148/2012-0347-0353

DOI:

http://dx.doi.org/10.7148/2012-0347-0353

Abstract:

This paper presents a new class of intelligent systems, called Evolutionary Ruin and Stochastic Recreate, that can learn and adapt to the changing enviroment. It improves the original Ruin and Recreate principle’s performance by incorporating an Evolutionary Ruin step which implements evolution within a single solution. In the proposed approach, a cycle of Solution Decomposition, Evolutionary Ruin and Stochastic Recreate continues until stopping conditions are reached. The Solution Decomposition step first uses some domain knowledge to break a solution down into its components and assign a score to each. The Evolutionary Ruin step then applies two operators (namely Selection and Mutation) to destroy a certain fraction of the entire solution. After the above steps, an input solution becomes partial and thus the resulting partial solution needs to be repaired. The repair is carried out by using the Stochastic Recreate step to reintroduce the removed items in a specific way (somewhat stochastic in order to have a better chance to jump out of the local optima), and then ask the underlying improvement heuristic whether this move will be accepted. These three steps are executed in sequence until a specific stopping condition is reached. Therefore, optimisation is achieved by solution disruption, iterative improvement and a stochastic constructive repair process performed within. Encouraging experimental results on exam timetabling problems are reported.

Full text: