Genetic Algorithms... Simply Amazing

[Luminal]

Several months ago I began reading up on genetic algorithms, and the impact they are going to potentially have on technology is earth-shattering.

 

I was at a workshop a few weeks back and saw a demonstration of a genetic algorithm in real-time on screen. It was simply several arms working in coordination to find the best angles and shortest path to hold onto a moving ball.

 

Several times while the presenter was talking (he hadn't touched the computer for minutes), the program suddenly started moving again and found a better position, then became inactive again.

 

The applications in every field of science (and even art, music, and literature) are quite literally limitless.

 

Human beings are the product of a genetic algorithm running for several billion years. However, our genetic algorithm took years to decades to move from one generation to a next, and had no specific reinforcer of a new mutation other than survival.

 

However, with artificial genetic algorithms, each generation takes place in the frame of milliseconds or less. On top of that, we can reinforce many, many goals in a mutation, not only survival.

 

And most importantly, we can create genetic algorithms controlling the parameters of the genetic algorithms themselves. This would be as if the whole of the DNA of all species on Earth could be tweaked to have a triple helix instead of a double helix to store vastly more information.

 

Why don't we hear more about this field?

[insane_alien]

Why don't we hear more about this field?

 

you just aren't listening in the right places. it is used in microchip manufacture. your processor was probably designed by a genetic algorithm.it's also used in aircraft design i believe.

[timo]

Are "genetic algorithms" the same as genetic optimization, is genetic optimization just a special case of a genetic algorithm or are the two unrelated? I find it very far-called to say that "the applications in every field of science are quite literally limitless". The reason why you don't hear more about the field? Probably the same as with density functional theory, maximal helicity-violating amplitudes and Monte-Carlo integration: Steven Hawking didn't mention it in his books .

[Edtharan]

As a demo in my year 12 computer class (about 12 -13 years ago now) I created a genetic algorithm to solve the travelling salesman problem.

 

The travelling Salesman problem is where a salesman wants to visit several cities, but wants to do it in the shortest time possible. He can start from any city and finish in any city, but can not visit a city more than once.

 

If you use a brute force approach, as the number of cities increases the number of possible paths that the salesman could take rises very quickly. For instance: with just 2 cities (A and B) there is 2 paths the salesman can take A -> B (and B -> A). With 3 cities (A, B and C) there are 6, with 5 cities there is 120 paths and with 10 cities there are 3,628,800. Imagine with 80 cities!

 

Searching all these paths using brute force is virtually impossible.

 

Using a simple Genetic algorithm I was able to generate a near solution (that is I could not guarantee that is was the shortest, but is was close) very quickly (20 cities with 2,432,902,008,176,640,000 paths in around 30 seconds). And this was 12 years ago.

 

The algorithm I used listed each path as a string of symbols (integers representing an ID number of the city).

 

I generated 1,000 of these strings and measured them for their length (using a lookup table of the inter city distances). The shortest 90 of these strings I kept and the rest I discarded.

 

Then for each string I kept, I made 9 copies (and kept the original) and "mutated" each copy by randomly selecting one of the cities and swapping it's position in the string with another random city on the string (as an example if I had a string like ...1, 2, 3, 4, 5... it might turn out like ...1, 2, 5, 4, 3... where 5 and 3 are swapped).

 

This would leave me with 900 strings, so I would then generate 100 more strings, but they would be completely random (that is they were not based on any string made previously). This would bring me back to the 1,000 strings and I would repeat the procedure again and again.

 

After about 30 seconds (for the 20 cities) the path length would have stabilised and this would be the near solution of the problem.

 

The applications in every field of science (and even art, music, and literature) are quite literally limitless.

I had a screen saver that used genetic algorithms to generate a short animation, so it can be used for art too.

 

A Genetic algorithm that used the genome as a music score might be interesting to attempt. You could output it as a midi file and let people down load each song and vote on the ones they like the best. The "songs" that people like the best are then "bred" and so are used to make the next "generation" of songs.

 

As for their use in "every" field of science, I'm not sure. It might be a bit of a stretch to use it in astrophysics. However, some scientific fields it would be extremely useful in. Although, chemistry would be a good field as you could describe a chemical formula as a GA (genetic algorithm) and have it design new chemicals for you.

 

And most importantly, we can create genetic algorithms controlling the parameters of the genetic algorithms themselves.

I have never though of something like this. However, each GA needs to have some selection criteria with which it defines the fitness of each Entity. What would be the selection criteria that the top level GA would be selected for?

 

This would be as if the whole of the DNA of all species on Earth could be tweaked to have a triple helix instead of a double helix to store vastly more information.

From what I have heard, Triple helices are actually possible in DNA, although I have never heard of it occuring naturally.

 

With a double helix though, if you want to store more "data' then it is far easier to just increase the length of the DNA strand than to add in another helix. It is also the same with GAs too. Just increase the length of the array that the "genetic" data is stored in.

 

you just aren't listening in the right places. it is used in microchip manufacture. your processor was probably designed by a genetic algorithm.it's also used in aircraft design i believe.

Yes, GAs are used in many industries and fields. They do have the potential to revolutionize the world. And are currently doing so.

[lucaspa]

Are "genetic algorithms" the same as genetic optimization, is genetic optimization just a special case of a genetic algorithm or are the two unrelated?

 

Genetic algorithms are natural or Darwinian selection. And yes, the implications for every field of science are enormous. The reason is that natural selection is much smarter than we are. Therefore people are using it for design problems that are too tough for us. Some examples where this is routinely being used -- and where it impacts your life:

 

1. MJ Plunkett and JA Ellman, Combinatorial chemistry and new drugs. Scientific American, 276: 68-73, April 1997. Summary of article: "By harnessing the creative power of Darwinian selection inside a test tube, chemists can now discover compounds they would not have known how to make. The key is combinatorial chemistry, a process that allows them to produce and screen millions of candidate molecules quickly and systematically."

2. GF Joyce, Directed molecular evolution. Scientific American 267: 90-97,July 1994.

4. G Taubes, Evolving a conscious machine. Discover 19: 72-79. June1998. Uses a Field Programmable Gate Array (FPGA) chip that can reprogram its architecture. Adrian Thompson of Univ. of Suxxex used Darwinianselection to have chip write its own architecture to solve problems. First problem was to distiguish between 1 kiloHz and 10 kHz sound. Allocated only 100 logic elements out of 4,096. Chip did the job withonly 32. Thompson can't figure out how. A chip designed by a human would require 10 to 100 times as many logic elements -- or at least access to aclock -- to perform the same task. "There are properties that humans have great trouble designing into a system, like being very efficient, using small amounts of power, or being fault tolerant. Evolution can cope withthem all."-- Thompson.

6. CW Petit, Touched by nature: putting evolution to work on the assembly line. US News and World Report, 125: 43-45, July 27, 1998. Use "genetic algorithms" (cumulative selection) to get design in industry. Boeing engineers had cumulative selection design a wing forthem for a jet to carry 600 passengers but have a wing the same size as a 747.

9. FS Santiago, HC Lowe, MM Kavurma, CN Chesterman, A Baker, DG Atkins,LM Khachigian, New DNA enzyme targeting Egr-1 mRNA inhibits vascular smooth muscle proliferation and regrowth after injury. Nature Medicine 5:1264-1269, 1999. Used Darwinian selection to design a DNA enzyme (not found in nature) that degrades mRNA for use in treating hyperplasia after balloon arthroplasty. Humans have no idea what the nucleotide sequence of the DNA enzyme because they didn't make it --Darwinian selection did.

10. Breaker RR, Joyce GF.A DNA enzyme that cleaves RNA. Chem Biol 1994 Dec;1(4):223-9

14. Jr Koza, MA Keane, MJ Streeter, Evolving inventions. Scientific American, 52-59, Feb 2003 check out http://www.genetic-programming.com

 

Human beings are the product of a genetic algorithm running for several billion years. However, our genetic algorithm took years to decades to move from one generation to a next, and had no specific reinforcer of a new mutation other than survival.

 

Well, DUH! Since genetic algorithms are natural selection, yes we are a product of natural selection!

 

"Survival" is the same reinforcer in GA. In this case, the human sets the environment and only those variations which "survive" in that environment reproduce. So don't discount survival.

 

On top of that, we can reinforce many, many goals in a mutation, not only survival.

 

No, you only reinforce survival -- survival in the environment you set up.

[Luminal]

Well, DUH! Since genetic algorithms are natural selection, yes we are a product of natural selection!

 

"Survival" is the same reinforcer in GA. In this case, the human sets the environment and only those variations which "survive" in that environment reproduce. So don't discount survival.

 

No, you only reinforce survival -- survival in the environment you set up.

 

Well, let's just say "reinforcing specific varying forms of survival" whereas natural selection can only reinforce survival as a whole.

 

For example, natural selection produced highly successful and very different species, such as humans, ants, mosquitoes, krill, and certain types of weeds. These species survive for different reasons, but natural selection wasn't aiming at intelligence for humans, or complex colonies for ants, or parasitism for mosquitoes, and so forth. In the last 100,000 years, humans could have possibly evolved in an entirely different direction from larger brains and intelligence. If we survived the transition, humans would still be around but much, much different.

 

When I say "we can reinforce many goals," we can specifically reinforce a certain type of survival, whereas evolution doesn't mind what type, as long as it survives.

[dichotomy]

When I say "we can reinforce many goals," we can specifically reinforce a certain type of survival, whereas evolution doesn't mind what type, as long as it survives.

 

Just a side point. And, I’m not sure that you are arguing this point, but here goes.

 

I keep hearing the statement, ‘natural evolution is very different to human manipulated evolution (technological evolution)’, in various guises. Now, just because humans can ‘specifically reinforce a certain type of survival’, this doesn’t mean it is not natural evolution, IMO. It is just how evolution works within the time of the Homo-sapiens rule of planet earth.

[Luminal]

Just a side point. And, I’m not sure that you are arguing this point, but here goes.

 

I keep hearing the statement, ‘natural evolution is very different to human manipulated evolution (technological evolution)’, in various guises. Now, just because humans can ‘specifically reinforce a certain type of survival’, this doesn’t mean it is not natural evolution, IMO. It is just how evolution works within the time of the Homo-sapiens rule of planet earth.

 

I do not think it is "very different" from natural evolution; it is natural evolution. In my opinion, it is the natural next stage of evolution on this planet. It is a smooth, logrithmic trend. From billions of years of bacteria, to several hundred million years of fish and reptiles, to only a few tens of millions of years of mammals ruling the earth after the extinction event. Within several tens of thousands of years, humans developed language, agriculture, cities, nations, governments, and so on. In the last 500 years, we've of course had the Renaissance, Agricultural Revolution, Industrial Revolution, and a huge population explosion. Next, I believe increasingly complex and independent GAs will continue the trend at an advancing rate.

 

For evolution to continue increasing speed, it needs to be capable of changing its "hardware" so to speak. Biological generations take decades; G.A. generations take (very small) fractions of a second.

[lucaspa]

Well, let's just say "reinforcing specific varying forms of survival" whereas natural selection can only reinforce survival as a whole.

 

For example, natural selection produced highly successful and very different species, such as humans, ants, mosquitoes, krill, and certain types of weeds. These species survive for different reasons, but natural selection wasn't aiming at intelligence for humans, or complex colonies for ants, or parasitism for mosquitoes, and so forth. In the last 100,000 years, humans could have possibly evolved in an entirely different direction from larger brains and intelligence. If we survived the transition, humans would still be around but much, much different.

 

When I say "we can reinforce many goals," we can specifically reinforce a certain type of survival, whereas evolution doesn't mind what type, as long as it survives.

 

I think you are confusing the contingency of evolution with "type of survival". Within a particular environment, "survival" means having particular designs. Not all designs work in all environments.

 

In all the examples of genetic algorithms I have seen, humans pick the environment. For instance, Thompson picked an environment where the computer circuit discriminated types of speech. Exactly HOW natural selection did that was up to natural selection and, in fact, natural selection found a way that Thompson doesn't understand.

 

Now, Thompson can change the environment such that he can add variables such as fault tolerance, etc. and natural selection will figure a balance between that and speech recognition. IOW, Thompson will still ONLY select for survival, but the environment he sets will be more complicated.

 

In nature, the environment is VERY complex, since environment is EVERYTHING that interacts with the individual. In the hominid lineage populations faced different environments and ecological niches. And yes, natural selection designed for them all. The entire genus Paranthropus was designed to be herbivorous. H. neandertals were evolved for a cold climate. So yes, many species of hominids did evolve differently. H. sapiens is the one that replaced the others. However, with an ecological niche where big brains and intelligence does well, natural selection would have evolved SOME species to fill it. That species may not even have been from primates. If the KT extinction hadn't occurred, the species could possibly have been from raptors.

 

However, Thompson's circuit could also have evolved very differently depending on the contingencies of the variations available. He would still have had a circuit that discriminated speech, but it would have been different.

 

I keep hearing the statement, ‘natural evolution is very different to human manipulated evolution (technological evolution)’, in various guises.

 

"Technological evolution" is very different from biological evolution. Machines do not have inheritance. Instead, the Darwinian selection of designing machines is taking place in human minds. In essence, humans make the mental variations.

 

Only when humans use genetic algorithms are they using natural selection. The variations are NOT coming from human minds, but are generated by the system.

 

"Evolution" has come to mean "change" and often is applied to individuals. However, biological evolution applies only to POPULATIONS. Populations evolve, not individuals and not "technology". Technology changes.

 

So, what humans are doing technologically is NOT evolution. Sometimes humans use natural selection in design: genetic algorithms.

[dichotomy]

"Technological evolution" is very different from biological evolution. Machines do not have inheritance. Instead, the Darwinian selection of designing machines is taking place in human minds. In essence, humans make the mental variations.

 

Only when humans use genetic algorithms are they using natural selection. The variations are NOT coming from human minds, but are generated by the system.

 

"Evolution" has come to mean "change" and often is applied to individuals. However, biological evolution applies only to POPULATIONS. Populations evolve, not individuals and not "technology". Technology changes.

 

So, what humans are doing technologically is NOT evolution. Sometimes humans use natural selection in design: genetic algorithms.

 

If this is the current paradigm, I understand it and can see the logic in it when it specifically refers to the body as involving darwinian evolution, and not the mind. But still, I disagree with this paradigm if it removes the mind from natural evolution. Or, conveniently disregards it. Like you stated – “Instead, the Darwinian selection of designing machines is taking place in human minds, humans make the mental variations”.

I’m not saying that man’s technology itself is naturally evolving. I’m specifically referring to the human mind evolving and producing new variations on technology and creativity, using the minds genetic algorithms. If this is called evolutionary psychology. That's fine. I just think it's a little dated to separate mind and body evolution if mind is not considered natural evolution. Having said that, if Darwin didn't see mind as part of his theory, I think he'd change his mind today.

 

I do not think it is "very different" from natural evolution; it is natural evolution.

 

I agree.

 

 

 

For evolution to continue increasing speed, it needs to be capable of changing its "hardware" so to speak. Biological generations take decades; G.A. generations take (very small) fractions of a second.

 

I don't agree that man's machines, all by themselves, naturally evolve. If this is what you are suggesting. Machines build machines, yes? But, machines don't naturally, biologically evolve other machines into existence.

[Luminal]

I don't agree that man's machines, all by themselves, naturally evolve. If this is what you are suggesting. Machines build machines, yes? But, machines don't naturally, biologically evolve other machines into existence.

 

No, I'm not saying that.

 

Think of it this way. Humans are a product a biological evolutiuon. Thus, any creation of a human is indirect biological evolution.

 

So, if at some point in this century (I personally believe this will happen within a decade at the current rate, but you may have a differing opinion) humans program a sufficiently complex G.A. that has enough complexity to exist as a physical entity and maintain its existence and become more complex over time... then ultimately, it is a descendant of biological evolution.

 

The lines between biotic and abiotic are going to get very blurred as our programs continue to shrink, add complexity, and maybe even one day self-replicate.

 

You might disagree, but unless we pass laws prohibiting naturally evolving machines, they are indeed the next stage of evolution.

 

Why?

 

1) Because the time between their generations is arbitrarily short (as fast as the computer itself).

