Genetic Algorithms Speciation for Finding Global Optimum in Combinatorial Optimization Problems

Genetic Algorithm is a commonly used algorithm to solve combinatorial optimization problems. It can effectively explore the solution space, preserve good solutions and provide heuristic search. However, parents are randomly chosen to produce offspring in original Genetic Algorithm. This may result in inbreeding, reducing the diversity in population and finally finding local optimal solutions instead of global optimal solutions. To address this problem, this thesis proposed a new genetic algorithm, which we name it Graph-based Genetic Algorithm. It views the whole population and kinship as a graph and introduces community detection on this graph. Comparative evaluations against original Genetic Algorithm on benchmark instances demonstrate the superior performance of our proposed genetic algorithm, showing its potential as an innovative and efficient solution for combinatorial optimization problems.