28 June 2006

My Genetic Programming Applet

I'm pleased to introduce a small applet implementing a Genetic Programming Algorithm.

From wikipedia: Genetic programming (GP) is an automated methodology inspired by biological evolution to find computer programs that best perform a user-defined task. It is therefore a particular machine learning technique that uses an evolutionary algorithm to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task.. I wrote this applet when I wondered if I could use this (the answer was no :-)) to discover a mathematical way how to describe a biological signal.



This applet is available at:




The java program takes as input a table of result and a list of expected numbers. Top-Left: table of data used for input. Last columns are: expected result, normalized expected result, normalized computed result, fitness (|computed-expected|). Top-Right: nine steps of the evolution process. In each setp, on the X axis are displayed the expected values and the comuted values
(calculated from the evolving methematical function) are on the Y axis. The fitness is diplayed. Bottom-Left: parameters, 'weight' of each function. Bottom-Right: The definition of the current best curve.


Update 2010-08-12:source code

./org/lindenb/geneticalgo/Function.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

import java.io.PrintWriter;

import org.lindenb.geneticalgo.GeneticProg.Shuttle;



/**
* @author pierre
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
public class Function extends Node {
private Node children[];
private Operator operator;

private Function(Function cp)
{
super(cp.getGeneticProg());
this.operator=cp.operator;
this.children=new Node[cp.children.length];
for(int i=0;i< this.children.length;++i)
{
setChildrenAt(cp.getChildAt(i).clone(this),i);
}
}


public NodeType getNodeType()
{
return NodeType.FUNCTION;
}

/**
* @param parent
* @param context
*/
public Function(GeneticProg genprog,GeneticProg.Shuttle n)
{
super(genprog);
this.operator= getGeneticProg().choose_operator();
this.children= new Node[operator.argc()];
for(int i=0;i< this.children.length;++i)
{
setChildrenAt(getGeneticProg().choose_random_node(n),i);
}
}


@Override
public boolean equals(Object o) {
if(this==o) return true;
if(!(o instanceof Function)) return false;
Function cp=(Function)o;
if(!this.operator.equals(cp.operator)) return false;
if(cp.getChildCount()!=this.getChildCount()) return false;
for(int i=0;i< getChildCount();++i)
{
if(!getChildAt(i).equals(cp.getChildAt(i))) return false;
}
return true;
}

/* (non-Javadoc)
* @see org.lindenb.geneticalgo.Node#getChildCount()
*/
public int getChildCount()
{
return this.children.length;
}

/* (non-Javadoc)
* @see org.lindenb.geneticalgo.Node#getChildAt(int)
*/
public Node getChildAt(int index)
{
return this.children[index];
}


void replaceChildren(Node old,Node recent)
{
assert(old.parent==this);

for(int i=0;i< getChildCount();++i)
{
if(getChildAt(i)==old)
{
setChildrenAt(recent,i);
return;
}
}
}


protected void setChildrenAt(Node node,int index)
{
if(this.children[index]!=null)
{
this.children[index].parent=null;
}
this.children[index]=node;
node.parent=this;
}


public void muteIt()
{
if(getGeneticProg().rnd()<0.5)
{
int tried=0;
while(tried<10)
{
++tried;
Operator newoperator= getGeneticProg().choose_operator();
if(newoperator==this.operator || newoperator.argc()!=this.operator.argc()) continue;
this.operator=newoperator;
return;
}
}
else
{
int n= getGeneticProg().getRandom().nextInt(this.getChildCount());
int nodefromroot= getRoot().countDescendant();
int nodefromhere= this.countDescendant();
Shuttle shutte= new Shuttle();
shutte.total_node=nodefromroot-nodefromhere;
this.setChildrenAt(getGeneticProg().choose_random_node(shutte),n);
}
}


public Double calc(int row) {
Number val= this.operator.calc(row,children);
if(val==null) return null;
return new Double(val.doubleValue());
}

public Node clone(Node parent)
{
Function c= new Function(this);
return c;
}


/* (non-Javadoc)
* @see org.lindenb.geneticalgo.Node#print(java.io.PrintWriter)
*/
public void print(PrintWriter out) {
out.print(toString());
}

@Override
public String toString() {
StringBuilder b=new StringBuilder( this.operator.getName()+"( ");
for(int i=0;i< getChildCount();++i)
{
if(i!=0) b.append(" , ");
b.append(getChildAt(i).toString());
}
b.append(" )");
return b.toString();
}


}


./org/lindenb/geneticalgo/BinaryOperator.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

public abstract class BinaryOperator extends Operator {
private String name;
protected BinaryOperator(String name,GeneticProg sheet)
{
super(sheet);
this.name=name;
}

@Override
public int argc()
{
return 2;
}

@Override
public String getName() {
return name;
}

@Override
public Number calc(int rowIndex, Node[] childs)
{
assert(childs!=null && childs.length==2);
Number value1= childs[0].calc(rowIndex);
if(value1==null ||
Double.isInfinite(value1.doubleValue()) ||
Double.isNaN(value1.doubleValue())) return null;
Number value2= childs[1].calc(rowIndex);
if(value2==null ||
Double.isInfinite(value2.doubleValue()) ||
Double.isNaN(value2.doubleValue())) return null;
return calc(rowIndex,value1.doubleValue(),value2.doubleValue());
}

public abstract Number calc(int rowIndex,double v1,double v2);
}


./org/lindenb/geneticalgo/GeneticProg.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Component;
import java.awt.Cursor;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.GridLayout;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StringReader;
import java.io.StringWriter;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;
import java.util.Vector;

import javax.imageio.ImageIO;
import javax.swing.AbstractAction;
import javax.swing.BorderFactory;
import javax.swing.Box;
import javax.swing.Icon;
import javax.swing.ImageIcon;
import javax.swing.JApplet;
import javax.swing.JButton;
import javax.swing.JComponent;
import javax.swing.JDialog;
import javax.swing.JFileChooser;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JMenu;
import javax.swing.JMenuBar;
import javax.swing.JMenuItem;
import javax.swing.JOptionPane;
import javax.swing.JPanel;
import javax.swing.JScrollPane;
import javax.swing.JSpinner;
import javax.swing.JTabbedPane;
import javax.swing.JTable;
import javax.swing.JTextArea;
import javax.swing.ListSelectionModel;
import javax.swing.SpinnerNumberModel;
import javax.swing.UIManager;
import javax.swing.event.ChangeEvent;
import javax.swing.event.ChangeListener;
import javax.swing.table.DefaultTableModel;
import javax.swing.table.TableCellRenderer;


