An attempt at the solution of the Keller Conjecture is possible because of a very good algorithm to find maximum cliques developed by Soule and Foster [SF95]. Because the algorithm uses a GA to do the search the possible solutions, or the population, needs to be diverse so the best are distinguishable from the rest. The Keller graphs do not have this feature, they are mostly uniform. After a certain point the GA can not tell the difference between one possible solution and another and makes no progress. A solution to this problem would be to add some kind of non-uniformity to the Keller graphs.
One way to add non-uniformity to a Keller graph is to remove nodes in sub-graphs that are ``useless'' in terms of clique size. When the GA finds a clique it hasn't seen before stop and try to add every node to the clique one at a time checking to see if the new node increases the size of the clique. If it doesn't increase with any node then remove all the nodes in that clique from the graph and restart the GA. This shouldn't be done to much or we could destroy the graph; making the results obtained useless. A limited number of node removals could increase the effectiveness of the GA on the Keller graphs.
Adding extra information to the Keller graphs may be useful also. If we give each node a color value being careful to group similar colors together on the graph this will increase non-uniformity of the graph. To use this color information we would need to extend the GA so that it would try to mate only solutions that have similar colors. With the GA trying stay within one color the size of the graph would be effectively reduced to the number of nodes in one color.
Along with adding one or both of the above ideas to the algorithm the GA as is could be optimized. Storing calculations that are costly to perform and may not change value between generation would speed the GA up overall. Certain parts of the GA may be inefficiently implemented tightening up the algorithm would also increase performance.
A solution to the Keller Conjecture is possible but much work needs to be done before we see anything resolved.