I want to create a hybrid genetic algorithm for a project to solve really high dimensional problems (1000+) One of my ideas is to incorporate a local optimization method within GA so each individual will be optimized to its local optima before fitness evaluation. I've read some papers on hybrid GAs with hill climbing. So I understand that doing this will allow a somewhat fairer representation of each individual's search area by preventing the GA from obtaining bad sample from good search regions. It would obviously increase the search completeness. But I was wondering if adding such a local optimization method would significantly decrease genetic variation? If so, should this be a big problem? And how can one prevent it?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
The details depend on your fitness function, which you have not shared.
With your modification, you can only ever jump from one local optimum to the slope of another. Hence, you will certainly get little diversity if
- there are few local optima or
- the local optima are far apart but you do only small steps (e.g. local mutations).
In the first case, little can be done.
In the second case, you can alleviate the effects by making larger steps. Some standard techniques like crossovers can help. You may also want to look into simulated annealing. You can also keep both the original point and it's local optimum, and select globally.
On the other hand, if there are many local optima and/or they are close together, I would expect little problems and your approach is likely to speed up the search.
-
$\begingroup$ Hi! Thanks so much for answering. I'm not really planning to solve a particular problem with this algorithm but I just wanted learn more about the nuances of hybrid GAs. But I am planning to compare the 2 algorithms with a traveling salesman problem. I guess there really isn't a way to tell how useful the local optimizer will be unless the programmer has a good idea of the search space? $\endgroup$ Aug 27, 2016 at 11:01
-
$\begingroup$ @Dniwrallets Yes. GA may look like silver bullet but they are actually quite weak a method, precisely because it is nigh impossible to predict when it will work how well. If you haven't read about the No Free Lunch Theorem, you should definitely do so! $\endgroup$– Raphael ♦Aug 27, 2016 at 12:47
$\begingroup$
$\endgroup$
Adding on Raphael's answer:
in a hybrid genetic algorithm (HGA), mutation plays a different role than it does in a "pure" GA.
The local refinement requirement of the mutation operator is unnecessary in the existence of an explicit local operator allowing the mutation operator to take a more exploratory role (see Evolutionary algorithms with local search for combinatorial optimization by Mark Land).
Using larger mutations, at least large enough to move from one basin to another, is a good idea.
you can introduce parameters to control the frequency / duration / probability of local search so reaching a balance between GA and hill climbing.
Hybrid Genetic Algorithms: A Review by Tarek El-Mihoub, Adrian Hopgood, Lars Nolle and Alan Battersby contains further details.
a nice approach you can try is to perform a local search only when the best offspring (solution) in the offspring population is also the best in the current parent population (aka BOHGA: Best Only Hybrid Genetic Algorithm).
This allows GA to explore a wide search space.
