The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences
Publications Copernicus
Download
Citation
Articles | Volume XLIV-4/W3-2020
Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XLIV-4/W3-2020, 117–120, 2020
https://doi.org/10.5194/isprs-archives-XLIV-4-W3-2020-117-2020
Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XLIV-4/W3-2020, 117–120, 2020
https://doi.org/10.5194/isprs-archives-XLIV-4-W3-2020-117-2020

  23 Nov 2020

23 Nov 2020

A NOVEL GREEDY GENETIC ALGORITHM TO SOLVE COMBINATORIAL OPTIMIZATION PROBLEM

M. A. Basmassi1, L. Benameur2, and J. A. Chentoufi1 M. A. Basmassi et al.
  • 1ISO Laboratory, Faculty of Sciences, Ibn Tofail University Kenitra, Morocco
  • 2LIROSA Laboratory, Faculty of Sciences, Abdelmalik Essaadi University Tetouan, Morocco

Keywords: Greedy Sequential Algorithm, Genetic Algorithm, Combinatorial Optimization Problem, Graph Coloring, Computational Intelligence, Chromatic Number

Abstract. In this paper, a modified genetic algorithm based on greedy sequential algorithm is presented to solve combinatorial optimization problem. The algorithm proposed here is a hybrid of heuristic and computational intelligence algorithm where greedy sequential algorithm is used as operator inside genetic algorithm like crossover and mutation. The greedy sequential function is used to correct non realizable solution after crossover and mutation which contribute to increase the rate of convergence and upgrade the population by improving the quality of chromosomes toward the chromatic number. Experiments on a set of 6 well-known DIMACS benchmark instances of graph coloring problem to test this approach show that the proposed algorithm achieves competitive results in comparison with three states of art algorithms in terms of either success rate and solution quality.