An Automatically Designed Recombination Heuristic for the Test-Assignment Problem

Created by W.Langdon from gp-bibliography.bib Revision:1.4549

  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,
                 test-assignment, binary quadratic programming,
                 automatic algorithm configuration, metaheuristics",
  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 =        "Also known as \cite{SouzaAndRitt2018} WCCI2018",

Genetic Programming entries for Marcelo de Souza Marcus Ritt