Example Solutions Evolved:

Here are examples of trivial and nontrivial problems to which solutions were evolved. We are using the FIT framework and its input HTML tables to set up input and expected result values, and using the Java language we code a fitness functions expressed as a unit test. Note that in the example we are merely testing for correct execution of evolved code rather than specifying algorithms or methodologies. One of the goals was to determine how general-purpose the resulting code would be, and the results are surprising.

As the test is running in the Neovolve framework, each 'Individual' executes a 'Chromosome' of code containing a tree structure of functions and arguments to those functions. The initial population of individuals is created with a random subset of all possible functions for the types we are using in the test, and have access to the full set of functions to evolve solutions.

Thousands or tens of thousands of Individuals are evaluated against the input values and the expected results in the form, with the fittest being chosen to crossbreed their chromosome code branches to evolve progressively more fit solutions. The best of each generation is output to the result page until a complete solution evolves.

• X+Y+Z
• Zero-strip
• Lower-level Test Construction
• Verification
• Observations

X+Y+Z:

Below we see three generations of the evolution of a solution to solve the addition of three numbers: X, Y, and Z. The evolution was accomplished by the second generation and the third presents another correct solution as well.

import fit.*;
import com.neocoretechs.neovolve.*;
import com.neocoretechs.neovolve.objects.*;
  public class test5aColumnFixture extends XGPFixture {
     public int X;
     public int Y;
     public int Z;    
     public int Add(Individual ind) {	
	Object[] args = new Object[]{new Integer(X), new Integer(Y), new Integer(Z)};
	int ret = ind.execute_int(0, args);
	//System.out.println("Res: "+ret);
	return ret;
  }
}

import fit.*;
import com.neocoretechs.neovolve.*;
import com.neocoretechs.neovolve.objects.*;
public class test4aColumnFixture extends XGPFixture {
        public String toStrip;
        public String fromStrippee;

        public test4aColumnFixture() {
                GENERATIONS = 100;
                POPULATION = 20000;
        }

        public String Strip(Individual ind) {
                Object[] args = new Object[]{new Strings(toStrip), new Strings(fromStrippee)};
                Strings ret = (Strings)(ind.execute_object(0, args));
                //System.out.println("Res: "+ret);
                return ret.data;
        }
}

java.lang.StringIndexOutOfBoundsException: String index out of range: -1
	at java.lang.String.substring(String.java:1470)
	at com.neocoretechs.neovolve.objects.Strings.execute_substring(Strings.java:33)
	at com.neocoretechs.neovolve.functions.Substring.execute_object(Substring.java:30)
	at com.neocoretechs.neovolve.Chromosome.execute_object(Chromosome.java:745)
	at com.neocoretechs.neovolve.functions.Add.execute_object(Add.java:49)
	at com.neocoretechs.neovolve.Chromosome.execute_object(Chromosome.java:747)
	at com.neocoretechs.neovolve.functions.Add.execute_object(Add.java:49)
	at com.neocoretechs.neovolve.Chromosome.execute_object(Chromosome.java:745)
	at com.neocoretechs.neovolve.functions.IndexOf.execute_int(IndexOf.java:34)
	at com.neocoretechs.neovolve.Chromosome.execute_int(Chromosome.java:671)
	at com.neocoretechs.neovolve.functions.Substring.execute_object(Substring.java:28)
	at com.neocoretechs.neovolve.Chromosome.execute_object(Chromosome.java:740)
	at com.neocoretechs.neovolve.Individual.execute_object(Individual.java:347)
	at test4aColumnFixture.Strip(test4aColumnFixture.java:15)
	at sun.reflect.GeneratedMethodAccessor1.invoke(Unknown Source)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
	at java.lang.reflect.Method.invoke(Method.java:324)
	at fit.TypeAdapter.invoke(TypeAdapter.java:95)
	at fit.TypeAdapter.get(TypeAdapter.java:81)
	at fit.XGPFixture.checkFinal(XGPFixture.java:140)
	at fit.XGPFixture.check(XGPFixture.java:165)
	at fit.ColumnFixture.doCell(ColumnFixture.java:41)
	at fit.Fixture.doCells(Fixture.java:100)
	at fit.Fixture.doRow(Fixture.java:94)
	at fit.ColumnFixture.doRow(ColumnFixture.java:27)
	at fit.Fixture.doRows(Fixture.java:88)
	at fit.ColumnFixture.doRows(ColumnFixture.java:17)
	at fit.Fixture.doTable(Fixture.java:82)
	at com.neocoretechs.neovolve.XGPWorld.computeRawFitness(XGPWorld.java:37)
	at com.neocoretechs.neovolve.World.run(World.java:497)
	at fit.XGPFixture.doTables(XGPFixture.java:102)
	at com.neocoretechs.neovolve.XGPWorld.process(XGPWorld.java:63)
	at com.neocoretechs.neovolve.XGPWorld.main(XGPWorld.java:114)

