Introduction to Non-Genetic Darwinism/Non-Biological Darwinism

w:Picture

Type classification: this is a lesson resource.

Aims

1. To Introduce the Evolution Algorythm
2. To show how it has been used in Engineering and Computer Science
3. To introduce the Idea of Self-Ordering or Self Organizing Systems
4. To make the case that Evolution is just one type of Self Organizing Sysetm

Lesson

The Evolution Algorithm, a Heuristic

When Computer Scientists and Artificial Intelligence experts looked at Evolution, they saw the fact that it was a self-organizing system, and wondered if they could catch the principles of it, in a special type of Algorythm called a Heuristic, or model of a natural system. In order to reuse the algorythm they wanted to abstract it down to its most basic structure, which ended up being three things, a Gradient against which to work, a Test that determined which population elements would go on to reproduce themselves, and a form of mutation, or recombination that could cause a perturbation in the general trend for the system to move in the direction of the gradient. Depending on how radical the test was, a portion of the population would be removed each generation, and the remainder would reproduce thus creating an opportunity for some elements of the population to move against the gradient. This made the Evolution Algorythm a hill climbing heuristic. What would happen is that most fatal combinations would be removed from the population over time, increasing the likelihood of survival of the remainder of the population because it would eventually diffuse from a position above the testing line. One interesting idea was that you could steer this algorythm by customizing the test so that it tested for different properties. The population would tend to drift in a direction away from the test, propelling it towards a goal.

Genetic Programming

One obvious method of using the Evolution Algorythm was in the development of an automatic prototyping system for programs. Called Genetic Programming because the programming language was rewritten to fit into the same general pattern as Gene encoding in DNA, The idea was to create a random population of program snippets, and Evolve them until they met some specification. Programs that failed to fit the specification would be eventually removed from the population, and an evaluation function would increase the likelihood that a good solution would reproduce and become part of the recombination of future generations. Since every algorythm would be evaluated, at the end of the process, a small population of really good combinations would exist that met or exceeded the specification. Of course it wasn't quite as simple as that, and the process required a major investment in processing time for the whole population to be evaluated, but the research indicated the feasibility of the approach.

Meta-Heuristics, Algorithms with an internal heuristic

Another less obvious way of using the Evolution algrorythm was to embed it into another algorythm, This mechanism called a Meta-Heuristic, because the actual algorythm included the heuristic within it, and therefore was a meta-algorythm or algorythm with an algorythm inside it, has been used most often for a search technique. Along with Evolution, other heuristics like Simulated Annealing, Neighborhood Algorythms Taboo Algorythms, and Greedy Algorythms have been used. These heuristics create a type of search that while it doesn't guarantee the best answer, comes to an answer faster than a brute force comparison search could. One place they are useful, is where speed is as important, or is more important than the accuracy of the search. One way of looking at Genetic Programming, is a search across most combinations of the genetic language for a solution that is good enough to pass the survival test. We promote it to Selection of a winning population by taking the Evaluation out of its context as a basis for the test, and using it to find the best solution in the population found. Evolution doesn't care which elements are the best, merely which follow the specifications as defined by the test used. But that doesn't mean we have to use it that way.

Meta-Heuristic Searches, and Self-Optimizing systems

One of the reasons we need Meta-Heuristics, is that some of the most natural functions of human processing, are hard to achieve computationally (As in with computers). One such difficult problem is the problem of optimizing a system, or changing it in a way that makes it more adaptive to its environment. As the number of elements you want to adapt increases, the size of the search space that must be searched increases logrythmically, It falls in a class of processing tasks that are labelled NP HARD, which if we translate it into English means that Even if we have a parallel processor with an infinite number of processor units, it would take a long time to execute. In the case of such a problem we can do one of three things, we can take the time up front, which slows down the processing of the rest of the system, as we use up all the processor cycles, We can spread the cost over time, by only doing a part of the optimization at any one pass, or we can cheat, and do a less accurate search and do it much faster than the classic brute force search could do. In some cases we might want to mix modes and do a faster but partial search thus spreading the cost over time, and speeding up the eventual results. Of course we won't necessarily get the best answer, but often all we need is an answer that is "Good Enough", and if it gets better over time, so much the better.

Similar Heuristics used in Meta-Heuristic Algorithms

The following Algorythms have been used in Metaheuristics.

• Genetic Algorythms
• Genetic Programming
• Evolution
• Ant Colony
• Estimation of Distribution
• Scatter Search
• Variable Neighbor Search
• Simulated Annealing
• Tabu Search
• Hybrids combining Breadth first Algorythms with later Depth first Algorythms

While each deserves it's own description, to do so would fall outside the scope of this course.

Why Meta-Heuristics are faster than and less accurate than brute force searches

The reason that Metaheuristics are faster than brute force searches, is simply because they only sample the search space, and do not search every element to find out if it is better then the next. They work best where there is some locality to the data, so that the best answers tend to aggregate in the same neighborhood. Where there is too much variation locally, they will miss the optimal local answer often, simply because they do not get a chance to compare it. However in the case where there is some locality of good answers, the search gradually gets more accurate in the area where there is the most chance of a good answer, and as a result, will while not always getting the most optimal answer, at least get a good one.

Auto-Prototyping in a Darwinian World

Once Auto-prototyping was proven to work in Genetic Programming, other engineering disciplines wanted in on the act, and other design languages were created that could be used in a Genetic Programming Environment to design other types of systems.

Digital DNA

The idea of Digital DNA, is that most digital circuits are made today as cells in a Field Programmanble Gate Array (FPGA), Since there are only a certain number of different cell designs, a Genetic Language could be developed that would create a chip to specifications in much the same way that programs were generated in Genetic Programming.

Printer of the Month Club, Marketing of Arbitrary Models

While I can't prove it, I suspect that of the reams of cheap printers being manufactured, many models are simply members of a Genetic Design population based on a much smaller set of actual printer mechanisms. Because the designs are so variable, and the production equipment is so flexible that it can do multiple different products at once, the result is that a model lifespan is much shorter on the design end, than it is on the actual user end. I jokingly call it the printer of the month club, because it seems whenever I drop into the store, a new design is being sold on a discount because it is being discontinued by the manufacturer, and a new line is being brought out.

Self-Ordering Systems

Although little understood, the concept of self-organization may be an important driving force in evolution. Self-organization occurs in many types of systems; phase transitions such as crystallization or the alignment of molecules to form a cell membrane, for example, exhibit self-organizing properties. Self-Ordering or Self-Organizing systems may still be somewhat alien to our understanding of how the world works. It is partly because of the existence of systems such as these that we need to rethink Darwinism, and the 2nd Law of Thermodynamics. Self-Ordering or Self-Organizing systems show the ability to organize into greater order, or into entities that are greater than either chance or the sum of their parts would indicate. A heuristic called simulated annealing, is often used in the same way that the Evolution Algorithm is used in meta-heuristics. It is based on a popular technique for softening metal, the technique, called annealing, calls for reheating the metal, while it is cooling so as to remove flaws in the crystal structure, and grow larger crystals. The result is a more malleable piece of metal. The similarities in these two Algorithms, may indicate a common principle in how they work. That such a common principle is involved in all Self-Organizing Systems, has not yet been proven.

The role of Darwinism in Self-Ordering Systems

If we limit Darwinism to Genetics, then there is no role of Darwinism in self-ordering systems, it is simply a special example of one. But if we look a little closer at Darwinism, we see that it does not need to be as tightly defined as all that. What Darwin Discovered was that Natural Forces acting on a population, result in Self-Ordering behavior. He called this principle Natural Selection, because he noted that it acted to select some elements of the population, to breed and others not to, in a way that seemed similar to how animal husbandry selected to create a breed. The factor that he thought made the difference was survival. Perhaps however, this is just the most obvious factor. Any Factor which acts to select between one individual and the next in the propagation of that factor in the population will work. Even I joke, bad breath.

Taking apart the Evolution Algorythm

If we look at the evolution algorythm we see that the main element in direction is the test, if we change the specifics of the test, we change the eventual characteristics of the population. So why do we need the gradient and the mutation rate? Those are needed to build the search background in which the test searches. Essentially there is a near infinite number of combinations that can be formed within the Universe, However not every combination is stable enough to survive. The gradient determines how quickly a combination will degrade back to its more simple elements, and the Test, determines which combinations will degrade soonest. The Mutation rate is simply a way of sampling a wider range of combinations. The more recombination and mutation happens the wider the diversity of the population, and incidentally the more combinations can be tested.

Simplicity of the Algorythm versus Complexity of Genetic Evolution

Are we talking about the same thing, when we talk about the Evolution Algorythm and Natural Selection? Perhaps not, The Evolution algorythm is much simpler than genetics. However, partly that is because DNA is a language similar to the languages we have developed for Genetic programming and Digital DNA. We can use the Evolution Algorythm to interpret our genetic languages, or we can use it as a search algorythm in an arbitrary data field. The Algorythm works both ways, and in just this manner, Darwinism might work to explain self-organization that does not involve Genetics.

Assignment

• Consider the Lazy God Hypothesis, that God Invented Self-Organization so he could spend more time on the golf course. Is this more or less absurd than the idea that the Universe that we know, is built from many different systems that self-organized naturally, without the need for genetics, and other systems that evolved because genetics was possible? Write a short essay on the subject.

• Consider that you want to design a program that does the Tower of Hanoi problem where you have different sized rings on three different "Towers" and you have to sort them from largest to smallest but can only move one ring at a time. You have a Genetic Programming system ready to help you, how would you describe the problem to the Genetic Programming System so it could evolve you a program that could do the project. Look up the Algorythm for solving the puzzle in an algorythm book, does this help?

• On the last problem, one of the things you have to do, is decide the size of the population base on which you will base your Genetic Programming Attempt. The wider the population the more sure you are that you will come up with a solution, but the longer it will take to do all the tests to see if each element in the population will survive to go on to the next generation. Considering that it takes a millisecond per element to test, and you are going to try 10,000 generations just to be sure that you get a really good implementation, and you have a Cluster computer that is 80% efficient and has 8 nodes each running at 2 ghz. How big can your population be, if you want the program to terminate sometime next week?

• Go Down to your local Computer Store and look for the cheapest printer on the shelf. Wait a month and go down to the same store and look for the cheapest printer again, is it the same printer? or has someone replaced it with a different model. Look closely at the specifications, do you think the actual mechanism the printer is built on has changed, or are they just mixing and matching a lot of different parameters to make the printer seem different?

<< Back >> << Next >>