Are you using a steady-state genetic algorithm approach? Some other heuristic approach, a different EA?
What sort of crossover (edge recombination) and are you using mutation as well?
How are you performing fitness evaluation on a given set of candidate solutions?