Lower-level Test Construction:

It is also possible to construct tests outside of the integrated FIT environment.

The example below iterates 50 times through six possible tests, upping the hits for each passing test. In this test case we are again attaching leading zeros to the string value of a number and comparing the result of the evolved code to the string value of the original number. The value returned from the evolved code and the original number have to be the same to have stripped the leading zeros.

During the run, the fitness of each individual is assigned from the computeRawFitness() test method below. For this example, 20000 individuals were evaluated over approximately 50 generations, with the fittest being proportionally chosen to crossbreed random branches of their chromosome code each generation. In this 'hill climbing' process, statistical methods are used to converge on a solution to the problem expressed in the unit test (fitness function).

The bold portion of the test below denotes the detrivializing element. The code to not only has to return the original value when there are no leading zeros, but return a 0 if the input string consists exclusively of one of more zeros.

Once we have a fit solution we store it to a persistent hash set for later verification of the evolved code.

        /**
        * In this test case we are attaching leading zeros to the string value of
        * a number and comparing the result of the evolved code to the string
        * value of the original number. The value returned from the evolved code
        * and the original number have to be the same to have stripped the leading zeros.
        * The code not only has to return the original value when there are no
        * leading zeros, but return a 0 if the input string consists exclusively
        * of one of more zeros.
        */
        public float computeRawFitness(Individual ind) {
                hits = 0;
                // The setStepFactors method takes the number of steps and tests per 
                // step as arguments and it sets the value MaxSteps and MinRawFitness based on 
                // those.
                setStepFactors(50, 6);
                // Strings are String types within the framework
                Strings j=null,k=null,l=null,m=null,n=null,o=null;
                // unit test
                for(int i = 0; i < MaxSteps; i++) {
                        // set the arguments: what to strip in 0, the target to strip in 1
                        argVals[0] = new Strings("0");
                        argVals[1] = new Strings(String.valueOf(i));
                        // and execute
                        j = (Strings)ind.execute_object(0, argVals);
                        // now set target with next value, a "0"+the original string
                        argVals[1] = new Strings("0"+String.valueOf(i));
                        // execute
                        k = (Strings)ind.execute_object(0, argVals);
                        // rinse, lather, repeat
                        argVals[1] = new Strings("00"+String.valueOf(i));
                        l = (Strings)ind.execute_object(0, argVals);

                        argVals[1] = new Strings("000"+String.valueOf(i));
                        m = (Strings)ind.execute_object(0, argVals);

                        argVals[1] = new Strings("0000"+String.valueOf(i));
                        n = (Strings)ind.execute_object(0, argVals);

                        argVals[1] = new Strings("00000"+String.valueOf(i));
                        o = (Strings)ind.execute_object(0, argVals);
						// check everything to and see if it came back stripped
                        if( j.data.equals(String.valueOf(i)) ) ++hits;
                        if( k.data.equals(String.valueOf(i)) ) ++hits;
                        if( l.data.equals(String.valueOf(i)) ) ++hits;
                        if( m.data.equals(String.valueOf(i)) ) ++hits;
                        if( n.data.equals(String.valueOf(i)) ) ++hits;
                        if( o.data.equals(String.valueOf(i)) ) ++hits;
                }
                float rawFit = (MinRawFitness - (float)(hits));
                // show some output if this is fittest (DEBUG = true)
                if(DEBUG) {
                        System.out.println(j.data);
                        System.out.println(k.data);
                        System.out.println(l.data);
                        System.out.println(m.data);
                        System.out.println(n.data);
                        System.out.println(o.data);
                        try {
                                if( rawFit == 0.0F ) {
                                        System.out.println("Storing..."+ind.hashCode());
                                        psh.add(ind);
                                }
                        } catch(IOException ioe) {
                                System.out.println("Persistent storage subsystem failed to store individual");
                        }
                }
                //System.out.println("Hits: "+hits);
                return rawFit;
        }

