Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Wikipedia defines the termination point of a GA to this:

Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached.

Now, if it terminates when a satisfactory fitness level has been reached, and you are the one defining that fitness level, why wouldn't you just be able to create the "perfect" genome from the beginning yourself, since you already know the characteristics of this perfect genome?

I guess I'm just a little confused here. I thought the purpose of a GA was to constantly evolve and show us possibly an even better solution than what we thought of, and our fitness function was just something that helped it along the way, not something we put on the pedestal as the termination "perfect" state. Doesn't that destroy the point?

share|improve this question
1  
Probably a better fit for cstheory. –  Karl Bielefeldt Aug 10 '11 at 15:23
    
Didn't even though there was that :) –  slandau Aug 10 '11 at 15:24
1  
@Karl: The question is a bit soft for cstheory. It will likely be closed there. –  Robert Harvey Aug 10 '11 at 15:31
2  
Thanks, @Robert. Now I remember why I don't visit there. I guess this is one of those "between the cracks" questions. –  Karl Bielefeldt Aug 10 '11 at 15:35
add comment

8 Answers

up vote 15 down vote accepted

The fitness function evaluates the output of your algorithm. It's quite possible to recognize an ideal output when you see it, but not know the steps to produce that output from any given input. That's where genetic algorithms are most useful.

For example, one common fun application of GA is in producing an animation that can move a virtual creature in an efficient way. It's easy to tell if the creature is moving at a certain speed in a relatively straight line. That's your fitness function. It's much more difficult to tell the exact sequence of "muscle" movements to get it to do so.

share|improve this answer
2  
It should also be noted, that you often stop after x generations because the GA could end up spinning indefinitely because it gets 'stuck' on a local minima/maxima which doesn't satisfy your optimal fitness score. This can happen if your selection/crossover/mutation functions aren't tuned well enough for the problem set. –  Steve Evers Sep 23 '11 at 14:19
    
@Karl I remember Andrew Cooke's genetic algorithm solution to producing the first Malbolge "Hello World" & then lost a better solution emailed to him stackoverflow.com/questions/5338627/… –  pageman Dec 16 '13 at 3:25
add comment

It's often the case that you can determine the fitness of a solution but can't directly determine the solution itself. Say you're trying to evolve fast rabbits, and there are a handful of genes that impact rabbit speed. You can test rabbit speed, but enumerating all the combinations of speed-related genes would be impractical. In such a case, you might have a GA that races rabbits and breeds the fastest ones. You could do that forever, but you'd probably prefer to stop when:

  • you've found a rabbit that's faster than X, or
  • the incremental improvement over n generations has dropped below some threshold, or
  • you've bred rabbits through m generations
share|improve this answer
add comment

The entire point of the GA is to give you the solution to the problem that has that fitness level. This solution would be very hard to find using other more conventional search algorithms, which is usually why you're using a GA in the first place.

Or instead of a fitness value limit, you could decide how many generations you want to run (the more generations you run, the higher chance you have of finding ever higher fitness values). For example, in the traveling salesman problem, getting a path that has the lowest cost between the cities you need to traverse.

Whether your stopping condition is a certain fitness level that is acceptable or a certain time constraint (running the GA for a maximum time period or a limited number of generations for time-critical applications such as pathfinding or AI applications) is determined usually by your problem domain.

share|improve this answer
add comment

Intuitively, the purpose of a genetic algorithm is to formulate an algorithmic solution to a problem that doesn't lend itself to a straightforward logical analysis. Once that goal is achieved, the GA need not pursue any further.

Of course, if better "fitness" is wanted, the genetic algorithm can be left running to see if it can find a more highly optimized solution, or the genetic algorithm can itself be tweaked to see if it will converge on a better solution.

share|improve this answer
add comment

A genetic algorithm requires some way to reward good genes with greater propagation. If you had no way to tell good genes from bad genes, you couldn't use a genetic algorithm at all.

