6
$\begingroup$

In genetic algorithms, a function called "fitness" (or "evaluation") function is used to determine the "fitness" of the chromosomes. Creating a good fitness function is one of the challenging tasks in genetic algorithms. How would you create a good fitness function?

$\endgroup$
  • $\begingroup$ I think this is a bit broad, as it depends very much on the problem. A couple of things that might help: (1) Asking what are considered good qualities of a fitness function (leaving out the process of finding one in a generic unstated problem). And (2) give an example of a problem where you are having trouble defining a fitness function, so the answer can focus on that problem. $\endgroup$ – Neil Slater Nov 22 '18 at 8:06
  • $\begingroup$ I would say that the, at least, two requirements to consider a fitness function "good" are: 1) it should allow a fast computation of the fitness of the individuals, 2) it should represent/compute the actual fitness of the individuals. $\endgroup$ – nbro Nov 22 '18 at 9:38
  • 1
    $\begingroup$ Have a look at this SO post: stackoverflow.com/q/7330407/3924118. $\endgroup$ – nbro Nov 22 '18 at 9:46
0
$\begingroup$

Fitness Function (also known as the Evaluation Function) evaluates how close a given solution is to the optimum solution of the desired problem. It determines how fit a solution is. Following points requirements should be satisfied in making good evaluating function:

(1) The fitness function should be clearly defined. The reader should be able to clearly understand how the fitness score is calculated. (2) The fitness function should be implemented efficiently. If the fitness function becomes the bottleneck of the algorithm, then the overall efficiency of the genetic algorithm will be reduced. (3) The fitness function should quantitatively measure how fit a given solution is in solving the problem. (4) The fitness function should generate intuitive results. The best/worst candidates should have best/worst score values. The fitness function that should be used depends on the given problem. for further knowledge

https://towardsdatascience.com/

https://www.sciencedirect.com

$\endgroup$
  • $\begingroup$ You're linking us to two websites. It is more useful if you link us to specific articles which discuss this problem more in detail. $\endgroup$ – nbro Feb 23 at 16:33
0
$\begingroup$

In the world of DNA, it has been proposed that fitness is closely related to energy return on energy invested1. In an artificial world, return on investment may be a ratio of two metrics of the same dimension that makes for an excellent driver of artificial genetic coding. That is more of a heuristic than a rule.

The question to answer, for the specific problem, is what constitutes a benefit contained in the genetic information such that it should be passed to the next generation of fitness trials, from the point of view of the stakeholder of the software project? After that question is answered, then, if it is a qualitative answer, how can one quantify this benefit?

The term evaluation function is strange in that all functions must be evaluated to be of use. It's not very descriptive. Perhaps the people that coined that term meant valuation function, which makes more sense. How do we value a given genetic code against others or against some norm or fixed ideal?

When we have a project stakeholder, principles of business driven development (BDD) must be the driver for the valuation and thus the formulation of a fitness function. However, we are not quantifying the result. We are quantifying the individual set of chromosomes in a generation. This is upstream from the result, so we must work backward from the business driver. This is not unlike developing software specifications from business objectives.

Work backward from the intended outcome. What kind of traits in each generation are most likely to, if preserved, result over time in the intended outcome? Said another way, how do we quantify the likelihood that a trait will be a component in a sequence of transformations that will lead to the desired genetic outcome after many generations?

Additional Considerations

There are seven things to keep in mind when thinking about genetic algorithms.

  1. Some traits may be recessive and not present in form or behavior.
  2. Some traits are disadvantages under current conditions but are foundations for more advanced traits that may be primary survival traits in future conditions.
  3. Mutations are no longer considered the sole form of change in gene distribution. In addition to normal reproduction, genetic transfer between species is now acknowledged as part of the network of evolutionary progress.2
  4. It is not solely death but also insufficient reproductive energy that leads to a stoppage in the forward passing of genetic material. In the natural world, how many offspring will be generated is a function that produces a probability distribution. Offspring will be generated based on the spare energy the parent has to reproduce after hunting, eating, and metabolizing. Once the energy return on energy invested diminishes to the point where the parent has insufficient energy left to reproduce, the chromosomes reach a dead end. Whether or not the parent dies is not relevant in this case. Energy remaining to perform reproduction is the natural fitness test for a set of chromosomes.
  5. There are symbiotic and social phenomena that further complicate the simplistic view that the fitness of the individual in comparison with other individuals is the sole indicator of reproductive quantity.
  6. The fitness test occurs in stages, especially in higher animals: at insemination, at meiosis, during gestation, at birth, and then through a series of events during maturing. Viability is a product of these probabilities.

These things are not arbitrary features of biology but functional ones, so they bear importance to how we write genetic algorithms and use them.


References

Energy Return on Investment: A Unifying Principle for Biology, Economics, and Sustainability, Charles Hall, 2017

Acquiring Genomes, Lynn Margulis, 2003

$\endgroup$
0
$\begingroup$

In my experience, the fitness function is a way to define the goal of a genetic algorithm. It provides a way to compare how "good" two solutions are, for example, for mate selection and for deleting "bad" solutions from the population.

The fitness function can also be a way to incorporate constraints, prior knowledge you may have about the shape of the fitness landscape, or the way your crossover/recombination operators will work in that fitness landscape.

For example, the fitness function can include hard constraints like "Genes x,y, and z must all stay on one side of the surface $Ax +By +Cz = k$" by assigning the fitness value at zero if the gene values are on the wrong side of the surface. However, it's often better in a case like that soften the boundary by assigning a fitness penalty that is zero at the surface and grows larger as the gene values move farther from the surface on the wrong side of the surface.

Different fitness functions can be used for mate selection vs deleting "bad" trial solutions. For example, "mating fitness" between two potential parents A and B can be a function of how different the two parents are. By providing a mating advantage to pairs that are significantly different, the population can be forced to remain fairly diverse and thus explore a larger region of solution space, or to avoid converging to local (sub-optimum) fitness maxima. Meanwhile, the usual kind of fitness will cull the low-fitness individuals from the population and drive evolution toward high fitness.

What is often much more important is the set of variables ("genes") used to represent a trial solution, how the genes are arranged in the "chromosome", and the ways genes from two parents can be combined to form a new trial solution. Since you didn't ask about those things I won't go into detail in this answer, but if you ask in a separate question I will provide a detailed answer.

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