1. the complete title of one (or more) paper(s) published in the open literature describing the work that the author claims describes a human-competitive result; An Automatically Designed Recombination Heuristic for the Test-Assignment Problem ========================================================================================================================================== 2. the name, complete physical mailing address, e-mail address, and phone number of EACH author of EACH paper(s); Name: Marcelo de Souza Physical address: Rua Eugênio Schneider, 62, Centro, Rio do Sul, SC, Brazil, 89167-018 E-mail address: marcelo.desouza@udesc.br Phone number: +55 47 996140178 Name: Marcus Rolf Peter Ritt Physical address: Avenida Bento Gonçalves 9500, Bloco IV, prédio 73, sala 201, Agronomia, Porto Alegre, RS, Brazil, 91501-970 E-mail address: marcus.ritt@inf.ufrgs.br Phone number: +55 51 33086818 ========================================================================================================================================== 3. the name of the corresponding author (i.e., the author to whom notices will be sent concerning the competition); Marcelo de Souza ========================================================================================================================================== 4. the abstract of the paper(s); 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 coloring 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. ========================================================================================================================================== 5. a list containing one or more of the eight letters (A, B, C, D, E, F, G, or H) that correspond to the criteria (see above) that the author claims that the work satisfies; (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (D) The result is publishable in its own right as a new scientific result independent of the fact that the result was mechanically created. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. ========================================================================================================================================== 6. a statement stating why the result satisfies the criteria that the contestant claims (see examples of statements of human-competitiveness as a guide to aid in constructing this part of the submission); (B) We applied a set of techniques for automatically design hybrid metaheuristics for the test-assignment problem. These techniques are based on the ideas of grammatical evolution, but apply a parameterized representation and use an algorithm configuration tool to evolve metaheuristics. The resulting algorithms outperform the method previously proposed and published by Duives et al. [1]. This fact can be observed in Table 3, in which we compare both approaches. Besides that, the automatically designed algorithms could find several new best solutions for the benchmark instances, as presented in Tables 4 and 5. Then, we claim that our "result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal". (D) The work was published in an international conference in the field of evolutionary computation, which focuses on the application of different artificial intelligence techniques on several optimization domains. This indicates that the work has been accepted as a new scientific result based upon its novelty and significance, independent of the used techniques. Regarding the automatic algorithm design methodology, we previously published a paper on EvoCop (see [2]) discussing the techniques in detail, with applications to the well known Unconstrained Binary Quadratic Programming and Maximum Cut problems. Our results show improvements in comparison to approaches from literature in a wide set of benchmark instances. This shows that the used techniques also have been accepted as a new scientific result. Besides that, the previous work of Duives et al. [1] reports the use of their tabu search algorithm to distribute tests in the laboratories of Engineering Faculty of the University of Bologna, Italy. Since our automatically designed metaheuristic improves over the existing method, it could also be used in real-world scenarios and could provide better solutions to the problem. (F) The results of Duives et al. were the best ones that experts could reach for the test-assignment problem since 2013. Our approach improves the existing approach. ========================================================================================================================================== 7. a full citation of the paper (that is, author names; publication date; name of journal, conference, technical report, thesis, book, or book chapter; name of editors, if applicable, of the journal or edited book; publisher name; publisher city; page numbers, if applicable); DE SOUZA, Marcelo; RITT, Marcus. An Automatically Designed Recombination Heuristic for the Test-Assignment Problem. In: 2018 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2018. p. 1-8. ========================================================================================================================================== 8. a statement either that "any prize money, if any, is to be divided equally among the co-authors" OR a specific percentage breakdown as to how the prize money, if any, is to be divided among the co-authors; Any prize money, if any, is to be divided equally among the co-authors. ========================================================================================================================================== 9. a statement stating why the authors expect that their entry would be the "best," and The process of designing heuristic algorithms to solve optimization problems is biased, tedious, and time-consuming. Usually, the researcher implements a set of algorithmic components and performs several experiments to identify the most promising strategies, the better combination of components, and an apropriate setting of parameter values. In this process, promising combinations of components and parameter values can be missed, and then it can lead to sub-optimal results. Moreover, it usually takes several months (or even more than a year) to obtain an algorithm competitive with state-of-the-art approaches. When using techniques to automatize the algorithm design process, we minimize these problems. The exploration of the design space is performed sistematically, avoiding bias and reducing the total time spent in this task. The researcher can put energy on creativity-related tasks, like the development of new algorithmic components and the exploration of new ideas. By using an automatic approach to design heuristic algorithms, we think that the whole field can evolve much more faster! ========================================================================================================================================== 10. An indication of the general type of genetic or evolutionary computation used, such as GA (genetic algorithms), GP (genetic programming), ES (evolution strategies), EP (evolutionary programming), LCS (learning classifier systems), GE (grammatical evolution), GEP (gene expression programming), DE (differential evolution), etc. Grammatical Evolution (GE) Evolution Strategies (ES) ========================================================================================================================================== 11. The date of publication of each paper. If the date of publication is not on or before the deadline for submission, but instead, the paper has been unconditionally accepted for publication and is “in press” by the deadline for this competition, the entry must include a copy of the documentation establishing that the paper meets the "in press" requirement. Date of conference: 8-13 July 2018 Date of publication on IEEE Xplore: 4 October 2018 DOI: 10.1109/CEC.2018.8477801 ========================================================================================================================================== # References: [1] J. Duives, A. Lodi, and E. Malaguti, “Test-assignment: A quadratic coloring problem,” Journal of heuristics, vol. 19, no. 4, pp. 549–564, 2013. [2] M. de Souza and M. Ritt, “Automatic grammar-based design of heuristic algorithms for unconstrained binary quadratic programming,” in Evolutionary Computation in Combinatorial Optimization, Springer, Springer International Publishing, 2018, pp. 67–84.