/**
* @author pierre
*
*/
public class GeneticProg extends JPanel implements Runnable
{
private static final long serialVersionUID = 1L;
private static final int EXTRA_COLUMNS=3;
private static final int SIMPLE_MATH_DEFAULT_SCORE=20;
private static final int PREDICATE_DEFAULT_SCORE=0;
private static final int TRIGO_DEFAULT_SCORE=1;


/**
*
* Frame
*
*/
private class Frame extends JFrame
{
private static final long serialVersionUID = 1L;
/** A Frame for GeneticProg.this */
Frame()
{
super("GeneticProg");
this.setDefaultCloseOperation(JFrame.DO_NOTHING_ON_CLOSE);
this.addWindowListener(new WindowAdapter()
{
@Override
public void windowClosing(WindowEvent e) {
promptExit();
}
});

JMenuBar bar= new JMenuBar();
setJMenuBar(bar);
JMenu menu= new JMenu("File");
bar.add(menu);
menu.add(new JMenuItem(new AbstractAction("About")
{
private static final long serialVersionUID = 1L;

public void actionPerformed(ActionEvent e) {

JOptionPane.showMessageDialog(null,new JLabel(
"<html><body><h1>GeneticProgramming</h1><h3>Pierre Lindenbaum PhD</h3><h6>plindenbaum@yahoo.fr</h6></body></html>"
),"About",JOptionPane.INFORMATION_MESSAGE);

}
}));
menu.add(new JMenuItem(new AbstractAction("Quit")
{
private static final long serialVersionUID = 1L;

public void actionPerformed(ActionEvent e) {
promptExit();

}
}));

Dimension screen= Toolkit.getDefaultToolkit().getScreenSize();
this.setBounds(20,20,screen.width-40,screen.height-40);
this.setContentPane(GeneticProg.this);
}

/**
* promptExit
*
*/
private void promptExit()
{
if(JOptionPane.showConfirmDialog(null,"Close window ?","Close ?",JOptionPane.OK_CANCEL_OPTION)==JOptionPane.OK_OPTION)
{
this.setVisible(false);
this.dispose();
if(GeneticProg.this.runThread!=null)
{
GeneticProg.this.runThread.interrupt();
GeneticProg.this.runThread=null;
}
}
}


}

/**
*
* Renderer
*
*/
private class Renderer extends JLabel implements TableCellRenderer
{
private static final long serialVersionUID = 1L;

Renderer()
{
setOpaque(true);
setFont(new Font("Helvetica",Font.PLAIN,14));
setHorizontalTextPosition(JLabel.RIGHT);
}

public Component getTableCellRendererComponent(JTable table, Object value, boolean isSelected, boolean hasFocus, int row, int column) {
column=table.convertColumnIndexToModel(column);
this.setBorder(hasFocus?BorderFactory.createLineBorder(Color.PINK):BorderFactory.createEmptyBorder());
this.setForeground(isSelected?Color.BLUE:Color.BLACK);

if(value==null)
{
this.setText("");
this.setBackground(Color.RED);
}
else
{
setText(value.toString());
if(!isSelected)
{
column-= GeneticProg.this.getColumnCount();
switch(column)
{
case 0: setBackground(Color.YELLOW);break;
case 1: setBackground(Color.GREEN);break;
case 2: setBackground(Color.PINK);break;
case 3: setBackground(Color.ORANGE);break;
default: setBackground(row%2==0?Color.LIGHT_GRAY:Color.GRAY);break;
}
}
else
{
this.setBackground(Color.RED);
}
}


return this;
}
}

public static class AsApplet extends JApplet
{
private static final long serialVersionUID = 1L;
public AsApplet()
{

}

@Override
public void init()
{
JComponent content=null;
try
{
String version = System.getProperty("java.specification.version");
if(version!=null)
{
if((10.0*Double.parseDouble(version))< 15.0)
{
throw new RuntimeException("Bad JAVA version : found \""+
version+"\" but expected >= 1.5.\nSee http://java.sun.com/j2se/1.5.0/download.jsp for more informations");
}
}
content= new JButton(new AbstractAction("Launch Applet")
{
private static final long serialVersionUID = 1L;

public void actionPerformed(ActionEvent e)
{
GeneticProg prog=null;
try
{
prog= GeneticProg.newInstanceDialog();
}
catch(Throwable err)
{
JOptionPane.showMessageDialog(null,err.getMessage(),"Error",JOptionPane.ERROR_MESSAGE);
prog=null;
}
if(prog!=null)
{
prog.asJFrame().setVisible(true);
prog.run();
}
}
});

}
catch (Exception e)
{
StringWriter out= new StringWriter();
e.printStackTrace(new PrintWriter(out,true));
out.flush();
content=new JScrollPane(new JTextArea("AN ERROR OCCURED:\n\n"+out.toString()));
}
this.setContentPane(content);
}
}



private Thread runThread= null;
private DefaultTableModel spreadsheet;
private JTable sheetTable;
private HashMap<Operator,SpinnerNumberModel> weigths;
private int total_operator_weight=0;
private double minmax[]={Double.MAX_VALUE,-Double.MAX_VALUE};
private Random random= new Random();
private Solution bestSolution=null;
private SVGPane svgPanes[];
private Vector<Solution> history;
private JTextArea functionArea;
private JLabel generationLabel;
private SpinnerNumberModel maxNodeInATree;
private SpinnerNumberModel numberOfParent;
private SpinnerNumberModel probaMutation;
private SpinnerNumberModel probaLeaf;
private SpinnerNumberModel maxNANPercent;
private SpinnerNumberModel numberOfExplorer;
private SpinnerNumberModel numberOfGeneration;

public GeneticProg()
{
super(new BorderLayout(5,5));
this.weigths=new HashMap<Operator,SpinnerNumberModel>();
this.spreadsheet= null;
this.history=new Vector<Solution>();

putOperator(new PredicateOperator("lt",this)
{
@Override
boolean compare(double n1, double n2)
{
return n1<n2;
}
},new Integer(PREDICATE_DEFAULT_SCORE));

putOperator(new PredicateOperator("gt",this)
{
@Override
boolean compare(double n1, double n2)
{
return n1>n2;
}
},new Integer(PREDICATE_DEFAULT_SCORE));


putOperator(new PredicateOperator("eq",this)
{
@Override
boolean compare(double n1, double n2)
{
return n1==n2;
}
},new Integer(PREDICATE_DEFAULT_SCORE));

putOperator(new PredicateOperator("ne",this)
{
@Override
boolean compare(double n1, double n2)
{
return n1!=n2;
}
},new Integer(PREDICATE_DEFAULT_SCORE));

putOperator(new PredicateOperator("ge",this)
{
@Override
boolean compare(double n1, double n2)
{
return n1>=n2;
}
},new Integer(PREDICATE_DEFAULT_SCORE));

putOperator(new PredicateOperator("le",this)
{
@Override
boolean compare(double n1, double n2)
{
return n1<=n2;
}
},new Integer(PREDICATE_DEFAULT_SCORE));


putOperator(new BinaryOperator("Add",this)
{
@Override
public Number calc(int rowIndex, double v1, double v2) {
return new Double(v1+v2);
}
},new Integer(SIMPLE_MATH_DEFAULT_SCORE));

putOperator(new BinaryOperator("Minus",this)
{
@Override
public Number calc(int rowIndex, double v1, double v2) {
return new Double(v1-v2);
}
},new Integer(SIMPLE_MATH_DEFAULT_SCORE));

putOperator(new BinaryOperator("Mul",this)
{
@Override
public Number calc(int rowIndex, double v1, double v2) {
return new Double(v1*v2);
}
},new Integer(SIMPLE_MATH_DEFAULT_SCORE));

putOperator(new BinaryOperator("Div",this)
{
@Override
public Number calc(int rowIndex, double v1, double v2) {
if(v2==0.0) return null;
return new Double(v1/v2);
}
},new Integer(SIMPLE_MATH_DEFAULT_SCORE));

putOperator(new UnaryOperator("sqrt",this)
{
@Override
public Number calc(int rowIndex, double value)
{
if(value<=0) return null;
return Math.sqrt(value);
}
},new Integer(TRIGO_DEFAULT_SCORE));


putOperator(new UnaryOperator("cos",this)
{
@Override
public Number calc(int rowIndex, double value)
{
return Math.cos(value);
}
},new Integer(TRIGO_DEFAULT_SCORE));

putOperator(new UnaryOperator("sin",this)
{
@Override
public Number calc(int rowIndex, double value)
{
return Math.sin(value);
}
},new Integer(TRIGO_DEFAULT_SCORE));

putOperator(new UnaryOperator("tan",this)
{
@Override
public Number calc(int rowIndex, double value)
{
return Math.tan(value);
}
},new Integer(TRIGO_DEFAULT_SCORE));
putOperator(new UnaryOperator("log",this)
{
@Override
public Number calc(int rowIndex, double value)
{
if(value<=0) return null;
return Math.log(value);
}
},new Integer(TRIGO_DEFAULT_SCORE));
putOperator(new UnaryOperator("exp",this)
{
@Override
public Number calc(int rowIndex, double value)
{
return Math.exp(value);
}
},new Integer(TRIGO_DEFAULT_SCORE));
putOperator(new UnaryOperator("negate",this)
{
@Override
public Number calc(int rowIndex, double value)
{
return -value;
}
},new Integer(TRIGO_DEFAULT_SCORE));

Box b1= Box.createHorizontalBox();
add(b1,BorderLayout.CENTER);


Box v2= Box.createVerticalBox();
b1.add(v2);
this.sheetTable= new JTable();
this.sheetTable.getSelectionModel().setSelectionMode(ListSelectionModel.SINGLE_SELECTION);
this.sheetTable.setAutoResizeMode(JTable.AUTO_RESIZE_OFF);
v2.add(new JScrollPane(this.sheetTable));

{
JPanel controlPane= new JPanel(new BorderLayout());
controlPane.setBorder(BorderFactory.createTitledBorder("Controls"));
v2.add(controlPane);
JTabbedPane tabbed=new JTabbedPane();
controlPane.add(tabbed,BorderLayout.CENTER);
{
JPanel ctrlPane= new JPanel(new GridLayout(0,1,5,5));
tabbed.addTab("Control",ctrlPane);
addSpinner(ctrlPane,this.maxNodeInATree= new SpinnerNumberModel(23,5,100,1),"Max Node in a Tree");
addSpinner(ctrlPane,this.numberOfParent= new SpinnerNumberModel(7,2,20,1),"Mumber of parents");
addSpinner(ctrlPane,this.probaMutation= new SpinnerNumberModel(0.95,0.0,1.0,0.05),"p(mutation)");
addSpinner(ctrlPane,this.probaLeaf= new SpinnerNumberModel(0.4,0.0,1.0,0.05),"p(node is leaf)");
addSpinner(ctrlPane,this.maxNANPercent= new SpinnerNumberModel(0.05,0.0,0.5,0.05),"max % of NaN");
addSpinner(ctrlPane,this.numberOfExplorer= new SpinnerNumberModel(3,1,100,1),"Number of Solution Explorer");
addSpinner(ctrlPane,this.numberOfGeneration= new SpinnerNumberModel(50,10,Integer.MAX_VALUE,1),"Generation/Explorer");





ctrlPane= new JPanel(new GridLayout(0,1,5,5));
tabbed.addTab("Simple Math",ctrlPane);

addOperator(ctrlPane,"Add");
addOperator(ctrlPane,"Mul");
addOperator(ctrlPane,"Minus");
addOperator(ctrlPane,"Div");
addOperator(ctrlPane,"negate");

ctrlPane= new JPanel(new GridLayout(0,1,5,5));
tabbed.addTab("Operations",ctrlPane);

addOperator(ctrlPane,"cos");
addOperator(ctrlPane,"sin");
addOperator(ctrlPane,"tan");
addOperator(ctrlPane,"sqrt");
addOperator(ctrlPane,"log");
addOperator(ctrlPane,"exp");

ctrlPane= new JPanel(new GridLayout(0,1,5,5));
tabbed.addTab("Logical",ctrlPane);

addOperator(ctrlPane,"eq");
addOperator(ctrlPane,"ne");
addOperator(ctrlPane,"lt");
addOperator(ctrlPane,"gt");
addOperator(ctrlPane,"le");
addOperator(ctrlPane,"ge");
}




}


/*JPanel operatorPane= new JPanel(new GridLayout(this.weigths.size(),2,5,5));
for(Iterator<Operator> r=this.weigths.keySet().iterator();r.hasNext();)
{
Operator op=r.next();
JSpinner spin=this.weigths.get(op);
operatorPane.add(new JLabel(op.getName(),JLabel.RIGHT));
operatorPane.add(spin);
}*/
//b1.add(operatorPane);

Box vpane=Box.createVerticalBox();
vpane.add(this.generationLabel= new JLabel("Generation"));
this.svgPanes=new SVGPane[9];
JPanel svgpane= new JPanel(new GridLayout(3,3,5,5));
for(int i=0;i< this.svgPanes.length;++i)
{
this.svgPanes[i]= new SVGPane();
svgpane.add(svgPanes[i]);
}
vpane.add(svgpane);

this.functionArea= new JTextArea(20,40);
this.functionArea.setPreferredSize(new Dimension(100,100));
this.functionArea.setMinimumSize(new Dimension(100,100));
this.functionArea.setEditable(false);
this.functionArea.setWrapStyleWord(true);
this.functionArea.setFont(new Font("Helvetica",Font.PLAIN,14));
vpane.add(new JLabel("Best Function",JLabel.CENTER));
vpane.add(new JScrollPane(this.functionArea));

b1.add(vpane);


}

private void addOperator(JPanel ctrlPane,String name)
{
for(Iterator<Operator> r=this.weigths.keySet().iterator();r.hasNext();)
{
Operator op=r.next();
if(!op.getName().equals(name)) continue;
SpinnerNumberModel spin=this.weigths.get(op);
addSpinner(ctrlPane,spin,name);
return;
}
System.err.println("cannot find"+name);
}

private void addSpinner(JPanel ctrlPane,SpinnerNumberModel model,String name)
{
JPanel b= new JPanel(new BorderLayout());
Font f= new Font("Helevetica",Font.PLAIN,10);
b.setFont(f);
b.setBorder(BorderFactory.createTitledBorder(name));
//b.add(new JLabel(name,JLabel.RIGHT));
//spin.setFont(f);
b.add(new JSpinner(model));
ctrlPane.add(b);
}


private void putOperator(Operator op,Integer weight)
{
//if(weight.intValue()<=0) return;
SpinnerNumberModel w= this.weigths.get(op);
if(w!=null) total_operator_weight-=((Number)w.getValue()).intValue();
SpinnerNumberModel spinmodel=new SpinnerNumberModel(weight.intValue(),0,100,1);

spinmodel.addChangeListener(new ChangeListener()
{
public void stateChanged(ChangeEvent evt)
{
calcWeight();
}
});
this.weigths.put(op,spinmodel);
this.total_operator_weight+=weight.intValue();
}

private void calcWeight()
{
int total=0;
for(Iterator<Operator> r=this.weigths.keySet().iterator();r.hasNext();)
{
Operator op=r.next();
SpinnerNumberModel spin=this.weigths.get(op);
total+= spin.getNumber().intValue();
}
this.total_operator_weight=total;
}


private void read(BufferedReader in) throws IOException
{
String line;
DefaultTableModel tableModel=null;

while((line=in.readLine())!=null)
{
if(line.trim().length()==0) continue;
String tokens[]=line.split("[\t]");

if(tableModel==null)
{
if(tokens.length<2)
{
throw new IOException("Expected at least 2 columns in "+line);
}
Vector<String> newheaders= new Vector<String>();
if(line.startsWith("#"))
{
for(String h:tokens) newheaders.addElement(h);
}
else
{
for(int i=0;i< tokens.length;++i) newheaders.addElement(String.valueOf(i+1));
}
newheaders.addElement("Normalized");
newheaders.addElement("Experimental");
newheaders.addElement("Fitness");

tableModel= new DefaultTableModel(newheaders,0)
{
/**
* serialVersionUID
*/
private static final long serialVersionUID = 1L;
@Override
public Class<?> getColumnClass(int col)
{
return Double.class;
}
@Override
public boolean isCellEditable(int arg0, int arg1) {
return false;
}
@Override
public Object getValueAt(int row, int column) {
if(column== this.getColumnCount()-(EXTRA_COLUMNS))
{
return new Double(getNormalizedResultAt(row));
}
return super.getValueAt(row, column);
}
};
if(!line.startsWith("#"))
{
Vector<Double> row= new Vector<Double>(newheaders.size());
for(int i=0;i< tokens.length;++i)
{
row.addElement(new Double(tokens[i]));
}
row.addElement(null);
row.addElement(null);
row.addElement(null);
tableModel.addRow(row);
}
}
else
{
if(tokens.length+EXTRA_COLUMNS!=tableModel.getColumnCount())
{
throw new IOException("Found "+tokens.length+" tokens in "+line+" expected "+(tableModel.getColumnCount()-2));
}

Vector<Double> row= new Vector<Double>(tableModel.getColumnCount());
for(String h:tokens) row.addElement(new Double(h));
row.addElement(null);
row.addElement(null);
row.addElement(null);
tableModel.addRow(row);
}
}
if(tableModel.getRowCount()==0) throw new IOException("Found no data");


setTableModel(tableModel);
}


private void setTableModel(DefaultTableModel model)
{
this.minmax=new double[]{Double.MAX_VALUE,-Double.MAX_VALUE};
for(int i=0;i< model.getRowCount();++i)
{
Double v= (Double)model.getValueAt(i,model.getColumnCount()-(1+EXTRA_COLUMNS));
this.minmax[0]=Math.min(this.minmax[0],v.doubleValue());
this.minmax[1]=Math.max(this.minmax[1],v.doubleValue());
}



this.spreadsheet=model;
this.sheetTable.setModel(this.spreadsheet);
Renderer renderer=new Renderer();
for(int i=0;i< this.sheetTable.getColumnCount();++i)
{
this.sheetTable.getColumnModel().getColumn(i).setCellRenderer(renderer);
}
}




private DefaultTableModel getTableModel()
{
return this.spreadsheet;
}

public JFrame asJFrame()
{
return new GeneticProg.Frame();
}


class Exploration implements Comparable<Exploration>
{
private Vector<Solution> sols;

public Exploration()
{
this.sols= new Vector<Solution>();
}


public int compareTo(Exploration o)
{
return this.best().compareTo(o.best());
}

void run(int geneIndex,int count) throws InterruptedException
{
for(int generation=geneIndex;generation< geneIndex+count;++generation)
{
while(this.sols.size()< getGeneticProg().num_parents())
{
sols.add(new Solution(choose_random_node(null),generation));
}

int n=this.sols.size();
for(int i=0;i< n;++i)
{
for(int j=0;j< n;++j)
{

Node n1= sols.elementAt(i).getNode().clone(null);
Node n2= sols.elementAt(j).getNode().clone(null);
Node.crossover(getGeneticProg(),n1,n2);
Solution s1= new Solution(n1,generation);
Solution s2= new Solution(n1,generation);
s1.mute();
s2.mute();
this.sols.addElement(s1);
this.sols.addElement(s2);
}
}

while(this.sols.size()< num_extra_parents())
{
this.sols.add(new Solution(getGeneticProg().choose_random_node(null),generation));
}

Collections.sort(sols);

//remove big ones
int k=0;
while(k< this.sols.size())
{
if(k!=0 && this.sols.elementAt(k).getNode().countDescendant()> getGeneticProg().max_nodes_in_a_tree())
{
this.sols.removeElementAt(k);
}
else
{
++k;
}
}

//remove duplicates
k=0;
while(k+1< this.sols.size())
{
if(sols.elementAt(k).equals(this.sols.elementAt(k+1)))
{
sols.removeElementAt(k);
}
else
{
++k;
}
}
getGeneticProg().challenge(this.sols.firstElement());
if(this.sols.size()> getGeneticProg().num_parents()) this.sols.setSize(getGeneticProg().num_parents());
if(generation%5==0 ) sols.setSize(1);
}
}

public GeneticProg getGeneticProg()
{
return GeneticProg.this;
}

public Solution best()
{
return this.sols.firstElement();
}

}

public void run()
{
this.runThread = new Thread(this, "GeneticAlgo")
{
public void run()
{
try
{


Vector<Exploration> explorations= new Vector<Exploration>(GeneticProg.this.getNumberOfExplorer());

int generation=0;
while(Thread.currentThread()==GeneticProg.this.runThread)
{
while(explorations.size()< GeneticProg.this.getNumberOfExplorer())
{
explorations.addElement(new Exploration());
}


GeneticProg.this.setCursor(Cursor.getPredefinedCursor(Cursor.WAIT_CURSOR));
GeneticProg.this.generationLabel.setText(String.valueOf(generation));
GeneticProg.this.generationLabel.paintComponents(GeneticProg.this.generationLabel.getGraphics());
int shift= GeneticProg.this.getGenerationPerExplorer();
for(Exploration exploration: explorations)
{
exploration.run(generation,shift);
}
generation+=shift;
GeneticProg.this.setCursor(Cursor.getDefaultCursor());
Collections.sort(explorations);




explorations.setSize(1);

}


}
catch (Exception e) {
e.printStackTrace();
}
}
};

this.runThread.start();
}


private synchronized boolean challenge(Solution best)
{
if(bestSolution==null || best.compareTo(bestSolution)<0)
{

bestSolution= (Solution)best.clone();
GeneticProg.this.generationLabel.setText(String.valueOf(best.getGeneration()));

GeneticProg.this.history.addElement(bestSolution);
keep_best_repesentation();


for(int i=0;i< GeneticProg.this.history.size();++i)
{
GeneticProg.this.svgPanes[i].setSolution(history.elementAt(i));
}

double ylist[]= bestSolution.calc();
for(int i=0;i< ylist.length && i< getTableModel().getRowCount();++i)
{
if(ylist[i]!=Double.MAX_VALUE)
{
getTableModel().setValueAt(new Double(ylist[i]),i, getColumnCount()+2);
getTableModel().setValueAt(new Double(Math.abs(ylist[i]-getNormalizedResultAt(i))),i, getColumnCount()+3);
}
else
{
getTableModel().setValueAt(null,i, getColumnCount()+2);
getTableModel().setValueAt(null,i, getColumnCount()+3);
}
}
getTableModel().fireTableDataChanged();
GeneticProg.this.functionArea.setText(bestSolution.getNode().toString());
GeneticProg.this.functionArea.setCaretPosition(0);
return true;
}
return false;
}

private void keep_best_repesentation()
{
double smallest_delat_score=(Double.MAX_VALUE);

//y_list_list.sort(); non deja fait

if( history.size()<10) return;
Collections.sort(this.history);
int r=(1)/* pas le premier !*/, r_end=(this.history.size()),r2;
int the_bad=(history.size());

while(r!=r_end)
{
r2=r+1;
if(r2!=r_end)
{
double d = history.elementAt(r).getScore()-history.elementAt(r2).getScore();
if( d<=smallest_delat_score)
{
the_bad = r;//r et pas r2, cela permet de garder le meilleur de la liste
smallest_delat_score = d;
}
}
++r;
};
if( the_bad != r_end)
{
history.removeElementAt( the_bad );
}
}




public int getColumnCount()
{
return getTableModel().getColumnCount()-(EXTRA_COLUMNS+1);
}

public int getRowCount()
{
return getTableModel().getRowCount();
}

public Double getValueAt(int row, int col)
{
assert(col < this.getColumnCount());
return (Double)getTableModel().getValueAt(row,col);
}

public Double getResultAt(int row)
{
Double v= (Double)getTableModel().getValueAt(
row,this.getColumnCount());
return v;
}

public Double getNormalizedResultAt(int row)
{
return (getResultAt(row).doubleValue()-minmax[0])/(minmax[1] -minmax[0]);
}

static class Shuttle
{
int total_node;
}

public Random getRandom()
{
return this.random;
}

public double rnd()
{
return getRandom().nextDouble();
}

public int max_nodes_in_a_tree()
{
return this.maxNodeInATree.getNumber().intValue();
}

public double proba_create_leaf()
{
return this.probaLeaf.getNumber().doubleValue();
}

public double proba_mutation()
{
return this.probaMutation.getNumber().doubleValue();
}

public int num_parents()
{
return this.numberOfParent.getNumber().intValue();
}


public double getMaxNANPercent()
{
return this.maxNANPercent.getNumber().doubleValue();
}


public int getNumberOfExplorer()
{
return this.numberOfExplorer.getNumber().intValue();
}

public int getGenerationPerExplorer()
{
return this.numberOfGeneration.getNumber().intValue();
}

public int num_extra_parents()
{
return 10;
}

private int getOperatorWeight(Operator op)
{
SpinnerNumberModel model= this.weigths.get(op);
return model.getNumber().intValue();
}

Operator choose_operator()
{
int n= getRandom().nextInt(this.total_operator_weight);
for (Iterator<Operator> iter = this.weigths.keySet().iterator(); iter.hasNext();) {
Operator op = iter.next();
int weight=getOperatorWeight(op);
if(n<weight)
{
return op;
}
n-=weight;
}
assert(false);
return this.weigths.keySet().iterator().next();
}



synchronized Node choose_random_node(Shuttle shuttle)
{
if(shuttle==null)
{
shuttle=new Shuttle();
shuttle.total_node=0;
}
Node nn=null;

++shuttle.total_node;

if( shuttle.total_node+1>= max_nodes_in_a_tree() ||
rnd() < proba_create_leaf() )
{
nn = make_leaf();
}
else
{
nn = new Function(this,shuttle);
}
assert(nn!=null);
return nn;
}

/****************************************
*
* make_leaf
*
*/
private Node make_leaf()
{
Node nn=null;
if( rnd() < 0.5 )
{
nn = new Constant(this);
}
else
{
nn = new Column(this);
}
assert(nn!=null);
return nn;
}

static public GeneticProg newInstanceDialog() throws IOException
{
StringBuilder content= new StringBuilder();
BufferedReader in= new BufferedReader(new InputStreamReader(GeneticProg.class.getResourceAsStream("/org/lindenb/geneticalgo/sample.xls")));
String line= null;
while((line=in.readLine())!=null)
{
content.append(line+"\n");
}
in.close();

Font font= new Font("Helvetica",Font.PLAIN,10);
JTextArea area= new JTextArea(content.toString(),25,40);
area.setFont(font);
content=null;
JPanel pane= new JPanel(new BorderLayout());
pane.add(new JScrollPane(area));

int rez= JOptionPane.showConfirmDialog(null,pane,"Copy/Paste a Tab delimited File",JOptionPane.OK_CANCEL_OPTION,JOptionPane.QUESTION_MESSAGE,geticon());
if(rez!=JOptionPane.OK_OPTION) return null;

in= new BufferedReader(new StringReader(area.getText()));
area=null;
GeneticProg prog = newInstance(in);
in.close();

return prog;
}


static public GeneticProg newInstance(File f) throws IOException
{
BufferedReader in= new BufferedReader(new FileReader(f));
GeneticProg prog=newInstance(in);
in.close();
return prog;
}

static public GeneticProg newInstance(BufferedReader in) throws IOException
{
GeneticProg prog=new GeneticProg();
prog.read(in);
return prog;
}

static public GeneticProg newInstance() throws IOException
{
JFileChooser chooser=new JFileChooser();
chooser.setDialogTitle("Choose a Tab delimited file.");
chooser.setAccessory(new JLabel(geticon()));
if( chooser.showOpenDialog(null)!=JFileChooser.APPROVE_OPTION) return null;
File f= chooser.getSelectedFile();
if(f==null) return null;

GeneticProg prog=newInstance(f);

return prog;
}


private static Icon geticon()
{
try
{
InputStream in= GeneticProg.class.getResourceAsStream("/org/lindenb/geneticalgo/icon.png");
ImageIcon icon=new ImageIcon(ImageIO.read(in));
in.close();
return icon;
}
catch (Exception e) {
return null;
}
}

/**
* @param args
*/
public static void main(String[] args) {

try {


try {
UIManager.setLookAndFeel("javax.swing.plaf.metal.MetalLookAndFeel");
} catch (Exception e) { }
JFrame.setDefaultLookAndFeelDecorated(true);
JDialog.setDefaultLookAndFeelDecorated(true);
GeneticProg prog= newInstance();
if(prog==null) return;


JFrame frame= prog.asJFrame();
frame.setVisible(true);
prog.run();
} catch (Exception e)
{
JOptionPane.showMessageDialog(null,e.getMessage(),e.getMessage(),JOptionPane.ERROR_MESSAGE);
e.printStackTrace();
}

}


}


