2
$\begingroup$

Situation:

Let's say you're running a genetic algorithm to improve the way people are interacting with an online service. The alleles in each individual determine the exact behaviour of the service, the fitness of each individual is a measure of how well the interaction of users with the service configured using that individual went. - So, performance of individuals is measured continuously by people interacting with the phenotype of the individual, evaluation of the fitness value can not be repeated.

Now, when you run your algorithm, the alleles that result in the fittest individuals (= best service user experience) will become more frequent in subsequent generations, the others' frequency will decline.

In this situation, you're trying to hit a 'moving target' since the people interacting with the service are a different set of people for every individual and so many factors might have an impact on the performance of a single individual at any one time. There is no absolute 'maximum fitness' or target that can be determined in advance, you just want to optimise the user experience as well as possible.

Questions:

After X generations, some allele for a gene turns out to occur most frequently in your population at that time. Now you want to check whether this most frequently occurring allele for that gene is indeed the allele that generally results in the fittest individuals.

1) Is it a valid approach to summarise the average fitness of all individuals (from the current AND previous generations) that have each allele so you get a result like this:

For gene A:

  • the individuals that have allele 1 have an average fitness of 20
  • the individuals that have allele 2 have an average fitness of 60
  • the individuals that have allele 3 have an average fitness of 35

For gene B:

  • the individuals that have allele x have an average fitness of 70
  • the individuals that have allele y have an average fitness of 42
  • the individuals that have allele z have an average fitness of 50

And conclude that allele 2 for gene A and allele x for gene B should be the most frequently occurring in the most recent generation because those resulted in the fittest individuals so far?

2) If not, what would be the best way to evaluate the convergence and quality of your current candidate solutions in a situation like this?

3) Are there any standard ways of analysing the performance of a genetic algorithm in this kind of environment, or other useful ways of looking at the results and evaluating the impact of the algorithm?

$\endgroup$
2
$\begingroup$

1) The problem with this approach is that it is neglecting interactions between alleles themselves. If it is safe to assume that interactions are negligible or nonexistent, you can try this. Assume that possible alleles for each gene $A_i$ ($i=1,2,\ldots,n)$ are $a_1^{(i)}, a_2^{(i)}, \ldots, a_{m_i}^{(i)}$. For each allele $a_j^{(i)}$ of $A_i$ record observed fitness values of the individuals having $a_j^{(i)}$. Thus, you will create $m_i$ samples for the alleles of the gene. Then, you can start with one way ANOVA or Kruskal-Wallis test to check if there are significant differences between the fitness values. If so, proceed with appropriate post-hoc analysis.

However, be cautious with this method. Sometimes the fitness function has more than one global optimum and this approach implicitly assumes that this is not the case.

2) GA does not guarantee to find the global optimum. Instead, it is more likely to produce a good local optimum of acceptable quality most of the time, and sometimes succeed in finding the global one. Even if you run GA for multiple times on the same problem where the fitness function is deterministic, you may not find the global optimum. Convergence to the optimum is an open question in theory of metaheuristics and to my best knowledge, most, if not all convergence proofs assume that the algorithm in question has infinite time to run. Therefore, the proofs reveal that as execution time approaches infinity, the algorithm in question is more likely to (a) visit the global optimum (best-so-far convergence) or (b) get to the state where it can visit only the global optima (model convergence). That being said, you should not aim for being sure that your implementation of GA converges to the global optima. You can only discover what some good solutions have in common and formulate a heuristic, not an exact rule on them.

The quality of the solution is expressed with the value of fitness function $f$. It would be best if you can find even a theoretical optimal value of the function. It would allow you to compare individuals in GA population on an absolute scale. Consider reformulating $f$ in a way that fitness values are non-negative real numbers and that lower values of $f$ mean better solution. If you can't do this, try to compare the solutions with the best known.

3) Since the fitness function is nondeterministic, try to google for stochastic (noisy, non-deterministic) objective functions. I have not worked with them, so I can't tell you more.

$\endgroup$

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.