When to use Tabu Search with Genetic Algorithms and when not?

Tabu Search may be using at Genetic Algorithms.

Genetic Algorithms may need many generations to get a success so running at high performance is important for them. Tabu Search is for enhancement for avoiding local maximums and good with memory mechanism to get better success through the iterations. However Tabu Search makes the algorithm more slower as usual beside its benefits.

My question is:

Is there any research about when to use Tabu Search with Genetic Algorit开发者_开发百科hms and when not?

Generally speaking, GAs spend a lot of time sampling points that are trivially suboptimal. Suppose you're optimizing a function that looks like a couple of camel humps. GAs will dump points all over the place initially, and slowly converge to the points being at the top of the humps. However, even a very simple local search algorithm can take a point that the GA generates on the slope of a hump and push it straight to the top of the hump essentially immediately. If you let every point the GA generates go through this simple local optimization, then you end up with a GA searching only the space of local optima, which generally will greatly improve your chances of finding the best solutions. The problem is that when you start on real problems instead of camel humps, simple local search algorithms often aren't powerful enough to find the really good local optima, but something like tabu search can be used in their place.

There are two drawbacks. One, each generation of the GA goes much more slowly (but you need many fewer generations usually). Two, you lose some diversity, which can cause you to converge to a suboptimal solution more often.

In practice, I would always include some form of local search inside a GA whenever possible. No Free Lunch tells us that sometimes you'll make things worse, but after ten years or so of doing GA and local search research professionally, I'd pretty much always put up a crisp new $100 bill that says that local search will improve things for the majority of cases you really care about. It doesn't have to be tabu search; you could use Simulated Annealing, VDS, or just a simple next-ascent hill climber.

When you combine multiple heuristics together, you have what's referred to as a hybrid-heuristic.

It has been a trend in the last decade or so to explore the advantages and disadvantages of hybrid-heuristics in the optimisation "crowd".

There are literally hundreds of papers available on the topic and a lot of them are quite good. I have seen papers which employ a local-search (hill-climbing, not Tabu) for each offspring at each generation of GA to direct each offspring to the local optimum. The authors report good results. I have also seen papers which use a GA to optimise the cooling schedule of a simulated annealing algorithm for both a particular problem instance and also for a general case and have good results. I've also read a paper which adds a tabu list to a simulated annealing algorithm so that it prevents revisiting solutions it has seen in the past n iterations, unless some aspiration function is satisfied.

If you're working on timetabling (as your other comment suggests), I suggest you read some papers from PATAT (practice and theory in automated timetabling), particularly from E.K.Burke and P.Brucker who are very active and well-known in the field. A lot of the PATAT proceedings are freely available.

Try a Scholar search like this:

http://scholar.google.com/scholar?q=%22hybrid+heuristics%22+%22combinatorial+optimization%22+OR+timetabling+OR+scheduling&btnG=&hl=en&as_sdt=0%2C5&as_ylo=2006

It is very difficult to prove the convergence of these sorts of heuristics mathematically. I have seen a Markov chain representation of simulated-annealing which shows upper- and lower-bounds of convergence and there exists something similar for GA. Often you can use many different heuristics on a single problem, and only experimental results will show which is better. You may need to do computational experiments to see if your GA can be improved with a TS or more generic local search, but in general, hybrid heuristics seem to be the go these days.

I haven't combined tabu search with genetic algorithms yet, but I have combined it with simulated annealing. It's not really tabu search, it's more enhancing the other algorithm with tabu.

From my experience, checking if something is tabu doesn't have a high performance cost.