./org/lindenb/geneticalgo/SVGPane.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;

import javax.swing.BorderFactory;
import javax.swing.JPanel;

/**
* @author lindenb
*
*/
public class SVGPane extends JPanel
{

private static final long serialVersionUID = 1L;
private Solution solution;
private double y_list[];
public SVGPane()
{
super(null);
this.setOpaque(true);
this.setBackground(Color.WHITE);
Dimension dim= new Dimension(150,150);
this.setPreferredSize(dim);
this.setMinimumSize(dim);
this.setFont(new Font("Helvetica",Font.BOLD,9));
setBorder(BorderFactory.createLineBorder(Color.BLUE));
this.y_list=null;
}


public void setSolution(Solution sol)
{
this.solution=sol;
this.y_list= getSolution().calc();
setToolTipText(sol.toString());
repaint();
}

public Solution getSolution() {
return solution;
}

static int SVGVAL(double i)
{
return (int)i;
}

@Override
protected void paintComponent(Graphics g1d) {
super.paintComponent(g1d);
Graphics2D g=(Graphics2D)g1d;
g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,RenderingHints.VALUE_ANTIALIAS_ON);
if(getSolution()==null) return;

int SVGSIZE= Math.min(this.getWidth(),this.getHeight());
if(SVGSIZE<=1) return;
int H=0;
int V=0;

FontMetrics fm= getFontMetrics(getFont());
String title=""+getSolution().getScore()+" [" + getSolution().getGeneration() + "]";
int titlew=fm.stringWidth(title);


g.setColor(Color.GRAY);
g.drawLine(SVGVAL(H),SVGVAL(V+SVGSIZE),SVGVAL(H+SVGSIZE),SVGVAL(V));


g.setColor(Color.LIGHT_GRAY);
for(int i=0;i< y_list.length;++i)
{
double x= H + getSolution().getGeneticProg().getNormalizedResultAt(i)*SVGSIZE;
double y= V + SVGSIZE- y_list[i]*SVGSIZE;

if( y_list[i]==Double.MAX_VALUE)
{
y= V + SVGSIZE-5;
}


//vertical
g.drawLine(SVGVAL(x),SVGVAL(y),SVGVAL(x),SVGVAL(V+SVGSIZE));

if( y_list[i]==Double.MAX_VALUE) continue;
g.drawLine(SVGVAL( H ),SVGVAL( y ),SVGVAL( x ),SVGVAL( y ));
}
g.setColor(Color.BLACK);
for(int i=0;i< y_list.length;++i)
{
double x= H + getSolution().getGeneticProg().getNormalizedResultAt(i)*SVGSIZE;
double y= V + SVGSIZE- y_list[i]*SVGSIZE;
//horizontal
g.drawOval(SVGVAL( x-2 ),SVGVAL( y-2 ),4,4);


}
g.setColor(Color.BLUE);
g.drawString(title,
SVGVAL((this.getWidth()-titlew)/2), SVGVAL(getHeight()/2.0-6)
);


}


}


