I started working again on a Genetic Algorithm and i’m trying a lot of operators and ways of selection. When I made the Tournament Selection , I noticed that it gets really easy to always get the top individuals to be selected, and the small ones get less chances of being selected. I saw some workaround methods like implementing some “selection probability” to the individual that wins the tournament so that if he doesn’t go trough the probability it gives chance to the others that lost.
Other method that I read was to give to each individual a limit of how many times he could be selected, but on that document wasn’t any way creating this “limit”. So I start thinking of using the % that each individual represent’s with his fitness. For example:
ind 1 : 10% ’till 100% goes 10x
ind 2 : 40% ’till 100% goes between 2 to 3x
ind 3 : 8% ’till 100% goes between 10 to 12x
ind 4 : 30% ’till 100% goes between 3 to 4x
or using the inverse %
ind 1 could be selected 90% of number of tournaments (or rounds)
ind 2 could be selected 60% …
ind 3 could be selected 92% …
ind 4 could be selected 70% …
This is just quick ideas nothing complex. What I would like to know is if there is any document that i could find that shows some method create this limits or if you know or have any idea/opinion that could improve this.
First there’s a couple of things to keep in mind when implementing genetic algorithms :
Just about everything in GAs is arbitrary. Your solution will depend on :
- The way your population individuals represent the potential solutions,
- The way you mesure the fitness of your individuals,
- The way you implement selection and breeding,
- The amount of mutation,
- The number of generations and the size of your populations,
- What other GA concepts you might choose to implement…
All of these are parameters to your implementation. Typically with GAs you are going to implement a solution, test it over several runs and then you’ll tweak it plenty of times.
Also consider what is your search space, and what it might look like :
- Your search space is a N-dimensional space that defines the universe of all of your potential population. (N being the number of caracteristics defining your individual solutions).
- If you think of it in 3 dimensions (to make it simple) then will you have a landscape which is rather flat, or will it look like a hughe mountain, or will it have lots of hills, mountains and valleys ? This is also important when tweaking your implementation.
Now, if you are worried about having some individuals take over the population too fast then you can review your fitness function to lessen the importance of fit individuals. (Your fitness function may be linear, or it could be linear with a max value, or logarithmic, or something else… ). Also you can increase the mutation rate. Also, as you suggest, you could limit the number of times a individual solution will breed. You can also try out different selection mechanisms to see how it goes (fitness proportionate, tournament, etc…)
Just tweak, test and iterate over and over. Typically that’s how you’ll refine a GA program.
If you give more detail about what you have already implement I’ll be glad to give you some further thoughts on it.
Good luck.