Un algoritmo evolutivo para resolver el problema de Coloración Robusta
Đã lưu trong:
| Nhiều tác giả: | , , , |
|---|---|
| Định dạng: | artículo original |
| Trạng thái: | Versión publicada |
| Ngày xuất bản: | 2005 |
| Miêu tả: | Let G and G be two complementary graphs. Given a penalty function defined over the edges of G, it is said that the rigidity of a k-coloring of G is the summation ofthe penalties of the edges of G that join vertices whose endpoint are equally colored. Based on this previous definition, the Robust Coloring Problem is set when searching the valid k-coloring of minimum rigidity. Yáñez and Ramírez proved that this is an NP-hard problem. In this work we present an evolutive algorithm based in the scatter search technique, which obtains optimal solutions for those instances for which an optimal solution is known, and obtains the best known solutions compared to other heuristics, such as: simulated annealing, tabu search and partial enumeration. |
| Quốc gia: | Portal de Revistas UCR |
| Tổ chức giáo dục: | Universidad de Costa Rica |
| Repositorio: | Portal de Revistas UCR |
| Ngôn ngữ: | Español |
| OAI Identifier: | oai:portal.ucr.ac.cr:article/255 |
| Truy cập trực tuyến: | https://revistas.ucr.ac.cr/index.php/matematica/article/view/255 |
| Từ khóa: | Scatter search graph coloring heuristics combinatorial optimization discrete optimization Búsqueda dispersa coloración de gráficas heurísticas optimización combinatoria optimización discreta |