Kriss Jessop About Me Projects Personal Projects RPGs

Fitness Evaluation

Posted on October 29th, 2016

This week on Natural Algorithms: We learn some terminology, Kriss makes a wisecrack and a dog does science!

Okay, so the point here is that we’re looking at different types of fitness functions. We divide the type of function an algorithm uses based on what it returns and how it searches for the result. Notably, a continuous or boolean function can be applied to both a full function search and a partial function search.

Continuous evaluation, used by DFO, is a form of fitness evaluation that relies on a real number. The algorithm then attempts to find a position with a smaller or larger value, dependant upon whether it’s a minimisation or maximisation problem.

Boolean evaluation is a method used by SDS, wherein the fitness returns a true/false value to determine a position’s suitability. It’s fair to assume that this value isn’t absolute. As with the restaurant example there may well be a person in the group that dislikes the restaurant, but everybody else likes it; so they don’t really have a choice.

Man, friends can be brutal.

Full function evaluation is a form of greedy evaluation. The point of full function evaluation is to be 100% certain that an entry is, or is not, the optimum result by doing what greedy searches do: Looking at everything. This is somewhat counter intuitive to the purpose of swarm searching, but at the same time makes for a fair (albeit slow) analysis of whether the partial function evaluation is returning the correct results.

The partial function evaluation is the essence of a swarm search. Not every location needs to be searched systematically. Instead, it relies on the swarm to disperse itself. In most cases, this is probably going to be more effective than performing the equivalent of a linear search. Because linear searches can be pretty damn slow.



Obligatory dog doing science

The given example, to drill these points home, is applications of both DFO and SDS, intended to search an image for symmetry.

I’m not a graphics-y person. The moment you put an image in front of me and ask me to do something programmatic with it, my eyes glaze over.

The actual aim of the task is to write a fitness function that judges the space around the agent to figure out if there’s any symmetry to be had. Perhaps it could use a full-function method but operate on a limited section of the search space, searching for horizontal and/or vertical symmetry. Or, perhaps, it just looks at a few pixels (or micro features) to determine whether there’s any symmetry at all then keeps improving the fitness until a lack of symmetry is found.