I am trying to develop a genetic algorithm to solve a graph colouring problem.The problem is the standard graph colouring problem, given a graph $G = (V,E)$ where $V$ is the set of vertices $V=\{0 \dots n-1\}$ and $E$ is the set of edges, colour the vertices such that no two adjacent vertices are the same colour and the objective is to minimise the number of colours used.the way i have represented it is in the following way:a population of individuals is established, each represented by an array of $n$ randomised integers in the range $0...m$ where $m$ is a number (representing the number of colours used) generated between $1...n$fitness is determined according to the following objective function:$min \sum_{i=1}^m(2|B_i||C_i|) - \sum_{i=1}^m|C_i|^2$where, $B_i$ is the set of edges which have two vertices coloured with colour $i$,$C_i$ is the set of vertices coloured with colour $i$the intuition behind this funciton is to minimise the number of violations while maximising the size of the colour classes (and hence minimise the colours used)once the individuals are ranked by fitness, parents are selected to mate in the following manner:parent_1 (m=6): [1 3 5 4 2 1|0 0 5 2]parent_2 (m=4): [2 0 1 3 0 1|0 2 1 3]* crossover applied at | *child_1: [1 3 5 4 2 1 0 2 1 3]child_2: [2 0 1 3 0 1 0 0 5 2]my problem now is that a 1 in the first subset of child_1, does not necessarily correspond to the same colour as the 1 in the 2nd subset of child_1. This does not matter before the crossover, because the values are just class labels, and are interchangable - but after the crossover has been applied, it will create relationships that weren't there and lose those that were.in an instance where the first subset of the vertices are highly connected, and the second subset are also highly connected without many connections across the crossover point, this would not be so much of a problem as it is more or less a case of connecting two disjoint graphs. but in the instance where many of the edges span the crossover point eg. (1, 8), (4, 6), etc. this becomes a large problem as the initial colour assignment matters. can anyone suggest a way to design the crossover operator such that it retains these relationships? or is this just a fundamental property of genetic algorithms, and they are not necessarily very effective for these types of problems with dependencies between variables? i just chose this problem because it seemed interesting and i wanted to get some practice implementing genetic algorithms, but maybe i should choose a more suited problem?Edit:I will use a very trivial example, just to be more explicit about my problem.for the graph $G = (V,E)$ where $V = \{0 \dots 3\}$ and $E = \{(0,1),(0,2),(0,3),(1,3)\}$two equally valid, equally optimal colourings would be:parent_1 (m=3): [0 1|1 2]parent_2 (m=3): [0 2|2 1]after applying crossover, the following children are generated:child_1: [0 1 2 1]child_2: [0 2 1 2]leaving vertices 1 and 3 the same colour for both offspring and therefore less fit than the previous generation. i understand that the stochastic nature of GAs can sometimes produce this kind of result, but this feels more like random search than any kind of metaheuristic behaviour where it is keeping the good features of the previous generation.applying some sort of lexicographical ordering of colour labels before mating would solve this problem for this particular very small example, but my intuition is that this wouldn't really help for larger problems as the dependencies would be much more complex.any ideas?
Genetic algorithm crossover technique for solving graph colouring problem
graph theory;genetic algorithms