Abstract
We face several teaching problems where a set of exercises has to be selected based on their capability to make students discover typical misconceptions or their capability to evaluate the knowledge of the students. We consider four different optimization problems, developed from two basic decision problems. The first two optimization problems consist in selecting a set of exercises reaching some required levels of coverage for each topic. In the first problem we minimize the total time required to present the selected exercises, whereas the surplus coverage of topics is maximized in the second problem. The other two optimization problems consist in composing an exam in such a way that each student misconception reduces the overall mark of the exam to some specific required extent. In particular, we consider the problem of minimizing the size of the exam fulfilling these mark reduction constraints, and the problem of minimizing the differences between the required marks losses due to each misconception and the actual ones in the composed exam. For each optimization problem, we formally identify its approximation hardness and we heuristically solve it by using a genetic algorithm. We report experimental results for a case study based on a set of real exercises of Discrete Mathematics, a Computer Science degree subject.
This work has been partially supported by Spanish project TIN2015-67522-C3-3-R, the UCM project PIMCD 2016_176, and by Comunidad de Madrid as part of the programs S2013/ICE-2731 (NGREENS-CM), and S2018/TCS-4339 (BLOQUES-CM) co-funded by EIE Funds of the European Union.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ausiello, G., Paschos, V.Th.: Reductions that preserve approximability. In: Handbook of Approximation Algorithms and Metaheuristics: Methologies and Traditional Applications, vol. 1 (2018)
Birattari, M.: Tuning Metaheuristics. A Machine Learning Perspective, vol. 197. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00483-4
Chen, S.-H.: Genetic Algorithms and Genetic Programming in Computational Finance. Springer, Heidelberg (2012)
Crescenzi, P.: A short guide to approximation preserving reductions. In: Proceedings of the 12th IEEE Conference on Computational Complexity, pp. 262–273. IEEE (1997)
Dasgupta, D., Michalewicz, Z.: Evolutionary Algorithms in Engineering Applications. Springer, Heidelberg (2013)
de Jong, K.: Evolutionary Computation: A Unified Approach. MIT Press, Cambridge (2006)
de la Encina, A., Hidalgo-Herrero, M., Rabanal, P., Rubio, F.: A parallel skeleton for genetic algorithms. In: Cabestany, J., Rojas, I., Joya, G. (eds.) IWANN 2011. LNCS, vol. 6692, pp. 388–395. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21498-1_49
Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634–652 (1998)
Hidalgo-Herrero, M., Rodríguez, I., Rubio, F.: Testing learning strategies. In: Fourth IEEE Conference on Cognitive Informatics 2005, (ICCI 2005), pp. 212–221. IEEE (2005)
Hidalgo-Herrero, M., Rodríguez, I., Rubio, F.: Comparing learning methods. Int. J. Cogn. Inf. Nat. Intell. (IJCINI) 3(3), 12–26 (2009)
Kolliopoulos, S.G., Young, N.E.: Approximation algorithms for covering/packing integer programs. J. Comput. Syst. Sci. 71, 495–505 (2005)
Kratsch, S., Marx, D., Wahlström, M.: Parameterized complexity and kernelizability of max ones and exact ones problems. In: Hliněný, P., Kučera, A. (eds.) MFCS 2010. LNCS, vol. 6281, pp. 489–500. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15155-2_43
Kratsch, S., Wahlström, M.: Preprocessing of min ones problems: a dichotomy. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 653–665. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14165-2_55
Man, K.F., Tang, K.S., Kwong, S.: Genetic Algorithms for Control and Signal Processing. Springer, Heidelberg (2012)
Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press, Cambridge (1998)
Oreski, S., Oreski, G.: Genetic algorithm-based heuristic for feature selection in credit risk assessment. Expert Syst. Appl. 41(4), 2052–2064 (2014)
Pal, S.K., Wang, P.P.: Genetic Algorithms for Pattern Recognition. CRC Press, Boca Raton (2017)
Paschos, V.Th.: An overview on polynomial approximation of NP-hard problems. Yugoslav J. Oper. Res. 19(1), 3–40 (2009)
Rabanal, P., Rodríguez, I., Rubio, F.: On the uselessness of finite benchmarks to assess evolutionary and Swarm methods. In: Proceedings of the Companion Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 1461–1462. ACM (2015)
Rabanal, P., Rodríguez, I., Rubio, F.: Assessing metaheuristics by means of random benchmarks. Procedia Comput. Sci. 80, 289–300 (2016)
Rodríguez, I., Rabanal, P., Rubio, F.: How to make a best-seller: optimal product design problems. Appl. Soft Comput. 55(C), 178–196 (2017)
Rodríguez, I., Rubio, F., Rabanal, P.: Automatic media planning: optimal advertisement placement problems. In: 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 5170–5177. IEEE (2016)
Sastry, K., Goldberg, D.E., Kendall, G.: Genetic algorithms. In: Burke, E., Kendall, G. (eds.) Search Methodologies, pp. 93–117. Springer, Heidelberg (2014). https://doi.org/10.1007/978-1-4614-6940-7_4
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
de la Encina, A., López, N., Rodríguez, I., Rubio, F. (2019). The Problems of Selecting Problems. In: Rojas, I., Joya, G., Catala, A. (eds) Advances in Computational Intelligence. IWANN 2019. Lecture Notes in Computer Science(), vol 11507. Springer, Cham. https://doi.org/10.1007/978-3-030-20518-8_63
Download citation
DOI: https://doi.org/10.1007/978-3-030-20518-8_63
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-20517-1
Online ISBN: 978-3-030-20518-8
eBook Packages: Computer ScienceComputer Science (R0)