Verification of Zero-strip:

The following test loads the Zero-strip results from persistent storage and uses the Neovolve framework to run the evolved code against further test cases. We have outfitted the test harness with methods to run both at command line and through the FIT testing framework

import java.io.*;
import java.util.*;
import com.neocoretechs.neovolve.*;
import com.neocoretechs.neovolve.functions.*;
import com.neocoretechs.neovolve.objects.*;
import com.neocoretechs.hashpool.*;

public class test4 {
        static PooledHashSet psh = null;
        static Vector individuals = new Vector();
        static Object[] vars = new Object[2];
        // static block loads elements from persistent hash set
        static {
           try {
                psh = new PooledHashSet("neovolve",10);
                Enumeration enum = psh.elements();
                while(enum.hasMoreElements()) 
                        individuals.addElement(enum.nextElement());
           } catch(Exception e) {
                        System.out.println(e);
                        e.printStackTrace();
                        System.exit(1);
           }
        }
        // Command line test
        public static void main(String argv[]) {
                try {
                
                vars[0] = new Strings(argv[0]);
                vars[1] = new Strings(argv[1]);
                
                int c = 0;
                for(int j = 0; j < individuals.size(); j++) {
                        Individual ind = (Individual)individuals.elementAt(j);
                        // execute chromosome 0 with passed args 
                        Strings al = (Strings)ind.execute_object(0, vars);
                        System.out.println(++c);
                        System.out.println(ind);
                        System.out.println(al.data);
                        System.out.println();
                }
                } catch(Exception e) { System.out.println(e); e.printStackTrace(); }
       }
       // We use this test to instrument a FIT run
       public static String strip(int ielem, String toStrip, String fromStrippee) throws Exception {
                vars[0] = new Strings(toStrip);
                vars[1] = new Strings(fromStrippee);
                Individual ind = (Individual)(individuals.elementAt(ielem));
                // execute chromosome 0 with passed args 
                Strings al = (Strings)ind.execute_object(0, vars);
                return al.data;
       }
}

Running the test first from the command line produces the output below. We assign the value "0" to strip from the value "000000099999" . The output consists of the sequence, the S-expression representation of the evolved code, and the result of the test. We have three individuals in storage to test. The LISP-like S-expressions can be somewhat cryptic, but notice that ARG0 and ARG1 are our arguments "0" and "000000099999" and various String functions and operators such as IF, + (concatenation), STRTS (startsWith), REPL (replace), SUBS (substring), LINDX (lastIndexOf), ENDS (endsWith), INDXA (indexOf, At), and booleans evolved from a set of all possible string functions and operators.

F:\java\>java test4 0 000000099999

