| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 2.07 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
[Introduction] Real world problems can often be described by a set of constraints to be satisfied, where the goal is to
find a feasible solution for the problem. The use of constraints allows one to model a wide variety of problems in a straightforward manner. However, finding a solution that either satisfies all constraints or maximizes some benefit is usually difficult, as existing algorithms for both problems are NP-hard.
Furthermore, it is not always possible to satisfy all the constraints. In such cases, the goal is to find a solution that satisfies the maximum number of constraints (MMAX-CSPs) or one that satisfies the most important ones (MAX-WCSPs, where each constraint has a weight). Currently, local search is widely used to tackle these difficult problems. However, those methods are usually incomplete (i.e., they do not guarantee the optimum), and are often mislead by local optima.
This situation is usually handled by restarting the search from another starting point. It is our goal in this paper to present a parallel architecture for solving constraint satisfaction problems (AntCSP); i.e., a parallel architecture that combines the stigmergetic capabilities of Ant Colony Optimization (ACO) metaheuristics, with local search heuristics to solve MANX-CSPs and Constraint Satisfaction and Optimization Problems (CSOPs).
One of the main advantages of this approach is that no auxiliary structure is needed. The structure followed by the ants is the proof tree itself, in which the pheromones are laid. This not. only provides a very efficient implementation of pheromone updating but also a more general approach to solve CSPs. The other advantage is the use of parallelism both to have a number of ant colonies running in parallel and to have function distribution of local search procedures. This architecture thus provides a powerful tool to tackle these difficult problems by using available processing power.
Descrição
Palavras-chave
Contexto Educativo
Citação
Mendes, R., Pereira, J. R. & Neves, J. (2001, July 16-20) A parallel architecture for solving constraint satisfaction problems.[Conference paper] 4th Metaheuristics International Conference - MIC'2001. Porto, Portugal
Editora
MIC'2001 - 4th Metaheuristics International Conference
Licença CC
Sem licença CC