/*
Sara Moss
Intro. to Artificial Intelligence
HW5 due Oct. 4, 2000

Evolution Strategies -
Utilization of evolution concepts to solve a minimization problem.

Class Individual contains the input values to the function and the value of the
function at those inputs.  It also contains a method to mutate itself into an
offspring by adding an increment determined by the Gauss function.

Class Population contains a parent individual and a child individual and a
selection method which contains the criteria for determining if the parent or
the child is more qualified (produces a smaller functin value) to be the
next parent.

Class Society extends Population and adds a dynamic means of changing the stepsize used
to produce the variation.  It uses the 20% success criteria to increase or
decrease the stepsize.

*/


import java.awt.*;
import java.awt.event.*;
import java.util.*;
import java.text.*;

class CloseableFrame extends Frame
{ public CloseableFrame()
  { addWindowListener(new WindowAdapter()
    { public void windowClosing(WindowEvent e)
      { System.exit(0);}
    });
  }
}

//draws graph of population
class PopulationCanvas extends Canvas
{ private int width;              //width of canvas
  private int height;             //height of canvas
  private Vector points;          //vector holds points of graph of f
  private int lowerBound;
  private int upperBound;
  private int offset;

  public PopulationCanvas(int lb, int ub, int w, int h)
  { width=w;
    height=h;
    lowerBound=lb;
    upperBound=ub;
    offset=20;
    points = new Vector();
  }

  public void AddPoint(double x, double y)
  { int posX=offset+(int)(width*((x-lowerBound)/(upperBound-lowerBound)));
    int posY=offset+(int)(height-(height*((y-lowerBound)/(upperBound-lowerBound))));
    points.addElement(new Point(posX, posY));
    repaint();
  }

  public void Reset()
  { points.removeAllElements();
    repaint();
  }

  public void paint(Graphics g)
  { //graph of function is drawn on canvas
    NumberFormat nf=NumberFormat.getNumberInstance();
    nf.setMaximumFractionDigits(1);
    nf.setMinimumFractionDigits(1);
    double midPoint=lowerBound+(upperBound-lowerBound)/2.0;

    g.drawString(String.valueOf(lowerBound), offset, offset-3);
    g.drawString(nf.format(midPoint),
      offset+(width/2),offset-3);
    g.drawString(String.valueOf(upperBound),offset+width, offset-3);

    g.drawString(String.valueOf(upperBound), 3, offset+10);
     g.drawString(nf.format(midPoint),
      3, offset+(height/2));
    g.drawString(String.valueOf(lowerBound),
      3, offset+height);

    g.drawRect(0, 0, width + 2*offset, height + 2*offset);
    g.drawRect(offset,offset,width, height);
    for (int i = 0; i < points.size(); i++)
    {
      Point p = (Point)points.elementAt(i);
      g.drawRect(p.x, p.y, 1, 1);
    }
  }
}

class Individual
{ public double[] x;                          //array of individual's input values
  public double value;                        //value of function for inputs
  protected int lb;                           //domain lower bound
  protected int ub;                           //domain upper bound
  protected int numPar;                       //number of inputs
  protected String function;                  //id of function in use

  public Individual(int lb, int ub, int numPar, String f)
  { this.lb=lb;
    this.ub=ub;
    this.numPar=numPar;
    x = new double[numPar];
    for (int i=0; i<numPar; i++)             //choose initial parent randomly
      x[i]=ub-((ub-lb)*Math.random());
    function=f;
    if (function=="X1^2 + X2^2")
      value=Math.pow(x[0],2)+Math.pow(x[1],2);
    else if (function=="X1^2 + 25*X2^2")
      value=Math.pow(x[0],2) + 25*Math.pow(x[1],2);
    else if (function=="100(X1^2 - X2)^2 + (1 - X1)^2")
      value=100*Math.pow(Math.pow(x[0],2)-x[1],2)+
        Math.pow(1-x[0],2);
  }

  public Individual Variation(double stepSize)
  { Individual temp=new Individual(lb, ub, numPar, function);
    for (int i=0; i < numPar; i++)
    { do
      { temp.x[i]=x[i]+Gauss(0.0, stepSize);    //alter parent incrementally
                                                //to produce child
      }while(temp.x[i]>ub || temp.x[i]<lb);     //domain checking
    }
    //evaluate value at chosen function
    if (function=="X1^2 + X2^2")
      temp.value=Math.pow(temp.x[0],2)+Math.pow(temp.x[1],2);
    else if (function=="X1^2 + 25*X2^2")
      temp.value=Math.pow(temp.x[0],2) + 25*Math.pow(temp.x[1],2);
    else if (function=="100(X1^2 - X2)^2 + (1 - X1)^2")
      temp.value=100*Math.pow(Math.pow(temp.x[0],2)-temp.x[1],2)+
        Math.pow(1-temp.x[0],2);
    return temp;
  }

  //function used by Variation to determine incremental change of parent,
  //larger v -> larger change and vice versa
  public double Gauss(double mean, double v)
  { double a, b, r;
    do
    { a=Math.random();
      b=Math.random();
    }while (a<=0 || b<=0);
    r=Math.sqrt(v/2.0);
    r*=Math.log(a/b);
    r+=mean;
    return r;
  }

  //returns a formatted string for output
  public String show()
  { NumberFormat nf=NumberFormat.getNumberInstance();
    nf.setMaximumFractionDigits(6);
    nf.setMinimumFractionDigits(6);
    String s="\n";
    for (int i=0; i< numPar; i++)
      s+="\nx["+i+"] = "+nf.format(x[i]);
    s+="\nvalue = "+nf.format(value);
    return s;
  }
}

