Constraint Solving and Optimization Using Evolutionary Techniques

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.