Evolutionary/Genetic Algorithms

[digitalgoth]

So, if you started with 100 objects (DNA?), then you make them go through the steps 1 and 2, and to steps 3 and 4. At the end of step 4, how many individuals would you still have? still 100?

If so, would you ended up with the last 100 objects that ALL fit? In other words, through the X cycles, the individuals that fit the criteria will become more and more. Is that right?

It depends, but usually you replace the members of your original population with the offspring that are created via selection. Two parents swap genes to make two children that will replace them.

That is NOT the only way to do it, sometimes the "best" member(s) may be kept from generation to generation (called elitism) so that you never lose your best solution, however this is not required.

If selection pressure is too high, you would quickly end up with 100 clones that are almost identical (minus changes due to mutation). That can lead to premature convergence, where all the solutions come to the same place, which is unhealthy in genetic algorithms and in life.

You have parameters that control how much selective pressure there is. You may start with little selection pressure so the genetic algorithm can explore the solution space for the best global solution, then it applies more and more pressure until you've found the best solution at the end when it is mostly optimizing the solution it found it.

Understand that genetic algorithms use principles of evolution, but are not evolution. There are a wide varieties of ways of structuring the algorithm, and what you're trying to balance is an appropriate level of selection pressure to test good ideas, and mutation to bring in new ideas that may be better. If you select to strongly, you get clones, if you mutate too strongly, you can never converge on a good answer because nothing can ever converge at a good solution.

 

[sfs]

I know.

In this linked study about chimp and bonobo, do you think the genetic difference is caused by the geographic isolation?

Yes, the isolation caused by the Congo River.

 

[digitalgoth]

I know.

about chimp and bonobo, do you think the genetic difference is caused by the geographic isolation?

Chimps can't swim, their bodies won't allow it. They drown. Even small bodies of water can prevent them from crossing.

Water is commonly used to prevent chimps in zoos from escaping or attacking people.

This caused them to not interbreed, because although they are close, they are effectively cut off completely.

Since the two groups are separated from one another from a selection standpoint, then their genetics will diverge due to different mutations between the two groups. The groups will continue to select out bad mutations, and propagate beneficial mutations, but they will be working on different mutations.

Because of this they will diverge more and more from each other.

We have this in people. In Africa, Asia, Europe, Americas, people all look different because we're mostly isolated from each other until very recently, so we started looking different because of the build up of mutations.

 

[DogmaHunter]

So, if you started with 100 objects (DNA?), then you make them go through the steps 1 and 2, and to steps 3 and 4. At the end of step 4, how many individuals would you still have? still 100?

Usually, in genetic algorithms the population size is fixed.
Since digitalgoth did a good job of explaining the inner workings, I'll focus on the bolded part of your quote.


In a genetic algorithm (just like in real life for that matter), there is a distinction between the genotype and the fenotype.

One of the hardest parts of designing a genetic algorithm is designing the structure of the genotype. Within the field, this is usually called the "chromosome". I called it DNA for clarity.

The genotype / chromosome is a datastring that represents the individual. It is also the string on which the mutation logic will be computed.

At the beginning of step 1, the application will convert the genotype into the fenotype. Meaning, it will take the datastring and "build" the system as it is described therein.

In the car app for example, this chromosome is an array of structured integers. Each integer represents something specific in the eventual car: the sizes/points of the polygons, the tension of the wheels, the position of the wheels, etc.

During mutation rounds, those numbers are mutated. And a slightly changed car emerges from it when building the fenotype.

Again, designing the structure of the chromosome is (imo at least) the hardest part.

If so, would you ended up with the last 100 objects that ALL fit?

Not necessarily. The "last" generation is really just another generation. The "last" part is quite arbitrary. As in: nothing stops you from continueing for another 1000 generations.

However, it could be that your population has reached some sort optimum. At which point it will stabilise there and not much changes will happen after that.


Here's an interesting read on the implementation of the GA in the car app:

http://boxcar2d.com/about.html

 

[sfs]

Note: phenotype, not fenotype.

 

[DogmaHunter]

Note: phenotype, not fenotype.

Right. It's an "f" in my native language

 

[Loudmouth]

I know.

So why did you say that the isolation of any monkey species was unlikely, so unlikely as to be impossible? What data did you draw that conclusion from?

 

[Loudmouth]

Right. It's an "f" in my native language