./org/lindenb/geneticalgo/Node.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

import java.io.PrintWriter;
import java.io.StringWriter;
import java.util.Vector;

/**
* @author pierre
*
* Node
*/
public abstract class Node
{
public static enum NodeType
{
COLUMN,
CONSTANT,
FUNCTION
};

protected Node parent;
private GeneticProg genprog;
protected Node(GeneticProg genprog)
{
this.parent=null;
this.genprog=genprog;
}

/**
* @return Returns the parent.
*/
public Node getParent()
{
return parent;
}

/**
* @return Returns the SpreadSheet.
*/
public GeneticProg getGeneticProg()
{
return this.genprog;
}




/****************************************
*
* get_root
*
*/
public Node getRoot()
{
Node curr= this;
while(curr.parent!=null)
{
curr=curr.parent;
}
return(curr);
}

/****************************************
*
* crossover
*
*/
@SuppressWarnings("unchecked")
static void crossover(GeneticProg ctxt,Node node1, Node node2)
{
Node father[]=new Node[]{null,null};
Node node_to_swap[]=new Node[]{null,null};
Vector<Node> nodes[]=new Vector[]
{
new Vector<Node>(),
new Vector<Node>()
};
//get all the nodes
node1.collect_node(nodes[0]);
node2.collect_node(nodes[1]);


//get the father of those list
//find each curr in the father child list

for(int i=0;i<2;++i)
{
//get a random node_t in the list
node_to_swap[i] = nodes[i].elementAt( ctxt.getRandom().nextInt(nodes[i].size()));
;

father[i] = node_to_swap[i].parent;
//test it is not the root
if( father[i]==null) return;
//test it is a node with children
if(father[i].getChildCount()==0) return;

assert( father[i]!=null);
}

/* swap link child->father */
node_to_swap[0].parent = father[1];
node_to_swap[1].parent = father[0];

/*
swap link father->child
ATTENTION a ce stade les father sont de type func_t (!=leaf)
*/

Function fun_father[]=new Function[]
{
(Function)father[0],
(Function)father[1]
};

for(int i=0;i<2;++i)
{
for(int j=0; j< fun_father[i].getChildCount();++j)
{
if( fun_father[i].getChildAt(j).parent != fun_father[i])
{
assert( fun_father[i].getChildAt(j).parent == fun_father[(i==0?1:0)] );
assert( node_to_swap[ (i==0?1:0) ].parent ==fun_father[i] );
fun_father[i].setChildrenAt(node_to_swap[ (i==0?1:0) ],j);
break;
}
}
}
}




/****************************************
*
* mute
*
*/
void mute()
{
//int old_type=my_type;
Node choosen=null;
Vector<Node> nodes=null;
int tried=0;
while( tried<2 && getGeneticProg().rnd() < getGeneticProg().proba_mutation())
{
++tried;
if(nodes==null)
{
nodes= getAllNodes();
}
assert(nodes.size()>0);
choosen = nodes.elementAt(
getGeneticProg().getRandom().nextInt(nodes.size() ));
if(getGeneticProg().rnd()>0.05)
{
choosen.muteIt();
}
else
{
Node parent=choosen.parent;
if(parent!=null)
{
assert(parent.getNodeType()==Node.NodeType.FUNCTION);
((Function)parent).replaceChildren(choosen,getGeneticProg().choose_random_node(null));
}
}
}
}


public Vector<Node> getAllNodes()
{
Vector<Node> nodes= new Vector<Node>();
collect_node(nodes);
return nodes;
}

/****************************************
*
* collect_node
*
*/
private void collect_node(Vector<Node> nodes)
{
nodes.addElement(this);
for(int i=0;i< getChildCount();++i)
{
getChildAt(i).collect_node(nodes);
}
}


public int countDescendant()
{
int n=1;
for(int i=0;i< getChildCount();++i)
{
n+= getChildAt(i).countDescendant();
}
return n;
}

public abstract int getChildCount();
public abstract Node getChildAt(int index);
public abstract void muteIt();
public abstract Number calc(int row);
public abstract void print(PrintWriter out);
public abstract Node clone(Node parent);
public abstract NodeType getNodeType();
public abstract boolean equals(Object o);





@Override
public String toString() {
StringWriter w= new StringWriter();
this.print(new PrintWriter(w,true));
w.flush();
return w.toString();
}


}


