0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure I fully understand your concerns, but one natural way of measuring the fitness of the population, as a whole, is to calculate the average fitness (or something similar) and plot that as a function of time (number of generations). Is this what you're asking? I don't actually know if this is the best way of doing it, but this is what comes to my mind right now. The other thing I don't understand is why you're confused about how to calculate the fitness. The definition of the fitness really depends on the problem. If you need to define how to calculate it for your problem. $\endgroup$
    – nbro
    Jan 1 at 19:25
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Interesting thanks. I'm thinking of genetic algorithms that are used in adversarial problems, so something that was once fit....could now not be fit, and vice versa, and how that could be detected with an algorithm. So I appreciate what you're saying. $\endgroup$ Jan 4 at 21:26
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This answer can be improved by providing links to references that support your claims. $\endgroup$
    – nbro
    Jan 6 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.