1
$\begingroup$

I am evaluating a genetic algorithm that was written for a vehicle routing problem with time windows. The problem was not solved with any exact method (or with any solver). I also do not know bound of the solution. I know that at each iteration, the GA is giving better results than the initial solution. I am trying to learn the following questions:

  1. Is there any way to make sure that the GA is converging to optimal/ near optimal solution?

    So far the solution at each iteration is getting better or not getting worse than the previous iteration. But I am not sure when I should stop it and how close it is to near optimal solution. Do GAs converges to optimal solution with a finite number of iteration for a feasible problem. Right now it stops after a specific number of iteration. If a GA is run for a large number of iterations, are they supposed to converge to near optimal solution eventually? or is some information lost during crossover and mutation for which it can not reach optimal solution?

  2. Let's say we have several versions of a GA( different generation size, elite size, mutation criteria etc.). How should one determine the best of algorithm?

    I can compare which one is faster and giving better solution after running for a specific number of iterations. But are there are any tested or 'in general' methods that are used for evaluating GA performance?

$\endgroup$

1 Answer 1

3
$\begingroup$
  1. GAs tend to "converge" in the sense that the population tends to become homogeneous after a while (which I believe is known as "stagnation"). There are various things implemented by some GAs ("immigration", "island model", ...) to try to ward off premature convergence, but not everyone uses them. If the GA does converge, there is in general no guarantee that it converges to an optimal solution. The only way to know if you are at or near an optimum is to have a tight bound for the optimal value (which would have to come from outside the GA). With a discrete problem (having a bounded feasible region) and a GA using either immigration (new random solutions being added in each generation) or mutation of surviving adults, it might be possible to prove that with probability 1.0 you would eventually see an optimal solution. I'm not positive about that, and in any case "eventually" and "within your lifetime" might not be synonymous. The issue is not that the GA cannot reach an optimum ... just that it might not.

  2. As far as I know, tuning the parameters of a GA is based on a couple of criteria. One is how fast the solutions improve, or how quickly you get to an objective function that (while possibly not optimal) makes you happy. The other, which I'm pretty sure is less commonly used, is how quickly the GA stagnates. You want to avoid early stagnation. I'm not sure how many GA codes actually provide the user with measures of stagnation. You can typically tell whether the best solution has or has not improved recently, but I believe to detect stagnation you would need to look at some measure of the distribution of objective values in the population (standard deviation, interquartile range, ...). If the objective values are too close together, it may be stagnating.

Incidentally, the objective value not getting worse from iteration to iteration may be a function of parameter settings. If the GA uses "elitism" (retaining a few of the best solutions from the previous generation), the objective value will automatically be monotonic, which would not tell you anything about how the GA was doing. Also, you need to look at whether the GA is reporting "best in generation" or "best ever" (the latter obviously being monotonic). The one combination where the objective could get worse from generation to generation would be no elitism plus reporting the best in generation value.

$\endgroup$
2
  • $\begingroup$ Thanks so much for the detailed answer. Do think it is a good idea to try to find a bound (for example lower bound for minimization problem) with LP relaxation or Lagrangian or other technique before using GA? I do not have the compact formulation ready but wondering if I should try this should try to solve to find optimal solution or a lower bound with a small data set and check the GA to see how close it is to the optimal solution or the lower bound. $\endgroup$
    – mars
    Jan 6, 2022 at 21:53
  • 1
    $\begingroup$ The answer to that may depend on context. If you are writing a paper for an academic journal, it might be useful to generate a bound (maybe via Lagrangian relaxation) to show that the GA is performing "well". Personally, I would hold off doing it and wait to see whether some reviewer asked for it. If you are solving a "real-world" problem, I would wait to see if the GA solution put a smile on the boss's face, or whether the boss asked how much it might be improved. $\endgroup$
    – prubin
    Jan 7, 2022 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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