Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring

Abstract :

We present a diversity-oriented hybrid evolutionary approach for the graph coloring problem. This approach is based on both generally applicable strategies and specifically tailored techniques. Particular attention is paid to ensuring population diversity by carefully controlling spacing among individuals. Using a distance measure between potential solutions, the general population management strategy decides whether an offspring should be accepted in the population, which individual needs to be replaced and when mutation is applied. Furthermore, we introduce a special grouping-based multi-parent crossover operator which relies on several relevant features to identify meaningful building blocks for offspring construction. The proposed approach can be generally characterized as “well-informed”, in the sense that the design of each component is based on the most pertinent information which is identified by both experimental observation and careful analysis of the given problem. The resulting algorithm proves to be highly competitive when it is applied on the whole set of the DIMACS benchmark graphs.

Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03255386
Contributeur : Okina Université d'Angers <>
Soumis le : mercredi 9 juin 2021 - 15:04:13
Dernière modification le : jeudi 10 juin 2021 - 03:39:57

Lien texte intégral

Identifiants

Collections

Citation

Daniel Cosmin Porumbel, Jin-Kao Hao, Pascale Kuntz. An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring. Computers and Operations Research, Elsevier, 2010, 37 (10), pp.1822 - 1832. ⟨10.1016/j.cor.2010.01.015⟩. ⟨hal-03255386⟩

Partager

Métriques

Consultations de la notice

4