Would that be Phrench or Phlemish?

 

[juvenissun]

So why did you say that the isolation of any monkey species was unlikely, so unlikely as to be impossible? What data did you draw that conclusion from?

I was not talking to you. You be quiet.

 

[juvenissun]

Not necessarily. The "last" generation is really just another generation. The "last" part is quite arbitrary. As in: nothing stops you from continueing for another 1000 generations.

However, it could be that your population has reached some sort optimum. At which point it will stabilise there and not much changes will happen after that.

In other words, when it is stabilized, then the deleting of non-fits (step 3) will not produce more fits. Right?

 

[juvenissun]

Yes, the isolation caused by the Congo River.

Why was there isolation at the first place? If it started with chimp and bonobo populations separately, then what is the point of this study?

 

[Loudmouth]

Why was there isolation at the first place?

You had a single population, and then a river formed through the middle of the population about 1.5 to 2 million years ago. The river was wide enough and violent enough to prevent apes from crossing it. This meant that from that point forward, any mutations that happened on one side of the river would not spread to the other side of the river. This caused different mutations to accumulation on each side of the river, resulting in genetic divergence.

 

[digitalgoth]

In other words, when it is stabilized, then the deleting of non-fits (step 3) will not produce more fits. Right?

When you use a genetic algorithm, you are either trying to optimize something (say the wind drag on a car by altering its physical shape) or trying to find the answer to something where you aren't sure what the answer is (such as how to put together an assembly line).

In either case you are trying to find the best answer closer to a goal.

The goal could be to give you the best answer after a certain number of generations, or it may be after a certain amount of time has passed, or might be when the "fitness" of the best solution has met a certain threshold.

At that point, if you have an answer that's acceptable, you go with it and that's your solution, and you may continue letting the genetic algorithm run for better answers down the road, or may just stop it because you're done.

Biologic evolution isn't the same, it doesn't really "stop" (although humans mostly have). The "fitness" of the organism is it's ability to survive and adapt to a changing world. if it does, then it will continue on. If it doesn't it goes extinct. In some cases an organism may be able to adapt to changing environment (humans and flies) easily, and in some cases it may have become too bound to its environment (say only being able to survive on a rare bamboo food source) which is wiped out and the organism goes extinct because it was over-fit for its environment. Breeding and mutation still occur, but nothing may change.

Humans are mostly outside of natural selection, because through medical technology we are able to counteract bad mutations (dentistry, optometry, allergens, antibiotics) and keep them from being selected out of the population.

Interesting enough, on a side point, is that eventually we'll probably die out due to excessive mutations causing issues that make us dependent on health technology, which is fine until our environment changes or technology fails and we'll eventually disappear.

Genetic algorithms also have this problem. Sometimes the population will stagnate. No new mutations are helping because it's stuck in something called a local optimum, where it can get no better because it lacks enough diversity to overcome it, or it may never find an answer at all, because it endlessly bounces around the solution space unable to find the best answer.

That's where the setup and parameters affecting your genetic algorithm matters. Maybe you need a larger population, and smaller mutation rate, or different options in how selection is made.

 

[juvenissun]

When you use a genetic algorithm, you are either trying to optimize something (say the wind drag on a car by altering its physical shape) or trying to find the answer to something where you aren't sure what the answer is (such as how to put together an assembly line).

In either case you are trying to find the best answer closer to a goal.

The goal could be to give you the best answer after a certain number of generations, or it may be after a certain amount of time has passed, or might be when the "fitness" of the best solution has met a certain threshold.

So, the type of GA you are designing is one that seeks the best track which leads a group of original objects to change most efficiently toward a special goal.

Is that right?

 

[juvenissun]

You had a single population, and then a river formed through the middle of the population about 1.5 to 2 million years ago. The river was wide enough and violent enough to prevent apes from crossing it. This meant that from that point forward, any mutations that happened on one side of the river would not spread to the other side of the river. This caused different mutations to accumulation on each side of the river, resulting in genetic divergence.

You have a good imagination. Ha ha.
A river does not work that way. Sorry.

 

[digitalgoth]

Why was there isolation at the first place? If it started with chimp and bonobo populations separately, then what is the point of this study?

Form the article:

