On integrating an Iterated Variable Neighborhood Search within a bi-objective Genetic Algorithm: Sum Coloring of Graphs Case Application
| Autor: | Jouhaina Chaouachi Siala, Hend Bouziri, Olfa Harrabi |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Theoretical computer science
Applied Mathematics Crossover 0102 computer and information sciences 02 engineering and technology Resolution (logic) 01 natural sciences Schema (genetic algorithms) 010201 computation theory & mathematics Iterated function Mutation (genetic algorithm) Genetic algorithm 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics 020201 artificial intelligence & image processing Graph coloring Variable neighborhood search Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics. 66:55-62 |
| ISSN: | 1571-0653 |
| DOI: | 10.1016/j.endm.2018.03.008 |
| Popis: | The minimum sum coloring of graphs is a variant of the classical graph coloring problem which is known to be NP-hard. The problem consists on minimizing the sum colorings of different graph vertices. In this paper, we propose a new bi-objective model for the underlying problem. We also propose for the resolution a hybrid schema which combines a bi-objective genetic algorithm with an Iterated Variable Neighborhood Search. The proposed approach relies on the use of different dedicated evolutionary operators mainly crossover and mutation. We also note two important features of the Variable Neighborhood Search: the use of destroy/repair method for shaking step and a multi-neighborhood search. Combined methods led us to preliminary promising results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect