So the discussion on AI begins. I’ll use specific terms to refer to distinctions in these discussions. The areas of coverage are:
- Genetic Algorithms
- Genetic Programming
- Artificial Life
- Emergent Computation
The definitions here are not formal. These are four distinct disciplines and while they may be combined when attacking problems, each of these disciplines stands on its own. It is important as well to distinguish, that while these definitions may become useful for reference, they are not comprehensive.
Genetic Algorithms
A class of algorithms that attempt to solve problems using, but not limited to, the genetic operators selection, crossover and mutation on a population of fixed locus candidate solutions over a fitness function. The distinctions here between GA and other evolutionary or genetic methodologies are simple:
- A GA puts the emphasis on selection and crossover operations
- The candidate solution is genetic material of a fixed length with fixed locus, i.e. the candidate solution is a bit string of fixed length where each bit or group of bits (gene) represents an exact part of the solution over an alphabet, or allowable set of values (allele).
It is important to note that the application and usage of GA over other methods of solution discovery, is primarily about the reduction in the cost of the discovery of the solution. This typically involves a reduction in the computational effort. Another important note here is that this discussion is about Simple Genetic Algorithms or SGA. Other GA representations may become more complex and begin to look like GP.
Genetic Programming
A class of algorithms that attempt to solve problems using, but not limited to, the genetic operators selection, crossover and mutation on a population of programs. The distinctions here between GP, GA and other evolutionary or genetic methodologies are simple:
- GP puts the emphasis on selection and crossover operations
- The candidate solution is genetic material implemented in a program classified by language family and representation.
- Functional programming GP
- Tree GP (as prescribed in LISP by Koza)
- DAG Tree GP (as prescribed by Keijzer and others)
- Imperative programming GP
- Standard imperative GP (on a known imperative language such as C# or VB.Net)
- Linear GP (as listed by Banzhaf, Nordin, Francone and Brameier)
- Other language GP (of which I know of at least five)
Like it’s cousin, GA, it is important to note that the application and usage of GP over other methods of solution discovery is primarily about the reduction in the cost of the discovery of the solution. This typically involves a reduction in the computational effort.
Another great feature of GP is that many of the same principles in a GA apply to GP in modeling, populations, fitness function definitions and the genetic primitive operators. A common distinction between GA and GP lies in the ability of a GP to properly represent recursion, iteration and other language constructs as primitives that participate in the discovery of the solution. Furthermore, GP can be used to automatically discover parts of itself that are useful when searching for the answer to a problem. Koza’s ADF in "Genetic Programming Volume 2" covers this topic.
Artificial Life
While Artificial Life refers to many things, it commonly refers to simulations that perform activities that are similar to behaviors in life. Agent based computing in ECHO, Tierra and Swarm are examples of Artificial Life. As Artificial Life is paired with EC regularly, I’ll provide information below. The distinction between ALife and EC is that ALife focuses on the agent, and EC focuses on the emergence. Both overlap in many respects. In fact, many in this field may argue that the two disciplines are the same.
Emergent Computation
Emergence within the context of Emergent Computation is the process by which patterns form from simple rules.Emergent Computation is the construction of observable emergent behaviors and events.
Typical examples of emergence are flocking and herding behaviors. Consider the following: Why do birds flock? Ask the following questions:
- Is there a central authority bird that controls every flock?
- How does an individual bird decide to join a flock?
- How does an individual bird decide to leave a flock?
- When flocking, how does a bird know what to do to make the flock?
There isn’t a Senior VP bird that says, "Hey. Let’s go flocking". Birds just flock by instinct. But there must be a set of rules that determine how the emergence of flocking occurs. Lets try the following rules (from a bird’s point of view):
- If I’m awake, I’ll rest, look for food or fly around.
- If I’m at rest, I’m on a branch, an electrical wire or someplace safe.
- If I’m hungry, I’ll look for food by flying around.
Still no flocking, yet. Lets expand the list. If the bird is not at rest, is not hungry and wants to do some flying, instincts must settle in and allow the bird to look for friends, i.e. I’m flying or I’m at rest and I want to fly:
- I look for other birds of my type that are within my field of vision. I fly toward them.
- If I’m near other birds, I must attempt to match the direction of the bird(s) nearest to me. I’ll try to fly in the same direction as 4-5 of my neighbors.
- If I’m near other birds, I don’t want to bump into them, so I want to keep a safe distance from them. I’ll try to stay about 2 meters from those same neighbors.
- If I’m near other birds, I want to continue to fly with them, so I should try to maintain speed (along with direction, we have velocity). I also don’t want to bump into the birds in front of me, so I can’t fly too quickly.
These rules have been shown to produce emergent behavior. In other words, if I have an Artificial Life simulation of birds that are capable of moving and flying and I add these rules, will I witness flocking? Craig Reynolds famous boids was one of the first simulations to demonstrate that this behavior was reproducible in artificial environments.
For the purposes of discussion here, I’ll refer to models of EC (as opposed to ALife) as I typically focus on the emergence and not the agent.
Emergent computation and genetic programming are my favorite hammers for much of the work that I do.
Occasionally, I have sleeping problems. During one of these periods (over a few weeks), no matter what I try or how I try, I fall asleep later and later into the night. Eventually my schedule either corrects itself from sleep deprivation or I end up in DNSIS (day-night sleep inversion syndrome).
I hate it when it happens, but I have to thank an anonymous friend of mine for coining the term. At least I have a name for it.
Stop me if you've heard this one . . .
There are three types of people in this world: Those that are good at mathematics and those that are not.
Summary: Rated 9 out of 10 possible points. List of problems in number theory that are easy to state, but hard to solve. For the mathematically challenged, lots of squiggly symbols interspersed with names of math guys. For the professional mathematician (which I am not), lots of squiggly symbols interspersed among names of friends
After an attempt to consume this book cover to cover, I find myself humbled, sweating profusely and in dire need of some serious therapy.
Richard K. Guy has released the third edition of this book to the world with little fanfare and with little notice from the general population. As its title states, this book is a catalog of problems that remain unsolved in that branch of mathematics known as Number Theory
Having read, but not owned previous editions of this book, I find this book to provide new and useful information and updates in this field. The second edition of this book was published in 1994, just as Andrew Wiles was completing his work to solve Fermat’s Last Theorem. This book extends this reach since 1994 and provides for a distinctly broader view of the class of mathematics problems that are "easy to state", "but difficult to solve".
Another great addition to this book is that many of these problems now provide the catalog reference to Neil Sloane’s Online Encyclopedia of Integer Sequences (OEIS).
I wish that I could personally thank Mr. Guy for this fantastic work. While many may find these problems trivial and pointless, those that find value in these exercises are indebted to him and his tireless search for this information. I myself have held my nose in this book for countless hours and learned a great deal from him. I hope life finds him in great spirits and health to publish the fourth edition of this work in the coming years.
Over the next several months, I intend on posting GP projects for the following:
-
GP starter application. GPI (Genetic Programming I) will be a demonstration of Tree based GP and other salient features of this common family of GP. It will simulate the control of a moveable unit on a bounded surface (ok, a gamepiece on a gameboard, if you use your imagination), that minimizes the total distance to complete some objective on the surface while avoiding obstacles.
-
GP Unit Test evolution. Imperative form GP will be used to evolve unit tests. Many unit tests provide insufficient coverage for the problem domain. They test a few useful cases, but fall short of on many fronts. Before I anger my TDD friends or other TDD community members, take some time and get a backgrounder on Hoare Calculus and Hoare Logic. I hope to use First Order Logic and Graph Theory heavily in this one as well.
-
GP Pattern evolution. Undisclosed form GP will be used to determine if a problem space with known software patterns as implemented by a human programmer can be improved. Would "new" patterns evolve, what constitutes a sufficient vs optimal state, what patterns are "better" at certain tasks in implementation are all questions that I'm considering for this project.
-
GP Performance Tuner. Imperative form GP will be used to take a current code sample and determine whether it is sufficiently implemented. The GP would use various forms of either CODEDOM, IL or other primitives along with a known set of unit tests to determine if evolved versions of the code could be discovered.
These projects will include full articles, .Net C# downloadable projects and reasonable tutorials. Because I will be writing these in my spare time, which is sparse, I won't release a schedule for these. I expect that GPI will be available within 30 days. The others, may take a bit more time . . .