INSPIRING FUTURES

New crossover operators for timetabling with evolutionary algorithms.

Lewis, Rhydian M R and Paechter, Ben (2004) New crossover operators for timetabling with evolutionary algorithms. In: 5th International Conference on Recent Advances in Soft Computing. RASC, Nottingham, England, pp. 189-195. ISBN 1-84233-110-8

[img]
Preview
PDF
Available under License Creative Commons Attribution Non-commercial.

Download (67kB) | Preview

    Abstract/Description

    When using an evolutionary algorithm (EA) to optimise a population of feasible course timetables, it is important that the mutation and crossover operators are designed in such a way so that they don?t produce unfeasible or illegal offspring. In this paper we present some specialised, problem specific genetic operators that enable us to do this successfully, and use these in conjunction with a steady state EA to address the University Course Timetabling Problem (UCTP). We introduce a number of different crossover operators, each of which attempts to identify useful building blocks within the timetables, and investigate whether these can be successfully propagated through the population to encourage the production of high quality solutions. We test the effectiveness of these crossover operators on twenty well-known problem instances and present the results found. Whilst the results are not state-of-the-art, we make some interesting observations on the nature of the various crossover operators and the effects that they have on the evolution of the population as a whole

    Item Type: Book Section
    ISBN: 1-84233-110-8
    Uncontrolled Keywords: Genetic algorithms; evolutionary computation; timetabling; scheduling; optimisation;
    University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries > School of Computing
    Dewey Decimal Subjects: 000 Computer science, information & general works > 000 Computer science, knowledge & systems > 006 Special Computer Methods > 006.3 Artificial intelligence
    Library of Congress Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
    Item ID: 3400
    Depositing User: Computing Research
    Date Deposited: 23 Apr 2010 16:19
    Last Modified: 11 Aug 2011 09:47
    URI: http://researchrepository.napier.ac.uk/id/eprint/3400

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...

    Edinburgh Napier University is a registered Scottish charity. Registration number SC018373