Preseeding a Genetic Algorithm

Question

I am working on a very large scale problem, I have an heuristic that gives a reasonably good solution in addition to the Genetic Algorithm heuristic which performs very well. I was wondering if there is any gain in pre-seeding the GA with the heuristics solution and if so how.

Thanks 2t

Answer 1

That very much depends on the heuristic, and your problem.

If you know this heuristic has a tendency of getting close to the global optimum, then it may be a good idea, as the GA may explore "around" this solution and find an optimal/closer to optimal solution.

The problem is, that when you pre-seed the GA with a good solution, it will have a huge advantage over other randomly generated solutions and will probably be selected many times to perform crossover, which means, if the heuristic gave you a local optimum, you might draw the GA towards that solution.

Another idea is to seed the GA in the middle of the process. let it run for half the generations and then inject it with the heuristic solution. then you have a smaller chance of dragging it to the heuristic solution if it was only a local optimum.

In general, since we're talking about heuristics and probabilistic models, it's better to benchmark all possibilities and see what works best for you, as these statements are usually problem-dependent.

Answer 2

In your case, I would go with a trajectory-based algorithm such as simulated annealing, tabu search or variable neighborhood search (VNS). When you have a single good point already you might already want to focus on a certain sub-region more intensively. VNS might be a good compromise in that it allows you to also make bigger changes and gradually increase optimization with respect to larger parts of the search space.

Answer 3

Other thing you can do is switching between different heuristics. For example in ANN training GA can be switched with BP in particular moments and voice versa.