./org/lindenb/geneticalgo/PredicateOperator.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

/**
* @author lindenb
*
*/
public abstract class PredicateOperator extends Operator {
private String name;
/**
* @param sheet
*/
public PredicateOperator(String name,GeneticProg sheet) {
super(sheet);
this.name=name;
}


@Override
public int argc() {
return 4;
}


@Override
public Number calc(int rowIndex, Node[] childs)
{
assert(childs!=null && childs.length==4);
Number value1= childs[0].calc(rowIndex);
if(value1==null || Double.isNaN(value1.doubleValue())) return null;
Number value2= childs[1].calc(rowIndex);
if(value2==null || Double.isNaN(value2.doubleValue())) return null;


if(compare(value1.doubleValue(),value2.doubleValue()))
{
return childs[2].calc(rowIndex);
}
else
{
return childs[3].calc(rowIndex);
}

}


abstract boolean compare(double n1,double n2);


@Override
public String getName() {
return this.name;
}

}


./org/lindenb/geneticalgo/Operator.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;


public abstract class Operator
{
private GeneticProg sheet;
protected Operator(GeneticProg sheet)
{
this.sheet=sheet;
}

public GeneticProg getSpreadSheet()
{
return this.sheet;
}
@Override
public int hashCode()
{
return getName().hashCode();
}

@Override
public boolean equals(Object o)
{
return this==o;
}

public abstract int argc();
public abstract Number calc(int rowIndex,Node childs[]);
public abstract String getName();
@Override
public String toString() {
return getName();
}
}