For a genetic algorithm to work, you must allow the more fit solutions to reproduce in preference to the less fit solutions. Otherwise, you'd just be trying random solutions.

Here's a typical example from my own experience: Developing one of the first voice dialing systems, we had a hard time finding an algorithm to match a spoken name to a stored copy of that same name. We were told that 95% accuracy picking one name out of 25 was sufficient. We had a stored corpus of people saying 25 names 10 times each.

First, we developed an input system that measured the length of the spoken word and the frequency energy in several normalized chunks of it. Then we developed an algorithm that assigned weights to the matches on those parameters and compared two sets of parameters through those weights.

Now, we had one last step -- what should the value of those weights be?

We created 1,000 random sets of weights and tested them against the corpus. We threw away the 500 that performed the worst. For the remaining 500, we duplicated each one and in one of them, randomly raised or lowered one of the weights.

We repeated this process on a computer for about two weeks until it finally had a set of weights that met the 95% accuracy criterion. Then we tested it on data not in the corpus. It was about 92% accurate. So we ran longer to get to 98% accuracy on the corpus and that set of weights produced 95% accuracy on data not in the corpus.

So, the point is, you must have a fitness function to run a genetic algorithm. If you have no way to tell good genes from bad genes, how can you make sure the good genes reproduce and the bad genes don't?

share|improve this answer
add comment

Iterate till a solution doesn't differ from the previos iteration one very much. For very much, please understand a fixed tolerance.

Solution in iteration n-6: 600
Solution in iteration n-5: 800
Solution in iteration n-4: 768
Solution in iteration n-3: 780 
Solution in iteration n-2: 778
Solution in iteration n-1: 778.23
Solution in iteration n: 780.18
Solution in iteration n+1: 780.1815

In this example, if your fixed tolerance was 0.01 then (n+1) tells you to stop because abs(solution(n+1)-solution(n)) < 0.01.

Resuming, thats when your algorithm can say: this wont get any better!

share|improve this answer
add comment

For a quick answer to you main question: There is a big difference between knowing what you want to achive, and knowing how to get there.

In more detail, for example, with one of the most popular problems solved by using genetic/evolutionary algorithms, usually a case study in class, finding the optimum route in a graph. This is often used in networking to find the cheapest route from one end to another. As you define costs (# of hops, cost from each hop, etc...) you also define your target cost (fitness level) at which you are happy with the result. Your algorithm might not find the best, but it will find an algorithmically acceptable optimum. By this I mean that the cost/benefit relationship of finding a better answer is prohibiting.

With GA/EA you'll find that it is normal behavior that you very quickly find a 95%+ optimum answer, but narrowing down that last 5% is exponentially more costly. So the theory is that you define an acceptable optimum to achive the best result in the least amount of time. Since the cost of finding, say the top 1%, might outweigh its benefits over the top 5%, you define your acceptable optimum.

To sum up, you don't now the answer to any particular problem, you just define, per problem, your acceptable optimum, the point in which finding a better answer is not practical.

share|improve this answer
add comment

There's some research into fixing bugs in C with genetic algorithms by supplying negative and positive test cases as fitness functions, along with broken code as input. This is an example of a problem that could be solved by a human, but is easier for a genetic algorithm to do. It's important to note:

Although the methods described in this paper do not evolve new programs from scratch, they do show how to evolve legacy software to repair existing faults.

However, new programs have been evolved from scratch—just not in C. The few nontrivial programs written in the Malbolge esoteric programming language have all (to my knowledge) been evolved, not written. The language is too complex for a programmer to use, and too convoluted to efficiently deduce programs from logic alone, so the majority of programs written in it have been produced by genetic algorithms. The fitness function is generally the edit distance to the expected output.

This is nicely circular, in a way. By observing that complex genetic code is written by evolutionary processes, we can simulate evolutionary processes to produce code in a different complex language, without even knowing how the code works!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.