## Archive for the ‘source code’ Category

## Cellular Automata

In Wolfram’s book “A New Kind of Science” he studies cellular automata. What is also interesting is the approach he is taking. Rather than take something we know and try to figure out the rules, he tries different rules to see what they will create. While his book was badly received when it came out, other’s have found great success using this approach recently.

Wolfram was hardly the first to use cellular automata to mimick real life. Martin Gerhardt and Heike Schuster created ‘HodgePodge’ a cellular automata to mimic a chemical reaction. They explained it as using a discrete form of a differential equation. Since we have described most natural phenomena with differential equations that may explain why we have not done more with cellular automata. We just haven’t needed it. We may find use for it in things we can not yet easily describe with differential equations.

For example, cellular automata has found success in artificial intelligence in solving echohydraulics modeling problems. Cellular automata is also being used in pattern recognition, image processing, fluid mechanics and bioinformatics.

Cellular automata is simple rules repeated over and over. While one would expect simple patterns to emerge and repetitive patterns to emerge, non-repetitive and complex patterns also emerge in some cases. The two examples shown use only two colors and simple rules. Three colors leads to many more complex designs.

Nested: If either neighbor but not both neighbors in previous row are black-> color this cell black else color it white.

Irregular: If self and right neighbor in previous row are white then self is same color as left neighbor in previous row. If self and right neighbor are not both white then self is opposite color of left neighbor in previous row.

Source code:

Java automata examples

More information:

A New Kind of Science, Talk at US by Stephen Wolfram

CelLab, Cellular Automata Laboratory

A New Kind of Science ( book is available online and free)

Some of the recent controversy about Wolfram’s book

Fractal Geometry

Cellular Automata Links

An Introduction to Lindenman Systems ( related subject )

The Primordial Soup Kitchen

One dimensional cellular automata Java applet

A weakly universal cellular automaton in the hyperbolic 3D space with three states

## Biomorphs and artificial intelligence

I hadn’t heard of Biomorphs until I started wandering through The Magic Machine: A Handbook of Computer Sorcery. I’m brushing up on math and coding now so I can do some new projects this year and this book is a fun way to do it.

[ z = z^3 + c]

[ z = sin(z) + z^2 + c ]

Biomorphs were discovered by Clifford Pickover at the IBM Research Center. Biomorphs are like Mandelbrot functions in that you iterate a simple function over the complex plane. The algorithm is in the 2 example Java files below. Several more besides these two are known to reside between -20 and 20. { z^z + z^6 + c; z^z + z^6 + c; sin(z) + e^z +c; z^5 + c; z^z + z^5 + c; . . . } You should be able to figure out how to create them by altering the two examples in the download file.

Some people breed biomorphs and let them evolve as an artificial life form.

Source Code

biomorphs.tar.gz ( 2 Java source files for the biomorphs above )

More information:

Fractal Geometry

Dr. Clifford Pickover home page

Mad Teddy’s Fractals #2 Biomorphs

## Fractals and artificial intelligence

Fractals are a fascinating toy, one can easily spend an afternoon lost in Mandelbrot or Julia sets. Mathematicians were aware of fractals as early as the 1700s but it wasn’t until we had computers to do the calculations that we really discovered fractals.

Benoit B. Mandelbrot doing research at IBM was revisiting Gaston Julia’s work with fractals (1917) when he discovered the Mandelbrot set. Fractals are simple equations that are recursively computed. These simple equations create complex shapes.

The Mandelbrot function is z = z^2 + c. z and c are complex numbers, z is set to zero, c is the position on the x ( x, yi ) plane. You recursively compute this function to obtain the Mandelbrot fractal. Black is for the numbers that do not escape to infinity, the other colors represent how many loops it takes to escape.

Fractals have found some use in artificial intelligence. In the world of computer games, fractals create plant life, clouds, mountains and other scenery that would not be possible in such detail. Parkinson’s patients are diagnosed by their gait. In 2004 a sensor was developed that measures the patient’s gait, and analyzes the gait using fractals. 2002 fractals were put to use to help predict natural disasters and better model hurricanes. More recently fractal patterns have been found in solar wind. It is hoped this information will allow us to better predict solar storms.

Fractals have been found in Jackson Pollacks paintings and are being used to try to identify real paintings from fakes. They are also being used in image compression. A more fun way to play with fractals is to use them to predict the stock and commodity markets.

Fractals ( Mandelbrot and Julia in Java – source code )

More information:

Fractal Geometry

Fractals

Math on Display, Science News Online

Genius: Benoit Mandelbrot

3D Mandelbrot images

Papers:

The Fractal Geometry of Nature, Mandelbrot ( pdf/ps )

## Genetic Algorithms

Genetic Algorithms create agents who compete to find the best solution to a problem using evolution.

Agents are initially created either using the best chromosomes from a previous run or a random mixture of chromosomes. After each round we evaluate each agent to see how well he has done. We then mix up the genes by switching among our best agents and or adding in some mutations. We repeat this for a set number of rounds or until some goal is reached.

If only gene switching is done and no mutations are entered into the population the agents will often only find local maximums not global maximums. If the number of agents is too small a solution may not be found.

Simple Genetic Program – you have predators, prey and food for the prey. When either a predator or prey reaches reproduction energy 2 of 3 genes are passed directly to the child, one is random.

GeneticLife.java

See Also:

Bioinformatics Blog: Genetic Algorithms: A Quick Tutorial

