Genetic Algorithm - New Generations Worsen

Question

I implemented a simple genetic algorithm to generate a short story based on Aesop's fables. Here are the options I'm using:

Mutation : A one-word mutation with a speed check of 0.01.

Crossover Change the plot proposals at this point. speed - 0.7

Choice : roulette wheel selection - stack overflow

Fitness function : 3 different functions. the highest score of each is 1.0. so the overall maximum fitness score is 3.0.

Population size . Since I use 86 Aesop basses, I tested the population size from 50.

Initial load : all 86 offers of fake offers are shuffled to make complete nonsense. And my goal is to generate lost fables from this structure (at least at a certain level) from this structure.

Stop state : 3000 generations. And the results are below:

However, this still did not bring a favorable result. I was expecting a plot that rose over generations. Any ideas why my GA works worse?

Update . As you said, I used elitism at 10% of the current generation, copied to the next generation. The result is still unchanged:

Maybe I should use the tournament selection.

Answer 1

All of the above answers are great, and I would look at them. I will add my thoughts.

Mutation

Your mutation speed seems great, although using the Genetic Algorithms, the mutation frequency can cause a lot of problems if it is not. I would make sure that you check many other values ​​to be sure.

With a mutation, I would use two types of mutations. One that replaces words with another from your dictionary, and that replaces two words in a sentence. This will contribute to the diversification of the population as a whole and the shuffling of words.

Crossover

I don’t know exactly how you implemented this, but the one-point crossover does not seem to be effective in this situation. I would try to implement an n-point crossover that would shuffle your sentences much better. Again, I'm not sure how this is implemented, but just replacing it might not be the best solution. For example, if a word is at the first point, is there a way to move it to another position or will it always be the first word if it is selected by choice?

If word order is important for your chosen problem, a simple crossover may not be ideal.

The choice

Again, this seems fine, but I would make sure that you are testing other options. I used to find that ranking based on rank would be much more successful.

Fitness

This is always the most important thing to consider in any genetic algorithm, and with the complexity of the problem you have, I would be doubly sure that this works. Have you tested that it works with known issues?

Population size

Your value seems small, but I have seen how genetic algorithms work successfully with small populations. Again, I would experiment with much larger populations to make sure your results are better.

The most popular offer so far is the realization of elitism, and I definitely recommend it. It does not have to be much, even just the best pair of chromosomes of each generation (although, like everything else, I would try different values).

Another useful implementation operator is culling. Destroy part of your weakest chromosomes or one that is similar to others (or both) and replace them with new chromosomes. This should help stop your population from becoming "obsolete", which, according to your schedule, looks like it could happen. Mutation only does so much to diversify the population.

Answer 2

You can lose the best combinations, you must keep the best of each generation without crossing (elite). Also, your function seems pretty stable, try other types of mutations that should improve.

Answer 3

Reduce 5% to 10% of your population to be elitist so that you do not lose the best that you have.

Make sure your selection process is well tuned, if bad candidates go through very often, it will ruin your evolution. You may also be stuck in a local optimum, you may need to introduce other material into your genome, otherwise you will not move far.

Moving sentences and words around will probably not make you very far, but new sentences or words may be interesting.

If you consider history as a point x, y and your evaluation function as f (x, y), and you are trying to find max for f (x, y), but your mutation and intersection are limited to x → y, y → y, it makes sense that you will not move far. Of course, there are a lot more variables in your problem, but without introducing anything new, I don't think you can avoid locality.

Answer 4

As @GettnDer said, elitism can help a lot.

I would suggest using a different selection strategy. Choosing a roulette wheel has one big problem: imagine that the best individual fitness is, for example, 90% of the total amount of all activities. Then the roulette wheel is unlikely to choose other people (see, for example, here ). The selction strategy that I like the most is the tournament choice . It is much more resistant to large differences in suitability values, and the selection pressure can be controlled very easily.

Search for news

I would also try the New Search . This is a relatively new approach in evolutionary computing, where you do not make a choice based on actual suitability, but rather on the basis of novelty, which should be some metric of how a person is different in behavior from others (but you still calculate fitness to catch good ones). Of particular interest are combinations of classic fitness-driven algorithms and novelties such as this one . Mura.

Answer 5

When working with genetic algorithms, it is recommended to structure the chromosome in order to reflect actual knowledge in the optimization process.

In your case, since you are going to generate stories that are made from sentences, it can improve your results if you turned your chromosomes into structured phrases, the line <adjectives>* <subject> <verb> <object>* <adverbs>* ( here is a huge simplification).

Each word can be assigned a class. For example, Fox = subject, looks = verb, grapes = object, and then your crossover operator will exchange elements from the same category between the chromosomes. In addition, your mutation operator could only insert new elements in the corresponding category (for example, an adjective in front of the subject) or replace a word for a random word in the same category.

Thus, you would minimize the number of meaningless chromosomes (for example, a beautiful daytime sky against a background of a fox) and improve the power of speech generation for your GA.

In addition, I agree with all the previous comments: if you use elitism, and the best performance decreases, then you introduce it incorrectly (note that in a pathological situation it can remain constant for a long period of time).

Hope this helps.