# Measuring solution quality and allele impact on population fitness for a genetic algorithm

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?

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.
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.