- author = "Marcelo {de Souza} and Marcus Ritt",
- title = "An Automatically Designed Recombination Heuristic for the Test-Assignment Problem",
- booktitle = "2018 IEEE Congress on Evolutionary Computation (CEC)",
- year = "2018",
- editor = "Marley Vellasco",
- address = "Rio de Janeiro, Brazil",
- month = "8-13 " # jul,
- publisher = "IEEE",
- keywords = "genetic algorithms, genetic programming, Grammatical Evolution, Evolution Strategies (ES), test-assignment, binary quadratic programming, automatic algorithm configuration, metaheuristics",
-
URL = "
http://human-competitive.org/sites/default/files/souza-ritt-paper.pdf",
-
DOI = "
doi:10.1109/CEC.2018.8477801",
- size = "8 pages",
-
abstract = "A way of minimizing the opportunity of cheating in
exams is to assign different tests to students. The
likelihood of cheating then depends on the proximity of
the students' desks, and the similarity of the tests.
The test-assignment problem is to find an assignment of
tests to desks that minimizes that total likelihood of
cheating. The problem is a variant of a graph colouring
problem and is NP-hard.
We propose a new heuristic solution for this problem. Our approach differs from the usual way of designing heuristics in two ways. First, we reduce test-assignment to the more general unconstrained binary quadratic programming. Second, we search for a good heuristic using an automatic algorithm configuration tool that evolves heuristics in a space of algorithms built from known components for binary quadratic programming. The best hybrid heuristics found repeatedly recombine elements of a population of elite solutions and improve them by a tabu search. Computational tests suggest that the resulting algorithms are competitive with existing heuristics that have been designed manually.",
-
notes = "Entered 2019 Humies.
Also known as \cite{SouzaAndRitt2018} WCCI2018",