Two African apes are the closest living relatives of humans: the chimpanzee (Pan troglodytes) and the bonobo (Pan paniscus). Although they are similar in many respects, bonobos and chimpanzees differ strikingly in key social and sexual behaviours1, 2, 3, 4, and for some of these traits they show more similarity with humans than with each other. Here we report the sequencing and assembly of the bonobo genome to study its evolutionary relationship with the chimpanzee and human genomes. We find that more than three per cent of the human genome is more closely related to either the bonobo or the chimpanzee genome than these are to each other. These regions allow various aspects of the ancestry of the two ape species to be reconstructed. In addition, many of the regions that overlap genes may eventually help us understand the genetic basis of phenotypes that humans share with one of the two apes to the exclusion of the other.

Phenotypes, which is the expression of the genes.

That's not fenotypes, that only lunatics use.

 

[DogmaHunter]

So, the type of GA you are designing is one that seeks the best track which leads a group of original objects to change most efficiently toward a special goal.

Is that right?

Almost.

Try: a specific outcome.

The way you phrased it, it seems to state that the end design of the to-optimised system is the goal. That's not the case. If that end design would be known, we wouldn't need GA's for optimization purposes.

The easiest way, imo, to understand it is to think about a specific example.

Suppose you have a fluid distribution system. There's input from one point on the left and the fluids need to be distributed to 7 different points on the right.

You design a structure of pipes etc but you find that your design doesn't live upto the requirements. Perhaps the pressure is too low on the 7 points or some of those 7. Perhaps the requirement is that the fluid needs to arrive at all 7 points at the same time, while your solution doesn't provide that.

You can then design a genetic algorithm that does exactly that: evolve the system of pipes to meet all requirements. To optimise the structure to zero in on the required outcome.

If you already know what structure design would provide the best performance, you wouldn't need a GA to find it for you.

 

[DogmaHunter]

You have a good imagination. Ha ha.
A river does not work that way. Sorry.

??

Don't work what way?

This didn't make any sense. Rivers form. If a newly formed river happens to cut right through a population of a certain species, ... well... guess.

 

[digitalgoth]

So, the type of GA you are designing is one that seeks the best track which leads a group of original objects to change most efficiently toward a special goal.

Is that right?

To continue on what DogmaHunter said...

Genetic Algorithms are very good at solving problems where you don't know the best way how to achieve something, but you know how to measure that you've achieved it.

A classic use that genetic algorithms are used for is scheduling of resources.

You have a company that operates 24/7. You have a thousand employees working in three shifts.

You need to create a schedule that will maximize coverage of operations, but minimize the number of employees needed. You want at least 30 people available for each department, but not more than 100. You need people to take breaks at different times as to not have a drop in coverage. You don't want more people standing around doing nothing if they aren't needed. You need to calculate coverage when people have applied for future vacations or time off that will affect that. You need a certain amount of managers covering the workers. No worker should work more than 5 consecutive days, and half your employees are part-time, so they can't work more than 20 hours a week or you have to pay them overtime. No worker can work more than 8 hours in a single 24 hour period. It is preferred that no workers hourly schedule alters their shift more often than every two weeks, and they must have a weekend in between shift changes.

Now to do this with five people is easy. To do this with a thousand people is much more difficult. It would take a team of people and a lot of complex if/then statements in code to possibly do this, and if you change the number of employees you have to go back and restart everything.

Genetic algorithms can solve this very easy and quickly.

You can randomly create, say, 20 schedules of all thousand employees. It doesn't matter if they even logically make sense, its all just random.

Each schedule is evaluated, and it is scored based on how closely that schedule is optimal to the rules stated above.

The "better" scored schedules are blended with some other "better" scored schedules to create the next generation of schedules in hopes of getting an even better one. Because all your randomly created schedules aren't very good, you occasionally change parts of it, such as shifting someone's break time randomly, or assigning an additional person to a shift. Then you evaluate the descendants.

This goes on over and over until a schedule is produced that matches your criteria, or comes close enough to it to be acceptable.

It's almost impossible to manually schedule your employees without spending significant time and resources to do so, and even a small change can throw the schedule off. A genetic algorithm can execute millions of schedules and evolve them to one that matches your criteria. You can easily measure if it's is a good schedule, but you can't easily create a good schedule.

This is the strength of Genetic Algorithms in this kind of situation.

 

[Loudmouth]

You have a good imagination. Ha ha.
A river does not work that way. Sorry.

Haha, all we have is your say so. HAHA.

Any evidence?