Genetic Programming - Fitness functions

Question

Let's say I have a set of training examples where A_i is an attribute and the outcome is binary (yes or no):

A1,             A2,             A3,             Outcome
red             dark            large           yes
green           dark            small           yes
orange          bright          large           no

I know I have to define the fitness function. But what is it for this problem? In my actual problem there are 10 parameters and 100 training examples but this is a similar problem.

Tortola

I give 5 dollars to everyone who has understood what the actual problem is. – Hammock

@SpyrosP, I'll send you my paypal information ;). I understand what he's asking, although I don't have an answer...yet – Mingo

:O Seriously you do ? Please, explain it a bit ! – Hammock

Consider A1, A2, A3 to be observed variables. Observing those varaibles you also see that they have a particular outcome. A1 = color of some guys car, A2 = the sky dark or light, A3 = is he driving a large or small car. Now assume that all your data is from car crashes, and your outcome is "Did the guy need to goto the hospital as a result of his crash". Using the input, and the outcome, you try to build a function (model) to predict in the future if the guy needs to goto the hospital or not if he crashes. This is quite contrived, but should help you to understand – Mingo

He's asking for a way to build that model from the dataset – Mingo

@SpyrosP - OP wants to generate a program, that takes i parameters [A_1 - A_i] and returns either yes or no. – Goodfornothing

@Precott - yes that's what I mean. Before you posted I was going to say this: "Have you read Mitchell's Machine Learning book? If so, the famous 'play sport' (sometimes 'play ball', 'play tennis' by other authors/teachers) is one often used for different machine algorithms. I want to come up with a genetic algorithm that determines whether someone enjoys sport. The example above is similar to that problem but I've made up something simpler (few examples, fewer attributes). I would like to define (and understand) a fitness function for this problem." – Tortola

@Mingo - Respect ! I could never go that far :) – Hammock

The question is very interesting and though i've written some GAs in the past, i can't really think of a decent way to create a fitness function. The events seem quite unrelated and, what is really the supremum ? :/ I will bookmark that :) – Hammock

@SpyrosP - yeh I've been struggling with this for ages :S. I don't think there's much more info I can give really except that the dataset I have has more examples, more paramaters and is the 'play sport' example from Mitchell's Machine Learning book. Hopefully someone will have a brain wave! – Tortola

@SpyrosP am I getting those 5 bucks? ;) – Banjermasin

You definitely got my upvote, which is worth a lot more :D:P – Hammock

LOL - I'd say so, more practical also :) – Banjermasin

Answer 1

I think the confusion here is coming from the fact that usually fitness functions give you back some scalar, sometimes on a discrete scale, but never a binary yes/no (or true/false). In this sense, this looks more like a 'classification' problem to be solved with neural nets (or possibly bayesian logic). Said so, you could certainly devise a GA to evolve whatever kind of classifier, and the fitness function would basically be expressed in terms of correct classifications over total evaluations.

Another pure GA approach to this - probably more relevant to the question - is to encode the whole classification rule set as a given individual for the genetic algorithm. In this sense, the fitness function could be expressed as a scalar representing how many yes/no classifications the given candidate solution at hand gets right over the total, and so forth. A similar approach can be found in this paper Using Real-Valued Genetic: Algorithms to Evolve R,de Sets for Classification.

Example (one of the possible ways to encode this):

A1,             A2,             A3,             Outcome
red             dark            large           yes
green           dark            small           yes
orange          bright          large           no

Encoding: red = 000, dark = 001, large = 010, green = 011, small = 100, orange = 101, bright = 111, etc. Outcome: yes = 1, no = 0

Chromosome:

A1,             A2,             A3,             Outcome
000             001             010             1
011             001             100             1
101             111             010             0

All of the above gets translated into a candidate solution as:

000001010-1/011001100-1/101111010-0

You will generate a random bunch of these and evolve them whichever way you like by testing fitness (correct classification/ total classifications in the ruleset) of the entire rule set (be careful picking your cross-over strategy here!).

I also suggest you listen to a binary solo, to get you in the mood.

NOTE: I highly doubt this would work with a rule-set composed by only 3 rules, not enough breadth for the GA.

Banjermasin

@Banjermasin Thanks for the answer. If I choose a chromosome design which made the three examples be 100101010, 010100110, 001010101 respectively (so the first example is 100 because the first attribute is red followed by 10 because the second attribute is dark followed by 10 because the third attribute is large followed by 10 because it was a 'yes' example) then do you think you could come up with the fitness function applied to one of the examples so I can see what you mean better? I'll have a look at this paper too. +1 for this thank you :). – Tortola

Slight correction: The fitness function applied to a initialised random hypothesis. I could make one up: 010101010. – Tortola

I edited the answer with an example. Yes, you would generate a a bunch of random binary strings to start with and feed them to the GA. Hope this helps! – Banjermasin

I find the binary solo to be quite inspirational :) – Banjermasin

The GA scheme can perhaps work for vivid's problem. However, looking at rules based on all possible combinations of attributes mean's searching through a hypothesis space comprised of all hypothesis. Thus, the only bias in the learner is that introduced via the crossover/mutation operators, which may be unnatural and may not lead to good generalization. To help, introduce more bias by considering a restricted (parameterized) set of rules based on your domain knowledge of the problem. E.g. rules made up of ranges/cutoff values or pairs of attributes (differences of) and evolve those parameters – Adelinaadelind