./org/lindenb/geneticalgo/Column.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

import java.io.PrintWriter;


/**
* @author pierre
*
* Column
*/
public class Column extends Leaf
{
private int columnIndex;
/**
* @param parent
* @param context
*/
public Column(GeneticProg genprog)
{
super(genprog);
mute();
}


public NodeType getNodeType()
{
return NodeType.COLUMN;
}

/* (non-Javadoc)
* @see org.lindenb.geneticalgo.Node#mute()
*/
public void muteIt()
{
this.columnIndex=getGeneticProg().getRandom().nextInt(getGeneticProg().getColumnCount());
}

public void print(PrintWriter out)
{
out.print("($"+(1+this.columnIndex)+")");
}

public Number calc(int row)
{
return getGeneticProg().getValueAt(row,this.columnIndex);
}

public Node clone(Node parent)
{
Column c= new Column(getGeneticProg());
c.parent=parent;
c.columnIndex=columnIndex;
return c;
}
@Override
public boolean equals(Object o) {
if(this==o) return true;
if(!(o instanceof Column)) return false;
Column cp=(Column)o;
return cp.columnIndex==this.columnIndex;
}

}


./org/lindenb/geneticalgo/Solution.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

import java.util.Vector;

/**
* @author pierre
*
*/
public class Solution implements Comparable<Solution>,Cloneable
{
private Node node;
private Double score;
private int generation;
private int countNaN;

public Solution(Node node,int generation)
{
this.node=node;
this.generation=generation;
this.score=null;
this.countNaN=0;
}




public int getGeneration()
{
return this.generation;
}

@Override
public Object clone()
{
Solution sol= new Solution(this.getNode().clone(null),getGeneration());
return sol;
}

public GeneticProg getGeneticProg()
{
return getNode().getGeneticProg();
}


@Override
public boolean equals(Object obj)
{
if(this==obj) return true;
Solution cp=(Solution)obj;
return cp.getNode().equals(this.getNode());
}

public Node getNode()
{
return this.node;
}

public int compareTo(Solution src)
{
int i= getScore().compareTo(src.getScore());
if(i!=0) return i;
return this.countNaN-src.countNaN;
}

public Double getScore()
{
if(this.score==null)
{
calc();
}
return this.score;
}

public void mute()
{

if(getGeneticProg().rnd()<0.05)
{
Vector<Node> nodes= getNode().getAllNodes();
Node newroot= nodes.elementAt(getGeneticProg().getRandom().nextInt(nodes.size()));
newroot.parent=null;
this.node=newroot;
}
else
{
getNode().mute();
}
this.score=null;
}


public double[] calc()
{
double my_score=0;
int number_of_NaN=(0);
double y_list[]= new double[getGeneticProg().getRowCount()];
double the_min = Double.MAX_VALUE;
double the_max = Double.MIN_VALUE;

my_score=0;

for(int i=0;i< getGeneticProg().getRowCount();++i)
{
Number val = getNode().calc(i);
if(val==null || Double.isInfinite(val.doubleValue()) || Double.isNaN(val.doubleValue()) )
{
y_list[i] = Double.MAX_VALUE;
++number_of_NaN;
}
else
{
y_list[i]=val.doubleValue();
the_min= Math.min(y_list[i],the_min);
the_max= Math.max(y_list[i],the_max);
}
}

//normalisation of the values
if( the_min!=the_max &&
getGeneticProg().getRowCount()* getGeneticProg().getMaxNANPercent() > number_of_NaN) // permettre 10% deNaN
{
int count_good_values=(0);
for(int i=0;i<y_list.length;++i)
{
if( y_list[i]==Double.MAX_VALUE) continue;
y_list[i]= (y_list[i]-the_min)/(the_max-the_min);
}
for(int i=0;i< getGeneticProg().getRowCount();++i)
{
if( y_list[i]==Double.MAX_VALUE) continue;
++count_good_values;
double v=(getGeneticProg().getNormalizedResultAt(i) - y_list[i]);
my_score+= (v<0?-v:v);
}

my_score/=(double)count_good_values;
}
else
{
my_score=Double.MAX_VALUE;
number_of_NaN=Integer.MAX_VALUE;
}
if(Double.isNaN(my_score) || Double.isInfinite(my_score))
{
my_score=Double.MAX_VALUE;
number_of_NaN=Integer.MAX_VALUE;
}
this.score= new Double(my_score);
this.countNaN= number_of_NaN;
return y_list;
}

@Override
public String toString()
{
return getNode().toString()+ " ("+getGeneration()+") ["+getScore()+"]";
}

}


