Comparing Genetic Algortihms and Matrix Factorization for Learning Heuristics in Constraint Solving Seda Polat Erdeniz and Andrei Popescu 1 Abstract. approaches. Matrix factorization is based on the idea of parameter- Knowledge-based recommender systems assist users in the active izing two low-dimensional matrices U and V in such a way that U configuration of complex products. These systems rely on solving x V = R’. The matrix R is an approximation of the original user x Constraint Satisfaction Problems (CSP). In constraint solving, vari- item preference matrix R. Consequently, missing values in R can be able and value ordering heuristics help to increase efficiency. Apply- estimated by the multiplication of the two low-dimensional matrices ing such heuristics can increase the performance of CSP solvers. On U and V. the other hand, if we apply specific heuristics to similar CSPs, CSP There exist a couple of research contributions focusing on the in- solver performance could be further improved. In previous work, we tegration of feature model configurators with recommender systems. have proposed novel approaches to learn such heuristics, however, an Rodas-Silva et al. [11] introduce a content-based and collaborative evaluation in terms of consistency and prediction quality is still lack- filtering approach to the recommendation of components that should ing. In this paper, we evaluate an compare two proposed approaches be selected for the implementation of a given configuration. Pereira to learn heuristics, one relying on Genetic Algorithms and Cluster- et al. [8, 1] integrate different collaborative filtering approaches into ing, and one on Matrix Factorization, on the same problem. Our re- feature model configuration processes to proactively support users sults provide valuable insights for future research in this domain. in the navigation through complex feature spaces. In this context, the authors also apply matrix factorization with the goal to fur- ther improve the prediction quality of the recommender system. Fi- 1 Introduction nally, Falkner et al. [3] provide an overview on different scenarios that can benefit from the integration of recommender systems with The configuration of complex items, such as financial services, soft- knowledge-based configurators. In another work, Erdeniz and Felfer- ware artefacts, and cars, is a cumbersome task (from a user point of nig [9] use k-means clustering and a genetic algorithm (GA) in order view) in the scope of the mass customization business model [5]. In to compute search heuristics to tackle the graph colouring problem. this context, a user often requires (or would benefit) from intelligent Compared to the approach of Erdeniz et al. [10], all of the men- support during the configuration task, to overcome sub-optimal sce- tioned approaches do not propose a solution focusing on the integra- narios induced by time constraints, information overload, and prod- tion of recommendations into the search heuristics of a configurator uct suitability issues. A widespread intelligent support system in this and thus not being able to guarantee the consistency of determined scenarios is provided by recommender systems. recommendations and runtime performance at the same time. A recommender system can be defined as any system that guides In this paper, we provide an evaluation and comparison between a user in a personalized way to interesting or useful objects in a large the approach developed by Erdeniz et al. [10] and the work of Er- space of possible options or that produces such objects as output deniz and Felfernig [9], in terms of prediction quality and achieved [4]. Knowledge-based recommender systems, in specific constraint- consistency in the recommendation task. The contributions of our pa- based recommender systems [2], have been widely adopted in sce- per are three-fold: (1) we apply the approach of Erdeniz and Felfer- narios involving the recommendation of complex tasks. These sys- nig [10], and Erdeniz et al. [9] on a configuration dataset, allowing tems generate recommendations by solving the corresponding Con- a direct comparison in terms of consistency and prediction perfor- straint Satisfaction Problem (CSP). Since the search space can mance; (2) we evaluate and compare the two approaches in terms of quickly become challenging, heuristics [6] are of fundamental im- achieved consistency and prediction quality; (3) we point out future portance in constraint-based recommender systems. research directions to be pursued towards machine learning-based Erdeniz et al. [10] have proposed a constraint-based recommen- search heuristics. dation approach that provides accurate heuristics based on historical In the remainder of the paper, we first describe the approach fol- configuration transactions. By integrating matrix factorization into lowed by Erdeniz et al. [10] in Section 2, and explain the work of the computation of search heuristics for the feature model configura- Erdeniz and Felfernig [9] in Section 3. In Section 4 we cover in more tion task, Erdeniz et al. [10] guarantee the consistency of determined details our evaluation approach, the results of which we discuss in recommendations. Section 5. We conclude in Section 6. The prediction of the preference of a user for a specific item was based on elementary matrix multiplication operation, so-called ma- trix factorization [7], as often are model-based collaborative filtering 1 Graz University of Technology, Austria, email: an- drei.popescu@ist.tugraz.at Copyright 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) 2 Matrix Factorization-based Heuristics To allow direct comparison between the two studies, we imple- ment both approaches and evaluate their performance on the basis Erdeniz et al. [10] have applied a constraint-based recommendation of a CSP comprised of 10 variables having a domain of size 5, and approach to compute value ordering heuristics, in order to support the two constraints, one domain constraint and one user constraint. The recommendation of missing configuration parameters in the scope of following is the definition of the used CSP. an online personalized bike shop. The proposed approach exploits V a r i a b l e s : V0 , V1 , V2 , V3 , V4 , V5 , V6 , V7 , V8 , v9 , V10 historical transactions in order to recommend missing configuration Domains : dom ( V1 ) = dom ( V2 ) . . . . = dom ( v10 ) = {1 , 2 , 3 , 4 , 5} parameters to the currently active user configuring his/her product, Domain C o n s t r a i n t s : by means of the matrix factorization. Matrix factorization is first ap- c1 : x > 2 −> y >= 4 plied on the sparse matrix composed of historical transactions (com- User Requirements : plete or incomplete) concluded by past users. This step produces a c2 : x = r e q . v a l where r e q . v a l i s a v a l u e i m p o s e d by t h e u s e r dense matrix R0 providing estimated configuration parameter values Pre-computed solutions of the above introduced CSP (without the for the whole matrix. For users that completed their configuration, user requirement) were used to build the training and test set. The test the recommendation of parameters is straightforward, as it is suffi- set in particular, consists of solutions to the problem, with an increas- cient to provide the complete historical transaction (HT1), whereas ing number of missing variable assignments (up to #variables-1). We for users who have provided an incomplete configuration, the corre- use matrix factorization (MP), matrix factorization with CSP solving sponding dense transaction is used to obtain search heuristics for the (MF with CSP solving), and genetic algorithms with CSP solving constraint-based recommender. (GA with CSP solving) to recommend values for the missing assign- Concerning the transaction currently active (AT), in the scope of ments. The genetic algorithm was hyper-tuned with the following which the user needs support, value ordering for missing variable as- parameters: signments are obtained based on the k-nearest neighbours (Euclidean Generations 10 Distance) applied with respect to the dense matrix. The obtained Cross-over Rate 0.9 search heuristic is then used by a CSP solver to provide an accurate Mutation Rate 0.05 / sizeOfGenes recommendation. Table 1. GA hyper-parameters 3 Genetic Algorithms with Clustering Heuristics Another approach to computing optimal variable and value ordering heuristics for Constraint Satisfaction Problems is to employ genetic The number of clusters for the Cluster and Learn approach [9] was algorithms. set to 4 for simplicity reasons. For each test case, the average per- Genetic algorithms are a subclass of Evolutionary Algorithms in- formance metrics (consistency and prediction quality) are calculated spired by the idea of natural selection. The algorithm starts with a and discussed in Section 5. random population of random individuals (the population can be seen as the solution to the problem, for example a set of variable 5 Evaluation Results assignments), which is iteratively improved generation by genera- tion. An improvement of the population in the current generation is According to the results depicted in the following figures, the ap- achieved by selecting the most appropriate individuals through a fit- proach of Erdeniz et al. [10] and Erdeniz and Felfernig [9] perform ness function (in our case based on the satisfaction of problem’s con- similarly. It can also be observed that two approaches perform better straints), and by modifying the genome of such individuals in order in terms of consistency, and only slightly better in terms of prediction to compose the next generation. quality with respect to basic matrix factorization. 1 Erdeniz and Felfernig [9] have proposed Cluster and Learn, an ap- MF-only proach that first uses k-means clustering and then applies a genetic 0.9 MF with CSP solving 0.8 GA with CSP solving algorithm to learn heuristics for solving the graph colouring problem. Consistency[percentage] In the first phase, Cluster and Learn performs a clustering operation 0.7 based on the euclidean distance between two user requirements. A 0.6 genetic algorithm is then applied to the obtained clusters in order to 0.5 minimize the runtime of CSP solving, returning the optimal variable 0.4 and value ordering heuristics. 0.3 0.2 0.1 4 Methodology 0 0 1 2 3 4 5 6 7 8 9 In this paper, we compare the performance of both the work of Er- Number of missing assignments in test CSPs deniz et al. [10] and Erdeniz and Felfernig [9] in terms of overall achieved consistency and prediction quality. While Erdeniz et al. [9] have evaluated their approach in terms of runtime, in the scenario of active configuration, consistency and prediction quality are of funda- mental relevance to assure a high user satisfaction, and thus ensure a positive interaction with the configurator. In this work, we provide a more detailed evaluation, that compares these two approaches with respect to the consistency and prediction quality of recommended configurations. 1 [8] Juliana Alves Pereira, Pawel Matuszyk, Sebastian Krieter, Myra MF-only Spiliopoulou, and Gunter Saake, ‘A feature-based personalized rec- 0.9 MF with CSP solving ommender system for product-line configuration’, in Proceedings of Prediction Quality[percentage] 0.8 GA with CSP solving the 2016 ACM SIGPLAN International Conference on Generative Pro- 0.7 gramming: Concepts and Experiences, GPCE 2016, p. 120–131, New 0.6 York, NY, USA, (2016). Association for Computing Machinery. 0.5 [9] Seda Polat Erdeniz and Alexander Felfernig, ‘Cluster and learn: Cluster-specific heuristics for graph coloring’, in 12th International 0.4 Conference on the Practice and Theory of Automated Timetabling 0.3 (PATAT’18), pp. 401–404, (2018). 0.2 [10] Seda Polat Erdeniz, Alexander Felfernig, Müslüm Atas, and Ralph 0.1 Samer, ‘Matrix factorization based heuristics for constraint-based rec- ommenders’, in SAC ’19, Proceedings Proceedings of the 34th ACM/SI- 0 GAPP Symposium on Applied Computing, pp. 1655–1662, United 0 1 2 3 4 5 6 7 8 9 Number of missing assignments in test CSPs States, (2019). Association of Computing Machinery. [11] Jorge Rodas-Silva, José A. Galindo, Jorge Garcı́a-Gutiérrez, and David Consistency Benavides, ‘Selection of software product line implementation compo- In terms of consistency, we can observe stable and high consis- nents using recommender systems: An application to wordpress’, IEEE tency of recommended variable assignments. In specific, as shown Access, 7, 69226–69245, (2019). in the first figure, by using the heuristics obtained with Cluster and Learn and with the approach integrating Matrix Factorization with Constraint solving, we are able to recommend variable assignments which are always consistent. The improvement is significant with re- spect to an approach that would simply rely on matrix factorization, especially when the number of missing variable assignments in the test set increases. In other words, consistency is not guaranteed when using matrix factorization only. Prediction Quality With respect to prediction quality, all approaches perform simi- larly, showing an abrupt decay in quality as the missing variable as- signments increase. 6 Conclusion and Future Work We have evaluated and compared two previously proposed value or- dering heuristics, [9] and [10], that improve both the runtime and quality of achieved recommendations in the context of active prod- uct configuration. We observed compelling growth in terms of the consistency of the two approaches, when compared with an approach relying on matrix factorization alone. We foresee potential in machine learning-based heuristics for con- straint solving to be applied in the scope of active configuration, multi-configuration, and reconfiguration. Consequently, we call for further research in this direction, for example, using a different set of learning models, for instance artificial neural networks. REFERENCES [1] Juliana Alves Pereira, Pawel Matuszyk, Sebastian Krieter, Myra Spiliopoulou, and Gunter Saake, ‘Personalized recommender systems for product-line configuration processes’, Computer Languages, Sys- tems Structures, 54, (02 2018). [2] Robin Burke, ‘Hybrid recommender systems: Survey and experiments’, User Modeling and User-Adapted Interaction, 12, (11 2002). [3] Andreas Falkner, Alexander Felfernig, and Albert Haag, ‘Recommen- dation technologies for configurable products’, AI Magazine, 32(3), 99– 108, (Oct. 2011). [4] Alexander Felfernig and Robin Burke, ‘Constraint-based recommender systems: technologies and research issues.’, p. 3, (08 2008). [5] Alexander Felfernig, Lothar Hotz, Claire ONeill, and Juha Tiihonen, Knowledge-Based Configuration: From Research to Business Cases, 05 2014. [6] Chris Groër, Bruce Golden, and Edward Wasil, ‘A library of local search heuristics for the vehicle routing problem’, Mathematical Pro- gramming Computation, 2, 79–101, (06 2010). [7] Yehuda Koren, Robert Bell, and Chris Volinsky, ‘Matrix factoriza- tion techniques for recommender systems’, Computer, 42(8), 30–37, (2009).