Roulette Wheel Selection

[danielsvane]

Hey Kirupians

I've been reading some stuff on neural networks, and I'm now trying to implement it in AS3. One thing thats giving me a hard time, is the way the individuals with the best fitness, has a probability of getting selected. It's described as spinning a large roulette wheel, where individuals has more space on, relative to their fitness. The wheel is then spinned, and the larger regions, have a higher change of getting selected.

It might be explained better by this image

http://www.edc.ncl.ac.uk/assets/hilite_graphics/rhjan07g02.png

My question is, how do i implement this in code?

My best idea so far, is adding all the fitnesses, and then generating a random number. Then go through an array, and if this random number is between this fitness and all its previous fitnesses summed, and the next fitness with all its previous summed, we got a winner.

I just somehow got the feeling that this is not the best way to do this. I could also just select the 2 individuals with the best fitness, but thats not how evolution works.

Thanks in advance

[TOdorus]

If you want to talk evolution you've got talk about a negative force. You throw a hundred+ things against the wall and see what sticks. It isn't that a specimen finds a niche and gets designed for that, it's that every other design around him dies out. It's called natural selection, not natural support. Sorry for that, but that is my more personal gripe with the more common look on evolution.

Your idea of the array wouldn't really punish the weak as evolution does. Your question is about genetic algorithms really, but those get used in combination with neural networks most of the time. You should actually have them pair up. The succesfull ones having more chance of pairing with a succesfull partner and let them have children. Then there's a few that don't get paired and get killed off.

Now you can see that's not really effective. Nature just throws a lot of wasted potential away constantly. If we'd only look at humans. A male produces millions of seeds and maybe one of them actually gets used. A female produces less eggs, but the point remains: wasted potential. So when you say: "that's not how evolution works", I'd reply: "but that's not a bad thing." I'm more for your idea of taking the most succesfull ones and create a new child out of those and throw away the least succesfull ones.

The way nature was succesfull in the way it works is because there is no goal at all. You do not now what your environment will demand of you next. The citeria are not set. So trying everything makes sense. Since you, as a coder, define the criteria for your neural network this is, in my opinion, utter rubbish to apply to genetic algorithms.

Sorry if that all was rambling or bad English. I'm somewhat... drunk.

[glosrfc]

"I'm somewhat... drunk."

And somewhat wrong too. I don't want to highjack this thread but it's not true that "every other design around him dies out". Otherwise how do you explain the multitude of organisms, both similar and diverse, that occupy identical niches? If every other 'design' (a word that is wholly inappropriate when discussing evolution) died out, why are there so many fish that share the same biological niche? Or sharks? Basking sharks and whales...seals and penguins? How about the many insectiverous birds...and bats? Or pollen-eating birds, bats, and insects?
And why are those disparate species so similar in appearance? Why are whales, dolphins, and sharks so fish-like in appearance? Why have birds and bats formed wings from their forearms and fingers rather than their legs and toes? Why did they not form insect-like wings?

Nor is it wasted potential to produce millions of eggs and sperm. Natural selection is a quite simple theory to understand:
1. Organisms are variable - for example, look at the number of different breeds of dog.
2. Organisms reproduce and their population grows. But unchecked population growth is unsustainable so this growth is limited by competition for natural resources.
3. The offspring of organisms that survive this competition are modified to improve their chances of breeding.
4. These modifications, in a natural environment (but see dogs again), take time. A long, long time.

The continuous production of eggs, or the mass production of sperm, isn't a waste. It's a modification that improves that surviving organisms chances of breeding, and thus passing its genes on to the next generation. Only one sperm is required to fertilise one egg but the organism that produces 100 million sperm is more likely to fertilise that egg than an identical organism that produces 10 sperm. The stag with the biggest antlers is more likely to mate with other deer; does this mean that the stag thinks its antlers are a waste of potential?

While it's true that an organism doesn't know what the environment will demand next, it's also true that an organism knows what the environment demands of it now. And it's the now which the organism is continually adapting and evolving into. And it's this which explains why there are so many similarities (e.g. the development of flight) yet also so many subtle differences (e.g. bird/mammalian wings v insect wings).

Organisms developed universal characteristics such as flight in order to lessen the competition for the natural resources available in their 'now' time. If life were to start over, we can be utterly confident that flight will occur again. However, different species of organism developed their own methods of flight...insects are descended from the first proto-insect that developed wings and so all insect wings are appendages of their exoskeleton. Birds and mammals are developed from the first fish to adapt to life on land, so their wings are formed from this early fishes internal skeletal pattern of one upper arm bone, two lower arm bones, a wrist, and five fingers. While we can be 100% certain that flight would re-evolve again and again, we can also be 100% certain that an identical internal skeleton would NOT develop.

