patternMinor
Does local optimization in a genetic algorithm decrease diversity?
Viewed 0 times
localdiversityoptimizationgeneticalgorithmdoesdecrease
Problem
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?
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?
Solution
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.
-
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.
Context
StackExchange Computer Science Q#62919, answer score: 5
Revisions (0)
No revisions yet.