2) Because mutations can be induced constantly, and are not just "copying accidents".

3) Because current life's genetic material, although extremely small, complex and versatile, is at a standstill in its underlying mechanics. Non-biological evolution will continue to get smaller and faster for centuries, until literally physical laws prohibit further progression (however many orders of magnitude beyond DNA this is, who knows). Every new technology can and will be implemented (such as quantum computing).

[Edtharan]

You might disagree, but unless we pass laws prohibiting naturally evolving machines, they are indeed the next stage of evolution.

 

Why?

 

1) Because the time between their generations is arbitrarily short (as fast as the computer itself).

2) Because mutations can be induced constantly, and are not just "copying accidents".

3) Because current life's genetic material, although extremely small, complex and versatile, is at a standstill in its underlying mechanics. Non-biological evolution will continue to get smaller and faster for centuries, until literally physical laws prohibit further progression (however many orders of magnitude beyond DNA this is, who knows). Every new technology can and will be implemented (such as quantum computing).

I would actually say there is also a 4th and 5th reason too.

4) Any Genetic algorithm based life created by humans, will be able to access documentation on the structure, organisation and operation of their genome.

 

5) Because of the machine that the genetic algorithm is processed is not directly the result of the process of the GA (but it can be an indirect result - as computers are an indirect result of our own genetic code), then they will have much more freedom to change their genetic code than biological life does.

 