./org/lindenb/geneticalgo/UnaryOperator.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

public abstract class UnaryOperator extends Operator {
private String name;
protected UnaryOperator(String name,GeneticProg sheet)
{
super(sheet);
this.name=name;
}

@Override
public int argc()
{
return 1;
}
@Override
public String getName() {
return name;
}

@Override
public Number calc(int rowIndex, Node[] childs)
{
assert(childs!=null && childs.length==1);
Number value= childs[0].calc(rowIndex);
if(value==null || Double.isInfinite(value.doubleValue()) || Double.isNaN(value.doubleValue())) return null;
return calc(rowIndex,value.doubleValue());
}

public abstract Number calc(int rowIndex,double value);
}


./org/lindenb/geneticalgo/Leaf.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

/**
* @author pierre
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
public abstract class Leaf extends Node {

/**
* @param parent
* @param context
*/
public Leaf(GeneticProg genprog)
{
super(genprog);
}

public int getChildCount()
{
return 0;
}

public Node getChildAt(int index)
{
return null;
}
}


./org/lindenb/geneticalgo/Constant.java

/*
* Author: Pierre Lindenbaum PhD
* Contact: plindenbaum (at) yahoo (dot) fr
* Created on 1:36:21 PM
*
* For condition of distribution and use, see the accompanying README file.
*
* $Id: $
* $Author: $
* $Revision: $
* $Date: $
* $Source: $
* $Log: $
*
*/
package org.lindenb.geneticalgo;