The first proto-insect might have wings growing out of its head, or have evolved a form of jet engine because that was a more suitable modification for the 'now' in which it was living. The first proto-amphibious fish might have adapted for it's 'now' by having eight legs, or nine fingers, or (as some fish already do) tentacles - if life on earth was re-run we (or the organisms that occupied our niche) might be scuttling around with their mouths.

[danielsvane]

Okay, this wasn't really a question on how evolution works, but more how to implement the roulette wheel selection. All I know about genetic algorithms and neural networks, is from a few guides, that might be wrong in detail. I'm no expert on the subject, hence why I'm asking.

I could also select the 2 fittest individuals, but according to my documents, this is wrong. The best individual only has a change of mating. Another option is something called tournament-selection, but I really have no idea what the best choice is here.

Another thing I'm wondering about, is how to use the 2 fittest individuals. Should I make a whole new population from these 2, or should I make a lot of pairing/mating, and make a population mixed from these?

So my questions are:
- Ideas, links to implement roulette wheel selection?
- Roulette wheel, 2 fittest, or tournament-selection?
- Make new population from 2 or more individuals?

If you could channel all your smartness to the topic, it would be much appreciated xD

[TOdorus]

This basicly sums up what I find wrong in the commonly accepted view on evolution.


While it's true that an organism doesn't know what the environment will demand next, it's also true that an organism knows what the environment demands of it now. And it's the now which the organism is continually adapting and evolving into. And it's this which explains why there are so many similarities (e.g. the development of flight) yet also so many subtle differences (e.g. bird/mammalian wings v insect wings).

I find it wrong to say that species adapts to it's environment. I cannot choose to grow wings and neither could the ancestors of creatures that can now. Adaption isn't an active proces, it's a by effect of the selection proces. Evolution in that perspective is the process of punishing what doesn't work and not working your way towards a goal. It's quite goalless.

Like you said, there is no design. There is only a system of interactions, so you don't really know what your environment demands of you yesterday, today or tomorrow. The system doesn't really know anything really, it just continues to run it's cycles. I think people try to define/categorize their environment all the time and apply the same to evolution. Evolution doesn't define or categorize and is therefore able to cope with a lot of variations in evironment.

Now if you would know the demands, you could just have a proces that weeds out the ones that don't meet them. That's what I mean with wasted potential. In nature this has proven to be able to cope with virtually everything that can be thrown at it. Given the complexity of reality this is also needed. Now to get a bit more on topic. In that perspective it's hard to define the fittest. Since a game envoriment is more abstract and simplified, you can actually define a fittest, a goal. I there think you should just take a few of the fittest, let them mate and throw a bit of mutation in. Using a roulette wheel sounds like trying to immitate nature to much, while in a game reality/envorinment you don't need that much diversity.

If you do want to simulate nature a bit more. Just kill of the lowest scoring ones, pair up every ai with every other ai and throw a dice per pair to mate. This way you can have a dominant male/female idea, where the more succesfull ones can mate with several partners.

I hope that makes my point about wasted potential more clear. If we're thinking about evolution as a proces to get an ultimate design (an AI in this case) and we can actually define the criteria, it's pointless to just try everything. Nature doesn't have that luxery and therefore is a superior system when you don't know the criteria, but if you do it's a bit expensive.

[glosrfc]

"I find it wrong to say that species adapts to it's environment. I cannot choose to grow wings and neither could the ancestors of creatures that can now."

Huh? You cannot choose to have blue eyes and red hair...but plenty of people have one or both. It's also absurd to say that the ancestors didn't have wings, or that their descendants chose to discard their wings. The evidence surrounds us in the skies, on the ground, or in the water...penguins, rails, and ostriches come immediately to mind. The organisms might not consciously choose to have wings or not, but the process is certainly active, even as we speak. If it weren't active, we wouldn't have breeds of dogs, sheep, cattle; or varieties of rose, petunia, carnation; and laboratories teeming with fruit-fly, rat and mice mutations.

