How to detect that the fitness landscape of a genetic algorithm is changing over time?

Question

I understand that in each generation of a genetic algorithm, that generation must re-prove it's fitness (and then the fittest of that population is taken for the next population).

In this case, I guess it's a presumption that if you take the fittest of each generation, and use them to form the basis of the next generation, that your population as a whole is getting fitter with time.

But algorithmically, how can I detect this? If there's no end goal known, then I can't measure the error/distance from goal? So how can you tell how much each generation is becoming fitter by?

Answer 1

There is no exact way to assess that a genetic algorithm has located a global optima. Indeed there may be multiple global optima. You must fall back to heuristic methods. The fitness of a population is the maximum fitness of any individual. Unless specific measures are taken to maintain diversity the population will converge to an optima, local or global. At that point all individuals will, except for mutation, be identical. You could take the fittest individual of such a population as your solution, but you will not know if the solution is a global or local optima.

Two reasonable heuristics are these. First, run the algorithm till it converges and maintains its fitness for a number of further generations. Or second run the algorithm multiple times, and take the fittest of all the located solutions. Neither is exact.

Answer 2

There is no general method to detect a change in the fitness landscape, since changes can be very local and can occur in just a small area of the fitness landscape. For this reason nature inspired optimization algorithms usually maintain a diversified population to cope with environmental changes. a common mechanism is using several sub-populations and ensuring that these sub-populations do not overlap. Also, there are some heuristics proposed that can help the algorithms in detecting changes. for instance if you are using multiple sub-populations, you can double test one element of each sub-population at some generation to find out if an environmental change has occurred or not. albeit, there are some comprehensive heuristics have been proposed for change detection, like the one proposed in [R. Mukherjee, S. Debchoudhury, S. Das, Modified differential evolution with locality induced genetic operators for dynamic optimization]. In my opinion, Use simple methods. for instance, at the keep a small by diverse set of population members at some k generations, and reevaluate them after k generations to detect change.