|
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: |