These last 2 reasons mean that any development from GAs (once they become self replicating (rather than being dependant on human intervention as it does now - we have to write the programs, specify the selection criteria, etc), then it will follow a non linear development.

 

Through documentation, they will be able to redesign their own genome to increase their fitness intelligently. They can therefore increase their intelligence, which then allows them to redesign their genome to produce more intelligence, which feeds back into allowing them to design their genome to give them more intelligence, as so on.

 

If we could have as complete documentation about our genome as any GA based entities created by ourselves would have, then we could do the same (baring ethical debate and law). However, because of reason (1), we will not be able to develop at the same rate that a GA based entity could.

[Luminal]

I would actually say there is also a 4th and 5th reason too.

4) Any Genetic algorithm based life created by humans, will be able to access documentation on the structure, organisation and operation of their genome.

 

5) Because of the machine that the genetic algorithm is processed is not directly the result of the process of the GA (but it can be an indirect result - as computers are an indirect result of our own genetic code), then they will have much more freedom to change their genetic code than biological life does.

 

These last 2 reasons mean that any development from GAs (once they become self replicating (rather than being dependant on human intervention as it does now - we have to write the programs, specify the selection criteria, etc), then it will follow a non linear development.

 

Through documentation, they will be able to redesign their own genome to increase their fitness intelligently. They can therefore increase their intelligence, which then allows them to redesign their genome to produce more intelligence, which feeds back into allowing them to design their genome to give them more intelligence, as so on.

 

If we could have as complete documentation about our genome as any GA based entities created by ourselves would have, then we could do the same (baring ethical debate and law). However, because of reason (1), we will not be able to develop at the same rate that a GA based entity could.

 

I entirely agree. If I let my mind wander when thinking about all the problems that G.A.s could help solve and how far they will push technology during the 21st century, I get shivers.

 

I think its sad that Genetic algorithms/Genetic programming receives such little "air time" in the public's eye when compared to other notable technologies in the works, such as stem cells, cloning, top-to-bottom AI approaches and so forth.