Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
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 Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : mercredi 9 juin 2021 - 15:04:13
Dernière modification le : vendredi 11 mars 2022 - 11:44:04

Lien texte intégral

Identifiants

Collections

Citation

Daniel 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

8