1
[0] IF ( STRTS ( ARG1 ARG0 ) SUBS ( ARG1 + ( INDXA ( REPL ( ARG1 ARG0 ARG0 ) SUB
S ( ARG1 + ( + ( LINDX ( ARG1 ARG0 ) 1 ) INDX ( ARG1 ARG0 ) ) LINDX ( + ( IF ( E
NDS ( ARG1 + ( ARG1 ARG0 ) ) ARG0 REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) A
RG0 ) ARG0 ) ) LINDX ( IF ( & ( STRTS ( ARG1 ARG0 ) > ( SUBS ( ARG1 + ( + ( INDX
A ( REPL ( ARG1 ARG0 ARG0 ) SUBS ( ARG1 + ( + ( LINDX ( ARG1 ARG0 ) 1 ) INDX ( A
RG1 ARG0 ) ) LINDX ( + ( IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) IF ( STRTS ( ARG1 AR
G0 ) IF ( < ( 1 1 ) + ( ARG1 ARG0 ) ARG1 ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG
1 ) ) ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ARG0 ) ARG0 ) ) 1 ) LINDX (
 ARG0 ARG0 ) ) LINDX ( ARG0 ARG0 ) ) LINDX ( + ( ARG1 ARG0 ) ARG0 ) ) IF ( ENDS
( ARG1 + ( ARG1 ARG0 ) ) ARG0 REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ) ) S
UBS ( ARG1 INDXA ( REPL ( ARG1 ARG0 ARG0 ) SUBS ( ARG1 + ( + ( LINDX ( ARG1 ARG0
 ) 1 ) INDX ( ARG1 ARG0 ) ) LINDX ( + ( IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) REPL
( ARG1 ARG0 ARG1 ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ARG0 ) ARG0 ) )
1 ) LINDX ( + ( IF ( ENDS ( ARG1 IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) IF ( < ( 1 1
 ) + ( ARG1 ARG0 ) ARG1 ) REPL ( ARG1 ARG1 ARG1 ) ) ) IF ( < ( 1 1 ) + ( ARG1 AR
G0 ) ARG1 ) REPL ( ARG1 ARG1 + ( ARG1 ARG0 ) ) ) ARG0 ) ARG0 ) ) REPL ( ARG1 IF
( F ARG0 IF ( ENDS ( ARG1 ARG1 ) REPL ( ARG1 ARG0 ARG1 ) REPL ( ARG1 ARG1 REPL (
 ARG1 ARG1 ARG1 ) ) ) ) ARG1 ) ) ARG0 ) ) LINDX ( ARG0 ARG0 ) ) LINDX ( + ( ARG1
 ARG0 ) ARG0 ) ) ARG1 )

99999

2
[0] IF ( STRTS ( ARG1 ARG0 ) SUBS ( ARG1 + ( INDXA ( REPL ( ARG1 ARG0 ARG0 ) SUB
S ( ARG1 + ( + ( LINDX ( ARG1 ARG0 ) 1 ) INDX ( ARG1 ARG0 ) ) LINDX ( + ( IF ( E
NDS ( ARG1 + ( ARG1 ARG0 ) ) ARG0 REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) A
RG0 ) ARG0 ) ) LINDX ( IF ( & ( STRTS ( ARG1 ARG0 ) > ( SUBS ( ARG1 + ( + ( INDX
A ( REPL ( ARG1 ARG0 ARG0 ) SUBS ( ARG1 + ( + ( LINDX ( ARG1 ARG0 ) 1 ) INDX ( A
RG1 ARG0 ) ) LINDX ( + ( IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) IF ( STRTS ( ARG1 AR
G0 ) IF ( < ( 1 1 ) + ( ARG1 ARG0 ) ARG1 ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG
1 ) ) ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ARG0 ) ARG0 ) ) 1 ) LINDX (
 ARG0 ARG0 ) ) LINDX ( ARG0 ARG0 ) ) LINDX ( + ( ARG1 ARG0 ) ARG0 ) ) IF ( ENDS
( ARG1 + ( ARG1 ARG0 ) ) ARG0 REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ) ) S
UBS ( ARG1 INDXA ( REPL ( ARG1 ARG0 ARG0 ) SUBS ( ARG1 + ( + ( LINDX ( ARG1 ARG0
 ) 1 ) INDX ( ARG1 ARG0 ) ) LINDX ( + ( IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) REPL
( ARG1 ARG0 ARG1 ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ARG0 ) ARG0 ) )
1 ) LINDX ( + ( IF ( ENDS ( ARG1 IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) IF ( < ( 1 1
 ) + ( ARG1 ARG0 ) ARG1 ) REPL ( ARG1 ARG1 ARG1 ) ) ) IF ( < ( 1 1 ) + ( ARG1 AR
G0 ) ARG1 ) REPL ( ARG1 ARG1 + ( ARG1 ARG0 ) ) ) ARG0 ) ARG0 ) ) REPL ( ARG1 IF
( F ARG0 IF ( ENDS ( ARG1 ARG1 ) REPL ( ARG1 ARG0 ARG1 ) REPL ( ARG1 ARG1 REPL (
 ARG1 ARG1 ARG1 ) ) ) ) ARG1 ) ) ARG0 ) ) LINDX ( ARG0 ARG0 ) ) LINDX ( + ( ARG1
 ARG0 ) ARG0 ) ) ARG1 )