import java.io.PrintWriter;



/**
* @author pierre
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
public class Constant extends Leaf {
private Double value;
/**
* @param parent
* @param context
*/
public Constant(GeneticProg genprog)
{
super(genprog);
muteIt();
}


public NodeType getNodeType()
{
return NodeType.CONSTANT;
}


public void muteIt()
{
if(getGeneticProg().rnd()<0.5)
{
this.value = new Double( 50.0 - getGeneticProg().getRandom().nextInt(100) );
}
else
{
this.value = new Double( 0.5 - getGeneticProg().getRandom().nextDouble() );
}
}

public void print(PrintWriter out)
{
out.print("("+this.value+")");
}

public Node clone(Node parent)
{
Constant c= new Constant(this.getGeneticProg());
c.parent=parent;
c.value=value;
return c;
}

@Override
public boolean equals(Object o) {
if(this==o) return true;
if(!(o instanceof Constant)) return false;
Constant cp=(Constant)o;
return cp.value.equals(this.value);
}


public Number calc(int row)
{
return this.value;
}


}

3 comments:

Anonymous said...

it was very gratefull subject!!!
good luck .

Einstein said...

Yours is an interesting implementation of GP but it isnt directly applied to biological systems. I mean you are solving a generic problem, instead of a specific one.

It would be exciting to see GP solving some of the hardest problems such as Protein 3d structure prediction, etc.

Check out my GP system coded in Python at: http://www.paraschopra.com/sourcecode/GP/index.php

and see this

http://www.paraschopra.com/projects/evoca_prot/index.php

Anonymous said...

Hi! I am currently writing a (free and open) e-book called "Global Optimization - Theory and Application". It is about genetic algorithms, evolutionary algorithms, evolution strategy, leaning classifier systems, simulated annealing, and so on. I hope that I can make this topic more interesting for students and fellow researchers and help people to get started with it. Of course, the book is still very incomplete and probably has also errors, but I try to improve it very much. You can find it at http://www.it-weise.de/projects/book.pdf, I will update it regularly. Constructive criticism is always welcom, as well as new suggestions on what to include in the book.
Kind regards,
Thomas.