What is niching scheme?
I am currently reading a paper on using GA in constrained optimization problems. At some part, it is talking about applying niching scheme on the individuals (or the Pareto front they make).
It seems like a typical selection scheme but as I searched, I couldn't find a good explanation for it.
Can someone explain to me as simply as possible, what niching scheme is?
Answer
Simply put, niching is a class of methods that try to converge to more than one solution during a single run.
Niching is the idea of segmenting the population of the GA into disjoint sets, intended so that you have at least one member in each region of the fitness function that is "interesting"; generally by this we mean that you cover more than one local optima.
Imagine a function like f(x) = sin(x^2).
A normal GA will eventually converge towards one of the two global minima. Which one depends on the initial population and the random genetic drift occurring throughout the run, but eventually, you'll get n copies of one individual in one or the other valleys. For example, if you looked at such a GA when it was almost converged, you might see something like
Niching is a general class of techniques intended to end up with roughly half the population converging in each minima (or possibly even including a few members in the less fit minimum at x=0).
As I just said, niching is not really an algorithm so much as a general class of algorithms. One such method is Goldberg's fitness sharing. In this method, we define a niche radius sigma. Any two individuals closer together than this sigma are considered to be in the same niche, and thus must share their fitness values (think of this as being a function that decreases fitness of each member of the niche the more densely populated the niche is). You then have the GA operate on the shared fitness values instead of the raw ones.
The idea here is that you discourage convergence to a single region of the fitness function by pretending there are limited resources there. The more individuals try to move in, the worse off they all are. The result is that as the GA converges to a single local optimum somewhere, the fitness of that optimum decreases because of the increased competition within the niche. Eventually, another region of the fitness landscape becomes more attractive, and individuals migrate over there. The idea is to reach a steady state -- a fixed point in the dynamics -- where an appropriate representation of each niche is maintained.
Sharing is hard because of the need to manually set the niche radius, and the algorithm is quite sensitive to this choice. Another alternative is crowding. In particular, you might look up "Deterministic Crowding", which was a popular method for a period of time. In crowding based methods, instead of dealing with an explicit radius, we work by limiting the set of individuals that a new offspring can replace to some set of similar solutions, for example an offspring might be allowed to replace only one of its parents. The effect is to try to prevent replacing a unique individual with one that is very similar to a dozen others in the population and thus to preserve diversity that way.