In the last years it has been observed that the fields of constraint programming and data mining interact: data mining techniques can improve constraint solving, and constraints are inherent while mining. In the current research these two fields are joined under the evolutionary computing framework. The evolutionary algorithms find difficulties in solving constraint satisfaction problems. The performance of metaheuristics can be improved by hybridization with other techniques. We verify how some specific data mining techniques can help the evolutionary search for CSPs solving.

The information mined from the previous steps of the evolutionary algorithm is used to guide the algorithm further. The proposed approach employs association rules, generated from the past experience of the algorithm. After the archive of previous best solutions has been sufficiently (re)filled, a data mining module is called to find association rules between variables and values.

Two different approaches were developed, based on the idea of using association rules mining to guide the evolutionary search. In the first case, the association rules are applied to all individuals only after the call of the Apriori algorithm in order to improve the current solutions. The idea is to have a boosting-like improvement from time to time. In the second approach, the association rules are used at each step of the algorithm. The information stored inside the association rules is used either as a separate step by applying the rules on the whole population of individuals after the call of the genetic operators, or inside the genetic operators. The mutation operator selects the most promising value for the variable with a probability that depends on a learning factor and a heuristic factor. The learning factor is based on the best patterns previously found from the mined association rules. A new escaping local optima strategy which uses the mined rules is also proposed.

• Date début : 01.09.2014
• Date fin : 31.08.2015
• Montant: 100 100 CHF
• Financement : Scientific Exchange Programme (SCIEX)

[1] M. Raschip, C. Croitoru, K. Stoffel. Using association rules to guide evolutionary search in solving constraint satisfaction, in Proceedings of IEEE Congress on Evolutionary Computation, CEC 2015, IEEE, May 25-28, 2015

[2] M. Raschip, C. Croitoru, K. Stoffel. Guiding evolutionary search with association rules for solving weighted CSPs. In Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, ACM, pages 481-488, 2015

[3] R. Necula, M. Breaban, M. Raschip. Performance Evaluation of Ant Colony Systems for the Single-Depot Multiple Traveling Salesman Problem, in Proceedings of the 10th International Conference Hybrid Artificial Intelligent Systems, HAIS 2015, Springer, Lecture Notes in Computer Science, vol. 9121, pages 257-268, 2015.

[4] R. Necula, M. Raschip, M. Breaban. Balancing the subtours for Multiple TSP approached with ACS: clustering-based approaches vs. MinMax formulation, in Proceedings of EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation, Advances in Intelligent Systems and Computing, Springer, Iasi, Romania, June 2015