Some organisms have adapted to meet their changing environment before our eyes. Think of wild dogs and cats that have exploited the environment in Australia, or the mice (http://www.kirupa.com/forum/showthread.php?t=333247) that now inhabit some Pacific islands. Not only have these mice adapted their body size due to natural competition (i.e. the lack of any natural predators) but the same natural competition (i.e. the lack of their normal insect foods) has forced them to completely change their dietary habits. And all this has happened in the geological blink of an eye.

While you might not agree with this view of natural selection, it is commonly accepted because it fits with all of the scientific theory and evidence.

On to the question though....

...you might want to start by looking at resources for Conway's Game-Of-Life which shows how, with the right set of basic rules, complex patterns can emerge. Langton's Ant has a similar algorithm. However there are alternatives and it does depend on what exactly you're trying to achieve. For example, you could adopt your earlier idea:
1. Generate a random number (R) between 1 - 100
2. If R < 20, then organism C "wins"
3. If R < 50, then organism B "wins"
4. If R => 50, then organism A "wins"

Another option would be to simulate Mendels Inheritance Law, whereby dominant genes or characteristics generally show a 3:1 ratio over recessive genes or characteristics. So you could simply generate a single random number for the weakest individual or recessive gene, but then three random numbers for the strongest individual, or the one with the dominant gene. The individual with the highest random number wins but the strongest will have a 3 to 1 chance of passing on its dominant characteristics.

A third option would be the "trump cards" approach. Each individual would be an object with an identical set of properties, e.g. food gathering, physical strength, acuity of vision, cunning, etc. But each property would have a different value for each individual. You would then compare properties for given scenario's, e.g. if organisms A and B fell into a bear-pit, the one most likely to survive would be the one who was strong enough to climb out...so the physical strength properties would be compared and the highest value "wins". Similarly, if food became more scarce, you might compare their food gathering properties.

Once you've decided on the basic evolutionary approach you want your model to take, it becomes easier to come up with an Actionscript algorithm to fit the bill.

[danielsvane]

Thanks for the reply glosrfc

I'm gonna try to use the roulette wheel selection, because it's the only one I really understand. Maybe I will research the others later.

[TOdorus]

Sorry to keep on the derailing, but since danielsvane seems to already got his answer, I don't think it's that much of a problem.


"I find it wrong to say that species adapts to it's environment. I cannot choose to grow wings and neither could the ancestors of creatures that can now."

Huh? You cannot choose to have blue eyes and red hair...but plenty of people have one or both. It's also absurd to say that the ancestors didn't have wings, or that their descendants chose to discard their wings. The evidence surrounds us in the skies, on the ground, or in the water...penguins, rails, and ostriches come immediately to mind. The organisms might not consciously choose to have wings or not, but the process is certainly active, even as we speak. If it weren't active, we wouldn't have breeds of dogs, sheep, cattle; or varieties of rose, petunia, carnation; and laboratories teeming with fruit-fly, rat and mice mutations.

I think there was a misunderstanding there, but I hope this post will clarify my point.


Some organisms have adapted to meet their changing environment before our eyes. Think of wild dogs and cats that have exploited the environment in Australia, or the mice (http://www.kirupa.com/forum/showthread.php?t=333247) that now inhabit some Pacific islands. Not only have these mice adapted their body size due to natural competition (i.e. the lack of any natural predators) but the same natural competition (i.e. the lack of their normal insect foods) has forced them to completely change their dietary habits. And all this has happened in the geological blink of an eye.

Now say you a species with a pretty diverse gene pool and disease strikes. Only specimens with a certain gene active/inactive are immune. Only those will survive and are suddenly deemed fittest. If that same gene would make you cripple, than all the fittest of the species would be cripples. My point is that "fittest" isn't really defined. It's constantly changing.

You say the species see a niche and occupy it. Adapt to the niche. The problem with the idea of evolution as species adapting to an environment is that it overlooks the fact that genes need to be available at the time that they are needed. A species doesn't mutate according to it's environment: it mutates completely at random. This way new genes become available and an experiment can begin: are they succesfull? If the gene that stops the disease wasn't avaible, the species would die out. If there weren't mice that could eat different foods, the mice would've died out.

So to say that species adapt to an environment is looking at the symptoms. I will totally agree that the result is a species fit for the environment, but I won't with the idea that it ever was the goal of the entire proces. Evolution serves no purpose as the definition of fittest is constantly changing. Fittest only exists in the here and now, so you can ask if fitness exists in reality or that it's just theoretic construct. We as humans think in goals and like to see that in evolution, but I believe that evolution is a side-effect of a complex set of interactions. A loop that came into existance at incredible odds which now just keeps repeating itself. Nothing more nothing less.



ps: glosrfc, you come across as a very intelligent guy so please don't say something like:

While you might not agree with this view of natural selection, it is commonly accepted because it fits with all of the scientific theory and evidence.
I really don't care if all the cool kids are doing it, they may be wrong.