Does defining the stopping point of a genetic algorithm defeat the purpose of the algorithm?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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?

Answer 6

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!

Answer 7

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.

Answer 8

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!