Advanced generic neighorhoood heuristics for VNS
| Autor: | Samir Loudni, Patrice Boizumault, Nicolas Levasseur |
|---|---|
| Přispěvatelé: | Equipe CODAG - Laboratoire GREYC - UMR6072, Groupe de Recherche en Informatique, Image et Instrumentation de Caen (GREYC), Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU)-Normandie Université (NU)-Université de Caen Normandie (UNICAEN), Normandie Université (NU)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Ingénieurs de Caen (ENSICAEN), Normandie Université (NU) |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
Mathematical optimization
Computer science 0211 other engineering and technologies RLFAP WCSP Experimental studies 02 engineering and technology LNS [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Neighborhood heuristics Artificial Intelligence VNS 0202 electrical engineering electronic engineering information engineering Constraint programming Local search (optimization) Electrical and Electronic Engineering Constraint satisfaction problem 021103 operations research Degree (graph theory) business.industry Heuristic Local search MaxCSP [INFO.INFO-TT]Computer Science [cs]/Document and Text Processing Variable (computer science) Control and Systems Engineering Graph (abstract data type) 020201 artificial intelligence & image processing Heuristics business |
| Zdroj: | Journal of Engineering Applications of Artificial Intelligence (EAAI) Journal of Engineering Applications of Artificial Intelligence (EAAI), 2010, 23 (5), pp.Pages 736-764. ⟨10.1016/j.engappai.2010.01.014⟩ |
| DOI: | 10.1016/j.engappai.2010.01.014⟩ |
| Popis: | International audience; Weighted CSPCSP (Constraint Satisfaction Problems) are used to model and to solve constraint optimization problems. As most WCSPWCSP are solved by local search methods that use large neighborhoods, selecting the neighborhood to explore is crucial. However, designing efficient neighborhoods is difficult and problem dependent. The very few generic heuristics defined for CSPCSP, as ConflictVar or H-PGLNS, are not well suited for WCSPWCSP. In this paper, we propose new generic neighborhood heuristics dedicated to WCSPWCSP. Our heuristics take advantage of both conflicted variables and the topology of the constraints graph. We define the concept of freedom degree of a variable to make a compromise between these two criteria, and introduce a diversification criterion by choosing non-conflicted variables connected to conflicted ones. Then we extend, in a systematic way, each proposed heuristic in order to take into account violation costs of constraints. Experiments have been performed on real life instances (RLFAP) as well as random instances (GRAPH and Kbtree) using VNS/LDS+CP (a particular instance of VNS we developed). Experiments show that our generic heuristics clearly outperform ConflictVar and H-PGLNS. Among all topological heuristics we proposed, ConflictVar-MaxDeg appears to be the best one. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|