99999

3
[0] IF ( STRTS ( ARG1 ARG0 ) SUBS ( ARG1 + ( INDXA ( REPL ( ARG1 ARG0 ARG0 ) SUB
S ( ARG1 + ( + ( LINDX ( ARG1 ARG0 ) 1 ) INDX ( ARG1 ARG0 ) ) LINDX ( + ( IF ( E
NDS ( ARG1 + ( ARG1 ARG0 ) ) ARG0 REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) A
RG0 ) ARG0 ) ) LINDX ( IF ( & ( STRTS ( ARG1 ARG0 ) > ( SUBS ( ARG1 + ( + ( INDX
A ( REPL ( ARG1 ARG0 ARG0 ) SUBS ( ARG1 + ( + ( LINDX ( ARG1 ARG0 ) 1 ) INDX ( A
RG1 ARG0 ) ) LINDX ( + ( IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) IF ( STRTS ( ARG1 AR
G0 ) IF ( < ( 1 1 ) + ( ARG1 ARG0 ) ARG1 ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG
1 ) ) ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ARG0 ) ARG0 ) ) 1 ) LINDX (
 ARG0 ARG0 ) ) LINDX ( ARG0 ARG0 ) ) LINDX ( + ( ARG1 ARG0 ) ARG0 ) ) IF ( ENDS
( ARG1 + ( ARG1 ARG0 ) ) ARG0 REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ) ) S
UBS ( ARG1 INDXA ( REPL ( ARG1 ARG0 ARG0 ) SUBS ( ARG1 + ( + ( LINDX ( ARG1 ARG0
 ) 1 ) INDX ( ARG1 ARG0 ) ) LINDX ( + ( IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) REPL
( ARG1 ARG0 ARG1 ) REPL ( ARG1 ARG1 REPL ( ARG1 ARG1 ARG1 ) ) ) ARG0 ) ARG0 ) )
1 ) LINDX ( + ( IF ( ENDS ( ARG1 IF ( ENDS ( ARG1 + ( ARG1 ARG0 ) ) IF ( < ( 1 1
 ) + ( ARG1 ARG0 ) ARG1 ) REPL ( ARG1 ARG1 ARG1 ) ) ) IF ( < ( 1 1 ) + ( ARG1 AR
G0 ) ARG1 ) REPL ( ARG1 ARG1 + ( ARG1 ARG0 ) ) ) ARG0 ) ARG0 ) ) REPL ( ARG1 IF
( F ARG0 IF ( ENDS ( ARG1 ARG1 ) REPL ( ARG1 ARG0 ARG1 ) REPL ( ARG1 ARG1 REPL (
 ARG1 ARG1 ARG1 ) ) ) ) ARG1 ) ) ARG0 ) ) LINDX ( ARG0 ARG0 ) ) LINDX ( + ( ARG1
 ARG0 ) ARG0 ) ) ARG1 )

99999

Putting this all together in the FIT testing framework, we use the above test4.strip() method from a column fixture in FIT. We are using three methods to test the three individuals in storage with each row of values indicating what to strip from the target fromStrippee string.

import fit.ColumnFixture;

public class test4ColumnFixture extends ColumnFixture {

    public String toStrip;
    public String fromStrippee;

    public String strippedA() throws Exception {
        return test4.strip(0, toStrip, fromStrippee);
    }
    public String strippedB() throws Exception {
        return test4.strip(1, toStrip, fromStrippee);
    }
    public String strippedC() throws Exception {
        return test4.strip(2, toStrip, fromStrippee);
    }

}

The results indicate that for each individual tested the proper value was returned from the evolved code. A green cell in FIT indicates a successful test. If the results of the strippedA()-strippedC() methods had come back different from the expected results in the cells, a red cell or perhaps an exception would be shown.

Observations:

The surprising aspect is that the code is general-purpose enough to solve the conditions we specified in the unit test, as well as surpassing our requirements by stripping any number of leading zeroes, although we checked for only 5 maximum in our test. In addition, the code is capable of stripping any value we designate as toStrip, as evidenced by the value "1" being stripped in our FIT test.