//contains a parent and a child individual and a method to determine which
//will survive
class Population
{ public Individual parent;
  public Individual child;

  public Population(int lb, int ub, int numPar, String f)
  { parent = new Individual(lb, ub, numPar, f);
  }

  public void Select()
  { if(child.value<parent.value)
      parent=child;
  }
}

//adds a criteria for dynamically altering stepsize depending on success
class Society extends Population
{ private int successCount;
  public double stepSize;

  public Society(int lb, int ub, int numPar, String f)
  { super(lb, ub, numPar, f);
    successCount=0;
    stepSize=0.82;
  }

  public void Select()
  { if(child.value<parent.value)    //determine if child or parent is better
    { parent=child;
      successCount++;               //keep track of successes this window
    }
  }

  public void UpdateStepsize(int windowSize)
  { if (successCount > windowSize*0.2)         //>20% success rate
      stepSize/=0.82;                          //increase stepsize
    else                                       //<20% success rate
      stepSize*=0.82;                          //decrease stepsize
    successCount=0;                            //reset counter for next window
  }
}

public class HW5 extends CloseableFrame
    implements ActionListener, Runnable
{ private Button b1, b2, b3;
  private TextArea ta;
  private PopulationCanvas popCanvas;       //visual graph of population
  private String function;                  //represents function chosen by user

  private long totGen;                      //total generations produced
  private int foundCount;                   //count of successful trials

  static final long MAX_GEN=50000;          //max generations/trial
  static final int MAX_TRIAL=5;             //max trials per run

  private Thread thread;

  public static void main(String[] args)
  { Frame f=new HW5();
    f.setSize(508, 400);
    f.setVisible(true);
  }

  public HW5()
  { setTitle("Evolution Strategies");

    setLayout(new BorderLayout());
    Panel p=new Panel();
    p.setLayout(new FlowLayout());
    p.add(b1=new Button("X1^2 + X2^2"));
    p.add(b2=new Button("X1^2 + 25*X2^2"));
    p.add(b3=new Button("100(X1^2 - X2)^2 + (1 - X1)^2"));
    add("North", p);
    add("Center", ta=new TextArea("", 8, 90,
                             TextArea.SCROLLBARS_VERTICAL_ONLY));


    add("Center", popCanvas=new PopulationCanvas(-10, 10, 300, 300));
    add("East", ta=new TextArea("", 7, 20,
                             TextArea.SCROLLBARS_VERTICAL_ONLY));
    b1.addActionListener(this);
    b2.addActionListener(this);
    b3.addActionListener(this);

    totGen=0;
    foundCount=0;
  }

  public void run()
  { Evolution();
  }

  public void actionPerformed(ActionEvent e)
  { String arg=e.getActionCommand();
    String s1=ta.getText();
    String s2="";
    ta.replaceRange(s2, 0, s1.length());
    popCanvas.Reset();
    totGen=0;
    foundCount=0;
    if (arg.equals("X1^2 + X2^2"))
    { function="X1^2 + X2^2";
    }
    else if (arg.equals("X1^2 + 25*X2^2"))
    { function="X1^2 + 25*X2^2";
    }
    else if (arg.equals("100(X1^2 - X2)^2 + (1 - X1)^2"))
    { function="100(X1^2 - X2)^2 + (1 - X1)^2";
    }
    thread=new Thread(this);
    thread.start();
  }

  private void Evolution()
  { int windowSize=50;
    //format output, set fraction digits
    NumberFormat nf=NumberFormat.getNumberInstance();
    nf.setMaximumFractionDigits(6);
    nf.setMinimumFractionDigits(6);

    for(int trial=1; trial<=MAX_TRIAL; trial++)
    { if (thread!=null)
      { popCanvas.Reset();
        try {thread.sleep(500);}
        catch(InterruptedException e){}
      }
      Society s = new Society(-10, 10, 2, function);
      for(long gen=1; gen<=MAX_GEN; gen++)
      { s.child=s.parent.Variation(s.stepSize);     //spawn child
        s.Select();                                 //choose survivor
        if(gen%windowSize==0)                       //every windowSize,
          s.UpdateStepsize(windowSize);             //alter stepsize according
                                                    //to success
        int size;
        if (function.equals("100(X1^2 - X2)^2 + (1 - X1)^2"))
          size=100;
        else
          size=10;
        if (gen%size==0)
        { if (thread!=null)
          { ta.append("\n\nTrial = "+trial+
                    "\nGeneration = "+gen+
                    "\nParent = "+nf.format(s.parent.value));
            popCanvas.AddPoint(s.parent.x[0], s.parent.x[1]);
            try {Thread.sleep(200);}
            catch (InterruptedException e){}
          }
        }
        if(s.parent.value < .005)        //criteria for success
        { ta.append("\n\nSolution found at generation #"+gen);
          totGen+=gen;
          foundCount++;
          break;
        }
      }
      ta.append(s.parent.show());
    }
    double ss=(double)foundCount/(double)MAX_TRIAL*100.0;
    ta.append("\n\nSuccess = "+ss+"%");
    totGen+=(MAX_TRIAL-foundCount)*MAX_GEN;
    ta.append("\nTotal #Generations = "+totGen);
    ta.append("\nAverage #Generations = "+(totGen/MAX_TRIAL));
  }
}