Solving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms
A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of constraint satisfaction problem. When the memory required to apply bucket elimination is too high, a heuristic method based on it (denominated mini-buckets) can be used to calculate bounds for the optimal solution. Nevertheless, the curse of dimensionality makes these techniques impractical on large scale problems. In response to this situation, we present a memetic algorithm for WCSPs in which bucket elimination is used as a mechanism for recombining solutions, providing the best possible child from the parental set. Subsequently, a multi-level model in which this exact/metaheuristic hybrid is further hybridized with branch-and-bound techniques and mini-buckets is studied. As a case study, we have applied these algorithms to the resolution of the maximum density still life problem, a hard constraint optimization problem based on Conways game of life. The resulting algorithm consistently finds optimal patterns for up to date solved instances in less time than current approaches. Moreover, it is shown that this proposal provides new best known solutions for very large instances.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Adapting Stochastic Search For Real-time Dynamic Weighted Constraint Satisfaction
This work presents two new algorithms for performing constraint satisfaction. The first algorithm presented, DMaxWalkSat, is a constraint solver specialized for solving dynamic, weighted constraint satisfaction problems.…
PyCSP3: Modeling Combinatorial Constrained Problems in Python
In this document, we introduce PyCSP$3$, a Python library that allows us to write models of combinatorial constrained problems in a declarative manner. Currently, with PyCSP$3$, you can write models of constraint satisfa…
Solving Combinatorial Counting Problems with Weighted First-Order Model Counting
Combinatorial counting problems pervade artificial intelligence, statistics, and discrete mathematics. Whether the task is enumerating subsets, multisets, permutations, partitions, or compositions under structural and ar…
A Hybrid APM-CPGSO Approach for Constraint Satisfaction Problem Solving: Application to Remote Sensing
Constraint satisfaction problem (CSP) has been actively used for modeling and solving a wide range of complex real-world problems. However, it has been proven that developing efficient methods for solving CSP, especially…
Object RecognitionMemetic Viability Evolution for Constrained Optimization
The performance of evolutionary algorithms can be heavily undermined when constraints limit the feasible areas of the search space. For instance, while Covariance Matrix Adaptation Evolution Strategy is one of the most e…
Evolutionary Algorithms