A NOVEL GREEDY GENETIC ALGORITHM TO SOLVE COMBINATORIAL OPTIMIZATION PROBLEM
- 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.