--- title: "Constraint Solving and Optimization Using Evolutionary Techniques" authors: - "Mahdi Bidar" - "Malek Mouhoub" doi: "10.24963/ijcai.2019/901" url: "https://ijcai.org/proceedings/2019/901" pdf: "https://ijcai.org/proceedings/2019/0901.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "6424-6425" track: "Doctoral Consortium" keywords: - "Constraints and SAT: Constraints: Solvers and Tools" - "Constraints and SAT: Constraint Satisfaction" - "Heuristic Search and Game Playing: Combinatorial Search and Optimisation" - "Heuristic Search and Game Playing: Heuristic Search" --- # Constraint Solving and Optimization Using Evolutionary Techniques Mahdi Bidar, Malek Mouhoub *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 6424-6425. DOI: [10.24963/ijcai.2019/901](https://doi.org/10.24963/ijcai.2019/901) ## Abstract Constraint Solving and Optimization is very relevant in many real world applications including scheduling, planning, configuration, resource allocation and timetabling. Solving a constraint optimization problem consists of finding an assignment of values to variables that optimizes some defined objective functions, subject to a set of constraints imposed on the problem variables. Due to their high dimensional and exponential search spaces, classical methods are unpractical to tackle these problems. An appropriate alternative is to rely on metaheuristics. My thesis is concerned with investigating the applicability of the evolutionary algorithms when dealing with constraint optimization problems. In this regard, we propose two new optimization algorithms namely Mushroom Reproduction Optimization algorithm (MRO) and Focus Group Optimization algorithm (FGO) for solving such problems. ## Full text ## 1 Introduction Constraint Satisfaction Problems (CSPs) provide an appropriate framework to formulate many real life combinatorial problems including scheduling, planning and configuration. More formally, a CSP consists of a set of variables, each defined over a discrete and finite set of values, and a set of constraints restricting the values that the variables can simultaneously take. Solving a CSP consists of finding a complete assignment of values to variables such that all the constraints are satisfied. In practice, we might face situations where the traditional CSP cannot be directly employed. This includes over-constrained problems where a complete solution does not exist, and the goal is to find a solution satisfying most of constraints. We also have problems where constraints are changing over time, and in this regard, we need to find in an incremental manner, solutions satisfying old and new constraints. Finally, we might be dealing with those problems where the constraints or the variables values do not have the same priority or preference. Overconstrained problems can be solved with a variant of CSPs called MAXCSP [Larrosa et al., 1999]. Problem including dynamic constraints can be tacked using Dynamic CSPs (DCSPs) [Dechter et al., 1988]. Here, a valid solution for the current CSP may not be valid when constraints are added. Local repair approaches can be used in this case, is an effective manner, with minimal perturbation [Roose et al., 2000]. Problems where constraints and/or variables values have difference preferences can be modeled using a Weighted CSP (WCSP). A WCSP is a CSP in which feasible solutions come with different preferences [Schiex et al., 1995]. Here, we consider two types of constraints: soft constraints that can be violated with associated costs and hard constraints that must be satisfied. The goal is to find a solution that satisfies all the hard constraints and minimizes the total cost related to soft constraints. CSPs can be tackled using exact methods including backtracking and its variants using constraint propagation. Given that these latter methods are exponential in time cost, O(d n ) where d is the domain size and n is the number of variables, an alternative is to use metaheuristics that trade running time for the quality of the returned solution. Although the already developed metaheuristic algorithms provide satisfactory results, they are not capable to deal with all the CSP variants we mentioned earlier. Hence, introducing new metaheuristic optimization algorithms are necessary. The aim of this work is to investigate the applicability of nature-inspired algorithms in dealing with CSPs including the three variants we listed before as well as other optimization problems. ## 2 Contributions We have applied Firefly and Particle Swarm Optimization algorithms to CSPs [Mahdi Bidar et al., 2018], DCSPs and WCSPs. In this regard, we have adapted these techniques so they can work in discrete problem spaces. Another aspect we have focused on is dealing with local optimum. To overcome this issue, we applied the chaos theory to the Firefly algorithm. Chaotic parameters boost the diversity of generating solutions, which results in exploring more quality solutions. These latter reduce the chances of being stuck in local optimum. We also developed a new self-adaptive Firefly algorithm. Self-adaption enables the search to adjust the exploration-exploitation balance considering the progress trend of the algorithm. The achieved dynamism of these methods enables the algorithm to achieve higher quality solution. Several experiments evaluating our proposed algorithms have been conducted on randomly generated instances. The results we obtained so far are very promising. We also employed fuzzy system in order to improve the performance of the firefly algorithm when dealing with constrained engineering problems [Mahdi Bidar et al., 2018]. The application of fuzzy system in our work was to keep the exploration-exploitation of the firefly algorithm in balanced, therefore reduce the risk of getting stuck in local optimum solutions. The second aspect focuses on developing new approaches to deal with optimization problems more effectively. In this regard, we have conducted an investigation on a natural phenomena namely mushrooms lifecycles, and also human social behavior for problem solving through group discussion, in order to develop new optimization algorithms. Based on these studies, two new metaheuristic algorithms have been proposed, namely Mushroom Reproduction Optimization algorithm (MRO) [Mahdi Bidar et al., 2018] and Focus Group Optimization algorithm (FGO) [Edris Fattahi et al., 2018]. MRO was inspired by the reproduction and growth mechanisms of mushrooms in nature. It follows the process of discovering rich areas by spores to grow and develop their own colonies. On the other hand, FGO inspired by the behavior of a focus group in sharing their ideas (solutions) about a specific subject and improving their solutions based on the cooperation and discussion. Both algorithms have been successfully applied to a wide range of constrain problems including standard benchmark functions and realworld problems. The results obtained so far are appealing. ## 3 Conclusion and Future Work This research investigates the applicability of metaheuristic algorithms in dealing with CSPs, their variants and other optimization problems. This is particularly important especially given that many real-world problems such as scheduling, planning, configuration, timetabling, resource allocation and vehicle routing can be represented and solved using CSPs or their variants. In this regard, we successfully applied a modified version of the Firefly algorithm to CSPs, WCSPs and DCSPs. We have also developed two new optimization algorithms namely MRO and FGO algorithms. These algorithms will be applied in the near future to different types of CSPs. We also plan to include user preferences when tackling CSPs. Here, preferences can be qualitative or quantitative. While a WCSP can be the suitable framework for quantitative preferences, qualitative preferences can be represented using the Conditional-Preference Networks (CP-Net) graphical model. An extension of this model to constraints will allow us to represent both constraints and ordinal preferences. Our proposed evolutionary techniques can then be used to solve constraints and preferences represented as a WCP or a constrained CP-net. ## References 1. [Larrosa et al., 1999] Larrosa, Javier, Pedro Meseguer, and Thomas Schiex. "Maintaining reversible DAC for Max- CSP." Artificial Intelligence 107, no. 1 (1999): 149-163. 2. [Dechter et al., 1988] Dechter, Rina, and Avi Dechter. Belief maintenance in dynamic constraint net- works. University of California, Computer Science Depart- ment, 1988. 3. [Roose et al., 2000] Roos, Nico, Yongping Ran, and Jaap Van Den Herik. "Combining local search and constraint propagation to find a minimal change solution for a dynamic csp." In International Conference on Artificial Intelligence: Methodology, Systems, and Applications, pp. 272-282. 4. [Schiex et al., 1995] Schiex, Thomas, Helene Fargier, and Gerard Verfaillie. "Valued constraint satisfaction problems: Hard and easy problems." IJCAI (1) 95 (1995): 631-639. 5. [Mahdi Bidar et al., 2018] Mahdi Bidar, Malek Mouhoub, and Samira Sadaoui. "Discrete Firefly Algorithm: A New Metaheuristic Approach for Solving Constraint Satisfaction Problems." In 2018 IEEE Congress on Evolutionary Com- putation (CEC), pp. 1-8. IEEE, 2018. 6. [Mahdi Bidar et al., 2018] Mahdi Bidar, Hamidreza Rashidy Kanan, Malek Mouhoub, and Samira Sadaoui. "Mushroom Reproduction Optimization (MRO): A Novel Nature- Inspired Evolutionary Algorithm." In 2018 IEEE Congress on Evolutionary Computation (CEC), pp. 1-10. IEEE, 2018. 7. [Edris Fattahi et al., 2018] Edris Fattahi, Mahdi Bidar, and Hamidreza Rashidy Kanan. "Focus Group: An Optimization Algorithm Inspired by Human Behavior." International Journal of Computational Intelligence and Applications 17, no. 01 (2018): 1850002. 8. [Mahdi Bidar et al., 2018] Mahdi Bidar, Samira Sadaoui, Malek Mouhoub, and Mohsen Bidar. "Enhanced Firefly Algorithm Using Fuzzy Parameter Tuner." Computer and Information Science 11, no. 1 (2018): 26.