Racing with Evolutionary Algorithms

## Knowledge based expert systems

There are knowledge based agents and expert systems that reason using rules of logic. These systems that do what an expert in a given field might do, tax consulting, medical diagnosis etc. They do well at the type of problem solving that people go to a university to learn. Usually predicate calculus is used to work through a given problem. This type of problem solving is known as ‘system inference’. The program should be able to infer relationships, functions between sets, some type of grammar, and some basic logic skills. The system needs to have three major properties: soundness, confidence that a conclusion is true; completeness, the system has the knowledge to be able to reach a conclusion; and tractability, it is realistic that a conclusion can be reached.

Reasoning is commonly done with if-then rules in expert systems. Rules are easily manipulated, forward chaining can produce new facts and backward chaining can check statements accuracy. The newer expert systems are set up so that users, who are not programmers, can add rules and objects and alter existing rules and objects. This provides a system that can remain current and useful with out having to have a full time programmer working on it.

There are three main parts to the expert system: knowledge base, a set of if-then rules; working memory, a database of facts; inference engine, the reasoning logic to create rules and data.

The knowledge base is composed of sentences. Each sentence is a representation of a fact or facts about the world the agent exists in or facts the expert system will use to make determinations. The sentences are in a language known as the knowledge representation language.

Rule learning for knowledge based and expert systems is done with either inductive or deductive reasoning. Inductive learning creates new rules, that are not derivable from previous rules about a domain. Deductive learning creates new rules from existing rules and facts.

Rules are made of antecedent clauses (if), conjunctions (and, or) and consequent clauses (then). A rule in which all antecedent clauses are true is ready to fire or triggered. Rules are generally named for ease of use and usually have a confidence index. The confidence index (certainty factor) shows how true something is, i.e. 100\% a car has four wheels, 50\% a car has four doors. Sometimes sensors are also part of the system. They may monitor states in the computer or environment. The Rete algorithm is the most efficient of the forward chaining algorithms.

Reasoning can be done using ‘Horn Clauses’, these are first-order predicate calculus statements that have, at most, one true literal. Horn Clauses have linear order time algorithms and this allows for a faster method of reasoning through lots of information. This is usually done with PROLOG or lisp. Clauses are ordered as such: goal, facts, rules. Rules have one or more negative literals and one positive literal that can be strung together in conjunctions that imply a true literal. A fact is a rule that has no negative literals. A list of positive literals with out a consequent are a goal. The program loops checking the list in order, when a resolution is performed a new loop is begun with that resolution. If the program resolves its goal the proof can be given in tree form, ‘and/or tree’.

Nonmonotomic reasoning is used to fix problems created by a change in information over time. More information coming in negates a previous conclusion and a new one needs to be drawn.

A conflict resolution process must be put in place as well to deal with conflicting information. This can be done by: first come, first serve; most specific rule is kept; most recently changed data rule triggered; once rule is resolved take it out of the conflict resolution set.

Forward chaining takes the available facts and rules and deduces new facts which it then uses to deduce more new facts, or invoke actions. Forward chaining can also be done by simply the application of if-then statements: The RETE algorithm is the most efficient at doing forward chaining right now, it compiles the rules into a network that it traverses efficiently. This is similar to the blackboard systems.

Dynamic knowledge bases, known as truth maintenance systems, may be used. This uses a ‘spreadline’ which is similar to a spread sheet that will calculate missing and updated values as other values entered.

General algorithm forward chaining

load rule base into memory

load facts into memory

load initial data into memory

match rules to data and collect triggered rules

LOOP

if conflict resolution done BREAK

use conflict resolution to resolve conflicts among rules

fire selected rules

END LOOP

Backward Chaining evaluates a goal and moves backward through the rules to see if true. An example is a medical diagnosis expert system, that takes in information from questions then returns a diagnoses. PROLOG systems are backward chaining.

General algorithm backward chaining

load rule base into memory

load facts into memory

load initial data

specify a goal

load rules specific to that goal onto a stack

LOOP

if stack is empty BREAK

pop stack

WHILE MORE ANTECEDENT CLAUSES

if antecedent is false pop stack and NEXT WHILE

if antecedent true fire rule and NEXT WHILE

if antecedent unknown PUSH onto stack (we may later ask user for more information about this antecedent.

END LOOP

The Rete Algorithm is considered to be the best algorithm for forward chaining expert systems. It is the fastest but also requires much memory. It uses temporal redundancy, rules only alter a few facts at a time, and structural similarity in the left hand side of rules to do so.

The Rete is a an acyclic graph that has a root node. The nodes are patterns and the paths are the left hand sides of the rules. The root node has one kind node attached to it for each kind of fact. Each kind node has one alpha node attached to it for each rule and pattern. Then the alpha nodes have associated memories which describe relationships. Each rule has two beta nodes. The left part is from alpha(i) and the right from alpha(i+1). Each beta node stores the JOIN relationships. Changes to rules are entered at the root and propagated through the graph.

Knowledge based agents loop through two main functions. One is to sense the world and TELL the knowledge base what it senses, two is to ASK what it should do about what it senses, which it then does. An agent can be constructed by giving it all the sentences it will need to perform its functions. An agent can also be constructed by a learning mechanism that takes perceptions about the environment and turns them into sentences that it adds to the knowledge base.

The Plant Doctor (perl)

Plant doctor in action

iPhone Plant Doctor