OthelloProj/ 40755 5763 134 0 6506556656 11777 5 ustar evs faculty OthelloProj/GP/ 40755 5763 134 0 6506556656 12305 5 ustar evs faculty OthelloProj/GP/docs/ 40755 5763 134 0 6506556646 13234 5 ustar evs faculty OthelloProj/GP/docs/packages.html 100644 5763 134 4020 6506556643 15766 0 ustar evs faculty
API User's Guide Class Hierarchy Index
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPContainer | +----gpjpp.GP
Besides the program itself, GP also stores the complexity and maximum depth of the tree, its standard fitness (as computed by a user subclass), its adjusted fitness, and its heritage. The heritage consists of the population indices of the two parents if the GP was created by crossover or the population index of one parent if the GP was created by straight reproduction. It also includes the crossover points and the last mutation locus when applicable.
The user must always create a subclass of GP for use in solving a particular problem. This subclass must override the evaluate() method, which returns a double that indicates the standard fitness of the GP. (The standard fitness must always be non-negative, and the genetic algorithm attempts to find individuals with minimal standard fitness.) The other fields of the GP are calculated by gpjpp.
Usually the user must also override the createGene() method to dynamically create genes of a problem-specific type. See the supplied example programs for more details.
protected double stdFitness
protected double adjFitness
protected int gpLength
protected int gpDepth
public int dadIndex
public int dadCross
public int mumIndex
public int mumCross
public int crossTree
public int swapTree
public int swapPos
public int shrinkTree
public int shrinkPos
public GP()
public GP(int trees)
public GP(GP gpo)
protected void clearHeritage()
protected synchronized Object clone()
public byte isA()
public GPGene createGene(GPNode gpo)
public void testNull()
public double evaluate(GPVariables cfg)
protected void calcAdjustedFitness()
public double getFitness()
public double getAdjFitness()
protected boolean betterThan(GP gp)
public int length()
public int depth()
protected void calcLength()
protected void calcDepth()
public int hashCode()
public boolean equals(Object obj)
public synchronized void create(int creationType, int allowableDepth, int allowableLength, GPAdfNodeSet adfNs)
public synchronized void shrinkMutation()
public synchronized void swapMutation(GPAdfNodeSet adfNs)
public void mutate(GPVariables cfg, GPAdfNodeSet adfNs)
public synchronized GPContainer cross(GPContainer parents, int maxDepthForCrossover, int maxComplexity)
protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
protected void save(DataOutputStream os) throws IOException
public void printOn(PrintStream os, GPVariables cfg)
public void printTree(PrintStream os, GPVariables cfg)
public void drawOn(GPDrawing ods, String fnameBase, GPVariables cfg) throws IOException
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPNodeSet.html 100644 5763 134 37075 6506556644 17160 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPContainer | +----gpjpp.GPNodeSet
GPNodeSet is a container that holds an arbitrary number of function and terminal nodes. For improved performance during some operations, all of the functions are stored at the beginning of the container and all of the terminals are stored at the end. There might be some null elements in the middle and the code is designed to accommodate those.
protected int numFunctions
protected int numTerminals
public GPNodeSet()
public GPNodeSet(int numOfNodes)
public GPNodeSet(GPNodeSet gpo)
protected synchronized Object clone()
public byte isA()
public int functions()
public int terminals()
public void putNode(GPNode gpo)
public boolean equals(Object obj)
protected GPNode searchForNode(int value)
public GPNode chooseFunction()
public GPNode chooseTerminal()
public GPNode chooseNodeWithArgs(int args)
protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
protected void save(DataOutputStream os) throws IOException
public void printOn(PrintStream os, GPVariables cfg)
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPPopulationRange.html 100644 5763 134 2073 6506556644 20674 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPPopulationRange
This class is not public and can therefore cannot be used outside this package.
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPNode.html 100644 5763 134 40614 6506556644 16475 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPNode
protected int nodeValue
protected int numOfArgs
protected String representation
protected byte nodeIndex
public GPNode()
public GPNode(int nVal, String str, int args)
public GPNode(int nVal, String str)
public GPNode(GPNode gpo)
protected synchronized Object clone()
public byte isA()
public int value()
public String rep()
public boolean isFunction()
public boolean isTerminal()
public int arguments()
public void setIndex(byte index)
public byte getIndex()
public boolean equals(Object obj)
protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
protected void save(DataOutputStream os) throws IOException
public void printOn(PrintStream os, GPVariables cfg)
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPGenePrint.html 100644 5763 134 67605 6506556644 17514 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPContainer | +----gpjpp.GPGene | +----gpjpp.GPGenePrint
The three key methods of the class are the constructor, GPGenePrint(GPGene), which clones a GPGene tree onto a new tree with the extra fields, printOn(), which prints the tree in pseudo-graphic format to a PrintStream, and drawOn(), which prints the tree as a true graphic gif file.
Several static public fields of the class can be used to adjust the appearance of the tree: xMargin, xSpacing, rectMargin, arcRadius, rowsPerNode.
public static double xMargin
public static double xSpacing
public static int rectMargin
public static int arcRadius
public static int rowsPerNode
protected double x
protected GPGene peer
protected synchronized Object clone()
public byte isA()
protected synchronized void load(DataInputStream is)
protected void save(DataOutputStream os)
protected double getNodeWidth()
protected double getNodeRight()
protected double calcPackedContainerWidth()
protected double calcContainerCenter()
protected void calcPackedPos(double minX[], int curDepth)
protected boolean adjustOverlaps(double minX[], double curX[], int curDepth)
This method is called repeatedly until no further adjustments are needed or an iteration limit is reached.
protected void spreadTerminals()
protected double calcMinX()
protected double calcMinX(double minSoFar)
protected double calcMaxX()
protected double calcMaxX(double maxSoFar)
protected void shiftX(double dx)
protected int calcXPositions()
protected void spaceTo(PrintStream os, int curDepth, double curX[], double rx)
protected void printLevel(PrintStream os, int depToPrint, int curDepth, double curX[])
protected void printConnectors(PrintStream os, int depToPrint, int curDepth, double curX[])
public void printOn(PrintStream os, GPVariables cfg)
protected final int xText(GPDrawing ods, double x)
protected final int yText(GPDrawing ods, int depth)
protected final int xBox(GPDrawing ods, double x)
protected final int yBox(GPDrawing ods, int depth)
protected final int wBox(GPDrawing ods, String nodeName)
protected final int hBox(GPDrawing ods)
protected void drawGifNode(GPDrawing ods, int curDepth)
public void drawOn(GPDrawing ods, String fname, String title, GPVariables cfg) throws IOException
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPContainer.html 100644 5763 134 33503 6506556644 17531 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPContainer
GPContainer provides a convenient location to centralize the streaming operations for its subclasses.
GPContainer is generally not instantiated directly.
Several of the GPContainer methods are marked "final" so that an optimizing compiler can inline these simple methods, causing a substantial improvement to gpjpp performance. Except for this desire for optimization, these methods don't need to be final.
No explicit array index checking or memory allocation checking is required because Java performs these checks automatically and throws exceptions if errors are detected.
protected GPObject container[]
public GPContainer()
public GPContainer(int numObjects)
public GPContainer(GPContainer gpc)
protected synchronized Object clone()
public byte isA()
public final void reserveSpace(int num)
public final int containerSize()
public final void put(int n, GPObject gpo)
public final GPObject get(int n)
public void clear()
protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
protected void save(DataOutputStream os) throws IOException
public void printOn(PrintStream os, GPVariables cfg)
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPProperties.html 100644 5763 134 13041 6506556644 17736 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----java.util.Dictionary | +----java.util.Hashtable | +----java.util.Properties | +----gpjpp.GPProperties
public GPProperties()
public GPProperties(Properties defaults)
public String getProperty(String key)
public synchronized void load(InputStream in) throws IOException
public void show()
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPInteger.html 100644 5763 134 2033 6506556644 17156 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPInteger
This class is not public and can therefore cannot be used outside this package.
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPGene.html 100644 5763 134 70510 6506556645 16465 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPContainer | +----gpjpp.GPGene
GPGene contains a reference to a GPNode object that describes the nature of the node. The arguments to a GPGene are stored in its container, of which GPGene is a subclass.
GPGene is abstract in the sense that it does not contain a method used to evaluate the fitness of a tree. It is not formally abstract in Java terminology because gpjpp does not know the data type embodied by the tree. A gene might represent and return a boolean, a real, an integer, a vector, nothing at all, or something completely different. Only at the GP level (a collection of tree branches forming a complete genetic program) does gpjpp enforce the requirement that the GP's fitness evaluate to a real number.
The user program typically must create a subclass of GPGene that defines a GPGene fitness function called by GP.evaluate(). The example programs show how to do so in several different situations.
protected static GPNode allNodes[]
protected GPNode node
public GPGene()
public GPGene(GPNode gpo)
public GPGene(GPGene gpo)
protected synchronized Object clone()
public byte isA()
public GPGene createChild(GPNode gpo)
public void testNull()
public boolean isFunction()
public boolean isTerminal()
public GPNode geneNode()
public String geneRep()
protected int countFunctions()
public int length()
public int depth()
protected int depth(int depthSoFar)
public synchronized int create(int creationType, int allowableDepth, int allowableLength, GPNodeSet ns)
public boolean equals(Object obj)
You might need to override this in cases where two terminal genes can have identical node types but still not be the same. This occurs for node types that represent random constants, for example.
protected boolean findNthNode(GPGeneReference ref, boolean findFunction)
public void chooseFunctionOrTerminalNode(GPGeneReference ref)
public boolean chooseFunctionNode(GPGeneReference ref)
public static synchronized void createNodeIndex(GPAdfNodeSet adfNs)
protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
protected void save(DataOutputStream os) throws IOException
public void printOn(PrintStream os, GPVariables cfg)
public void printTree(PrintStream os, GPVariables cfg)
public void drawOn(GPDrawing ods, String fname, String title, GPVariables cfg) throws IOException
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPVariables.html 100644 5763 134 124130 6506556645 17535 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPVariables
It is common to create a user subclass of GPVariables in order to add problem-specific configuration parameters. Examples include the size and filename for an ant trail, or the number of address lines that form the input to a boolean multiplexer. In other cases it may be useful to add non-configuration variables to a subclass of GPVariables. gpjpp passes a reference to the global variables to all methods that are likely to need them, including the evaluate() method of GP and all of the printOn() methods. Examples that add to GPVariables in this way include the ant "automaton" that responds to command functions and eats food, and the set of data and address inputs for the multiplexer problem.
public final static int GPVARIABLE
public final static int GPGROW
public final static int GPRAMPEDHALF
public final static int GPRAMPEDVARIABLE
public final static int GPRAMPEDGROW
protected final static String CreationStr[]
public final static int GPPROBABILISTICSELECTION
public final static int GPTOURNAMENTSELECTION
public final static int GPGREEDYSELECTION
protected final static String SelectionStr[]
public int PopulationSize
public int NumberOfGenerations
public int CreationType
public int MaximumDepthForCreation
public int MaximumDepthForCrossover
public int MaximumComplexity
public int SelectionType
public int TournamentSize
public double CrossoverProbability
public double CreationProbability
public double SwapMutationProbability
public double ShrinkMutationProbability
public double TerminationFitness
public int GoodRuns
public boolean UseADFs
public boolean TestDiversity
public boolean ComplexityAffectsFitness
public int CheckpointGens
public boolean DemeticGrouping
public int DemeSize
public double DemeticMigProbability
public boolean AddBestToNewPopulation
public boolean SteadyState
public boolean PrintDetails
public boolean PrintPopulation
public boolean PrintExpression
public boolean PrintTree
public int TreeFontSize
public GPVariables()
public GPVariables(GPVariables gpo)
protected synchronized Object clone()
public byte isA()
public boolean equals(Object obj)
protected int getInt(Properties props, String proStr, int def)
protected boolean getBoolean(Properties props, String proStr, boolean def)
protected double getDouble(Properties props, String proStr, double def)
protected int getEnumeratedType(Properties props, String EnumStr[], String proStr, int def)
protected int getCreationType(Properties props, String proStr, int def)
protected int getSelectionType(Properties props, String proStr, int def)
public synchronized void load(Properties props)
protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
protected void save(DataOutputStream os) throws IOException
public void printOn(PrintStream os, GPVariables cfg)
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPDrawing.html 100644 5763 134 32335 6506556645 17205 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----java.awt.Component | +----java.awt.Container | +----java.awt.Window | +----java.awt.Frame | +----gpjpp.GPDrawing
In my experience using Java console applications running under the Microsoft J++ 1.1 VM in Windows 95, creating a GPDrawing object causes the console window to temporarily lose focus until the GPDrawing.dispose() method (inherited from Frame) is called. See GPRun.showFinalGeneration for an example. Although the effect can be disconcerting, a mouse click returns focus to any window you desire without disturbing the drawing process. Numerous experiments have not uncovered a solution. The same effect does not occur under the Sun VM.
The GPGenePrint and LawnGP classes show examples of drawing images with GPDrawing. If you just want to create gif files of the genetic trees, set PrintTree to true in your configuration file and don't worry about the rest.
public static String fontName
public static int defFontSize
protected Canvas cvs
protected Font fnt
protected FontMetrics fm
protected Image img
protected Graphics gra
protected int fontSize
public int cw
public int ch
public int as
public GPDrawing()
public void setFontSize(int fontSize)
public void prepImage(int w, int h)
public void prepImage(int w, int h, int fontSize)
public int stringWidth(String s)
public Graphics getGra()
public void writeGif(String fname) throws IOException
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPRun.html 100644 5763 134 104002 6506556645 16365 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPRun
The user must override two methods of this class: createNodeSet(), which defines the branch structure and the node types used in each branch of each tree; and createPopulation(), which creates an instance of a user-defined subclass of GPPopulation.
It is common to override another method of this class: createVariables(), which creates an instance of GPVariables with the default configuration parameters for the run. Frequently you may need to add problem-specific configuration variables (the size of an ant trail, e.g.), which is best done by subclassing GPVariables and overriding createVariables() to create an instance of your own class.
GPRun then handles numerous details of managing a test run. These include:
1. Initializing the random number generator used by gpjpp.
2. Reading a configuration file so that most properties of the test run can be adjusted without recompiling. Also creates a default configuration file if the named one isn't found.
3. Creating output files for run statistics and detailed population reporting.
4. Registering all necessary classes with the stream manager.
5. Trapping all exceptions to report a detailed stack trace in case of error.
6. Loading a previous checkpoint stream if found, or creating an initial population of individuals.
7. Displaying status output to the console window and also printing configurable output to report files.
8. Streaming a checkpoint file after a configurable number of generations in case a long run needs to be interrupted.
9. Running a configurable number of generations and terminating the run when a configurable fitness target is reached.
10.Writing configurable reports on the best individual at the end of a run, including graphic images of its tree structure and possibly its fitness performance (such as the trail of an ant or a lawnmower).
11.Running multiple runs until a configurable number of good runs is found, and timing each run's performance.
GPRun is divided into a number of reasonably small routines so that additional aspects of its behavior can be customized by creating a subclass. Nevertheless, it is not suitable for writing applets or other graphics-intensive Java applications. These could be written by using the lower level classes of gpjpp directly, since these classes enforce no user interface of their own.
protected final static int RUNENDID
protected static int outBufSize
protected static int stmBufSize
protected String baseName
protected GPVariables cfg
protected GPAdfNodeSet adfNs
protected GPPrintStream dout
protected GPPrintStream sout
protected GPPopulation pop
protected GPPopulation newPop
protected int curGen
protected int curRun
protected int goodRuns
protected int cntGen
public GPRun(String baseName, boolean createDefaultIni)
protected abstract GPAdfNodeSet createNodeSet(GPVariables cfg)
protected abstract GPPopulation createPopulation(GPVariables cfg, GPAdfNodeSet adfNs)
protected void run()
protected GPVariables createVariables()
protected Random createRandomGenerator()
protected void readIni(String iniName, boolean createDefaultIni) throws IOException
protected GPPrintStream createOrAppend(String fname, boolean append) throws IOException
protected void echoPrint(String dispStr)
protected void showConfiguration()
protected void showRunNumber(int curRun, int goodRuns)
protected void showCreation(boolean preCreation)
protected char checkChar(boolean savedCheckpoint)
protected void showGeneration(boolean showLegend, int curGen, boolean savedCheckpoint)
protected void showFinalGeneration(int curGen, boolean goodRun) throws IOException
baseName+curRun+branchName+".gif"
where branchName is "RPB" for the result-producing branch
and "ADFn" for the ADF branches, or "" for single-branch trees.For some Java implementations, Microsoft J++ in particular, the console window loses focus temporarily while the off-screen drawing window is active. Focus is returned to the previous window once drawing is complete. The same behavior is not seen for the Sun virtual machine running under Windows 95.
protected void showTiming(double elapsedSecs, double secsPerGen)
protected void registerAllClasses() throws IllegalAccessException
protected String getCheckpointName()
protected String getStatisticsName()
protected String getDetailName()
protected File getCheckpointFile()
protected boolean loadCheckpoint() throws FileNotFoundException, IOException
After the checkpoint is loaded, the run picks up exactly where it left off when the checkpoint was stored. The only difference is that the random number sequence used in the new run won't match any results obtained after the original checkpoint was stored. (The random number seed is not stored on the stream.)
protected boolean saveCheckpoint() throws IOException
protected void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
protected void save(DataOutputStream os) throws IOException
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPPrintStream.html 100644 5763 134 12022 6506556645 20051 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----java.io.OutputStream | +----java.io.FilterOutputStream | +----java.io.PrintStream | +----gpjpp.GPPrintStream
protected String lineSeparator
public GPPrintStream(OutputStream out)
public GPPrintStream(OutputStream out, boolean autoflush)
public void writeEol()
public void write(int b)
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPAdfNodeSet.html 100644 5763 134 16117 6506556645 17566 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPContainer | +----gpjpp.GPAdfNodeSet
GPAdfNodeSet holds a GPNodeSet for the result-producing branch of the tree and also one for each ADF.
Because this class has no data fields of its own, its load and save methods are inherited unchanged from GPContainer.
public GPAdfNodeSet()
public GPAdfNodeSet(int numOfTrees)
The supplied example programs show how to create GPAdfNodeSets with and without ADFs.
public GPAdfNodeSet(GPAdfNodeSet gpo)
protected synchronized Object clone()
public byte isA()
public boolean equals(Object obj)
public void printOn(PrintStream os, GPVariables cfg)
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/AllNames.html 100644 5763 134 272324 6506556646 15765 0 ustar evs faculty
All Packages Class Hierarchy
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPGeneReference
This class is for internal use.
public GPContainer container
public int index
public int count
public GPGeneReference()
public GPGeneReference(GPContainer container, int index)
public GPGeneReference(GPGeneReference ref)
public void assignRef(GPGeneReference ref)
public void assignContainer(GPContainer container, int index)
public GPGene getGene()
public void putGene(GPGene g)
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPRandom.html 100644 5763 134 10557 6506556646 17035 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPRandom
protected static Random r
public static void setGenerator(Random ran)
public static int nextInt(int limit)
public static boolean flip(double percent)
public static double nextDouble()
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPObject.html 100644 5763 134 47730 6506556646 17026 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject
protected final static byte NULLID
protected final static byte OBJECTID
protected final static byte CONTAINERID
protected final static byte NODEID
protected final static byte NODESETID
protected final static byte ADFNODESETID
protected final static byte VARIABLESID
protected final static byte GENEID
protected final static byte GPID
protected final static byte POPULATIONID
protected final static byte GENEPRINTID
public final static byte USERGENEID
public final static byte USERGPID
public final static byte USERPOPULATIONID
public final static byte USERVARIABLESID
protected GPObject()
protected synchronized abstract Object clone()
public abstract byte isA()
protected synchronized abstract void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
protected abstract void save(DataOutputStream os) throws IOException
public abstract void printOn(PrintStream os, GPVariables cfg)
protected static int findRegisteredClass(byte id)
public static GPObject createRegisteredClassObject(byte id) throws InstantiationException, IllegalAccessException
protected static void registerClass(byte id, Class c)
public static void registerClass(GPObject gpo) throws IllegalAccessException
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/gpjpp.GPPopulation.html 100644 5763 134 161374 6506556646 17773 0 ustar evs faculty
All Packages Class Hierarchy This Package Previous Next Index
java.lang.Object | +----gpjpp.GPObject | +----gpjpp.GPContainer | +----gpjpp.GPPopulation
GPPopulation includes references to the GPVariables configuration of the run and the GPAdfNodeSet set of node types. These references are passed as parameters to lower level classes when needed.
GPPopulation has several public data fields that can be used by the calling program to obtain the status of the population. These include bestOfPopulation (the index of the individual with the best fitness), worstOfPopulation, attemptedDupCount (the number of duplicate individuals detected but rejected when creating the initial population), and others.
Although GPPopulation represents a single population of individuals, it is designed to work with either a single population (steady state evolution) or two populations (generational evolution). This behavior is implemented in the generate() method.
The user must always create a subclass of GPPopulation for use in solving a particular problem. This subclass must override the createGP() method, which creates a GP of user type. That GP subclass must in turn override the evaluate() method to compute fitness for the target problem.
Otherwise, the typical details of using GPPopulation are encapsulated in the GPRun class.
protected static int minTreeDepth
protected double sumAdjFitness
protected double cutoffAdjFitness
protected double sumG1AdjFitness
protected double sumG2AdjFitness
protected double sumFitness
protected GPVariables cfg
protected GPAdfNodeSet adfNs
protected double avgFitness
protected double avgLength
protected double avgDepth
public double bestFitness
public double worstFitness
public int bestOfPopulation
(GP)pop.get(bestOfPopulation)
.
public int worstOfPopulation
(GP)pop.get(worstOfPopulation)
.
public int longestLength
protected Hashtable uniqueGPs
public int dupCount
public int attemptedDupCount
public int attemptedComplexCount
public GPPopulation()
public GPPopulation(GPVariables cfg, GPAdfNodeSet adfNs)
public GPPopulation(GPPopulation gpo)
protected synchronized Object clone()
public byte isA()
public GP createGP(int numOfTrees)
protected int getUniqueGPsSize()
protected void clearUniqueGPs()
protected void updateUniqueGPs(GP gp)
protected void buildUniqueGPs()
protected boolean checkForDiversity(GP gp)
public void create()
The depth of each GP is guaranteed to fall in the range GPPopulation.minTreeDepth (2) to cfg.MaximumDepthForCreation (6 by default).
create() calls GP.create() to create each individual in the population.
create() uses one of several tree-building strategies depending on the value of the configuration variable CreationType. If this variable equals GPRAMPEDHALF (the default), alternating individuals are created using GPGROW (function nodes to maximum depth) and GPVARIABLE (nodes chosen with a 50:50 probability of being a function or a terminal). With GPRAMPEDHALF, the depth of successive individuals is ramped from minTreeDepth to MaximumDepthForCreation and back again.
If CreationType equals GPRAMPEDVARIABLE, all individuals are created using the GPVARIABLE strategy and the depth of successive individuals is ramped from minTreeDepth to MaximumDepthForCreation.
If CreationType equals GPRAMPEDGROW, all individuals are created using the GPGROW strategy and the depth of successive individuals is ramped.
If CreationType equals GPGROW, all individuals are created using the GPGROW strategy with depth MaximumDepthForCreation.
If CreationType equals GPVARIABLE, all individuals are created using the GPVARIABLE strategy with depth MaximumDepthForCreation.
If a unique individual is not found in 50/4 tries, the tree depth is incremented for each try thereafter, up to a maximum of MaximumDepthForCreation.
If an individual of acceptable complexity is not found in 50/4 tries, the tree depth is decremented for each try thereafter, down to a minimum of minTreeDepth.
If no acceptable individual is found after 50 tries, a RuntimeException is thrown.
After each individual is created, its fitness is calculated by calling GP.evaluate(). After all individuals are created, calculateStatistics() is called.
protected void tournamentSelection(int selected[], int numToSelect, boolean selectWorst, GPPopulationRange range)
protected void sumFitnessRange(GPPopulationRange range)
protected void probabilisticSelection(int selected[], int numToSelect, boolean selectWorst, GPPopulationRange range)
protected double calcGroupIFraction(int size)
protected void calcCutoffFitness(GPPopulationRange range)
The routine stores values in the fields cutoffAdjFitness, sumG1AdjFitness, and sumG2AdjFitness. It assumes that sumAdjFitness has already been calculated by calling sumFitnessRange().
protected void greedySelection(int selected[], int numToSelect, boolean selectWorst, GPPopulationRange range)
protected void selectIndices(int selected[], int numToSelect, boolean selectWorst, GPPopulationRange range)
protected synchronized GPContainer select(int numToSelect, GPPopulationRange range)
protected GPContainer selectParents(GPPopulationRange range)
protected synchronized GPContainer evolve(GPPopulationRange range)
Brand-new individuals are created using the GPVARIABLE strategy with depth ramped between calls to this method.
Crossover is considered first, then (if crossover did not occur) creation of a new individual, then (if creation did not occur) reproduction of an existing individual.
Mutation does not occur in this method but rather as an independent step in generate(). Thus an individual passed on via reproduction could still undergo mutation.
protected synchronized void addBest(GPPopulation newPop)
public void generate(GPPopulation newPop)
If DemeticGrouping is true, the overall population is divided into "demes" of size DemeSize and each of these is treated individually as a subpopulation.
If AddBestToNewPopulation is true and SteadyState is false, the best individual in this population is automatically added to the new population at its same index location.
After each new individual or pair of individuals is generated by evolve(), generate() calls mutate() to possibly modify the new individuals further.
If TestDiversity is true, the diversity table is updated while the new population is built to keep track of duplicates. No duplicates are rejected within generate(), however.
After the new population is generated, demeticMigration() is called if this feature is activated. Population statistics are always calculated for the new generation.
protected synchronized void demeticMigration()
protected void calculateStatistics()
protected static String formatInt(int i, int width)
protected static String overflow(int width)
public static String formatDouble(double d, int width, int places)
public static String trimFormatDouble(double d, int width, int places)
public void printStatisticsLegend(PrintStream sout)
public void printStatistics(int generation, char chk, PrintStream sout)
protected String formatParentage(int len, int index, int tree, int cut)
public void printIndividual(GP current, int num, boolean showExpression, boolean showTree, PrintStream dout)
If showExpression is true, the GP's printOn() method is called to print the s-expression. If showTree is true, the GP's printTree() method is called to print the expression in pseudo-graphic text format.
public void printDetails(int generation, boolean showAll, boolean showBest, boolean showWorst, boolean showExpression, boolean showTree, PrintStream dout)
protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException
public void printOn(PrintStream os, GPVariables cfg)
All Packages Class Hierarchy This Package Previous Next IndexOthelloProj/GP/docs/tree.html 100644 5763 134 32166 6506556647 15207 0 ustar evs faculty
All Packages Index
* * GPContainer provides a convenient location to centralize the * streaming operations for its subclasses.
* * GPContainer is generally not instantiated directly.
* * Several of the GPContainer methods are marked "final" so that an * optimizing compiler can inline these simple methods, causing a * substantial improvement to gpjpp performance. Except for this * desire for optimization, these methods don't need to be final.
* * No explicit array index checking or memory allocation checking * is required because Java performs these checks automatically * and throws exceptions if errors are detected. * * @version 1.0 */ public class GPContainer extends GPObject { /** * An array that is allocated once during the lifetime of the * container. It doesn't need to be resized. Use the get() and * put() methods to access elements of the array. * * @see gpjpp.GPContainer#get * @see gpjpp.GPContainer#put */ protected GPObject[] container; //array of objects /** * Public null constructor used during stream loading only. */ public GPContainer() { reserveSpace(0); } /** * The constructor called by many GPContainer subclasses to * allocate a container of specified size. * * @param numObjects the number of references the container can hold. */ public GPContainer(int numObjects) { reserveSpace(numObjects); } /** * Constructor called to clone a deep copy of another container. * This is used during the genetic evolution process to make * unique copies of selected individuals. * * @param gpc the container to copy. */ public GPContainer(GPContainer gpc) { if (gpc == null) return; reserveSpace(gpc.containerSize()); //make a copy of all container objects of gpc for (int i = 0; i < containerSize(); i++) { GPObject current = gpc.container[i]; if (current == null) put(i, null); else put(i, (GPObject)current.clone()); } } /** * Implements the Cloneable interface. * This clones any GPContainer subclass that doesn't have its * own data fields. * * @return the cloned object. */ protected synchronized Object clone() { return new GPContainer(this); } /** * Returns a code identifying the class in a stream file. * * @return the ID code CONTAINERID. */ public byte isA() { return CONTAINERID; } /** * Reserves space for the specified number of object references. * Note that Java allows allocating a zero-size array and that * the array is filled with nulls after allocation. * * @param num the number of places to reserve */ public final void reserveSpace(int num) { container = new GPObject[num]; } /** * Returns the number of elements the container can hold. * * @return the container capacity. */ public final int containerSize() { return container.length; } /** * Stores an object reference at the specified location in the * container. * * @param n the container location. Must be in the range from * 0 to containerSize()-1. * @param gpo the object reference to store. null is ok. */ public final void put(int n, GPObject gpo) { container[n] = gpo; } /** * Returns the object reference from the specified location in the * container. * * @param n the container location. Must be in the range from * 0 to containerSize()-1. * @return the object reference at that location. May be null. */ public final GPObject get(int n) { return container[n]; } /** * Sets all container elements to null to ensure that no * references remain to objects currently held by this container. * This was used during testing of garbage collection but is not * normally called by gpjpp. */ public void clear() { for (int i = 0; i < containerSize(); i++) put(i, null); } /** * Loads a GPContainer from the specified stream. Calls * createRegisteredClassObject to construct the objects * contained within the container. * * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. * @exception java.io.IOException * if an error occurs while reading the stream. * @exception java.lang.RuntimeException * if the class ID code found next in the stream * does not match the isA() code for the calling * object. */ protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException { //confirm that ID indicates right kind of container if (is.readByte() != isA()) throw new RuntimeException("Invalid stream"); //read container size from stream and reserve space if (this instanceof GPPopulation) reserveSpace(is.readInt()); else reserveSpace(is.readByte()); //load all members of the container for (int i = 0; i < containerSize(); i++) { //test if element was a null pointer or an object byte id = is.readByte(); if (id != NULLID) { //create that element depending on the ID that was saved container[i] = createRegisteredClassObject(id); //let the object load itself container[i].load(is); } } } /** * Saves a GPContainer to the specified stream. It saves the * container by recursively calling the save method of each * object contained within the container. Any null elements * in the container are represented by the NULLID constant alone. * * @param os a formatted output stream. * * @exception java.lang.RuntimeException * if a container other than * GPPopulation * has more than 255 elements. This allows save() to * store most container sizes in a single byte, leading * to a reduction in overall stream size of almost 4x. */ protected void save(DataOutputStream os) throws IOException { //save the container ID and size os.writeByte(isA()); if (this instanceof GPPopulation) os.writeInt(containerSize()); else { //max 255 elements in all containers but population if (containerSize() > 0xFF) throw new RuntimeException( "Streamed containers (except populations) are limited to 255 elements"); os.writeByte(containerSize()); } //save all members of the container for (int i = 0; i < containerSize(); i++) { GPObject current = container[i]; if (current == null) //no element os.writeByte(NULLID); else { //save ID and element itself os.writeByte(current.isA()); current.save(os); } } } /** * Writes a GPContainer in text format to a PrintStream. * Every supplied GPContainer subclass overrides this method * to write the container in a non-generic format. */ public void printOn(PrintStream os, GPVariables cfg) { os.println("Container has "+containerSize()+" elements:"); //print all members of the container for (int i = 0; i < containerSize(); i++) if (container[i] == null) os.print("(null) "); else container[i].printOn(os, cfg); } } OthelloProj/GP/gpjpp/GPObject.java 100644 5763 134 27512 6506556653 16046 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; /** * Abstract class used to define cloning and streaming capabilities. * All gpjpp classes that can be streamed are subclasses of GPObject. * * @version 1.0 */ public abstract class GPObject implements Cloneable { /** * This do-nothing constructor gets called implicitly by * subclasses of GPObject. */ protected GPObject() {} /** * Implements the Cloneable interface. * GPGene and GP classes are cloned during reproduction * and crossover. * * @return the cloned object. */ abstract protected synchronized Object clone(); /** * Returns a code identifying the class in a stream file. * Every class in a streamed gpjpp program must override * isA() and return a unique byte. Predefined ID values are * provided for the built-in gpjpp classes and the classes * a user is expected to provide. * * @return the unique ID code. * @see gpjpp.GPObject#OBJECTID */ abstract public byte isA(); /** * Loads a GPObject subclass from the specified stream. The * object calling this method should have been previously * constructed using its null constructor. * * @param is a formatted input stream. * * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. * @exception java.io.IOException * if an error occurs while reading the stream. */ abstract protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException; /** * Saves a GPObject subclass to the specified stream. * * @param os a formatted output stream. * * @exception java.io.IOException * if an error occurs while writing the stream. */ abstract protected void save(DataOutputStream os) throws IOException; /** * Writes a GPObject subclass in text format to a PrintStream. * Every gpjpp subclass overrides this method to print a text * representation of the class' current state. * * Because printOn writes to a PrintStream, it does not generate * IOExceptions. PrintStream traps exceptions, which can be * checked via its checkError() method. * * @param os a PrintStream. * @param cfg the set of gpjpp configuration variables, * sometimes used to control the output. */ abstract public void printOn(PrintStream os, GPVariables cfg); //ID codes used for all classes /** * An ID code used to identify null object references in * gpjpp streams. */ final protected static byte NULLID = 0; /** * An ID code used to identify GPObject references in * gpjpp streams. This code is not written to streams * under normal circumstances, since GPObject is an * abstract class. */ final protected static byte OBJECTID = 1; /** * An ID code used to identify * GPContainer * references in gpjpp streams. This code is not written to streams * under normal circumstances, since GPContainer subclasses * provide their own ID codes. */ final protected static byte CONTAINERID = 2; /** * An ID code used to identify * GPNode references in * gpjpp streams. A GPNode defines the identifying code, * number of arguments, and string representation for * every function and terminal in a genetic program. */ final protected static byte NODEID = 3; /** * An ID code used to identify * GPNodeSet references in * gpjpp streams. A GPNodeSet contains all the GPNode * values for a particular branch (main result-producing * or ADF) of a genetic program. */ final protected static byte NODESETID = 4; /** * An ID code used to identify * GPAdfNodeSet * references in gpjpp streams. A GPAdfNodeSet contains all the * GPNodeSet containers for a genetic program. */ final protected static byte ADFNODESETID = 5; /** * An ID code used to identify * GPVariables * references in gpjpp streams. A GPVariables contains all the * settings that specify the behavior of a genetic programming test. * A user subclass of GPVariables is often, but not always, * defined to specify additional problem-specific variables. */ final protected static byte VARIABLESID = 6; /** * An ID code used to identify * GPGene references in * gpjpp streams. A GPGene is one node of a genetic program * parse tree and includes a reference to a * GPNode and * a container holding references to the arguments of the * node, if any. This ID code may appear hundreds of thousands * of times in a stream. A user subclass of GPGene is almost * always defined to implement a problem-specific fitness * calculation for each gene tree. */ final protected static byte GENEID = 7; /** * An ID code used to identify * GP references in * gpjpp streams. GP is a container holding references to * a GPGene for each branch * of the genetic program, including one for the main * result-producing branch and zero or more * for the ADFs of the program. There is a GP for each member * of the population. A user subclass of GP is always defined * to implement a problem-specific fitness calculation for each * genetic program. */ final protected static byte GPID = 8; /** * An ID code used to identify * GPPopulation * references in gpjpp streams. GPPopulation is a container holding * references to a GP for each individual in the population. * A user subclass of GPPopulation is always defined to create GP * subclass instances when the program needs them. */ final protected static byte POPULATIONID = 9; /** * An ID code used to identify * GPGenePrint * references in gpjpp streams. This code is not written to streams * under normal circumstances, and the GPGenePrint load and save * methods do nothing. */ final protected static byte GENEPRINTID = 10; //for registering user subclasses /** * An ID code normally used to identify the user subclass of * GPGene. */ final public static byte USERGENEID = 20; /** * An ID code normally used to identify the user subclass of * GP. */ final public static byte USERGPID = 21; /** * An ID code normally used to identify the user subclass of * GPPopulation. */ final public static byte USERPOPULATIONID = 22; /** * An ID code normally used to identify the user subclass of * GPVariables. For any stream classes besides those * discussed here, use ID codes larger than USERVARIABLESID. */ final public static byte USERVARIABLESID = 23; //arrays used to map ID codes to object classes in streams final private static int MAXIMUMCLASSNUM = 20; private static byte[] ids = new byte[MAXIMUMCLASSNUM]; private static Class[] loadSaveClasses = new Class[MAXIMUMCLASSNUM]; private static int registered = 0; /** * Returns index of existing registered class, -1 if not found. * For internal use. */ protected static int findRegisteredClass(byte id) { for (int i = 0; i < registered; i++) if (ids[i] == id) return i; return -1; } /** * Creates an object of specified ID and returns it. * This method is called by appropriate load() methods in the * gpjpp class hierarchy. * * @param id the registered ID code for the class type to create. * @return an object of the specified type, created via its * null constructor. Returns null if the ID code does * not specify a registered type. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. */ public static GPObject createRegisteredClassObject(byte id) throws InstantiationException, IllegalAccessException { int index = findRegisteredClass(id); if (index < 0) return null; else return (GPObject)loadSaveClasses[index].newInstance(); } /** * Registers a single class. For internal use. */ protected static void registerClass(byte id, Class c) { if (findRegisteredClass(id) < 0) { //class not already registered if (registered == MAXIMUMCLASSNUM) //array full throw new ArrayStoreException(); //save ID and class of object ids[registered] = id; loadSaveClasses[registered++] = c; } } /** * Registers the class of the specified object and * all of its non-abstract superclasses up to but * not including GPObject. * * @param gpo an instance of the class to register * @exception java.lang.IllegalAccessException * if a superclass of the specified class or * its null constructor is not public. */ public static void registerClass(GPObject gpo) throws IllegalAccessException { byte id = gpo.isA(); Class c = gpo.getClass(); do { registerClass(id, c); c = c.getSuperclass(); if (c == null) break; Object tmp; try { tmp = c.newInstance(); } catch (InstantiationException e) { break; } id = ((GPObject)tmp).isA(); } while (true); } } OthelloProj/GP/gpjpp/GPGene.java 100644 5763 134 56505 6506556653 15522 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; /** * GP trees are composed of GPGene objects, which represent the * function or terminal of each element of an s-expression. Each * tree is rooted by a GPGene object, which in turn contains GPGene * objects for each of its function arguments.
* * GPGene contains a reference to a * GPNode object that describes the nature of the node. The * arguments to a GPGene are stored in its container, of which GPGene * is a subclass.
* * GPGene is abstract in the sense that it does not contain a method * used to evaluate the fitness of a tree. It is not formally abstract * in Java terminology because gpjpp does not know the data type * embodied by the tree. A gene might represent and return a boolean, * a real, an integer, a vector, nothing at all, or something * completely different. Only at the GP * level (a collection of tree branches forming a complete genetic * program) does gpjpp enforce the requirement that the GP's fitness * evaluate to a real number.
* * The user program typically must create a subclass of GPGene that * defines a GPGene fitness function called by GP.evaluate(). The * example programs show how to do so in several different situations. * * @version 1.0 */ public class GPGene extends GPContainer { /** * An array of all node types in all branches used temporarily * while loading the array from a stream. * * @see gpjpp.GPGene#createNodeIndex */ protected static GPNode[] allNodes; /** * A reference to the node type for this gene. */ protected GPNode node; /** * Public null constructor used during stream loading only. */ public GPGene() { } /** * Constructor used when trees are first created with random * node types. * * @param gpo a node type that is an element of the current * branch's node set. */ public GPGene(GPNode gpo) { super(gpo.arguments()); node = gpo; } /** * A constructor that is called to clone a GPGene. Used * whenever a tree is selected for reproduction or crossover. */ public GPGene(GPGene gpo) { super(gpo); node = gpo.node; } /** * Implements the Cloneable interface. * This (or its user subclass) is called during reproduction. * * @return the cloned object. */ protected synchronized Object clone() { return new GPGene(this); } /** * Returns a code identifying the class in a stream file. * * @return the ID code GENEID. */ public byte isA() { return GENEID; } /** * Creates a child gene while new trees are being built. The * user must generally override this in a subclass to create * genes of user type. See the example programs. * * @param gpo a node type that is an element of the current * branch's node set. * @return the newly created gene with an empty container. */ public GPGene createChild(GPNode gpo) { return new GPGene(gpo); } /** * A debugging/testing method to ensure that no null node or gene * references are found in this gene or any of its children. * * @exception java.lang.RuntimeException * if a null gene or node reference is found. */ public void testNull() { if (node == null) throw new RuntimeException("Null node found in gene"); for (int i = 0; i < containerSize(); i++) { GPGene current = (GPGene)get(i); if (current == null) throw new RuntimeException("Null gene found in gene tree"); //test children of the gene current.testNull(); } } /** * Returns true if this gene represents a function. */ public boolean isFunction() { return (containerSize() > 0); } /** * Returns true if this gene represents a terminal. */ public boolean isTerminal() { return (containerSize() == 0); } /** * Returns the node reference of this gene. */ public GPNode geneNode() { return node; } /** * Returns the string representation of this gene as given * by its node type. This method can be overridden in a user * subclass of GPGene if the string representation should vary * depending on the data value of each gene. See the Lawn * program for an example. */ public String geneRep() { return node.rep(); } /** * Returns the total number of function genes included by * this gene and all of its children. If this gene is a terminal, * countFunctions returns 0. Otherwise it returns at least 1 * and recursively traces all of its children. Used internally * during shrink mutation. */ protected int countFunctions() { if (isFunction()) { int count = 1; //loop through the children for (int i = 0; i < containerSize(); i++) count += ((GPGene)get(i)).countFunctions(); return count; } else return 0; } /** * Returns the number of genes attached to this one, including * itself. This is the complexity or length of the branch. */ public int length() { int lengthSoFar = 1; //add length of children for (int i = 0; i < containerSize(); i++) lengthSoFar += ((GPGene)get(i)).length(); return lengthSoFar; } /** * Returns the largest depth of the tree attached to this gene. * If this gene is a terminal, the depth is 1. */ public int depth() { return depth(1); } /** * Called internally by depth() to compute the tree depth. */ protected int depth(int depthSoFar) { int maxDepth = depthSoFar; for (int i = 0; i < containerSize(); i++) { int d = ((GPGene)get(i)).depth(depthSoFar+1); if (d > maxDepth) maxDepth = d; } return maxDepth; } /** * Creates the arguments to this gene and recursively creates * children according to the limits and methods specified. The * gene for which this method is called should have been created * by calling the createGene() * method of GP, which allocates an argument container of * appropriate size and assigns the node field but doesn't fill * in the children. create() is called by * GP.create(). * * @param creationType the method used to create the tree, either * GPGROW (use * function nodes to fill the tree to allowable depth) or * GPVARIABLE * (choose function and terminal nodes with 50:50 probability). * @param allowableDepth the maximum allowable depth of the tree * starting from this level. If the allowable depth is 1, * the children are always chosen to be terminals. * @param allowableLength the maximum allowable number of nodes * in the tree starting at this level. Since create() cannot * predict how many nodes will be added recursively it * simply stops adding nodes if it exceeds allowableLength. * A higher level routine in GPPopulation rejects the * returned tree if the GP complexity exceeds a global limit. * @param ns the node set used to select functions and terminals * for this branch of the GP tree. * * @return the total number of nodes in the created tree. If this * value exceeds allowableLength, the tree will be rejected. * create() ensures that it doesn't waste much time creating * extra nodes. */ public synchronized int create(int creationType, int allowableDepth, int allowableLength, GPNodeSet ns) { int lengthSoFar = 1; for (int i = 0; i < containerSize(); i++) { //decide whether to create a function or terminal for this argument boolean chooseTerm; if (allowableDepth <= 1) //no more depth, must use terminal chooseTerm = true; else if (creationType == GPVariables.GPGROW) //use functions to allowableDepth chooseTerm = false; else //50:50 chance of choosing a function or a terminal chooseTerm = GPRandom.flip(50.0); GPNode newNode; if (chooseTerm) newNode = ns.chooseTerminal(); else newNode = ns.chooseFunction(); //create a new gene of chosen type and add it GPGene g = createChild(newNode); put(i, g); //if function node, call recursively to allowed depth if (chooseTerm) lengthSoFar++; else lengthSoFar += g.create(creationType, allowableDepth-1, allowableLength-lengthSoFar, ns); //stop early if complexity limit exceeded if (lengthSoFar > allowableLength) break; } return lengthSoFar; } /** * Determines whether this GPGene equals another object. It returns * true if obj is not null, is an instance of a GPGene (or a * descendant), and has the same structure and node values as this * gene. This function is called when a GPPopulation is testing the * diversity of the population. equals() is called only after a * hashCode() function * determines that two GPs are at least quite similar.
* * You might need to override this in cases where two terminal * genes can have identical node types but still not be the same. * This occurs for node types that represent random constants, for * example. * * @param obj any Java object reference, including null. * @return true if this and obj are equivalent. */ public boolean equals(Object obj) { if ((obj == null) || !(obj instanceof GPGene)) return false; GPGene g = (GPGene)obj; //compare node type reference values if (node != g.node) return false; //compare the number of children if (containerSize() != g.containerSize()) return false; //compare all children. for (int i = 0; i < containerSize(); i++) { GPGene g1 = (GPGene)get(i); GPGene g2 = (GPGene)g.get(i); if (g1 != null) { //recursively test subtree if (!g1.equals(g2)) return false; } else if (g2 != null) return false; } return true; } /** * Returns true if a gene of specified position and type can be * found within this gene. Called within * * chooseFunctionOrTerminalNode and * * chooseFunctionNode of this same class, which are used to * select appropriate genes for crossover and mutation. * * @param ref on entry specifies the container that holds this * gene, the index of this gene within that container, * and the count of genes to scan. On exit returns * the container that holds the found gene and the * index of that gene within the container. * @param findFunction true if only function nodes are to be * counted, false if function and terminal nodes * are acceptable. * * @return true if an acceptable node is found; false if * there are fewer nodes than specified. */ protected boolean findNthNode( GPGeneReference ref, boolean findFunction) { //return ref when count nodes of proper type have been visited if (!findFunction || (containerSize() > 0)) if (--ref.count <= 0) return true; //otherwise scan children of this node for (int i = 0; i < containerSize(); i++) { ref.assignContainer(this, i); if (((GPGene)get(i)).findNthNode(ref, findFunction)) return true; } //proper node not found return false; } /** * Attempts to find a random function node within this gene, not * considering this gene itself. If 10 random attempts don't find * a function, it returns a terminal as a last resort. Used for * crossover and * swap mutation * by the GP class. * * @param ref on entry specifies the container that holds this * gene and the index of this gene within that * container. On exit returns the container that * holds the found gene, the index of that gene * within the container, and the number of genes * counted to reach the found one. * * @exception RuntimeException * if findNthNode can't find a node that should * rightfully exist in the tree. */ public void chooseFunctionOrTerminalNode(GPGeneReference ref) { //calculate the length of the subtree int totalLength = length(); //loop trying to return a function GPContainer saveContainer = ref.container; int saveIndex = ref.index; int maxTries = 10; for (int i = 0; i < (totalLength < maxTries? totalLength : maxTries); i++) { //restore starting ref ref.assignContainer(saveContainer, saveIndex); //count a random distance into subtree int saveCount = 1+GPRandom.nextInt(totalLength); ref.count = saveCount; if (!findNthNode(ref, false)) throw new RuntimeException("Couldn't find expected tree node"); //return count in gene reference ref.count = saveCount; if (ref.getGene().isFunction()) return; } //otherwise return a terminal } /** * Finds a random function node within this gene, not * considering this gene itself. If no such function exists, * the function returns false. Used for * shrink mutation * by the GP class. * * @param ref on entry specifies the container that holds this * gene and the index of this gene within that * container. On exit returns the container that * holds the found gene, the index of that gene * within the container, and the number of genes * counted to reach the found one. * @return true if any function node can be found, else false. */ public boolean chooseFunctionNode(GPGeneReference ref) { //choose a random number in the range of available functions //exclude this gene int totalFunctions = countFunctions(); if (totalFunctions > 0) { int saveCount = 1+GPRandom.nextInt(totalFunctions); ref.count = saveCount; if (findNthNode(ref, true)) { //return count for mutation tracking ref.count = saveCount; return true; } else return false; } else return false; } /** * Must be called by the stream manager before saving and * loading genes. The routine initializes the * allNodes static * array and also stores within each GPNode its allNodes index. * This byte-sized index is stored on the stream * to represent the type of each gene. When the stream is loaded * again, the index is converted back to a node reference. * * @exception java.lang.RuntimeException * if the total number of node types exceeds 255. */ public static synchronized void createNodeIndex(GPAdfNodeSet adfNs) { //count the number of global nodes int count = 0; for (int i = 0; i < adfNs.containerSize(); i++) { GPNodeSet ns = (GPNodeSet)adfNs.get(i); if (ns != null) { for (int j = 0; j < ns.containerSize(); j++) { GPNode n = (GPNode)ns.get(j); if (n != null) count++; } } } if (count > 255) throw new RuntimeException("At most 255 node types can be streamed"); //allocate and initialize the allNodes array allNodes = new GPNode[count]; count = 0; for (int i = 0; i < adfNs.containerSize(); i++) { GPNodeSet ns = (GPNodeSet)adfNs.get(i); if (ns != null) { for (int j = 0; j < ns.containerSize(); j++) { GPNode n = (GPNode)ns.get(j); if (n != null) { allNodes[count] = n; //store the index in the node itself n.setIndex((byte)count); count++; } } } } } /** * Loads a GPGene from the specified stream. Reads the * node index from the stream and converts it to a GPNode * reference. Then loads the container of child genes.
* * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. * @exception java.io.IOException * if an error occurs while reading the stream. * * @see gpjpp.GPGene#createNodeIndex */ protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException { //allNodes must be initialized // by calling createNodeIndex before getting to this point node = allNodes[is.readByte()]; //load container (children) super.load(is); } /** * Saves a GPGene to the specified stream. Writes the * node index value to the stream and then stores the container. * * @exception java.io.IOException * if an error occurs while writing the stream. * * @see gpjpp.GPGene#createNodeIndex */ protected void save(DataOutputStream os) throws IOException { //nodeIndex field of GPNode must be initialized // by calling createNodeIndex before getting to this point os.writeByte(node.getIndex()); //save container (children) super.save(os); } /** * Writes a GPGene in text format to a PrintStream. * Each node is printed as its representation string followed * by its children, if any, in recursive depth-first order. * Parentheses are used to surround the arguments to each * function. The entire expression is written on a single * text line. */ public void printOn(PrintStream os, GPVariables cfg) { if (isFunction()) os.print("("); os.print(geneRep()); //print all children for (int i = 0; i < containerSize(); i++) { os.print(" "); ((GPGene)get(i)).printOn(os, cfg); } if (isFunction()) os.print(")"); } /** * Writes a GPGene in text tree format to a PrintStream. * The GPGenePrint class * is used to format the tree in a pseudo-graphic format. Each node * is printed as its representation string and is connected to its * children on a lower text row using line drawing characters. * * @param os a PrintStream. * @param cfg the set of gpjpp configuration variables, * sometimes used to control the output. */ public void printTree(PrintStream os, GPVariables cfg) { (new GPGenePrint(this)).printOn(os, cfg); } /** * Writes a GPGene in graphic gif file format. The * GPGenePrint * class is used to format the tree, which is drawn onto the * AWT-based offscreen drawing surface represented by GPDrawing. * This offscreen drawing is then encoded into the gif format and * stored in the file named by fname. * * @param ods an instantiated drawing surface. GPDrawing is * a subclass of java.awt.Frame containing a * single Canvas component whose image is dynamically * sized to hold the tree. * @param fname the name of the file to hold the gif image. * This name should include the .gif extension. * @param title a string that is drawn on the first line of the * image to title it. Can be null or empty. * @param cfg configuration parameters for the genetic * run. The * TreeFontSize field is used to determine the font * size for text in the drawing. * * @exception java.io.IOException * if an error occurs while writing the image file. */ public void drawOn(GPDrawing ods, String fname, String title, GPVariables cfg) throws IOException { (new GPGenePrint(this)).drawOn(ods, fname, title, cfg); } } OthelloProj/GP/gpjpp/GPNode.java 100644 5763 134 20273 6506556653 15522 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; /** * Stores information about one function or terminal type in * a particular genetic programming problem. GPNode objects are * stored within the container of a * GPNodeSet object, * representing all the node types allowed within one branch * of a genetic program. * * @version 1.0 */ public class GPNode extends GPObject { /** * Indicates a node's purpose to a user fitness evaluation method. * The nodeValue is often the integer value of a character such * as '+' or '-', or is assigned a symbolic constant such as * FROG or MOW. */ protected int nodeValue; /** * The number of arguments used by the node, 0 if the node is * a terminal instead of a function. numOfArgs must be in the * range from 0 to 255 when streaming is used, since the * number of arguments is stored on the stream in a single byte. */ protected int numOfArgs; /** * The string usually printed by printOn when displaying * s-expressions and when drawing graphic tree images. */ protected String representation; /** * A unique index value used to stream genes efficiently. Its * value is set by the static method * * GPGene.createNodeIndex which must be called by the stream * manager before genes are streamed. * * @see gpjpp.GPNode#setIndex */ protected byte nodeIndex; /** * Public null constructor used during stream loading only. */ public GPNode() { } /** * The constructor called by user code to describe the functions * for the genetic programming problem. * * @param nVal an arbitrary integer value used to identify the node type. Must be unique within the branch (within its GPNodeSet). * @param str a string that is usually written out to represent the node in s-expressions and tree diagrams. * @param args the number of arguments to the function. * * @see gpjpp.GPNode#nodeValue * @see gpjpp.GPNode#numOfArgs */ public GPNode(int nVal, String str, int args) { nodeValue = nVal; representation = new String(str); numOfArgs = args; } /** * The constructor called by user code to describe the terminals * for the genetic programming problem. * * @param nVal an arbitrary integer value used to identify the node type. Must be unique within the branch (within its GPNodeSet). * @param str a string that is usually written out to represent the node in s-expressions and tree diagrams. * * @see gpjpp.GPNode#nodeValue * @see gpjpp.GPNode#numOfArgs */ public GPNode(int nVal, String str) { nodeValue = nVal; representation = new String(str); numOfArgs = 0; } /** * A constructor that can be called to clone a GPNode. Normally * not used. */ public GPNode(GPNode gpo) { this(gpo.value(), gpo.rep(), gpo.arguments()); } /** * Implements the Cloneable interface. * This clones a GPNode but is normally not used. * * @return the cloned object. */ protected synchronized Object clone() { return new GPNode(this); } /** * Returns a code identifying the class in a stream file. * * @return the ID code NODEID. */ public byte isA() { return NODEID; } /** * Returns the integer node value. */ public int value() { return nodeValue; } /** * Returns the string representation of the node. */ public String rep() { return representation; } /** * Returns true if the node is a function, that is, has more * than zero arguments. */ public boolean isFunction() { return (numOfArgs != 0); } /** * Returns true if the node is a terminal, that is, has zero * arguments. */ public boolean isTerminal() { return (numOfArgs == 0); } /** * Returns the number of arguments to the node. */ public int arguments() { return numOfArgs; } /** * Sets the node index used for streaming. * * @see gpjpp.GPGene#createNodeIndex */ public void setIndex(byte index) { nodeIndex = index; } /** * Returns the node index used for streaming. * * @see gpjpp.GPGene#createNodeIndex * @see gpjpp.GPGene#save */ public byte getIndex() { return nodeIndex; } /** * Determines whether this GPNode equals another object. It returns * true if obj is not null, is an instance of a GPNode (or a * descendant), and has the same value, number of arguments, * and string representation. This function is called when a * checkpoint is loaded by GPRun, to determine whether the * program and the checkpoint are consistent. * * @param obj any Java object reference, including null. * @return true if this and obj are equivalent. */ public boolean equals(Object obj) { if ((obj == null) || !(obj instanceof GPNode)) return false; GPNode gpo = (GPNode)obj; if (value() != gpo.value()) return false; if (arguments() != gpo.arguments()) return false; if (!rep().equals(gpo.rep())) return false; return true; } /** * Loads a GPNode from the specified stream. Reads the * nodeValue, numOfArgs, and representation fields from the * stream. * * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. * @exception java.io.IOException * if an error occurs while reading the stream. */ protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException { nodeValue = is.readInt(); numOfArgs = is.readInt(); representation = is.readUTF(); } /** * Saves a GPNode to the specified stream. Writes the * nodeValue, numOfArgs, and representation fields to the * stream. * * @exception java.io.IOException * if an error occurs while writing the stream. */ protected void save(DataOutputStream os) throws IOException { os.writeInt(nodeValue); os.writeInt(numOfArgs); os.writeUTF(representation); } /** * Writes a GPNode in text format to a PrintStream. * The node is printed simply as its representation string. */ public void printOn(PrintStream os, GPVariables cfg) { os.print(representation); } } OthelloProj/GP/gpjpp/GPVariables.java 100644 5763 134 100462 6506556653 16564 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; import java.util.Properties; /** * Holds all global configuration parameters for a genetic programming * run. All parameters have default values as described below. * The GPRun class also * automatically reads a configuration file in Java property or * Windows .ini format which can be used to set configuration * parameters without recompiling an application.
* * It is common to create a user subclass of GPVariables in order to * add problem-specific configuration parameters. Examples include the * size and filename for an ant trail, or the number of address lines * that form the input to a boolean multiplexer. In other cases it * may be useful to add non-configuration variables to a subclass of * GPVariables. gpjpp passes a reference to the global variables to all * methods that are likely to need them, including the * evaluate() * method of GP and all of the printOn() methods. Examples that * add to GPVariables in this way include the ant "automaton" that * responds to command functions and eats food, and the set of * data and address inputs for the multiplexer problem. * * @version 1.0 */ public class GPVariables extends GPObject { //enumerated type for tree creation /** * A tree creation type that selects each non-root node with a * 50:50 chance of becoming a function or terminal and that * continues building every tree to * * MaximumDepthForCreation. */ public final static int GPVARIABLE = 0; /** * A tree creation type that makes every node but those on the * bottom level a function and that builds every tree to * MaximumDepthForCreation. */ public final static int GPGROW = 1; /** * A tree creation type that builds alternating trees using * the GPRAMPEDVARIABLE and GPRAMPEDGROW methods. The default * method. */ public final static int GPRAMPEDHALF = 2; /** * A tree creation type that is like GPVARIABLE but starts with * a tree depth of two and increases the depth by one for each * tree until it reaches MaximumDepthForCreation, at which point * it cycles back to two. Note that if * TestDiversity * is enabled many of the shallow trees are duplicates, so the * distribution is skewed toward deeper trees than one might expect. */ public final static int GPRAMPEDVARIABLE = 3; /** * A tree creation type that is like GPGROW but starts with * a tree depth of two and increases the depth by one for each * tree until it reaches MaximumDepthForCreation, at which point * it cycles back to two. Note that if TestDiversity is enabled * many of the shallow trees are duplicates, so the distribution * is skewed toward deeper trees than one might expect. */ public final static int GPRAMPEDGROW = 4; /** * An array of strings used to detect and print the creation * type in configuration files and status reports. The values * are "Variable", "Grow", "RampedHalf", "RampedVariable", * and "RampedGrow". */ protected final static String[] CreationStr = {"Variable", "Grow", "RampedHalf", "RampedVariable", "RampedGrow"}; //enumerated type for selection /** * A fitness-based selection type that uses a roulette * algorithm. The default method. * * @see gpjpp.GPPopulation#probabilisticSelection */ public final static int GPPROBABILISTICSELECTION = 0; /** * A fitness-based selection type that uses a tournament * algorithm. * * @see gpjpp.GPPopulation#tournamentSelection */ public final static int GPTOURNAMENTSELECTION = 1; /** * A fitness-based selection type that uses greedy * over-selection. When this type is enabled, demetic * grouping is always disabled. * * @see gpjpp.GPPopulation#greedySelection */ public final static int GPGREEDYSELECTION = 2; /** * An array of strings used to detect and print the selection * type in configuration files and status reports. The values * are "Probabilistic", "Tournament", and "Greedy". */ protected final static String[] SelectionStr = {"Probabilistic", "Tournament", "Greedy"}; //variables controlling a run, with defaults //=================================================================== /** * The number of individuals (GP instances) in a population. * If SteadyState is false, two populations of this size are * created and filled. If SteadyState is true, only one * population is created, and weaker individuals are replaced by * new individuals as they are created. Default 500. */ public int PopulationSize = 500; /** * The maximum number of generations in a run. If the best * individual's standardized fitness drops below * * TerminationFitness, the run will terminate sooner. * Default 51. */ public int NumberOfGenerations = 51; /** * The strategy used to * create * generation 0. Default * GPRAMPEDHALF. */ public int CreationType = GPRAMPEDHALF; /** * The largest depth allowed for newly created trees. * Default 6. The minimum tree depth is always 2. */ public int MaximumDepthForCreation = 6; /** * The largest depth allowed for trees after * crossover. * Default 17. Note that MaximumDepthForCrossover * must always be at least as large as MaximumDepthForCreation. */ public int MaximumDepthForCrossover = 17; /** * The largest complexity (number of nodes) allowed in any * individual GP, including the main branch and all ADFs. * Although keeping a tight rein on complexity can speed * the algorithm and cut memory requirements, be cautious * not to limit the complexity too much. This can lead to * lack of diversity in the population and to wasted time * attempting to create and evolve new individuals. * Default 200. * * @see gpjpp.GPPopulation#create */ public int MaximumComplexity = 200; /** * The strategy used to select individuals with a probability * related to their fitness. Default * * GPPROBABILISTICSELECTION. */ public int SelectionType = GPPROBABILISTICSELECTION; /** * Number of randomly selected individuals forming a "tournament" * when SelectionType is * * GPTOURNAMENTSELECTION. Default 7. */ public int TournamentSize = 7; /** * Percent probability that a crossover operation will occur * while evolving * a new generation. Default 90.0. */ public double CrossoverProbability = 90.0; /** * Percent probability that a creation operation will occur * while evolving * a new generation. Default 0.0. */ public double CreationProbability = 0.0; /** * Percent probability that * swap mutation * will occur for each individual added to a new generation. * Default 0.0. */ public double SwapMutationProbability = 0.0; /** * Percent probability that * shrink mutation * will occur for each individual added to a new generation. * Default 0.0. */ public double ShrinkMutationProbability = 0.0; /** * A run terminates if the best individual in any generation * has standardized fitness below this level. Default 0.0. * Because fitness must always be non-negative, the default * value will never cause a run to stop before NumberOfGenerations. */ public double TerminationFitness = 0.0; /** * GPRun does multiple runs * until this many of them terminate with the best individual's * fitness below TerminationFitness. Set it to 0 if you want just * a single run regardless of results. Default 5. */ public int GoodRuns = 5; /** * A boolean that can be tested by user functions to determine * whether to add ADFs to the branch definition and whether to * evaluate them in fitness functions. Provides a convenient * way to test performance without recompiling. This * configuration variable is not used by gpjpp itself. * Default false. */ public boolean UseADFs = false; /** * Determines whether gpjpp tests the diversity of genetic * populations. If true, gpjpp guarantees that there are no * duplicate individuals in generation 0 and then tracks * and reports the diversity of succeeding generations. If * false, gpjpp does not verify or measure diversity. * Default true. */ public boolean TestDiversity = true; /** * A boolean that can be tested by the user evaluate() function * to determine whether to incorporate complexity into the * fitness calculation. When this is done, solutions tend to * be parsimonious and average population complexity * tends to remain lower. Provides a convenient way to test * population statistics without recompiling. This * configuration variable is not used by gpjpp itself. * Default true. */ public boolean ComplexityAffectsFitness = true; /** * The number of generations between checkpoints saved by * GPRun. If zero, * checkpointing is not performed at all, in which case runs * cannot be restarted after a crash or system shutdown. If * one, a checkpoint is saved after every generation. * Default 0. */ public int CheckpointGens = 0; /** * Determines whether * * demetic migration is performed. If true, * the overall population is subdivided into groups of size * DemeSize. * These groups are isolated for the purpose of fitness-based * selection. After all the demetic groups of a new * generation are created, one individual from each group is * fitness-selected and swapped with a fitness-selected individual * from the next group, with each swap controlled by the * probability * DemeticMigProbability. Default false. */ public boolean DemeticGrouping = false; /** * The number of individuals in each demetic group, if * DemeticGrouping * is true. * PopulationSize must be an exact integer multiple of DemeSize. * Default 100. */ public int DemeSize = 100; /** * Percent probability that demetic migration will occur * for each demetic group, if * DemeticGrouping * is true. Default 100.0. */ public double DemeticMigProbability = 100.0; /** * Determines whether the best individual is automatically * added to the next generation, when SteadyState is false. * Default false. * * @see gpjpp.GPPopulation#generate */ public boolean AddBestToNewPopulation = false; /** * Determines whether each new generation is created in * isolation from the previous generation (SteadyState = false) or * is created by replacing the weaker individuals one by one * (SteadyState = true). Steady state operation reduces * peak memory usage by a factor of two. Default false. * * @see gpjpp.GPPopulation#generate */ public boolean SteadyState = false; /** * Determines whether a detail file is generated by GPRun. * The detail file includes the population index, heritage, * fitness, complexity, depth, and optionally the s-expression * for individuals after each generation. Default false. */ public boolean PrintDetails = false; /** * Determines whether the detail file includes every individual * in the population (PrintPopulation = true) or just the best * and worst individuals in the population (PrintPopulation = * false). Default false. */ public boolean PrintPopulation = false; /** * Determines whether the detail file shows the s-expression for * each selected individual after each generation. Also determines * whether the statistics file includes the s-expression for * the best individual of each run. Default true. * * @see gpjpp.GPRun#showGeneration */ public boolean PrintExpression = true; /** * Determines whether the statistics file shows a pseudo-graphic * tree for the best individual of each run. Also determines * whether gif files are created showing the best individual * of each run in true graphic format. Default true. * * @see gpjpp.GPRun#showFinalGeneration */ public boolean PrintTree = true; /** * The font size in points used to draw the text in graphic * trees enabled by PrintTree. The typeface is always Courier, * a monospaced font. Default 12. */ public int TreeFontSize = 12; //=================================================================== /** * Public null constructor used to create a set of variables * with default values and also during stream loading. */ public GPVariables() { /*gets default values above*/ } /** * A constructor that can be called to clone GPVariables. Normally * not used. */ public GPVariables(GPVariables gpo) { PopulationSize = gpo.PopulationSize; NumberOfGenerations = gpo.NumberOfGenerations; CreationType = gpo.CreationType; MaximumDepthForCreation = gpo.MaximumDepthForCreation; MaximumDepthForCrossover = gpo.MaximumDepthForCrossover; MaximumComplexity = gpo.MaximumComplexity; SelectionType = gpo.SelectionType; TournamentSize = gpo.TournamentSize; DemeticGrouping = gpo.DemeticGrouping; DemeSize = gpo.DemeSize; CrossoverProbability = gpo.CrossoverProbability; CreationProbability = gpo.CreationProbability; SwapMutationProbability = gpo.SwapMutationProbability; ShrinkMutationProbability = gpo.ShrinkMutationProbability; DemeticMigProbability = gpo.DemeticMigProbability; TerminationFitness = gpo.TerminationFitness; GoodRuns = gpo.GoodRuns; AddBestToNewPopulation = gpo.AddBestToNewPopulation; SteadyState = gpo.SteadyState; CheckpointGens = gpo.CheckpointGens; PrintDetails = gpo.PrintDetails; PrintPopulation = gpo.PrintPopulation; PrintExpression = gpo.PrintExpression; PrintTree = gpo.PrintTree; TreeFontSize = gpo.TreeFontSize; UseADFs = gpo.UseADFs; TestDiversity = gpo.TestDiversity; ComplexityAffectsFitness = gpo.ComplexityAffectsFitness; } /** * Implements the Cloneable interface. * This clones GPVariables but is normally not used. * * @return the cloned object. */ protected synchronized Object clone() { return new GPVariables(this); } /** * Returns a code identifying the class in a stream file. * * @return the ID code VARIABLESID. */ public byte isA() { return VARIABLESID; } /** * Determines whether this set of variables equals another object. * It returns true if obj is not null, is an instance of GPVariables * (or a descendant), and contains the same field values. * This function is called when a checkpoint is loaded by GPRun, * to determine whether the program and the checkpoint are * consistent. One can think of various harmless changes * made to GPVariables that would still allow a checkpoint to * continue (increasing the number of generations, for example), * but this is not allowed here. * * @param obj any Java object reference, including null. * @return true if this and obj are equivalent. */ public boolean equals(Object obj) { if ((obj == null) || !(obj instanceof GPVariables)) return false; GPVariables cfg = (GPVariables)obj; if (PopulationSize != cfg.PopulationSize) return false; if (NumberOfGenerations != cfg.NumberOfGenerations) return false; if (CreationType != cfg.CreationType) return false; if (MaximumDepthForCreation != cfg.MaximumDepthForCreation) return false; if (MaximumDepthForCrossover != cfg.MaximumDepthForCrossover) return false; if (MaximumComplexity != cfg.MaximumComplexity) return false; if (SelectionType != cfg.SelectionType) return false; if (TournamentSize != cfg.TournamentSize) return false; if (DemeticGrouping != cfg.DemeticGrouping) return false; if (DemeSize != cfg.DemeSize) return false; if (CrossoverProbability != cfg.CrossoverProbability) return false; if (CreationProbability != cfg.CreationProbability) return false; if (SwapMutationProbability != cfg.SwapMutationProbability) return false; if (ShrinkMutationProbability != cfg.ShrinkMutationProbability) return false; if (DemeticMigProbability != cfg.DemeticMigProbability) return false; if (TerminationFitness != cfg.TerminationFitness) return false; if (GoodRuns != cfg.GoodRuns) return false; if (AddBestToNewPopulation != cfg.AddBestToNewPopulation) return false; if (SteadyState != cfg.SteadyState) return false; if (CheckpointGens != cfg.CheckpointGens) return false; if (PrintDetails != cfg.PrintDetails) return false; if (PrintPopulation != cfg.PrintPopulation) return false; if (PrintExpression != cfg.PrintExpression) return false; if (PrintTree != cfg.PrintTree) return false; if (TreeFontSize != cfg.TreeFontSize) return false; if (UseADFs != cfg.UseADFs) return false; if (TestDiversity != cfg.TestDiversity) return false; if (ComplexityAffectsFitness != cfg.ComplexityAffectsFitness) return false; return true; } /** * An internal routine used to convert a property string * to an int. If the numeric conversion fails, the default * value is used. */ protected int getInt(Properties props, String proStr, int def) { int i; try { i = Integer.parseInt(props.getProperty(proStr)); } catch (NumberFormatException e) { i = def; } return i; } /** * An internal routine used to convert a property string * to a boolean. Acceptable boolean values in a configuration * file are 0/non-zero, false/true, and FALSE/TRUE. If the * conversion fails, the default value is used. */ protected boolean getBoolean(Properties props, String proStr, boolean def) { String s = props.getProperty(proStr); if (s == null) return def; try { //check for non-zero=true and 0=false return (Integer.parseInt(s) != 0)? true : false; } catch (NumberFormatException e) { //check for TRUE/true and FALSE/false return Boolean.valueOf(s).booleanValue(); } } /** * An internal routine used to convert a property string * to a double. If the numeric conversion fails, the default * value is used. */ protected double getDouble(Properties props, String proStr, double def) { double d; try { d = Double.valueOf(props.getProperty(proStr)).doubleValue(); } catch (NumberFormatException e) { d = def; } return d; } /** * An internal routine used to convert a property string * to an enumerated type with int values. Either the integer * value or the string representation is acceptable, and string * matching is not case sensitive. If the conversion fails, * the default value is used. */ protected int getEnumeratedType( Properties props, String[] EnumStr, String proStr, int def) { String s = props.getProperty(proStr); if (s == null) return def; try { //use integer value if specified return Integer.parseInt(s); } catch (NumberFormatException e) { //check string values for (int i = 0; i < EnumStr.length; i++) if (s.equalsIgnoreCase(EnumStr[i])) return i; return def; } } /** * An internal routine that calls getEnumerated type to convert * a property string to the int value for a creation type. * * @see gpjpp.GPVariables#CreationStr */ protected int getCreationType( Properties props, String proStr, int def) { return getEnumeratedType(props, CreationStr, proStr, def); } /** * An internal routine that calls getEnumerated type to convert * a property string to the int value for a selection type. * * @see gpjpp.GPVariables#SelectionStr */ protected int getSelectionType( Properties props, String proStr, int def) { return getEnumeratedType(props, SelectionStr, proStr, def); } /** * Loads the values from a Properties container (read from a * configuration file) into the GPVariables fields. If the * property strings are invalid, default values for the affected * fields remain unchanged. If props is null, nothing happens. * * @see gpjpp.GPVariables#getInt * @see gpjpp.GPVariables#getBoolean * @see gpjpp.GPVariables#getDouble * @see gpjpp.GPVariables#getCreationType * @see gpjpp.GPVariables#getSelectionType */ public synchronized void load(Properties props) { if (props == null) return; PopulationSize = getInt(props, "PopulationSize", PopulationSize); DemeSize = getInt(props, "DemeSize", DemeSize); NumberOfGenerations = getInt(props, "NumberOfGenerations", NumberOfGenerations); CreationType = getCreationType(props, "CreationType", CreationType); MaximumDepthForCreation = getInt(props, "MaximumDepthForCreation", MaximumDepthForCreation); MaximumDepthForCrossover = getInt(props, "MaximumDepthForCrossover", MaximumDepthForCrossover); MaximumComplexity = getInt(props, "MaximumComplexity", MaximumComplexity); SelectionType = getSelectionType(props, "SelectionType", SelectionType); TournamentSize = getInt(props, "TournamentSize", TournamentSize); DemeticGrouping = getBoolean(props, "DemeticGrouping", DemeticGrouping); CrossoverProbability = getDouble(props, "CrossoverProbability", CrossoverProbability); CreationProbability = getDouble(props, "CreationProbability", CreationProbability); SwapMutationProbability = getDouble(props, "SwapMutationProbability", SwapMutationProbability); ShrinkMutationProbability = getDouble(props, "ShrinkMutationProbability", ShrinkMutationProbability); DemeticMigProbability = getDouble(props, "DemeticMigProbability", DemeticMigProbability); TerminationFitness = getDouble(props, "TerminationFitness", TerminationFitness); GoodRuns = getInt(props, "GoodRuns", GoodRuns); AddBestToNewPopulation = getBoolean(props, "AddBestToNewPopulation", AddBestToNewPopulation); SteadyState = getBoolean(props, "SteadyState", SteadyState); CheckpointGens = getInt(props, "CheckpointGens", CheckpointGens); PrintDetails = getBoolean(props, "PrintDetails", PrintDetails); PrintPopulation = getBoolean(props, "PrintPopulation", PrintPopulation); PrintExpression = getBoolean(props, "PrintExpression", PrintExpression); PrintTree = getBoolean(props, "PrintTree", PrintTree); TreeFontSize = getInt(props, "TreeFontSize", TreeFontSize); UseADFs = getBoolean(props, "UseADFs", UseADFs); TestDiversity = getBoolean(props, "TestDiversity", TestDiversity); ComplexityAffectsFitness = getBoolean(props, "ComplexityAffectsFitness", ComplexityAffectsFitness); } /** * Loads the GPVariables from the specified stream. * * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. * @exception java.io.IOException * if an error occurs while reading the stream. * @exception java.lang.RuntimeException * if the ID code read next in the stream doesn't * match the ID code returned by isA(). */ protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException { //confirm that ID indicates GPVariables if (is.readByte() != isA()) throw new RuntimeException("Invalid stream"); PopulationSize = is.readInt(); NumberOfGenerations = is.readInt(); CrossoverProbability = is.readDouble(); CreationProbability = is.readDouble(); CreationType = is.readInt(); MaximumDepthForCreation = is.readInt(); MaximumDepthForCrossover = is.readInt(); MaximumComplexity = is.readInt(); SelectionType = is.readInt(); TournamentSize = is.readInt(); DemeticGrouping = is.readBoolean(); DemeSize = is.readInt(); DemeticMigProbability = is.readDouble(); TerminationFitness = is.readDouble(); GoodRuns = is.readInt(); SwapMutationProbability = is.readDouble(); ShrinkMutationProbability = is.readDouble(); AddBestToNewPopulation = is.readBoolean(); SteadyState = is.readBoolean(); CheckpointGens = is.readInt(); PrintDetails = is.readBoolean(); PrintPopulation = is.readBoolean(); PrintExpression = is.readBoolean(); PrintTree = is.readBoolean(); TreeFontSize = is.readInt(); UseADFs = is.readBoolean(); TestDiversity = is.readBoolean(); ComplexityAffectsFitness = is.readBoolean(); } /** * Writes the GPVariables to the specified stream. * * @exception java.io.IOException * if an error occurs while writing the stream. */ protected void save(DataOutputStream os) throws IOException { os.writeByte(isA()); os.writeInt(PopulationSize); os.writeInt(NumberOfGenerations); os.writeDouble(CrossoverProbability); os.writeDouble(CreationProbability); os.writeInt(CreationType); os.writeInt(MaximumDepthForCreation); os.writeInt(MaximumDepthForCrossover); os.writeInt(MaximumComplexity); os.writeInt(SelectionType); os.writeInt(TournamentSize); os.writeBoolean(DemeticGrouping); os.writeInt(DemeSize); os.writeDouble(DemeticMigProbability); os.writeDouble(TerminationFitness); os.writeInt(GoodRuns); os.writeDouble(SwapMutationProbability); os.writeDouble(ShrinkMutationProbability); os.writeBoolean(AddBestToNewPopulation); os.writeBoolean(SteadyState); os.writeInt(CheckpointGens); os.writeBoolean(PrintDetails); os.writeBoolean(PrintPopulation); os.writeBoolean(PrintExpression); os.writeBoolean(PrintTree); os.writeInt(TreeFontSize); os.writeBoolean(UseADFs); os.writeBoolean(TestDiversity); os.writeBoolean(ComplexityAffectsFitness); } /** * Writes the GPVariables fields in the format of a * Properties text file. */ public void printOn(PrintStream os, GPVariables cfg) { os.println("PopulationSize = "+PopulationSize); os.println("NumberOfGenerations = "+NumberOfGenerations); os.println("CrossoverProbability = "+CrossoverProbability); os.println("CreationProbability = "+CreationProbability); os.println("CreationType = "+CreationStr[CreationType]); os.println("MaximumDepthForCreation = "+MaximumDepthForCreation); os.println("MaximumDepthForCrossover = "+MaximumDepthForCrossover); os.println("MaximumComplexity = "+MaximumComplexity); os.println("SelectionType = "+SelectionStr[SelectionType]); os.println("TournamentSize = "+TournamentSize); os.println("DemeSize = "+DemeSize); os.println("DemeticMigProbability = "+DemeticMigProbability); os.println("SwapMutationProbability = "+SwapMutationProbability); os.println("ShrinkMutationProbability = "+ShrinkMutationProbability); os.println("TerminationFitness = "+TerminationFitness); os.println("GoodRuns = "+GoodRuns); os.println("DemeticGrouping = "+DemeticGrouping); os.println("AddBestToNewPopulation = "+AddBestToNewPopulation); os.println("SteadyState = "+SteadyState); os.println("PrintDetails = "+PrintDetails); os.println("PrintPopulation = "+PrintPopulation); os.println("PrintExpression = "+PrintExpression); os.println("PrintTree = "+PrintTree); os.println("TreeFontSize = "+TreeFontSize); os.println("UseADFs = "+UseADFs); os.println("TestDiversity = "+TestDiversity); os.println("ComplexityAffectsFitness = "+ComplexityAffectsFitness); os.println("CheckpointGens = "+CheckpointGens); } } OthelloProj/GP/gpjpp/GPNodeSet.java 100644 5763 134 24433 6506556653 16200 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; /** * Stores information about the functions and terminals used in * one tree branch of a particular genetic programming problem.
* * GPNodeSet is a container that holds an arbitrary number of * function and terminal nodes. For improved performance during * some operations, all of the functions are stored at the beginning * of the container and all of the terminals are stored at the end. * There might be some null elements in the middle and the code is * designed to accommodate those. * * @see gpjpp.GPNode * @see gpjpp.GPAdfNodeSet * * @version 1.0 */ public class GPNodeSet extends GPContainer { /** * The number of function node types supported by this branch. */ protected int numFunctions; /** * The number of terminal node types supported by this branch. */ protected int numTerminals; /** * Public null constructor used during stream loading only. */ public GPNodeSet() { } /** * The constructor called by user code to reserve space for * the functions and terminals allowed in this branch. * * @param numOfNodes the maximum number of functions and terminals * to be specified. This can exceed the actual * number added subsequently by calling putNode * but should generally equal the actual number. */ public GPNodeSet(int numOfNodes) { super(numOfNodes); } /** * A constructor that can be called to clone a GPNodeSet. Normally * not used. */ public GPNodeSet(GPNodeSet gpo) { super(gpo); numFunctions = gpo.numFunctions; numTerminals = gpo.numTerminals; } /** * Implements the Cloneable interface. * This clones a GPNodeSet but is normally not used. * * @return the cloned object. */ protected synchronized Object clone() { return new GPNodeSet(this); } /** * Returns a code identifying the class in a stream file. * * @return the ID code NODESETID. */ public byte isA() { return NODESETID; } /** * Returns the number of functions in this node set. * * @see gpjpp.GPNodeSet#numFunctions */ public int functions() { return numFunctions; } /** * Returns the number of terminals in this node set. * * @see gpjpp.GPNodeSet#numTerminals */ public int terminals() { return numTerminals; } /** * Adds a function or terminal node to a GPNodeSet. Functions are * automatically stored at the next available location at the * start of the container, while terminals are added at the end * of the container. Do not call GPContainer.put() to store * nodes in a GPNodeSet since this may corrupt the expected * ordering of the nodes. * * @param gpo a non-null GPNode instance. * * @exception java.lang.ArrayStoreException * if the container is already full. * @exception java.lang.RuntimeException * if a node with gpo's value is already found in * the GPNodeSet. */ public void putNode(GPNode gpo) { //check if full if (numFunctions+numTerminals == containerSize()) throw new ArrayStoreException(); //cannot duplicate node with same identification number if (searchForNode(gpo.value()) != null) throw new RuntimeException("Cannot duplicate node ID in node set"); //put functions at the beginning, terminals at the end. if (gpo.isFunction()) super.put(numFunctions++, gpo); else super.put(containerSize()-(++numTerminals), gpo); } /** * Determines whether this GPNodeSet equals another object. * It returns true if obj is not null, is an instance of a GPNodeSet * (or a descendant), and contains the same * GPNode values. * This function is called when a checkpoint is loaded by * GPRun, * to determine whether the program and the checkpoint are * consistent. * * @param obj any Java object reference, including null. * @return true if this and obj are equivalent. */ public boolean equals(Object obj) { if ((obj == null) || !(obj instanceof GPNodeSet)) return false; GPNodeSet gpo = (GPNodeSet)obj; if (containerSize() != gpo.containerSize()) return false; if (functions() != gpo.functions()) return false; if (terminals() != gpo.terminals()) return false; //loop through all subtrees and compare them for (int i = 0; i < containerSize(); i++) { GPNode g1 = (GPNode)get(i); GPNode g2 = (GPNode)gpo.get(i); if (g1 != null) { if (!g1.equals(g2)) return false; } else if (g2 != null) return false; } return true; } /** * Returns the GPNode in this set that has the specified node * value, or null if none is found. For internal use. */ protected GPNode searchForNode(int value) { for (int i = 0; i < containerSize(); i++) { GPNode current = (GPNode)get(i); if ((current != null) && (current.value() == value)) return current; } return null; } /** * Returns a random function node from this set. Used by * GP.create() and * GPGene.create() * to build new trees. */ public GPNode chooseFunction() { return (GPNode)get(GPRandom.nextInt(numFunctions)); } /** * Returns a random terminal node from this set. Used by * GPGene.create() * to build new trees. */ public GPNode chooseTerminal() { return (GPNode)get(containerSize()-numTerminals+ GPRandom.nextInt(numTerminals)); } /** * Returns a random node from this set with the specified * number of arguments. Returns null if there is no such * node. Used for * swap mutation. */ public GPNode chooseNodeWithArgs(int args) { int num; //count all nodes that have the specified number of arguments num = 0; for (int i = 0; i < containerSize(); i++) { GPNode n = (GPNode)get(i); if (n != null) if (n.arguments() == args) num++; } if (num == 0) return null; //return the node with random index int k = GPRandom.nextInt(num); num = 0; for (int i = 0; i < containerSize(); i++) { GPNode n = (GPNode)get(i); if (n != null) if (n.arguments() == args) if (num++ == k) return n; } //avoid compiler warnings (this code is never reached) return null; } /** * Loads a GPNodeSet from the specified stream. Reads the * numFunctions and numTerminals fields from the stream * and then loads the container. * * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. * @exception java.io.IOException * if an error occurs while reading the stream. */ protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException { numFunctions = is.readInt(); numTerminals = is.readInt(); super.load(is); } /** * Saves a GPNodeSet to the specified stream. Writes the * numFunctions and numTerminals fields to the stream * and then stores the container. * * @exception java.io.IOException * if an error occurs while writing the stream. */ protected void save(DataOutputStream os) throws IOException { os.writeInt(numFunctions); os.writeInt(numTerminals); super.save(os); } /** * Writes a GPNodeSet in text format to a PrintStream. * Each node is printed as its representation string followed * by its number of arguments, if any. */ public void printOn(PrintStream os, GPVariables cfg) { for (int i = 0; i < containerSize(); i++) { GPNode current = (GPNode)get(i); if (i > 0) os.print(" "); if (current != null) { current.printOn(os, cfg); if (current.isFunction()) os.print("("+current.arguments()+")"); } else os.print("null"); } } } OthelloProj/GP/gpjpp/GP.java 100644 5763 134 77271 6506556653 14726 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; /** * Stores the structure and status of a particular genetic program. * GP is a container that contains an element for the result-producing * branch of the program as well as for each ADF, if any. Each is a * GPGene object, which forms * the root of a variably sized tree whose elements are nodes from * the node set for that branch.
* * Besides the program itself, GP also stores the complexity and * maximum depth of the tree, its standard fitness (as computed by a * user subclass), its adjusted fitness, and its heritage. The heritage * consists of the population indices of the two parents if the * GP was created by crossover or the population index of one parent * if the GP was created by straight reproduction. It also includes * the crossover points and the last mutation locus when applicable.
* * The user must always create a subclass of GP for use in solving * a particular problem. This subclass must override the * evaluate() method, which * returns a double that indicates the standard fitness of the GP. * (The standard fitness must always be non-negative, and * the genetic algorithm attempts to find individuals with minimal * standard fitness.) The other fields of the GP are calculated * by gpjpp.
* * Usually the user must also override the * createGene() method to * dynamically create genes of a problem-specific type. See the * supplied example programs for more details. * * @version 1.0 */ public class GP extends GPContainer { /** * The standardized fitness of the GP. Must be non-negative and * 0.0 is considered optimal. This field is initialized with the * value returned by the evaluate() * method, which must be overridden by the user. */ protected double stdFitness; /** * The adjusted fitness of the GP. This value is initialized by * the * calcAdjustedFitness() method. Adjusted fitness is always * in the range 0.0 to 1.0, with 1.0 being optimal. */ protected double adjFitness; /** * The complexity, or length, of the GP. This is a count of the * total number of nodes in all branches of the genetic program. */ protected int gpLength; /** * The maximum depth of any branch of the GP. */ protected int gpDepth; /** * The population index of this GP's "dad" when it was generated * as a result of crossover or reproduction. This value is shown * in the detail report file when enabled. Has the value -1 if * the GP was generated by creation. * * @see gpjpp.GP#cross */ public int dadIndex; /** * The s-expression index of this GP's "dad" when it was generated * as a result of crossover. Otherwise has a value of -1. The * index is a depth-first count of nodes to reach the crossover * locus. */ public int dadCross; /** * The population index of this GP's "mum" when it was generated * as a result of crossover. This value is shown * in the detail report file when enabled. Has the value -1 if * the GP was generated by creation or reproduction. */ public int mumIndex; /** * The s-expression index of this GP's "mum" when it was generated * as a result of crossover. Otherwise has a value of -1. The * index is a depth-first count of nodes to reach the crossover * locus. */ public int mumCross; /** * The branch number of this GP's mum and dad when it was generated * as a result of crossover. Otherwise has the value -1. Branch * number 0 is the result-producing branch, number 1 is the first * ADF, and so on. */ public int crossTree; /** * The branch number used in * swap mutation when this * GP was generated. Has the value -1 if swap mutation was not * involved. */ public int swapTree; /** * The s-expression index used to apply swap mutation. Has the * value -1 if swap mutation was not involved. The * index is a depth-first count of nodes to reach the mutation * locus. */ public int swapPos; /** * The branch number used in * shrink mutation when * this GP was generated. Has the value -1 if shrink mutation was * not involved. */ public int shrinkTree; /** * The s-expression index used to apply shrink mutation. Has the * value -1 if shrink mutation was not involved. The * index is a depth-first count of nodes to reach the mutation * locus. */ public int shrinkPos; /** * Sets all of the heritage fields (dadIndex, dadCross, mumIndex, * MumCross, crossTree, swapTree, swapPos, shrinkTree, shrinkPos) * to -1 when a new GP is created or cloned. Used internally. */ protected void clearHeritage() { dadIndex = -1; dadCross = -1; mumIndex = -1; mumCross = -1; crossTree = -1; swapTree = -1; swapPos = -1; shrinkTree = -1; shrinkPos = -1; } /** * Public null constructor used during stream loading only. * Note that heritage fields are not stored on streams, so * this information is lost after a checkpoint. */ public GP() { clearHeritage(); } /** * Constructor used when GPs are first created. * This constructor creates a container capable of holding the * predefined branches of the GP, but does not fill in any nodes. * * @param trees the number of branches in the GP. */ public GP(int trees) { super(trees); clearHeritage(); } /** * A constructor that is called to clone a GP. Used * whenever a GP is selected for reproduction or crossover. * The heritage of the GP is reset by this constructor because * it will always be updated by the population manager. */ public GP(GP gpo) { super(gpo); stdFitness = gpo.stdFitness; adjFitness = gpo.adjFitness; gpLength = gpo.gpLength; gpDepth = gpo.gpDepth; //heritage is reset even during copying and cloning clearHeritage(); } /** * Implements the Cloneable interface. * This (or its user subclass) is called during reproduction. * * @return the cloned object. */ protected synchronized Object clone() { return new GP(this); } /** * Returns a code identifying the class in a stream file. * * @return the ID code GPID. */ public byte isA() { return GPID; } /** * Creates a root gene while a new branch is being built. The * user must generally override this in a subclass to create * genes of user type. See the example programs. * * @param gpo a node type that is an element of the current * branch's node set. Always a function node type. * @return the newly created gene. */ public GPGene createGene(GPNode gpo) { return new GPGene(gpo); } /** * A debugging/testing method used to ensure that no null node or * gene references are found in this GP. * * @exception java.lang.RuntimeException * if a null branch, gene, or node reference is found. */ public void testNull() { for (int i = 0; i < containerSize(); i++) { GPGene current = (GPGene)get(i); if (current == null) throw new RuntimeException("Null tree found in GP"); //test children of the gene current.testNull(); } } /** * The user must override this method to evaluate and return * the standardized fitness * of the GP. The subclass method should not call * super.evaluate(). * * @exception java.lang.RuntimeException * if it has not been overridden. */ public double evaluate(GPVariables cfg) { throw new RuntimeException("Must override to evaluate each GP"); } /** * Calculates the * adjusted fitness after evaluate() has computed * the standardized fitness. Adjusted fitness is 1/(1+stdFitness). * Adjusted fitness is always in the range 0.0 to 1.0 and is * optimal at 1.0. Adjusted fitness is used to select the best * individuals in * * probabilistic and * greedy * selection. Standardized fitness is used to select the worst * individuals. */ protected void calcAdjustedFitness() { adjFitness = 1.0/(1.0+stdFitness); } /** * Returns the already-calculated standard fitness. * * @see gpjpp.GP#stdFitness * @see gpjpp.GP#evaluate */ public double getFitness() { return stdFitness; } /** * Returns the already-calculated adjusted fitness. * * @see gpjpp.GP#adjFitness * @see gpjpp.GP#calcAdjustedFitness */ public double getAdjFitness() { return adjFitness; } /** * Returns true if this GP is better than another specified * non-null GP. Compares standardized fitness and then uses * complexity as a tiebreaker. Used internally by the * * tournament selection method. */ protected boolean betterThan(GP gp) { if (stdFitness < gp.stdFitness) return true; if (stdFitness > gp.stdFitness) return false; return (length() < gp.length()); } /** * Returns the complexity (length, or number of nodes) of the * GP. */ public int length() { return gpLength; } /** * Returns the maximum depth of the GP. */ public int depth() { return gpDepth; } /** * Calculates the complexity of the GP by calling * GPGene.length() * method for each of its branches. Used internally. * * @see gpjpp.GP#length */ protected void calcLength() { gpLength = 0; for (int i = 0; i < containerSize(); i++) gpLength += ((GPGene)get(i)).length(); } /** * Calculates the depth of the GP by calling * GPGene.depth() * method for each of its branches. Used internally. * * @see gpjpp.GP#depth */ protected void calcDepth() { gpDepth = 0; for (int i = 0; i < containerSize(); i++) { int imaxdepth = ((GPGene)get(i)).depth(); if (imaxdepth > gpDepth) gpDepth = imaxdepth; } } /** * Returns an integer hashcode for this GP. This is used * internally when calculating the diversity of a population. * The hash code is composed from the GP's complexity, depth, * and the root node type of up to 10 of its branches. */ public int hashCode() { //hash uses 8 bits of length and 4 bits of depth int hash = gpLength ^ (gpDepth << 8); int shift = 12; //and 2 bits for the root function of each GP branch for (int i = 0; (i < containerSize()) && (shift < 32); i++) { hash ^= ((GPGene)get(i)).geneNode().value() << shift; shift += 2; } return hash; } /** * Determines whether this GP equals another object. It returns * true if obj is not null, is an instance of a GP (or a * descendant), and has the same structure and node values as * this GP. This function is called when testing the * diversity of the population. equals() is called only after the * hashCode() function determines that two GPs are at least * similar. * * @param obj any Java object reference, including null. * @return true if this and obj are equivalent. */ public boolean equals(Object obj) { if ((obj == null) || !(obj instanceof GP)) return false; GP gp = (GP)obj; if (containerSize() != gp.containerSize()) throw new RuntimeException("Number of ADFs differs"); //loop through all subtrees and compare them for (int i = 0; i < containerSize(); i++) { GPGene g1 = (GPGene)get(i); GPGene g2 = (GPGene)gp.get(i); if (g1 != null) { if (!g1.equals(g2)) return false; } else if (g2 != null) return false; } return true; } /** * Creates the branches of this GP and then creates the genes * of each branch according to the limits and methods specified. * The GP for which this method is called should have been created * by calling the * createGP() method of a subclass of GPPopulation. * createGP() allocates a branch container of appropriate size * but doesn't fill in the children. * * @param creationType the method used to create the tree, either * GPGROW * (use function nodes to fill the tree to allowable depth) * or GPVARIABLE * (choose function and terminal nodes with 50:50 probability). * @param allowableDepth the maximum allowable depth of each tree. * The allowable depth must always be at least 2. * @param allowableLength the maximum allowable number of nodes * in the GP. Since create() cannot predict how many nodes * will be added recursively it simply stops adding nodes * if it exceeds allowableLength. The * create() routine * in GPPopulation rejects the returned GP if the total * complexity exceeds allowableLength. * @param adfNs the node set used to select functions and terminals * for the GP. * * @exception java.lang.RuntimeException * if creationType is neither GPGROW nor GPVARIABLE, or * if allowableDepth is less than 2. */ public synchronized void create(int creationType, int allowableDepth, int allowableLength, GPAdfNodeSet adfNs) { if ((creationType != GPVariables.GPGROW) && (creationType != GPVariables.GPVARIABLE)) throw new RuntimeException("Argument creationType must be GPGROW or GPVARIABLE"); if (allowableDepth < 2) throw new RuntimeException("allowableDepth must be at least 2"); //decrease allowableDepth because first node is always a function allowableDepth--; //keep track of GP's complexity int lengthSoFar = 0; //loop through each adf for (int i = 0; i < containerSize(); i++) { GPNodeSet ns = (GPNodeSet)adfNs.get(i); //choose random function from node set and create // a compatible gene to be the root of the tree GPGene g = createGene(ns.chooseFunction()); put(i, g); //create tree structure under the root lengthSoFar += g.create(creationType, allowableDepth, allowableLength-lengthSoFar, ns); //save length and return if already too complex gpLength = lengthSoFar; if (gpLength > allowableLength) return; } //calculate the maximum depth calcDepth(); } //used only in shrinkMutation and swapMutation; avoid reallocating static private GPGeneReference parentRef = new GPGeneReference(); /** * Mutates this GP by finding a random function gene in a random * branch and then replacing that gene by one of its immediate * children. This has the effect of shrinking the tree one level. */ public synchronized void shrinkMutation() { //select random tree int randTree = GPRandom.nextInt(containerSize()); //get root gene GPGene rootGene = (GPGene)get(randTree); //initialize parent reference for searching and updating tree parentRef.assignContainer(this, randTree); //select a function gene on that branch if (rootGene.chooseFunctionNode(parentRef)) { //a function node is available GPGene g = parentRef.getGene(); shrinkTree = randTree; shrinkPos = parentRef.count; //display results before mutation //System.out.println("before shrink mutation, shrinkPos "+shrinkPos); //rootGene.printOn(System.out); //System.out.println(); //select random immediate child of chosen function gene int subTree = GPRandom.nextInt(g.containerSize()); GPGene child = (GPGene)g.get(subTree); //no point in creating a tree of depth 1 if ((g == rootGene) && child.isTerminal()) return; //ensure chopped-off tree doesn't continue to refer to child //shouldn't be necessary, but in case of faulty gc... g.put(subTree, null); //put the child in the position of the former parent parentRef.putGene(child); //recalculate length and depth calcLength(); calcDepth(); //System.out.println("after shrink mutation, subTree "+subTree); //((GPGene)get(randTree)).printOn(System.out); //System.out.println(); //System.in.read(); } } /** * Mutates this GP by finding a random function gene in a * random branch and changing the node type of that gene. * The node type is changed randomly to another type that has * the same number of arguments. If such a node cannot be * found in 5 tries, nothing is done. */ //replace a randomly chosen function node's operator public synchronized void swapMutation(GPAdfNodeSet adfNs) { //select random tree and get node set and root node int randTree = GPRandom.nextInt(containerSize()); GPNodeSet ns = (GPNodeSet)adfNs.get(randTree); GPGene rootGene = (GPGene)get(randTree); //initialize parent reference for searching and updating tree parentRef.assignContainer(this, randTree); //select a gene on that branch, hopefully a function rootGene.chooseFunctionOrTerminalNode(parentRef); GPGene g = parentRef.getGene(); //get number of args to this node, if any int args = g.containerSize(); int val = g.node.value(); //try 5 times to find a node with different id but same args for (int i = 0; i < 5; i++) { //choose random node from node set with matching args GPNode node = ns.chooseNodeWithArgs(args); if (node.value() != val) { //replace old function with new one g.node = node; swapTree = randTree; swapPos = parentRef.count; break; } } } /** * Uses the configuration probabilities * * SwapMutationProbability and * * ShrinkMutationProbability to determine whether * to apply either or both forms of mutation to this GP. Swap * mutation is considered first, then shrink mutation. * * @see gpjpp.GP#swapMutation * @see gpjpp.GP#shrinkMutation */ public void mutate(GPVariables cfg, GPAdfNodeSet adfNs) { if (GPRandom.flip(cfg.SwapMutationProbability)) swapMutation(adfNs); if (GPRandom.flip(cfg.ShrinkMutationProbability)) shrinkMutation(); } //used only in cross; avoid repeated allocation static private GPGeneReference dadRef = new GPGeneReference(); static private GPGeneReference mumRef = new GPGeneReference(); static private GPGeneReference dadCut = new GPGeneReference(); static private GPGeneReference mumCut = new GPGeneReference(); /** * Performs crossover on two GPs. Then a random gene, preferably a * function gene, is chosen from the same random branch of each GP * and the two subtrees are swapped between the two GPs. * * @param parents a container holding the two parent GPs. Upon * exit, the same container holds the two GPs * after crossover. * @param maxDepthForCrossover the maximum depth allowed for * either GP after crossover. If the result of * a crossover exceeds this depth, the subtrees * are swapped back to their original state and * another random crossover on the same branch * is attempted, continuing until an acceptable * result is achieved. * @param maxComplexity the maximum complexity (number of nodes) * allowed for either GP after crossover. If the * result of a crossover exceeds this limit, the * subtrees are swapped back and another crossover * is attempted. * @return the parents container, now containing the * crossed GPs. * * @exception java.lang.RuntimeException * if parents does not contain exactly 2 GPs, or * if both parents don't have the same number of * branches, or if the number of branches is zero. */ // Cross the objects contained in the given container. public synchronized GPContainer cross( GPContainer parents, int maxDepthForCrossover, int maxComplexity) { //only two sexes allowed if (parents.containerSize() != 2) throw new RuntimeException("Only two parents allowed for crossover"); //get mum and dad from container GP dad = (GP)parents.get(0); GP mum = (GP)parents.get(1); //GP's must have the same number of trees if (dad.containerSize() != mum.containerSize()) throw new RuntimeException("Mum and Dad must have same number of trees"); if (dad.containerSize() == 0) throw new RuntimeException("Parents contain no trees"); //pick random adf branch to cut from int randTree = GPRandom.nextInt(dad.containerSize()); dad.crossTree = randTree; mum.crossTree = randTree; //save references to Dad and Mum dadRef.assignContainer(dad, randTree); mumRef.assignContainer(mum, randTree); //compute partial length without randTree int dadPartialLength = dad.gpLength-dadRef.getGene().length(); int mumPartialLength = mum.gpLength-mumRef.getGene().length(); int dadLength; int mumLength; //loop until crossover results have acceptable depth and length do { int dadDepth; int mumDepth; //assign starting cut references dadCut.assignRef(dadRef); mumCut.assignRef(mumRef); //determine cut points within mum and dad dadRef.getGene().chooseFunctionOrTerminalNode(dadCut); mumRef.getGene().chooseFunctionOrTerminalNode(mumCut); //store data for crossover tracking dad.dadCross = dadCut.count; dad.mumCross = mumCut.count; mum.dadCross = mumCut.count; mum.mumCross = dadCut.count; //display results before crossover //dadDepth = dadRef.getGene().depth(); //System.out.println("dad before (depth "+dadDepth+")"); //System.out.println("dad index "+dad.dadIndex+"; mum index "+dad.mumIndex); //System.out.println("cross tree "+dad.crossTree+"; dad cross "+dad.dadCross+"; mum cross "+dad.mumCross); //dadRef.getGene().printOn(System.out); //System.out.println(); //mumDepth = mumRef.getGene().depth(); //System.out.println("mum before (depth "+mumDepth+")"); //System.out.println("dad index "+mum.dadIndex+"; mum index "+mum.mumIndex); //System.out.println("cross tree "+mum.crossTree+"; dad cross "+mum.dadCross+"; mum cross "+mum.mumCross); //mumRef.getGene().printOn(System.out); //System.out.println(); //swap the whole subtrees GPGene tmpD = dadCut.getGene(); dadCut.putGene(mumCut.getGene()); mumCut.putGene(tmpD); //compute new tree depth dadDepth = dadRef.getGene().depth(); mumDepth = mumRef.getGene().depth(); //update overall GP complexity dadLength = dadPartialLength+dadRef.getGene().length(); mumLength = mumPartialLength+mumRef.getGene().length(); //display results after crossover //System.out.println("dad after (depth "+dadDepth+")"); //dadRef.getGene().printOn(System.out); //System.out.println(); //System.out.println("mum after (depth "+mumDepth+")"); //mumRef.getGene().printOn(System.out); //System.out.println(); if ((dadDepth > maxDepthForCrossover) || (mumDepth > maxDepthForCrossover) || (dadLength > maxComplexity) || (mumLength > maxComplexity)) { //undo crossover and try again tmpD = dadCut.getGene(); dadCut.putGene(mumCut.getGene()); mumCut.putGene(tmpD); } else //crossover acceptable break; } while (true); //recompute or save changed values dad.calcDepth(); mum.calcDepth(); dad.gpLength = dadLength; mum.gpLength = mumLength; //return the same container return parents; } /** * Loads a GP from the specified stream. Reads the * standardized and adjusted fitness from the stream, * then loads the container of gene branches. Afterwards, * the length and depth of the GP is recalculated. * The heritage of the GP is not stored and therefore is * lost after a save/load cycle. * * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. * @exception java.io.IOException * if an error occurs while reading the stream. */ protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException { stdFitness = is.readDouble(); adjFitness = is.readDouble(); //load container super.load(is); //recalculate length and depth calcLength(); calcDepth(); //heritage is not stored to save space } /** * Saves a GP to the specified stream. Writes the * standardized and adjusted fitness to the stream, * then saves the container of gene branches. */ protected void save(DataOutputStream os) throws IOException { os.writeDouble(stdFitness); os.writeDouble(adjFitness); //gpLength and gpDepth are recalculated after loading //heritage is not stored to save space //save container super.save(os); } /** * Writes a GP in text format to a PrintStream. * Each branch is preceded by "RPB" (for the result-producing * branch) or "ADFn" (for the ADFs) and continues with the * branch's s-expression on one line. * * @see gpjpp.GPGene#printOn */ public void printOn(PrintStream os, GPVariables cfg) { for (int i = 0; i < containerSize(); i++) { if (i == 0) os.print("RPB: "); else os.print("ADF"+(i-1)+": "); ((GPGene)get(i)).printOn(os, cfg); os.println(); os.println(); } } /** * Writes a GP in text tree format to a PrintStream. * If there are no ADFs, the main branch's tree is printed * without any title. Otherwise, each branch is preceded * by "RPB" (for the result-producing branch) or "ADFn" * (for the ADFs), which is followed by the tree in * pseudo-graphic format. * * @see gpjpp.GPGene#printTree */ public void printTree(PrintStream os, GPVariables cfg) { for (int i = 0; i < containerSize(); i++) { if (containerSize() != 1) if (i == 0) os.println("RPB: "); else os.println("ADF"+(i-1)+": "); ((GPGene)get(i)).printTree(os, cfg); os.println(); } } /** * Writes a GP in graphic gif file format. This method simply * computes a title for the gif file and then calls * GPGene.drawOn. * If there are no ADFs, the title is blank; otherwise it is "RPB" * for the result-producing branch and "ADFn" for the ADF branches. */ public void drawOn(GPDrawing ods, String fnameBase, GPVariables cfg) throws IOException { //scan main branch and each ADF for (int i = 0; i < containerSize(); i++) { String title; if (containerSize() == 1) title = ""; else if (i == 0) title = "RPB"; else title = "ADF"+(i-1); ((GPGene)get(i)).drawOn(ods, fnameBase+title+".gif", title, cfg); } } } OthelloProj/GP/gpjpp/GPRandom.java 100644 5763 134 5034 6506556653 16033 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.util.Random; /** * Manages a static instance of the standard Random class, and * adds a couple of random number methods that are of use to gpjpp. * GPRandom cannot be instantiated; all members are static. It is * designed this way in order to avoid having to pass an instance * variable to various and dispersed methods of gpjpp. * * @version 1.0 */ public class GPRandom { //not intended to be instantiated since all members are static private GPRandom() {} /** * A static instance of a Random that is used throughout the * gpjpp package. This must be valid before creating a * population. It is instantiated automatically by the * GPRun class. */ static protected Random r = null; /** * Sets the static field r to an instance of Random. */ static public void setGenerator(Random ran) { r = ran; } /** * Returns a random integer uniformly distributed in the range * 0 to limit-1. limit must 0 or greater. */ static public int nextInt(int limit) { return (int)Math.floor(limit*r.nextDouble()); } /** * Returns true if a random real in the range from 0.0 to 100.0 * is less than the specified percent. Thus, if percent is 50.0, * the result has equal probability of returning true or false. */ static public boolean flip(double percent) { return (r.nextDouble()*100.0 < percent)? true : false; } /** * Returns a random double uniformly distributed in the range * 0.0 to 1.0. Simply calls r.nextDouble(). */ static public double nextDouble() { return (r.nextDouble()); } } OthelloProj/GP/gpjpp/GPAdfNodeSet.java 100644 5763 134 10661 6506556654 16612 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; /** * Stores information about the functions and terminals used in * all branches of a particular genetic programming problem.
* * GPAdfNodeSet holds a * GPNodeSet for the result-producing branch * of the tree and also one for each ADF.
* * Because this class has no data fields of its own, its load and * save methods are inherited unchanged from * GPContainer. * * @version 1.0 */ public class GPAdfNodeSet extends GPContainer { /** * Public null constructor used during stream loading only. */ public GPAdfNodeSet() {} /** * The constructor called by user code to reserve space for * the branches in each GP. The zeroth branch is always the * result-producing branch. The other branches, if any, are * ADFs that can be called from the zeroth branch.
* * The supplied example programs show how to create * GPAdfNodeSets with and without ADFs. * * @param numOfTrees the number of branches in each individual. */ public GPAdfNodeSet(int numOfTrees) { super(numOfTrees); } /** * A constructor that can be called to clone a GPAdfNodeSet. * Normally not used. */ public GPAdfNodeSet(GPAdfNodeSet gpo) { super(gpo); } /** * Implements the Cloneable interface. * This clones a GPAdfNodeSet but is normally not used. * * @return the cloned object. */ protected synchronized Object clone() { return new GPAdfNodeSet(this); } /** * Returns a code identifying the class in a stream file. * * @return the ID code ADFNODESETID. */ public byte isA() { return ADFNODESETID; } /** * Determines whether this GPAdfNodeSet equals another object. * It returns true if obj is not null, is an instance of a GPAdfNodeSet * (or a descendant), and contains the same GPNodeSet values. * This function is called when a checkpoint is loaded by GPRun, * to determine whether the program and the checkpoint are * consistent. * * @param obj any Java object reference, including null. * @return true if this and obj are equivalent. */ public boolean equals(Object obj) { if ((obj == null) || !(obj instanceof GPAdfNodeSet)) return false; GPAdfNodeSet gpo = (GPAdfNodeSet)obj; if (containerSize() != gpo.containerSize()) return false; //loop through all subtrees and compare them for (int i = 0; i < containerSize(); i++) { GPNodeSet g1 = (GPNodeSet)get(i); GPNodeSet g2 = (GPNodeSet)gpo.get(i); if (g1 != null) { if (!g1.equals(g2)) return false; } else if (g2 != null) return false; } return true; } /** * Writes a GPAdfNodeSet in text format to a PrintStream. * Each node set is labeled as "RPB" or "ADFn" depending * on its position within the GPAdfNodeSet. */ public void printOn(PrintStream os, GPVariables cfg) { for (int i = 0; i < containerSize(); i++) { GPNodeSet current = (GPNodeSet)get(i); if (current != null) { if (i == 0) os.print("RPB: "); else os.print("ADF"+(i-1)+": "); current.printOn(os, cfg); os.println(); } else os.println("Null set"); } } } OthelloProj/GP/gpjpp/GPGeneReference.java 100644 5763 134 6135 6506556654 17314 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; /** * Encapsulates the input and output parameters to the tree search * routines used for crossover and mutation. This class is needed * because Java cannot compute the address of a variable. The * functions in gpc++ that take the address of a pointer in order to * update a tree cannot be directly ported to Java. Instead, gpjpp * maintains the container and index within the container of each * gene being searched. This effectively provides the address of the * gene itself and makes it possible to replace the gene with a * gene branch from another source.
* * This class is for internal use. * * @version 1.0 */ public class GPGeneReference { /** * The container that holds a particular gene. */ public GPContainer container; /** * The index of a particular gene within its container. */ public int index; /** * Used by a search function to count the number of * genes to pass or the number that were passed. */ public int count; /** * Instantiates a gene reference for later use. */ public GPGeneReference() {} /** * Instantiates a gene reference with a known container and index. */ public GPGeneReference(GPContainer container, int index) { this.container = container; this.index = index; } /** * Clones another gene reference. */ public GPGeneReference(GPGeneReference ref) { container = ref.container; index = ref.index; count = ref.count; } /** * Assigns another gene reference to this one. */ public void assignRef(GPGeneReference ref) { container = ref.container; index = ref.index; count = ref.count; } /** * Assigns a particular container and index to this gene reference. */ public void assignContainer(GPContainer container, int index) { this.container = container; this.index = index; } /** * Returns the gene referenced by this class. */ public GPGene getGene() { return (GPGene)container.get(index); } /** * Puts a different gene into the place of this class. */ public void putGene(GPGene g) { container.put(index, g); } } OthelloProj/GP/gpjpp/GPPopulation.java 100644 5763 134 206532 6506556654 17014 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; import java.util.Hashtable; /** * Stores a fixed-size array of genetic programs of type * GP. * GPPopulation has methods for evolving this population by * fitness-based selection and reproduction, crossover, mutation, * and demetic migration. It also has methods for printing * the status of the population at various degrees of detail. * And it includes a Hashtable-based data structure for measuring * and enforcing diversity of the individuals in the population.
* * GPPopulation includes references to the * GPVariables configuration * of the run and the * GPAdfNodeSet set of node * types. These references are passed as parameters to lower level * classes when needed.
* * GPPopulation has several public data fields that can be used * by the calling program to obtain the status of the population. These * include bestOfPopulation (the index of the individual with the * best fitness), worstOfPopulation, attemptedDupCount (the number * of duplicate individuals detected but rejected when creating the * initial population), and others.
* * Although GPPopulation represents a single population of individuals, * it is designed to work with either a single population (steady * state evolution) or two populations (generational evolution). This * behavior is implemented in the * generate() method.
* * The user must always create a subclass of GPPopulation for use * in solving a particular problem. This subclass must override * the createGP() method, * which creates a GP of user type. That GP subclass must in turn * override the evaluate() method * to compute fitness for the target problem.
*
* Otherwise, the typical details of using GPPopulation are
* encapsulated in the GPRun class.
*
* @version 1.0
*/
public class GPPopulation extends GPContainer {
/**
* Specifies the minimum tree depth for newly created individuals.
* Default value 2.
*/
protected static int minTreeDepth = 2;
/**
* The sum of the adjusted fitness over an entire range.
* Used for probabilistic and greedy selection only.
*/
protected double sumAdjFitness;
/**
* The cutoff fitness for an individual to get into group I.
* Used for greedy selection only.
*/
protected double cutoffAdjFitness;
/**
* The sum of the adjusted fitness for group I individuals.
* Used for greedy selection only.
*/
protected double sumG1AdjFitness;
/**
* The sum of the adjusted fitness for group II individuals.
* Used for greedy selection only.
*/
protected double sumG2AdjFitness;
/**
* The sum of the standardized fitness over an entire range.
*/
protected double sumFitness;
/**
* A reference to the global configuration variables for the run.
*/
protected GPVariables cfg;
/**
* A reference to the functions and terminals for the run.
*/
protected GPAdfNodeSet adfNs;
/**
* Average fitness of the entire population. Used in
* probabilistic selection and reported by printStatistics().
* Calculated in calculateStatistics().
*/
protected double avgFitness;
/**
* Average complexity of the entire population. Reported by
* printStatistics() and calculated in calculateStatistics().
*/
protected double avgLength;
/**
* Average tree depth of the entire population. Reported by
* printStatistics() and calculated in calculateStatistics().
*/
protected double avgDepth;
/**
* Best standardized fitness found in the entire population.
* Reported by printStatistics() and calculated in
* calculateStatistics().
*/
public double bestFitness;
/**
* Worst standardized fitness found in the entire population.
* Reported by printStatistics() and calculated in
* calculateStatistics().
*/
public double worstFitness;
/**
* The index of the individual with the best standardized fitness.
* In case of ties, the lower complexity wins. The GP associated
* with this index is obtained by
* (GP)pop.get(bestOfPopulation)
.
*/
public int bestOfPopulation;
/**
* The index of the individual with the worst standardized fitness.
* In case of ties, the higher complexity wins. The GP associated
* with this index is obtained by
* (GP)pop.get(worstOfPopulation)
.
*/
public int worstOfPopulation;
/**
* The highest complexity found anywhere in the population. This
* may differ from the complexity of the individual that has the
* worst fitness. longestLength is calculated in printStatistics()
* but is not printed in any standard reports.
*/
public int longestLength;
/**
* A table of the unique GPs found in the population. This table
* is created and updated only if the
* TestDiversity
* configuration option is enabled. Each unique GP is entered in
* the table along with a count of the times it appears in the
* population. When TestDiversity is enabled, the initial
* population is guaranteed to be 100% diverse by rejecting any
* individuals that already appear in the table. For successive
* generations, duplicates are allowed but the diversity is
* reported by printStatistics(). The Hashtable approach to
* tracking diversity is fast enough that the option can be left
* on at all times.
*/
protected Hashtable uniqueGPs;
/**
* The number of duplicate individuals in the current generation.
* For the initial generation, this number is always 0. dupCount
* is not printed in any standard reports, but the diversity
* ratio (1-dupCount/popSize) is reported by printStatistics().
*/
public int dupCount;
/**
* The number of duplicate individuals that were created in
* generation 0 but rejected. When diversity checking is enabled
* generation 0 is guaranteed to be 100% diverse.
* attemptedDupCount is printed among the standard output of the
* GPRun class.
*/
public int attemptedDupCount;
/**
* The number of individuals that were created for generation 0
* but rejected because their complexity exceeded the global
* configuration variable
*
* MaximumComplexity. attemptedComplexCount
* is printed among the standard output of the GPRun class.
*/
public int attemptedComplexCount;
/**
* Public null constructor used during stream loading only.
*/
public GPPopulation() {}
/**
* Constructor used when populations are first created.
* This constructor creates a container capable of holding the
* population individuals, but does not create the individuals.
* It also performs a number of consistency checks on the
* configuration variables and node set.
*
* @param cfg the global configuration variables
* @param adfNs the set of node types for all branches
*
* @exception java.lang.RuntimeException
* if any problems are found in the configuration.
* The exception message provides more details.
*
* @see gpjpp.GPPopulation#create
*/
public GPPopulation(GPVariables cfg, GPAdfNodeSet adfNs) {
//make sure there's something to do
if (cfg.NumberOfGenerations < 1)
throw new RuntimeException("Number of generations must be at least 1");
if (cfg.PopulationSize < 2)
throw new RuntimeException("Population size must be at least 2");
//check for possibility of infinite loop during crossover
if (cfg.MaximumDepthForCrossover < cfg.MaximumDepthForCreation)
throw new RuntimeException("MaximumDepthForCrossover cannot be less than MaximumDepthForCreation");
//check tournament selection parameters
if (cfg.SelectionType == GPVariables.GPTOURNAMENTSELECTION)
if (cfg.TournamentSize < 2)
throw new RuntimeException("Tournament size must be at least 2");
//disable demetic grouping for greedy over-selection
if (cfg.SelectionType == GPVariables.GPGREEDYSELECTION)
cfg.DemeticGrouping = false;
//check demetic grouping parameters
if (cfg.DemeticGrouping) {
int demeSize = cfg.DemeSize;
int popSize = cfg.PopulationSize;
if (demeSize < 2)
throw new RuntimeException("Demetic group size must be greater than 1");
if (demeSize > popSize)
throw new RuntimeException("Demetic group size must not exceed population size");
if (popSize % demeSize != 0)
throw new RuntimeException("Population must be an integer multiple of deme size");
}
//confirm that the user has initialized the node sets correctly.
if (adfNs.containerSize() < 1)
throw new RuntimeException("Node set is empty");
for (int tree = 0; tree < adfNs.containerSize(); tree++) {
GPNodeSet ns = (GPNodeSet)adfNs.get(tree);
if ((ns == null) || (ns.containerSize() == 0))
throw new RuntimeException("Node set "+tree+" is undefined");
if (ns.functions() == 0)
throw new RuntimeException("No functions are available");
if (ns.terminals() == 0)
throw new RuntimeException("No terminals are available");
for (int i = 0; i < ns.containerSize(); i++)
if (ns.get(i) == null)
throw new RuntimeException("RPB/ADF tree "+tree+" is missing functions or terminals");
}
//save configuration and node set references
this.cfg = cfg;
this.adfNs = adfNs;
//reserve space for the genetic programs
reserveSpace(cfg.PopulationSize);
//allocate diversity checker
clearUniqueGPs();
}
/**
* A constructor that can be called to clone a population.
* Normally not used.
*/
public GPPopulation(GPPopulation gpo) {
super(gpo);
adfNs = gpo.adfNs;
cfg = gpo.cfg;
avgLength = gpo.avgLength;
avgDepth = gpo.avgDepth;
//compute the diversity
buildUniqueGPs();
}
/**
* Implements the Cloneable interface.
* This clones a GPPopulation but is normally not used.
*
* @return the cloned object.
*/
protected synchronized Object clone() {
return new GPPopulation(this);
}
/**
* Returns a code identifying the class in a stream file.
*
* @return the ID code POPULATIONID.
*/
public byte isA() { return POPULATIONID; }
/**
* Creates the GP used for a new individual. The
* user must override this in a subclass to create
* GPs of user type. See the example programs.
*
* @param numOfTrees the number of branches in the genetic program.
* @return the newly created GP.
*/
public GP createGP(int numOfTrees) { return new GP(numOfTrees); }
/**
* Computes the size of the hash table used for diversity checking.
* It equals an odd number just larger than twice the population
* size, which should generally avoid having to expand the diversity
* table after it is created.
*/
protected int getUniqueGPsSize() { return (2*cfg.PopulationSize+1); }
/**
* Creates or clears the diversity table and the
* dupCount and
*
* attemptedDupCount fields. If
* TestDiversity
* is false, does nothing.
*/
protected void clearUniqueGPs() {
if (cfg.TestDiversity) {
if (uniqueGPs == null)
uniqueGPs = new Hashtable(getUniqueGPsSize());
else
uniqueGPs.clear();
dupCount = 0;
attemptedDupCount = 0;
}
}
/**
* Adds the specified GP to the diversity table, or increments
* its count if already in the table. If
* TestDiversity
* is false, does nothing.
*/
protected void updateUniqueGPs(GP gp) {
if (cfg.TestDiversity) {
//try to add element to table
GPInteger count = (GPInteger)uniqueGPs.put(gp, new GPInteger(1));
if (count != null) {
//element already present, increment it
count.setValue(count.intValue()+1);
dupCount++;
}
}
}
/**
* Clears the diversity table and calls updateUniqueGPs for each
* individual in the population. If
* TestDiversity
* is false, does nothing.
*/
protected void buildUniqueGPs() {
if (cfg.TestDiversity) {
clearUniqueGPs();
for (int i = 0; i < containerSize(); i++)
updateUniqueGPs((GP)get(i));
}
}
/**
* Returns true if the specified GP is not already in the
* diversity table or if cfg.TestDiversity is false. If the
* GP is already in the table, returns false and increments
* attemptedDupCount. Used when creating an initial population.
*/
protected boolean checkForDiversity(GP gp) {
if (cfg.TestDiversity && (gp != null)) {
//try adding GP to table
GPInteger count = (GPInteger)uniqueGPs.put(gp, new GPInteger(1));
if (count != null) {
//already in table
attemptedDupCount++;
return false;
}
}
return true;
}
/**
* Creates all of the individuals in an initial population. If
* cfg.TestForDiversity is true, tries up to 50 times per
* individual to create a unique GP. Also tries up to 50 times per
* individual to create GPs whose complexity is less than
* cfg.MaximumComplexity and increments attemptedComplexCount for
* each individual that fails.
* * The depth of each GP is guaranteed to fall in the range * GPPopulation.minTreeDepth (2) to cfg.MaximumDepthForCreation * (6 by default).
* * create() calls GP.create() * to create each individual in the population.
* * create() uses one of several tree-building strategies depending * on the value of the configuration variable * CreationType. * If this variable equals GPRAMPEDHALF (the default), alternating * individuals are created using GPGROW (function nodes to * maximum depth) and GPVARIABLE (nodes chosen with a 50:50 * probability of being a function or a terminal). With * GPRAMPEDHALF, the depth of successive individuals is ramped from * minTreeDepth to MaximumDepthForCreation and back again.
* * If CreationType equals GPRAMPEDVARIABLE, all individuals are * created using the GPVARIABLE strategy and the depth of * successive individuals is ramped from minTreeDepth to * MaximumDepthForCreation.
* * If CreationType equals GPRAMPEDGROW, all individuals are * created using the GPGROW strategy and the depth of successive * individuals is ramped.
* * If CreationType equals GPGROW, all individuals are created * using the GPGROW strategy with depth MaximumDepthForCreation.
* * If CreationType equals GPVARIABLE, all individuals are created * using the GPVARIABLE strategy with depth MaximumDepthForCreation.
* * If a unique individual is not found in 50/4 tries, the tree * depth is incremented for each try thereafter, up to a maximum * of MaximumDepthForCreation.
* * If an individual of acceptable complexity is not found in 50/4 * tries, the tree depth is decremented for each try thereafter, * down to a minimum of minTreeDepth.
* * If no acceptable individual is found after 50 tries, a * RuntimeException is thrown.
* * After each individual is created, its fitness is calculated * by calling GP.evaluate(). * After all individuals are created, * * calculateStatistics() is called. */ public void create() { //clear diversity checker clearUniqueGPs(); attemptedComplexCount = 0; int treeDepth = minTreeDepth; int creationTries = 50; for (int i = 0; i < containerSize(); i++) { //create a new GP, or the user's subclass of it GP newGP = createGP(adfNs.containerSize()); //compute desired creation type and tree depth int creationType; int depth = treeDepth; switch (cfg.CreationType) { case GPVariables.GPRAMPEDHALF: //use grow or variable every other element if (i % 2 != 0) creationType = GPVariables.GPGROW; else creationType = GPVariables.GPVARIABLE; break; case GPVariables.GPRAMPEDVARIABLE: creationType = GPVariables.GPVARIABLE; break; case GPVariables.GPRAMPEDGROW: creationType = GPVariables.GPGROW; break; case GPVariables.GPGROW: creationType = GPVariables.GPGROW; depth = cfg.MaximumDepthForCreation; break; case GPVariables.GPVARIABLE: creationType = GPVariables.GPVARIABLE; depth = cfg.MaximumDepthForCreation; break; default: throw new RuntimeException("Invalid creation type"); } //attempt to build a unique tree of allowable complexity int tries = 0; do { newGP.create(creationType, depth, cfg.MaximumComplexity, adfNs); if (newGP.length() > cfg.MaximumComplexity) { //GP is too complex attemptedComplexCount++; //decrease depth if ((tries >= creationTries/4) && (depth > minTreeDepth)) depth--; } else { //test whether GP is unique if (checkForDiversity(newGP)) { //evaluate and store new GP newGP.stdFitness = newGP.evaluate(cfg); newGP.calcAdjustedFitness(); put(i, newGP); break; } //increase depth if struggling to find a unique GP if ((tries >= creationTries/4) && (depth < cfg.MaximumDepthForCreation)) depth++; } //tries prevents an infinite loop while finding a valid GP tries++; if (tries >= creationTries) throw new RuntimeException("Unable to create valid GP in "+creationTries+" tries"); } while (true); //increase depth for ramped schemes if (++treeDepth > cfg.MaximumDepthForCreation) treeDepth = minTreeDepth; } //evaluate the entire population calculateStatistics(); } /** * Selects one or two individuals from the specified range of * the population by using a tournament algorithm. numToSelect * individuals are randomly selected from the specified range * and their indexes stored in the selected array. Standardized * fitness is used to define "best" and complexity is used to * break ties. The tournament size is given by the configuration * variable * TournamentSize. * * @param selected an array that, upon return, must contain * the indices of the selected individuals. * @param numToSelect the number of individuals to select. * The value must be 1 or 2. * @param selectWorst true if the routine is to select the * worst individuals from the range, false to select * the best. * @param range the range of indices from which to select. Unless * demetic migration is enabled, this is the entire * population. * * @exception java.lang.RuntimeException * if numToSelect is greater than 2. */ protected void tournamentSelection(int[] selected, int numToSelect, boolean selectWorst, GPPopulationRange range) { //method designed to select only 1 or 2 elements if (numToSelect > 2) throw new RuntimeException("numToSelect must not exceed 2"); //arbitrarily initialize two best or worst elements int i; int first = range.getRandom(); int second = range.getRandom(); GP firstGP = (GP)get(first); GP secondGP = (GP)get(second); int ith; GP ithGP; if (selectWorst) { //select two worst elements from tournament if (firstGP.betterThan(secondGP)) { int tmp = first; first = second; second = tmp; GP tmpGP = firstGP; firstGP = secondGP; secondGP = tmpGP; } for (i = 2; i < cfg.TournamentSize; i++) { ith = range.getRandom(); ithGP = (GP)get(ith); if (!ithGP.betterThan(firstGP)) { second = first; secondGP = firstGP; first = ith; firstGP = ithGP; } else if (secondGP.betterThan(ithGP)) { second = ith; secondGP = ithGP; } } } else { //select two best elements from tournament if (secondGP.betterThan(firstGP)) { int tmp = first; first = second; second = tmp; GP tmpGP = firstGP; firstGP = secondGP; secondGP = tmpGP; } for (i = 2; i < cfg.TournamentSize; i++) { ith = range.getRandom(); ithGP = (GP)get(ith); if (!firstGP.betterThan(ithGP)) { //ith is better than or same as first, demote first second = first; secondGP = firstGP; first = ith; firstGP = ithGP; } else if (ithGP.betterThan(secondGP)) { //ith is better than second, replace second second = ith; secondGP = ithGP; } } } //store the selected indices selected[0] = first; if (numToSelect == 2) selected[1] = second; } /** * Sums the standardized and adjusted fitnesses over a * specified range and stores the results in the fields * sumFitness and sumAdjFitness. Used internally. */ protected void sumFitnessRange(GPPopulationRange range) { sumFitness = 0.0; sumAdjFitness = 0.0; for (int i = range.startIx; i < range.endIx; i++) { GP gp = (GP)get(i); sumFitness += gp.stdFitness; sumAdjFitness += gp.adjFitness; } } /** * Selects one or more individuals from the specified range of * the population by using a roulette algorithm. Each individual * in the specified range has a probability of selection equal * to its fitness divided by the sum total fitness of all * individuals in the range. Complexity does not play a role * in the selection unless it has already been factored into the * fitness. All fitness values must be non-negative or this method * may hang or produce unexpected results. When selectWorst is false, * adjusted fitness is used; otherwise standardized fitness is used. * * @param selected an array that, upon return, must contain * the indices of the selected individuals. * @param numToSelect the number of individuals to select. * The value must be 1 or more. * @param selectWorst true if the routine is to select the * worst individuals from the range, false to select * the best. * @param range the range of indices from which to select. Unless * demetic migration is enabled, this is the entire * population. */ protected void probabilisticSelection(int[] selected, int numToSelect, boolean selectWorst, GPPopulationRange range) { int i; //first time through, sum all fitnesses if (range.firstSelection) { range.firstSelection = false; sumFitnessRange(range); } //select requested number of members, usually 1 or 2 for (int n = 0; n < numToSelect; n++) { double rand = GPRandom.nextDouble(); double sum = 0.0; if (selectWorst) { rand *= sumFitness; for (i = range.startIx; i < range.endIx; i++) { sum += ((GP)get(i)).stdFitness; if (sum >= rand) break; } } else { rand *= sumAdjFitness; for (i = range.startIx; i < range.endIx; i++) { sum += ((GP)get(i)).adjFitness; if (sum >= rand) break; } } //this shouldn't happen, but just in case... if (i >= range.endIx) i = range.endIx-1; //add selected population member to array of indices selected[n] = i; } } /** * Calculates Koza's c constant for greedy over-selection. * Returns 0.32 for range size 1000 or less, and 320/size * for any larger range size. */ protected double calcGroupIFraction(int size) { if (size <= 1000) return 0.32; else return (double)320.0/size; } /** * Computes the adjusted fitness boundary that separates * group I from group II individuals using Koza's form of * greedy over-selection. First calculates the fitness * proportion c, which Koza defines to be 0.32 at population * size 1000, 0.16 at 2000, 0.08 at 4000, and so on. For * populations less than 1000, a constant value of 0.32 is * used. Then uses binary search to find a boundary such * that the sum of adjusted fitness for individuals whose * fitness is greater than the boundary equals c times the * total adjusted fitness. The search doesn't need to be * too accurate since c is largely arbitrary anyway, so * the search stops when the normalized sum is within 0.005 * of c.
* * The routine stores values in the fields cutoffAdjFitness, * sumG1AdjFitness, and sumG2AdjFitness. It assumes that * sumAdjFitness has already been calculated by calling * sumFitnessRange(). * * @param range the range of indices from which to select. Demetic * migration is always disabled when greedy selection * is enabled, so this is the entire population. The * routine would work for restricted ranges, but * this would run counter to Koza's assumptions. * * @see gpjpp.GPPopulation#calcGroupIFraction */ protected void calcCutoffFitness(GPPopulationRange range) { //calculate Koza's c constant double c = calcGroupIFraction(range.endIx-range.startIx); //perform a binary search double l = 0.0; double r = 1.0; int tries = 0; do { cutoffAdjFitness = (l+r)/2.0; //sum the adjusted fitness in group I sumG1AdjFitness = 0.0; for (int i = range.startIx; i < range.endIx; i++) { double f = ((GP)get(i)).adjFitness; if (f > cutoffAdjFitness) //GP is in group I sumG1AdjFitness += f; } //compute normalized sum fitness in group I double sumG1NormFitness = sumG1AdjFitness/sumAdjFitness; //done if close to c if (Math.abs(sumG1NormFitness-c) < 0.005) break; if (sumG1NormFitness < c) //need to lower fitness cutoff r = cutoffAdjFitness; else l = cutoffAdjFitness; //limit number of loops in case of chunky distribution if (++tries > 20) break; } while (true); sumG2AdjFitness = sumAdjFitness-sumG1AdjFitness; } /** * Selects one or more individuals from the specified range of * the population by using Koza's "greedy over-selection". This * divides the population into two groups based on an adjusted * fitness boundary, such that the sum of the adjusted fitness * for the first, higher-fitness group has a specified proportion * c of the total adjusted fitness. By Koza's definition c equals * 0.32 for population size 1000, 0.16 for 2000, 0.08 for 4000, * and so on. Then, 80% of the time the method returns an * individual from group I using probabilistic selection and * the other 20% it returns an individual from group II using * probabilistic selection. * * @param selected an array that, upon return, must contain * the indices of the selected individuals. * @param numToSelect the number of individuals to select. * The value must be 1 or more. * @param selectWorst true if the routine is to select the * worst individuals from the range, false to select * the best. * @param range the range of indices from which to select. Demetic * migration is always disabled when greedy selection * is enabled, so this is the entire population. * * @see gpjpp.GPPopulation#sumFitnessRange * @see gpjpp.GPPopulation#calcCutoffFitness */ protected void greedySelection(int[] selected, int numToSelect, boolean selectWorst, GPPopulationRange range) { int i; if (range.firstSelection) { range.firstSelection = false; //sum all fitnesses, just like probabilisticSelection sumFitnessRange(range); //calculate cutoff fitness and the adjusted fitness sums // for groups I and II calcCutoffFitness(range); } //select requested number of members, usually 1 or 2 for (int n = 0; n < numToSelect; n++) { double rand = GPRandom.nextDouble(); double sum = 0.0; if (selectWorst) { //no greediness for worst GPs // probabilistic finds lethals very well rand *= sumFitness; for (i = range.startIx; i < range.endIx; i++) { sum += ((GP)get(i)).stdFitness; if (sum >= rand) break; } } else if (GPRandom.flip(80.0)) { //select from group I 80% of the time for best GPs rand *= sumG1AdjFitness; for (i = range.startIx; i < range.endIx; i++) { double f = ((GP)get(i)).adjFitness; if (f > cutoffAdjFitness) { sum += f; if (sum >= rand) break; } } } else { //select from group II the other 20% rand *= sumG2AdjFitness; for (i = range.startIx; i < range.endIx; i++) { double f = ((GP)get(i)).adjFitness; if (f <= cutoffAdjFitness) { sum += f; if (sum >= rand) break; } } } //this shouldn't happen, but just in case... if (i >= range.endIx) i = range.endIx-1; //add selected population member to array of indices selected[n] = i; } } /** * Calls one of the available selection methods based on the * configuration variable * SelectionType. * Override this method if you want to implement a new selection * technique. * * @exception java.lang.RuntimeException * if numToSelect is less than 1, or * if the specified range is empty, or * if an unknown selection method is specified. * * @see gpjpp.GPPopulation#tournamentSelection * @see gpjpp.GPPopulation#probabilisticSelection * @see gpjpp.GPPopulation#greedySelection */ protected void selectIndices(int[] selected, int numToSelect, boolean selectWorst, GPPopulationRange range) { if (numToSelect < 1) throw new RuntimeException("numToSelect cannot be less than 1"); if (range.endIx-range.startIx < 1) throw new RuntimeException("Selection range is empty"); switch (cfg.SelectionType) { case GPVariables.GPTOURNAMENTSELECTION: tournamentSelection( selected, numToSelect, selectWorst, range); break; case GPVariables.GPPROBABILISTICSELECTION: probabilisticSelection( selected, numToSelect, selectWorst, range); break; case GPVariables.GPGREEDYSELECTION: greedySelection( selected, numToSelect, selectWorst, range); break; default: throw new RuntimeException("Unknown selection method"); } } //used only in select; avoid reallocating temporaries each call private int[] selected = new int[2]; private GPContainer cont1 = new GPContainer(1); private GPContainer cont2 = new GPContainer(2); /** * Returns one or more individuals from the specified range * of this population using a fitness-based selection method. * The returned individuals are cloned copies from this * population so that they can be modified (via crossover or * mutation) without disturbing the existing population. select() * also updates the heritage fields of the cloned individuals * to indicate their parent(s). This method uses two preallocated * (private) containers of length 1 and 2 to return the individuals * in order to avoid allocating new arrays every time the routine * is called. * * @param numToSelect the number of individuals to select. * The value must be 1 or 2. One is used to select * an individual to reproduce; two is used to select * two parents for crossover. * @param range the range of indices from which to select. Unless * demetic migration is enabled, this is the entire * population. * @return an array of GP references holding the selected * individuals. The length of the array exactly * matches the number of individuals in it. * * @exception java.lang.RuntimeException * if numToSelect is not 1 or 2. */ protected synchronized GPContainer select( int numToSelect, GPPopulationRange range) { if ((numToSelect != 1) && (numToSelect != 2)) throw new RuntimeException("Invalid numToSelect"); //select the best ones selectIndices(selected, numToSelect, false, range); //put copies in container to return GP newCopy; switch (numToSelect) { case 1: //copy newCopy = (GP)((GP)get(selected[0])).clone(); newCopy.dadIndex = selected[0]; newCopy.dadCross = -1; cont1.put(0, newCopy); return cont1; case 2: //crossover newCopy = (GP)((GP)get(selected[0])).clone(); newCopy.dadIndex = selected[0]; newCopy.mumIndex = selected[1]; cont2.put(0, newCopy); newCopy = (GP)((GP)get(selected[1])).clone(); newCopy.dadIndex = selected[1]; newCopy.mumIndex = selected[0]; cont2.put(1, newCopy); return cont2; } //shouldn't get here return null; } /** * Calls select() to * select exactly two parents for use in crossover. */ protected GPContainer selectParents(GPPopulationRange range) { return select(2, range); } //variable used among multiple calls to evolve private int treeDepth = 2; /** * Based on the configuration variables * * CrossoverProbability and * * CreationProbability, creates two individuals using * crossover or one new individual using creation (a brand-new * GP) or reproduction (a fitness-selected copy of an existing * individual). The new individuals are guaranteed to have * depth no more than * * MaximumDepthForCrossover or * * MaximumDepthForCreation and complexity no more than * * MaximumComplexity.
* * Brand-new individuals are created using the * GPVARIABLE * strategy with depth ramped between calls to this method.
* * Crossover is considered first, then (if crossover did not occur) * creation of a new individual, then (if creation did not occur) * reproduction of an existing individual.
* * Mutation does not occur in this method but rather as an * independent step in * generate(). * Thus an individual passed on via reproduction could still * undergo mutation. * * @param range the range of indices from which to select. Unless * demetic migration is enabled, this is the entire * population. * @return an array of GP references holding the selected * individuals. The length of the array is 2 for * individuals created via crossover and 1 for individuals * generated by creation or reproduction. * * @exception java.lang.RuntimeException * if an individual of acceptable complexity cannot be * created in 50 attempts. */ protected synchronized GPContainer evolve(GPPopulationRange range) { GPContainer gpCont; if (GPRandom.flip(cfg.CrossoverProbability)) { //crossover, select copies of parents into gpCont gpCont = selectParents(range); //call first parent's crossover function GP dad = (GP)gpCont.get(0); gpCont = dad.cross(gpCont, cfg.MaximumDepthForCrossover, cfg.MaximumComplexity); } else if (GPRandom.flip(cfg.CreationProbability)) { //create a new GP with correct number of subtrees. GP newGP = createGP(adfNs.containerSize()); do { int creationAttempts = 50; int attempts = 0; //use simple variable grow method newGP.create(GPVariables.GPVARIABLE, treeDepth, cfg.MaximumComplexity, adfNs); if (newGP.length() <= cfg.MaximumComplexity) break; else if ((attempts >= creationAttempts/4) && (treeDepth > minTreeDepth)) treeDepth--; attempts++; if (attempts >= creationAttempts) throw new RuntimeException("Unable to create valid GP in "+creationAttempts+" tries"); } while (true); //increase tree depth after creating a valid GP if (++treeDepth > cfg.MaximumDepthForCreation) treeDepth = minTreeDepth; //use one-item container and put new GP into it gpCont = cont1; gpCont.put(0, newGP); } else //fitness-select one individual to copy to next generation gpCont = select(1, range); return gpCont; } /** * Adds the best individual from this generation to the next. * This method does nothing unless the configuration variable * * AddBestToNewPopulation is true. It can be called only when * a steady state population is not in use and therefore newPop * exists. * * @param newPop the population for the next generation. */ protected synchronized void addBest(GPPopulation newPop) { if (cfg.AddBestToNewPopulation) { GP newGP = (GP)((GP)get(bestOfPopulation)).clone(); newGP.dadIndex = bestOfPopulation; newPop.put(bestOfPopulation, newGP); newPop.updateUniqueGPs(newGP); } } //used only in generate; avoid reallocating each time private int[] badGPs = new int[2]; private GPPopulationRange range = new GPPopulationRange(); /** * Generates the next generation of individuals using genetic * processes. If the configuration variable * SteadyState is * true, the newPop parameter is ignored and the next generation * is created by replacing the worst (fitness-based) individuals * in the current generation with new individuals. Otherwise, * newPop is filled in from scratch with new individuals. In either * case, * PopulationSize * individuals are created and added to the new generation.
* * If * DemeticGrouping is true, the overall population is divided * into "demes" of size * DemeSize and each * of these is treated individually as a subpopulation.
* * If * AddBestToNewPopulation is true and SteadyState is * false, the best individual in this population is automatically * added to the new population at its same index location.
* * After each new individual or pair of individuals is generated * by evolve(), * generate() calls * mutate() to possibly modify * the new individuals further.
* * If TestDiversity * is true, the diversity table is updated while the new population * is built to keep track of duplicates. No duplicates are rejected * within generate(), however.
* * After the new population is generated, * * demeticMigration() is called if this feature is activated. * Population statistics are always calculated for the new * generation. * * @param newPop an instantiated new population to fill. */ public void generate(GPPopulation newPop) { //divide population into groups if demetic migration enabled int demeSize; if (cfg.DemeticGrouping) demeSize = cfg.DemeSize; else demeSize = containerSize(); if (!cfg.SteadyState) { //clear the duplicate checker newPop.clearUniqueGPs(); //if requested, take best and add to new generation addBest(newPop); } //build new generation, deme by deme for (int demeStart = 0; demeStart < containerSize(); demeStart += demeSize) { range.startIx = demeStart; range.endIx = demeStart+demeSize; range.firstSelection = true; //continue until the whole deme or population is full for (int n = 0; n < demeSize; ) { //make 1 or 2 new GPs via creation, crossover, reproduction GPContainer gpCont = evolve(range); //select bad GPs to replace for steady state if (cfg.SteadyState && (gpCont.containerSize() != 0)) selectIndices(badGPs, gpCont.containerSize(), true, range); //add GPs to next population for (int i = 0; i < gpCont.containerSize(); i++) { //avoid overwriting best of previous generation if (!cfg.SteadyState && cfg.AddBestToNewPopulation) if (demeStart+n == bestOfPopulation) { n++; if (n >= demeSize) break; } //get the GP from the evolve container GP newGP = (GP)gpCont.get(i); //apply mutation here, not in evolve newGP.mutate(cfg, adfNs); //calculate fitness of new GP newGP.stdFitness = newGP.evaluate(cfg); newGP.calcAdjustedFitness(); if (cfg.SteadyState) { //update fitness sums for probabilistic selection GP badGP = (GP)get(badGPs[i]); sumFitness += newGP.stdFitness-badGP.stdFitness; sumAdjFitness += newGP.adjFitness-badGP.adjFitness; //replace bad old GP put(badGPs[i], newGP); } else { newPop.put(demeStart+n, newGP); newPop.updateUniqueGPs(newGP); } n++; if (n >= demeSize) break; } //for i < gpCont.containerSize } //for n < demeSize } //for demeStart < containerSize if (cfg.SteadyState) //count the duplicates in the updated population buildUniqueGPs(); //if demetic grouping is used, let members migrate into other demes if (cfg.DemeticGrouping) if (cfg.SteadyState) demeticMigration(); else newPop.demeticMigration(); //calculate statistics of the new generation if (cfg.SteadyState) calculateStatistics(); else newPop.calculateStatistics(); } //used only in demeticMigration; avoid reallocating each call private int[] r1 = new int[1]; private int[] r2 = new int[1]; private GPPopulationRange range1 = new GPPopulationRange(); private GPPopulationRange range2 = new GPPopulationRange(); /** * Based on the configuration variable * * DemeticMigProbability, fitness-selects a good individual * from each deme and exchanges it with a good individual from the * next deme. This process occurs for each adjacent pair of demes, * and the last deme is considered to be adjacent to the first deme. */ protected synchronized void demeticMigration() { //for each deme exchange best member with next deme for (int demeStart = 0; demeStart < containerSize(); demeStart += cfg.DemeSize) { if (GPRandom.flip(cfg.DemeticMigProbability)) { //set selection range range1.firstSelection = true; range1.startIx = demeStart; range1.endIx = range1.startIx+cfg.DemeSize; //second range is just beyond first, but wraps at end range2.firstSelection = true; range2.startIx = range1.endIx; if (range2.startIx >= containerSize()) range2.startIx = 0; range2.endIx = range2.startIx+cfg.DemeSize; //select the best of each deme selectIndices (r1, 1, false, range1); selectIndices (r2, 1, false, range2); //exchange population members GPObject p1 = get(r1[0]); GPObject p2 = get(r2[0]); put(r2[0], p1); put(r1[0], p2); } } } /** * Calculates statistics about a complete population, including * the best, average, and worst fitness, complexity, and depth. * Also stores the indices of the best and worst individuals. * * @exception java.lang.RuntimeException * if a null GP is unexpectedly found in the population. */ protected void calculateStatistics() { //search for the best, worst, and longest GP worst = (GP)get(0); GP best = (GP)get(0); worstOfPopulation = 0; bestOfPopulation = 0; bestFitness = best.stdFitness; worstFitness = bestFitness; longestLength = worst.length(); int worstLen = longestLength; int bestLen = longestLength; int sumLength = 0; int sumDepth = 0; for (int i = 0; i < containerSize(); i++) { GP current = (GP)get(i); if (current == null) throw new RuntimeException("Null GP found in population"); //test for nulls anywhere in the GP //current.testNull(); int curLen = current.length(); if (curLen > longestLength) longestLength = curLen; sumLength += curLen; sumDepth += current.depth(); double curFitness = current.stdFitness; sumFitness += curFitness; if ((worstFitness < curFitness) || ((worstFitness == curFitness) && (worstLen < curLen))) { worstOfPopulation = i; worst = current; worstFitness = curFitness; worstLen = curLen; } if ((bestFitness > curFitness) || ((bestFitness == curFitness) && (bestLen > curLen))) { bestOfPopulation = i; best = current; bestFitness = curFitness; bestLen = curLen; } } //get averages avgFitness = sumFitness/containerSize(); avgLength = (double)sumLength/containerSize(); avgDepth = (double)sumDepth/containerSize(); } /** * Converts an integer to a string right-justified in a field * of specified width. */ protected static String formatInt(int i, int width) { String s = String.valueOf(i); while (s.length() < width) s = " "+s; return s; } /** * Returns a string of asterisks with specified width. */ protected static String overflow(int width) { StringBuffer sb = new StringBuffer(width); for (int i = 1; i < width; i++) sb.append("*"); return sb.toString(); } /** * Converts a double to a string right justified in a field of * specified width. Returns an overflow string if the number cannot * be formatted as specified. Uses scientific notation whenever * java.lang.String.valueOf(double) returns a number in scientific * format. Rounds the number to the specified number of decimal * places. Not industrial strength but works as needed for * GPPopulation and GPRun reports. */ public static String formatDouble(double d, int width, int places) { if (Double.isNaN(d) || Double.isInfinite(d)) return overflow(width); String s; double pow10 = Math.pow(10.0, places); d = Math.rint(d*pow10)/pow10; //round to places if ((d < 1.0e+006) && (d > Math.pow(10.0, width-1-places)-Math.pow(10.0, -places))) //fixed-point value won't fit in field return overflow(width); s = String.valueOf(d); int ePos = s.indexOf('e'); if (ePos < 0) ePos = s.indexOf('E'); if (ePos < 0) { //no exponent in string int dpos = s.indexOf('.'); if (dpos < 0) s = s+"."; //add decimal point else if (dpos+places+1 < s.length()) s = s.substring(0, dpos+places+1); //truncate places dpos = s.indexOf('.'); while (s.length()-dpos < places+1) s = s+"0"; //zero-pad to places } else if (width > 6) { //scientific notation String sExp = s.substring(ePos, s.length()); String sMant; if (ePos-2 > places) sMant = s.substring(0, places+2); else sMant = s.substring(0, ePos); s = sMant+sExp; } else return overflow(width); while (s.length() < width) s = " "+s; //left-pad to width return s; } /** * Calls formatDouble to create a formatted string and then strips * any leading blanks. */ public static String trimFormatDouble(double d, int width, int places) { String s = formatDouble(d, width, places); for (int i = 0; i < s.length(); i++) if (s.charAt(i) != ' ') return s.substring(i, s.length()); return ""; } /** * Prints a legend line for the standard statistics report to the * specified PrintStream. */ public void printStatisticsLegend(PrintStream sout) { sout.print (" Gen| Fitness | Complexity | Depth "); if (cfg.TestDiversity) sout.print("|Variety"); sout.println(); sout.print (" | Best Average Worst| B A W| B A W"); //xxxx|xxxxxxx.xx xxxxxxx.xx xxxxxxx.xx|xxxx xxxx.x xxxx| xx xx.x xx| x.xxx if (cfg.TestDiversity) sout.print("|"); sout.println(); } /** * Prints one generation's statistics to the specified PrintStream. * The output is on one line and includes the generation number; * the best, average, and worst standardized fitness; the complexity * of the best, average, and worst individuals; the depth of the * best, average, and worst individuals; and the diversity of the * population if cfg.TestDiversity is true. If this generation has * been saved to a stream by GPRun's checkpointing facility, the * letter 'c' is printed at the end of the line. * * @param generation the generation number. * @param chk the checkpoint character ('c' or ' '). * @param sout the statistics PrintStream */ public void printStatistics(int generation, char chk, PrintStream sout) { sout.print(formatInt(generation, 4)); sout.print("|"); sout.print(formatDouble(((GP)get(bestOfPopulation)).stdFitness, 10, 2)); sout.print(" "); sout.print(formatDouble(avgFitness, 10, 2)); sout.print(" "); sout.print(formatDouble(((GP)get(worstOfPopulation)).stdFitness, 10, 2)); sout.print("|"); sout.print(formatInt(((GP)get(bestOfPopulation)).length(), 4)); sout.print(" "); sout.print(formatDouble(avgLength, 6, 1)); sout.print(" "); sout.print(formatInt(((GP)get(worstOfPopulation)).length(), 4)); //sout.print(formatDouble(longestLength, 6, 1)); sout.print("| "); sout.print(formatInt(((GP)get(bestOfPopulation)).depth(), 2)); sout.print(" "); sout.print(formatDouble(avgDepth, 4, 1)); sout.print(" "); sout.print(formatInt(((GP)get(worstOfPopulation)).depth(), 2)); if (cfg.TestDiversity) { sout.print("| "); sout.print(formatDouble(1.0-((double)dupCount/containerSize()), 5, 3)); } sout.print(" "); sout.print(chk); sout.println(); } /** * Formats a string that shows the heritage of a crossover, * reproduction, or mutation operation. * * @param len the length of the string to return. * @param index the population index of the parent. * @param tree the branch number in which crossover or * mutation occurred. Branch 0 is converted to * "RPB", branch 1 is converted to "ADF0", and so on. * @param cut the s-expression index at which crossover or * mutation occurred. */ protected String formatParentage(int len, int index, int tree, int cut) { String sIndex; String sTree; String sCut; StringBuffer sb = new StringBuffer(len); int pos = len; for (int i = 0; i < pos; i++) sb.append(' '); if (index >= 0) { sIndex = String.valueOf(index); pos -= sIndex.length(); } else sIndex = ""; if (tree >= 0) { if (tree == 0) sTree = "RPB"; else sTree = "ADF"+(tree-1); pos -= sTree.length(); } else sTree = ""; if ((index >= 0) && (tree >= 0)) pos--; if (cut >= 0) { sCut = String.valueOf(cut); pos -= sCut.length()+1; } else sCut = ""; //transfer substrings to display buffer for (int i = 0; i < sIndex.length(); i++) sb.setCharAt(pos++, sIndex.charAt(i)); if ((index >= 0) && (tree >= 0)) sb.setCharAt(pos++, ':'); for (int i = 0; i < sTree.length(); i++) sb.setCharAt(pos++, sTree.charAt(i)); if (cut >= 0) sb.setCharAt(pos++, ':'); for (int i = 0; i < sCut.length(); i++) sb.setCharAt(pos++, sCut.charAt(i)); return sb.toString(); } /** * Prints details about a particular individual to the specified * PrintStream. The first line shows 'B' if the individual is the * best in its population, or 'W' if it is the worst. The line * goes on to show the population index (num) of the individual, its * reproduction or crossover heritage, its mutation heritage, and * its standardized fitness, complexity, and depth.
* * If showExpression is true, the GP's printOn() method is called * to print the s-expression. If showTree is true, the GP's * printTree() method is called to print the expression in * pseudo-graphic text format. */ public void printIndividual(GP current, int num, boolean showExpression, boolean showTree, PrintStream dout) { if (num == bestOfPopulation) dout.print("B"); else if (num == worstOfPopulation) dout.print("W"); else dout.print(" "); dout.print(formatInt(num, 4)); //display creation, copy, crossover history dout.print(formatParentage(14, current.dadIndex, current.crossTree, current.dadCross)); dout.print(formatParentage(14, current.mumIndex, current.crossTree, current.mumCross)); //display mutation history dout.print(formatParentage(9, -1, current.swapTree, current.swapPos)); dout.print(formatParentage(9, -1, current.shrinkTree, current.shrinkPos)); dout.print(" "+formatDouble(current.stdFitness, 10, 2)); dout.print(" "+formatInt(current.length(), 4)); dout.print(" "+formatInt(current.depth(), 4)); dout.println(); if (showExpression) { dout.println(); current.printOn(dout, cfg); } if (showTree) { dout.println(); current.printTree(dout, cfg); } } /** * Prints details about some or all of the population. It starts by * printing a columnar header, then calls printIndividual() for * all individuals, the best, and/or the worst depending on the * parameters passed to the method. */ public void printDetails(int generation, boolean showAll, boolean showBest, boolean showWorst, boolean showExpression, boolean showTree, PrintStream dout) { if (showAll || showBest || showWorst) { dout.println("========================================================================"); dout.println("Generation:"+generation+" best:"+bestOfPopulation+" worst:"+worstOfPopulation); dout.println(" GP# dad mum oper mut shrk mut fitness len dep"); dout.println("===== ============= ============= ======== ======== ========== ==== ===="); //Bnnnn iiii:adf0:ppp iiii:adf0:ppp adf0:ppp adf0:ppp nnnnnnn.n llll dddd } GP current; if (showAll) for (int i = 0; i < containerSize(); i++) { current = (GP)get(i); printIndividual(current, i, showExpression, showTree, dout); } if (showBest && !showAll) { current = (GP)get(bestOfPopulation); printIndividual(current, bestOfPopulation, showExpression, showTree, dout); } if (showWorst && !showAll) { current = (GP)get(worstOfPopulation); printIndividual(current, worstOfPopulation, showExpression, showTree, dout); } } /** * Loads a GPPopulation from the specified stream. Reads all * of the GPs from the stream, then rebuilds the diversity table and * recalculates the population statistics. Note that GPPopulation * doesn't have a save() method because its superclass GPContainer * does everything that's necessary in its save() method. * * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if the specified class or its null constructor is * not public. * @exception java.io.IOException * if an error occurs while reading the stream. */ protected synchronized void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException { //load population container super.load(is); //recalculate remaining variables buildUniqueGPs(); calculateStatistics(); } /** * Writes every GP in text format to a PrintStream by * simply calling GP.printOn() * for every individual in the population. */ public void printOn(PrintStream os, GPVariables cfg) { for (int i = 0; i < containerSize(); i++) ((GP)get(i)).printOn(os, cfg); } } //used by Hashtable to count duplicates //like java.lang.Integer, but allows value to be changed class GPInteger { private int value; GPInteger() {} GPInteger(int value) { this.value = value; } public int intValue() { return value; } public void setValue(int value) { this.value = value; } public int hashCode() { return value; } public boolean equals(Object obj) { if ((obj != null) && (obj instanceof GPInteger)) return value == ((GPInteger)obj).intValue(); return false; } } //used to track subranges of entire population class GPPopulationRange { public int startIx; public int endIx; public boolean firstSelection; public GPPopulationRange() {} public GPPopulationRange(int startIx, int endIx) { this.startIx = startIx; this.endIx = endIx; firstSelection = true; } //return a random element within the range public int getRandom() { return startIx+GPRandom.nextInt(endIx-startIx); } } OthelloProj/GP/gpjpp/GPProperties.java 100644 5763 134 16524 6506556654 16776 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; import java.util.Enumeration; import java.util.Properties; /** * Extends the standard Properties class. GPProperties fixes mishandling * of tab and space in the load() method of JDK 1.0 (fixed in JDK 1.1). * It makes keynames case-insensitive ala Windows ini files. * And it allows comments at the end of each line, delimited by the * first space, tab, #, or ! character after the value string. * This means that the value string cannot contain any of these * characters, of course, but this does not impose an important * limitation for this package. * * @version 1.0 */ public class GPProperties extends Properties { /** * Creates an empty property set. */ public GPProperties() { super(null); } /** * Creates an empty property set with specified default values. */ public GPProperties(Properties defaults) { super(defaults); } /** * Looks up a property value based on a key. The key is forced * to lowercase before calling Properties.getProperty. */ public String getProperty(String key) { return super.getProperty(key.toLowerCase()); } /** * Loads a property set from an InputStream. This completely * replaces Properties.load() with the following differences: * fixes bugs in handling embedded tab and space characters * in JDK 1.0; terminates the value string with the first * space, tab, !, or # character, treating the rest of the * line as a comment; and forces key strings to lowercase * before adding them to the property table. * * @exception IOException * if an error occurs while reading the stream. */ public synchronized void load(InputStream in) throws IOException { //deprecated in JDK 1.1, but JDK 1.1 still uses it! in = Runtime.getRuntime().getLocalizedInputStream(in); int ch = in.read(); while (true) { //skip comments switch (ch) { case -1: return; case '#': case '!': do { ch = in.read(); } while ((ch >= 0) && (ch != '\n') && (ch != '\r')); continue; case '\n': case '\r': case ' ': case '\t': ch = in.read(); continue; } // Read the key StringBuffer key = new StringBuffer(); while ((ch >= 0) && (ch != '=') && (ch != ':') && (ch != ' ') && (ch != '\t') && (ch != '\n') && (ch != '\r')) { key.append((char)ch); ch = in.read(); } //skip space to = while ((ch == ' ') || (ch == '\t')) //!! krk 970422 ch = in.read(); //skip = if ((ch == '=') || (ch == ':')) ch = in.read(); //skip space after = while ((ch == ' ') || (ch == '\t')) //!! krk 970422 ch = in.read(); // Read the value StringBuffer val = new StringBuffer(); readval: while ((ch >= 0) && (ch != '\n') && (ch != '\r')) { switch (ch) { //value terminated by any of these comment delimiters case '#': case '!': case ' ': case '\t': //skip to end of line do { ch = in.read(); } while ((ch >= 0) && (ch != '\n') && (ch != '\r')); break readval; case '\\': //interpret escapes switch (ch = in.read()) { case '\r': if (((ch = in.read()) == '\n') || (ch == ' ') || (ch == '\t')) { // fall thru to '\n' case } else continue; case '\n': while (((ch = in.read()) == ' ') || (ch == '\t')); continue; case 't': ch = '\t'; break; case 'n': ch = '\n'; break; case 'r': ch = '\r'; break; case 'u': { while ((ch = in.read()) == 'u'); int d = 0; loop: for (int i = 0 ; i < 4 ; i++, ch = in.read()) { switch (ch) { case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': d = (d << 4) + ch - '0'; break; case 'a': case 'b': case 'c': case 'd': case 'e': case 'f': d = (d << 4) + 10 + ch - 'a'; break; case 'A': case 'B': case 'C': case 'D': case 'E': case 'F': d = (d << 4) + 10 + ch - 'A'; break; default: break loop; } } ch = d; } } break; } //switch (ch) val.append((char)ch); ch = in.read(); } //System.out.println(key + " = '" + val + "'"); put(key.toString().toLowerCase(), val.toString()); } } /** * Writes the contents of the properties to System.out. For * testing and debugging. */ public void show() { for (Enumeration e = propertyNames(); e.hasMoreElements();) { String key = (String)e.nextElement(); String val = (String)getProperty(key); System.out.println(key+"="+val); } } } OthelloProj/GP/gpjpp/GPGenePrint.java 100644 5763 134 61477 6506556654 16544 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; import java.awt.Graphics; /** * Formats a gene tree for printing in graphic or pseudo-graphic * format. GPGenePrint extends GPGene to add an x position which * it computes by spreading out the nodes of the tree just enough * to prevent them from overlapping at all levels of the tree. * Note that GPGenePrint formats just a single branch of a * complete GP, which would frequently be too wide to print * on standard paper.
* * The three key methods of the class are the constructor, * GPGenePrint(GPGene), * which clones a GPGene tree onto a new tree with the extra fields, * printOn(), * which prints the tree in pseudo-graphic format to a PrintStream, and * drawOn(), * which prints the tree as a true graphic gif file.
* * Several static public fields of the class can be used to * adjust the appearance of the tree: * xMargin, * xSpacing, * rectMargin, * arcRadius, * rowsPerNode. * * @version 1.0 */ public class GPGenePrint extends GPGene { /** * The number of blank columns printed at the left edge of the * tree by printOn(). Default 2. */ public static double xMargin = 2.0; /** * The minimum number of columns (character widths) that separate * adjacent nodes. Default 3. */ public static double xSpacing = 3.0; /** * The number of pixels separating the node rectangle from the * node text that it surrounds in a graphic tree. Default 2. */ public static int rectMargin = 2; /** * The pixel radius of the arc at each corner of a node rectangle. * Default 10. */ public static int arcRadius = 10; /** * The number of character heights per node level in a graphic * tree. Default 3. */ public static int rowsPerNode = 3; /** * The computed x position of this node, in character units. The * number is non-negative when the algorithm is finished. * It is a floating point number that is rounded to integer * columns by printOn() and converted to integer pixels by * drawOn(). */ protected double x; /** * A reference to the original gene of which the GPGenePrint * object is an extended copy. The purpose for peer is to * call methods in a user subclass of GPGene. Specifically, * GPGenePrint calls the * geneRep() method of * GPGene to get the string representation of each node. * When the gene represents a randomly generated constant, * geneRep() can return the constant value instead of the generic * representation of the node type. * See the Lawnmower problem for an example. */ protected GPGene peer; /** * This constructor clones the specified gene and all its * children, creating a parallel tree composed of GPGenePrint * nodes. Each GPGenePrint node contains an x coordinate, * initially 0.0, and a reference to the original gene. */ GPGenePrint(GPGene gpo) { //x = 0.0; peer = gpo; node = gpo.node; reserveSpace(gpo.containerSize()); //make a copy of all container objects of gpo for (int i = 0; i < containerSize(); i++) if (gpo.container[i] == null) put(i, null); else put(i, new GPGenePrint((GPGene)gpo.container[i])); } /** * Disables the cloning operation inherited from GPGene, * since GPGenePrint does not need to be cloned. This * version of clone() always returns null. */ protected synchronized Object clone() { return null; } /** * Returns a code identifying the class. GPGenePrint is * not stored in streams, but it is given the unique code * GENEPRINTID just for completeness. */ public byte isA() { return GENEPRINTID; } /** * Disables the load operation inherited from GPGene, since * GPGenePrint does not need to be streamed. This version * of load() does nothing. */ protected synchronized void load(DataInputStream is) { } /** * Disables the save operation inherited from GPGene, since * GPGenePrint does not need to be streamed. This version * of save() does nothing. */ protected void save(DataOutputStream os) { } /** * Returns the length of the node representation string in * characters. * * @see gpjpp.GPGenePrint#peer */ protected double getNodeWidth() { return peer.geneRep().length(); } /** * Returns the x coordinate of the right edge of the node * text in characters. */ protected double getNodeRight() { return x+getNodeWidth()-1.0; } /** * Returns the minimum width of the arguments to this node * taking into account the node width of each argument and the * minimum spacing between nodes, * xSpacing. */ protected double calcPackedContainerWidth() { double width = 0.0; for (int i = 0; i < containerSize(); i++) width += ((GPGenePrint)get(i)).getNodeWidth()+xSpacing; //don't include trailing space return width-xSpacing; } /** * Returns the x coordinate of the horizontal center of the * arguments to this node at their current positions. */ protected double calcContainerCenter() { if (containerSize() == 0) //return node's own center return (x+getNodeRight())/2.0; GPGenePrint current = (GPGenePrint)get(0); double leftX = current.x; double rightX = current.getNodeRight(); for (int i = 1; i < containerSize(); i++) { current = (GPGenePrint)get(i); if (current.x < leftX) leftX = current.x; double curX = current.getNodeRight(); if (curX > rightX) rightX = curX; } //doesn't include trailing space return (rightX+leftX)/2.0; } /** * Calculates the x coordinates of all the nodes below this * level assuming that all can be packed to minimum spacing * and each container is centered under its parent. This is * a first-order approximation to the final position but * generally leads to overlaps between adjacent node groups. * The x coordinate of this node must be initialized before * calling calcPackedPos(). * * @param minX an array holding the minimum x coordinate * at each level of the tree. This array is * updated for every node that is processed here. * @param curDepth the current node depth, where the root of * the tree is depth 0. */ protected void calcPackedPos(double[] minX, int curDepth) { //update minX at this depth if (x < minX[curDepth]) minX[curDepth] = x; //done if it's a terminal if (containerSize() == 0) return; //nodes contained in this gene are centered under it double leftX = (x+getNodeRight()-calcPackedContainerWidth())/2.0; //place the children for (int i = 0; i < containerSize(); i++) { GPGenePrint current = (GPGenePrint)get(i); current.x = leftX; leftX += current.getNodeWidth()+xSpacing; //place the children's children current.calcPackedPos(minX, curDepth+1); } } /** * Adjusts the x coordinate of this node and its children whenever * the node overlaps the region of the node to its left. This * spreads the nodes to the right just enough to get rid of * overlaps. Two additional adjustments are also made: terminal * nodes dangling at more than minimum spacing to the left or * right of their node groups are tightened to minimum spacing; * and parent nodes are recentered over their children after * the other adjustments have been made.
* * This method is called repeatedly until no further adjustments * are needed or an iteration limit is reached. * * @param minX an array holding the minimum x coordinate * at each level of the tree. This array is * updated for every node that is processed here. * @param curX an array holding the largest x coordinate * used by a node at each depth level so far. This * allows the detection of overlaps. * @param curDepth the current node depth, where the root of * the tree is depth 0. * @return true if the position of any node was adjusted. */ protected boolean adjustOverlaps( double[] minX, double[] curX, int curDepth) { boolean ret; if (x < curX[curDepth]) { //node overlaps one to its left, move it and its children right shiftX(x-curX[curDepth]); ret = true; } else ret = false; //move past this node at this depth curX[curDepth] = getNodeRight()+xSpacing; //check children for (int i = 0; i < containerSize(); i++) { GPGenePrint current = (GPGenePrint)get(i); ret |= current.adjustOverlaps(minX, curX, curDepth+1); if (i < containerSize()-1) { //look for terminals dangling to the left if (current.containerSize() == 0) { double nextX = ((GPGenePrint)get(i+1)).x; if (nextX-current.getNodeRight() > xSpacing) { current.x = nextX-current.getNodeWidth()-xSpacing; ret = true; } } } else if (i > 0) { //look for terminals dangling to the right if (current.containerSize() == 0) { double prevX = ((GPGenePrint)get(i-1)).getNodeRight(); if (current.x-prevX > xSpacing+1.0) { current.x = prevX+xSpacing+1.0; ret = true; } } } } //recenter node for shifts in its children double newX = calcContainerCenter()-getNodeWidth()/2.0; if (Math.abs(newX-x) > 0.01) { x = newX; ret = true; if (x < minX[curDepth]) minX[curDepth] = x; } //return true if any node in tree required adjustment return ret; } /** * Spreads terminal nodes so that they are equally spaced within * the boundaries of the container. */ protected void spreadTerminals() { //done if it's a terminal if (containerSize() == 0) return; //space out terminals within constraints int left = 0; for (int i = 1; i < containerSize(); i++) { GPGenePrint current = (GPGenePrint)get(i); if ((i == containerSize()-1) || (current.containerSize() != 0)) { //found a region of fixed positions int spaceCount = i-left; if (spaceCount > 1) { //there's at least one terminal to space out double insideLeft = ((GPGenePrint)get(left)).getNodeRight(); double freeSpace = ((GPGenePrint)get(i)).x-insideLeft; for (int j = left+1; j < i; j++) freeSpace -= ((GPGenePrint)get(j)).getNodeWidth(); //divide free space into equal parts freeSpace /= spaceCount; //place inside nodes at this spacing for (int j = left+1; j < i; j++) { insideLeft += freeSpace; GPGenePrint currentj = (GPGenePrint)get(j); currentj.x = insideLeft; insideLeft += currentj.getNodeWidth(); } } //prepare for another region left = i; } } //do the same for children for (int i = 0; i < containerSize(); i++) ((GPGenePrint)get(i)).spreadTerminals(); } /** * Returns the smallest x value anywhere in the tree. */ protected double calcMinX() { return calcMinX(x); } /** * Returns the smallest x value anywhere in the tree. */ protected double calcMinX(double minSoFar) { if (x < minSoFar) minSoFar = x; for (int i = 0; i < containerSize(); i++) { double d = ((GPGenePrint)get(i)).calcMinX(minSoFar); if (d < minSoFar) minSoFar = d; } return minSoFar; } /** * Returns the largest x value anywhere in the tree. */ protected double calcMaxX() { return calcMaxX(getNodeRight()); } /** * Returns the largest x value anywhere in the tree. */ protected double calcMaxX(double maxSoFar) { double right = getNodeRight(); if (right > maxSoFar) maxSoFar = right; for (int i = 0; i < containerSize(); i++) { double d = ((GPGenePrint)get(i)).calcMaxX(maxSoFar); if (d > maxSoFar) maxSoFar = d; } return maxSoFar; } /** * Shifts the x coordinates of all nodes by subtracting dx. */ protected void shiftX(double dx) { x -= dx; for (int i = 0; i < containerSize(); i++) ((GPGenePrint)get(i)).shiftX(dx); } /** * Calculates the x coordinates of all nodes so that none * overlap, otherwise-unconstrained nodes are evenly spaced, * and parent nodes are centered over their children as much * as possible. The minimum x value is 0.0 upon return. * * @return the depth of the tree. */ protected int calcXPositions() { //create array to hold minimum x position at each level of tree int dep = depth(); double[] minX = new double[dep]; //root node is centered at x = 0 x = -getNodeWidth()/2.0; //compute ideal position of each node, fill in min x at each level calcPackedPos(minX, 0); //spread out nodes to avoid overlaps double[] curX = new double[dep]; int maxTries = 2*dep; //maximum tries in case of non-convergence do { for (int i = 0; i < dep; i++) curX[i] = minX[i]; } while (adjustOverlaps(minX, curX, 0) && (maxTries-- > 0)); //equally space non-edge terminals within their containers spreadTerminals(); //find minimum value of x and shift all x values to 0.0 or greater shiftX(calcMinX()); return dep; } /** * Prints spaces until curX[curDepth] equals or exceeds rx. */ protected void spaceTo( PrintStream os, int curDepth, double[] curX, double rx) { while (curX[curDepth] < rx) { os.print(' '); curX[curDepth] += 1.0; } } /** * Prints all nodes at level depToPrint in left-to-right order. * This forms one line of pseudo-graphic output. */ protected void printLevel(PrintStream os, int depToPrint, int curDepth, double[] curX) { if (depToPrint == curDepth) { spaceTo(os, curDepth, curX, Math.rint(x)); os.print(peer.geneRep()); curX[curDepth] += getNodeWidth(); } else { for (int i = 0; i < containerSize(); i++) ((GPGenePrint)get(i)).printLevel(os, depToPrint, curDepth+1, curX); } } /** * Prints pseudo-graphic connectors between nodes at * level depToPrint and nodes at level depToPrint+1. */ protected void printConnectors(PrintStream os, int depToPrint, int curDepth, double[] curX) { if (depToPrint == curDepth) { //does it need connectors to a deeper level? if (containerSize() != 0) { //compute left, right, center of this node double lx = Math.rint(x); double rx = Math.rint(getNodeRight()); double cx = Math.rint((lx+rx)/2.0); for (int i = 0; i < containerSize(); i++) { GPGenePrint current = (GPGenePrint)get(i); //compute left and right of child node double clx = Math.rint(current.x); double crx = Math.rint(current.getNodeRight()); //compute character and position for connector double conx; char conCh; if (((conx = cx) >= clx) && (cx <= crx)) conCh = '|'; else if (((conx = rx+1.0) >= (clx-1.0)) && (conx <= crx)) conCh = '\\'; else if (((conx = lx-1.0) <= (crx+1.0)) && (conx >= clx)) conCh = '/'; else if (clx > rx) { conx = clx-1.0; conCh = '\\'; } else { conx = crx+1.0; conCh = '/'; } //print connector spaceTo(os, curDepth, curX, conx); os.print(conCh); curX[curDepth] += 1.0; } } } else { for (int i = 0; i < containerSize(); i++) ((GPGenePrint)get(i)).printConnectors(os, depToPrint, curDepth+1, curX); } } /** * Computes the x coordinates for all nodes in this gene tree * and writes the tree in pseudo-graphic format to the * specified PrintStream. None of the configuration variables * in cfg are used by default. */ public void printOn(PrintStream os, GPVariables cfg) { //fill in the x field of all nodes int dep = calcXPositions(); //print all depths, row by row double[] curX = new double[dep]; for (int d = 0; d < dep; d++) { //print the node names curX[d] = 0.0; spaceTo(os, d, curX, xMargin); curX[d] = 0.0; printLevel(os, d, 0, curX); os.println(); //print the connectors if (d < dep-1) { //no connectors below final level curX[d] = 0.0; spaceTo(os, d, curX, xMargin); curX[d] = 0.0; printConnectors(os, d, 0, curX); os.println(); } } } //following for drawing graphics version of tree /** * Converts the x coordinate of a node to the corresponding * x pixel position for the start of the node text. */ protected final int xText(GPDrawing ods, double x) { return (int)Math.round(ods.cw*x)+rectMargin; } /** * Converts the depth of a node to the corresponding y pixel * position for the node text. */ protected final int yText(GPDrawing ods, int depth) { return (rowsPerNode*depth*ods.ch)+ods.as+rectMargin; } /** * Converts the x coordinate of a node to the corresponding * x pixel position for the left edge of the surrounding * node rectangle. */ protected final int xBox(GPDrawing ods, double x) { return xText(ods, x)-rectMargin; } /** * Converts the depth of a node to the corresponding * y pixel position for the top edge of the surrounding * node rectangle. */ protected final int yBox(GPDrawing ods, int depth) { return rowsPerNode*depth*ods.ch; } /** * Computes the pixel width of the node rectangle given * the string to appear within the rectangle. */ protected final int wBox(GPDrawing ods, String nodeName) { return ods.stringWidth(nodeName)+2*rectMargin; } /** * Computes the pixel height of the node rectangle. */ protected final int hBox(GPDrawing ods) { return ods.ch+2*rectMargin; } /** * Draws all the nodes recursively starting with this one, * including each node's text, a rounded rectangle surrounding it, * and connectors to all of its children. */ protected void drawGifNode(GPDrawing ods, int curDepth) { //compute important coordinates int xt = xText(ods, x); int yt = yText(ods, curDepth); int xb = xBox(ods, x); int yb = yBox(ods, curDepth); int wb = wBox(ods, peer.geneRep()); int pxc = xb+wb/2; int hb = hBox(ods); int pyb = yb+hb; int cyb = yBox(ods, curDepth+1); //draw node name with a box around it ods.getGra().drawString(peer.geneRep(), xt, yt); ods.getGra().drawRoundRect(xb, yb, wb, hb, arcRadius, arcRadius); for (int i = 0; i < containerSize(); i++) { GPGenePrint current = (GPGenePrint)get(i); //draw connector to child int cxc = xBox(ods, current.x)+wBox(ods, current.peer.geneRep())/2; ods.getGra().drawLine(pxc, pyb, cxc, cyb); //draw child current.drawGifNode(ods, curDepth+1); } } /** * Computes the x coordinates for all nodes in this gene tree * and writes the tree in gif format to the specified file. * * @param ods a surface to draw on. * @param fname the name of a gif file to create. * @param title a title to draw on the image, usually "RPB", * "ADF0", etc. The title is always placed on the * first row of the drawing, to the left of the root * node if possible, otherwise at the right edge * of the image. * @param cfg a set of global configuration variables. Only the * * TreeFontSize variable is used here, to set the font * size for text within the image. */ public void drawOn(GPDrawing ods, String fname, String title, GPVariables cfg) throws IOException { //fill in the x field of all nodes int dep = calcXPositions(); double maxX = calcMaxX(); //set the font size in the image ods.setFontSize(cfg.TreeFontSize); //determine optimum image size int w = xText(ods, maxX+1.0)+rectMargin+1; int h = yBox(ods, dep-1)+hBox(ods)+1; //adjust width to fit title if needed int xb = 0; int sw = 0; boolean haveTitle = (title != null) && (title.length() != 0); if (haveTitle) { xb = xBox(ods, x); sw = ods.stringWidth(title)+5; int wb = wBox(ods, peer.geneRep()); if ((xb <= sw) && (xb+wb+sw > w)) w = xb+wb+sw; } //prepare drawing surface of needed size ods.prepImage(w, h); //write the title to the image if (haveTitle) { if (xb > sw) ods.getGra().drawString(title, xText(ods, 0.0), yText(ods, 0)); else ods.getGra().drawString(title, w-sw+5, yText(ods, 0)); } //write the tree to the image drawGifNode(ods, 0); //write the image to a file ods.writeGif(fname); } } OthelloProj/GP/gpjpp/GPRun.java 100644 5763 134 105140 6506556654 15417 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; import java.util.Properties; import java.util.Random; /** * Abstract class that encapsulates the details of running a * genetic programming test in a Java console application.
* * The user must override two methods of this class: createNodeSet(), * which defines the branch structure and the node types used in * each branch of each tree; and createPopulation(), which creates * an instance of a user-defined subclass of GPPopulation.
* * It is common to override another method of this class: * createVariables(), which creates an instance of GPVariables with * the default configuration parameters for the run. Frequently you * may need to add problem-specific configuration variables (the size * of an ant trail, e.g.), which is best done by subclassing * GPVariables and overriding createVariables() to create an instance * of your own class.
* * GPRun then handles numerous details of managing a test run. These * include:
* * 1. Initializing the random number generator used by gpjpp.
* * 2. Reading a configuration file so that most properties of the * test run can be adjusted without recompiling. Also creates * a default configuration file if the named one isn't found.
* * 3. Creating output files for run statistics and detailed * population reporting.
* * 4. Registering all necessary classes with the stream manager.
* * 5. Trapping all exceptions to report a detailed stack trace * in case of error.
* * 6. Loading a previous checkpoint stream if found, or creating * an initial population of individuals.
* * 7. Displaying status output to the console window and also * printing configurable output to report files.
* * 8. Streaming a checkpoint file after a configurable number of * generations in case a long run needs to be interrupted.
* * 9. Running a configurable number of generations and terminating * the run when a configurable fitness target is reached.
* * 10.Writing configurable reports on the best individual at the * end of a run, including graphic images of its tree structure * and possibly its fitness performance (such as the trail of * an ant or a lawnmower).
* * 11.Running multiple runs until a configurable number of good * runs is found, and timing each run's performance.
* * GPRun is divided into a number of reasonably small routines so * that additional aspects of its behavior can be customized by * creating a subclass. Nevertheless, it is not suitable for * writing applets or other graphics-intensive Java applications. * These could be written by using the lower level classes of gpjpp * directly, since these classes enforce no user interface of their own.
*
* @version 1.0
*/
public abstract class GPRun {
/**
* An ID code written at the end of checkpoint streams. This
* is primarily useful for checking to see whether a stream
* was fully flushed in the event of a machine crash.
*/
protected static final int RUNENDID = 0x87654321;
/**
* The size in bytes of the output buffer used for PrintStreams.
* These streams are flushed at the end of every line, so
* there is little point in using a larger buffer.
*/
protected static int outBufSize = 128; //buffer for GPPrintStreams
/**
* The size in bytes of the input or output buffer used for a
* DataInputStream or a DataOutputStream during checkpoint
* loading or saving. A reasonably large buffer provides better
* performance, since these streams are composed of very many
* small data items.
*/
protected static int stmBufSize = 4096; //buffer for DataIOStreams
/**
* The base name for all input and output files used in the
* run. To get the configuration file name, ".ini" is appended
* to baseName. To get the statistics file name, ".stc" is
* appended to baseName. To get the detailed population file
* name, ".det" is appended to baseName. To get the checkpoint
* file name, ".stm" is appended to baseName. This field is
* passed as a parameter to the GPRun constructor.
*/
protected String baseName;
/**
* The configuration variables used for the run. The instance is
* created by the createVariables() abstract method. Its values
* are assigned from the configuration file (baseName+".ini") if
* found.
*/
protected GPVariables cfg;
/**
* The branch and node definitions for all the GPs used during
* the run.
*/
protected GPAdfNodeSet adfNs;
/**
* The PrintStream used for the detailed population output file.
* If cfg.PrintDetails is false, this field is null and the
* report file is not created.
*/
protected GPPrintStream dout;
/**
* The PrintStream used for statistics and summary reporting.
* This file (baseName+".stc") is always created. It includes
* a list of the configuration parameters, a list of the
* branch and node definitions, the printStatistics output for
* each generation, timing per run and per generation,
* and a report on the best individual at the
* end of each run. In case a run is restarted from a checkpoint,
* additional output is appended to the existing statistics file
* if found.
*/
protected GPPrintStream sout;
/**
* The main population, instantiated in GPRun() and reused
* repeatedly in run().
*/
protected GPPopulation pop;
/**
* The secondary population. If cfg.SteadyState is true, newPop
* is not used and remains null. Otherwise each new generation
* is created in the run() method by calling pop.generate(newPop).
* Then the newPop and pop references are swapped to proceed with
* the next generation.
*/
protected GPPopulation newPop;
/**
* The current generation number. It starts with 0 for the
* initial population and increments to cfg.NumberOfGenerations.
* When restarted from a checkpoint, the run starts again from
* the last generation that was checkpointed.
*/
protected int curGen;
/**
* The current run number.
*/
protected int curRun;
/**
* The number of good runs found so far. A good run is one
* where the best individual's fitness becomes less than
* cfg.TerminationFitness.
*/
protected int goodRuns;
/**
* The number of generations until the next checkpoint will be stored.
* If cfg.CheckpointGens is 0, this field is not used. Otherwise
* it is initialized to cfg.CheckpointGens and decremented after
* each generation.
*/
protected int cntGen;
//==== abstract methods ====
/**
* Returns a properly initialized instance of GPAdfNodeSet,
* containing the branch and node definitions for this problem.
* You must override this method to create your own set of
* functions and terminals. Your version can create a different
* node set depending on whether cfg.UseADFs is true or false.
* createNodeSet() can also refer to other user-defined
* configuration parameters when cfg is a subclass of GPVariables
* to further customize the node set to the problem configuration.
*/
abstract protected GPAdfNodeSet createNodeSet(GPVariables cfg);
/**
* You must override this method to return a new instance
* of a user subclass of GPPopulation. The user subclass must
* at least override the createGP() method of GPPopulation
* to create instances of a user subclass of GP. If the
* configuration does not specify a steady state population,
* createPopulation() is called twice; otherwise it is called
* just once regardless of the number of generations or runs.
*/
abstract protected GPPopulation createPopulation(GPVariables cfg,
GPAdfNodeSet adfNs);
//==== remaining methods are not abstract ====
/**
* This constructor allocates the basic data structures and
* prepares for a run. GPRun() traps all exceptions. If it
* catches one, it dumps a stack trace and calls System.exit(1).
*
* @param baseName specifies the base file name for
* the run's configuration file, output files,
* and stream file.
* @param createDefaultIni if true, and if baseName+".ini"
* is not found, GPRun creates a configuration file
* holding the default configuration values.
*/
public GPRun(String baseName, boolean createDefaultIni) {
//trap all exceptions to report details
try {
if (baseName.toLowerCase().endsWith(".ini"))
//strip .ini from baseName (common error by this author)
this.baseName = baseName.substring(0, baseName.length()-4);
else
this.baseName = baseName;
//create random number generator used by algorithm
GPRandom.setGenerator(createRandomGenerator());
//create configuration class
cfg = createVariables();
//read configuration parameters
readIni(this.baseName+".ini", createDefaultIni);
//create the function and terminal descriptions
adfNs = createNodeSet(cfg);
//make population instances; individuals aren't created until run()
pop = createPopulation(cfg, adfNs);
if (!cfg.SteadyState)
newPop = createPopulation(cfg, adfNs);
//open output files
boolean append = (getCheckpointFile() != null);
sout = createOrAppend(getStatisticsName(), append);
if (cfg.PrintDetails)
dout = createOrAppend(getDetailName(), append);
else
dout = null;
//register all user and gpjpp classes for streaming
//also creates node type index used to stream genes
registerAllClasses();
} catch (Exception e) {
//provide details on any exceptions thrown and halt
e.printStackTrace();
System.exit(1);
}
}
/**
* The main method of GPRun creates and evolves populations,
* writes reports, loads and saves checkpoint files, and does
* multiple runs until a configurable number of good ones is
* found. run() traps all exceptions. If it catches one,
* it dumps a stack trace and calls System.exit(1). run() calls
* a number of small methods for reporting output to the console
* and to files; these can be overridden to make small changes
* to its behavior. However, most changes are accomplished by
* modifying the configuration file that controls the run.
*/
protected void run() {
//trap all exceptions to report details
try {
curGen = 0;
curRun = 1;
goodRuns = 0;
cntGen = cfg.CheckpointGens;
//load checkpoint if available
boolean loadedCheckpoint = loadCheckpoint();
if (!loadedCheckpoint)
showConfiguration();
//do runs until some that reach terminating fitness are found
do {
//display run number
showRunNumber(curRun, goodRuns);
//time the run
long timeStart = System.currentTimeMillis();
if (loadedCheckpoint)
//create population next run through
loadedCheckpoint = false;
else {
//create initial population
showCreation(true);
pop.create();
showCreation(false);
}
//show initial generation
showGeneration(true, curGen, false);
//time the generations
long timeGenStart = System.currentTimeMillis();
int gens = 0;
boolean goodRun = false;
//loop through the generations
while (curGen < cfg.NumberOfGenerations) {
//create next generation
curGen++;
gens++;
pop.generate(newPop);
if (!cfg.SteadyState) {
//swap the pops
GPPopulation tmp = pop;
pop = newPop;
newPop = tmp;
//ensure no references remain to obsolete GPs
//newPop.clear();
}
//checkpoint this generation's population
boolean savedCheckpoint = saveCheckpoint();
//show this generation
showGeneration(false, curGen, savedCheckpoint);
goodRun = (pop.bestFitness < cfg.TerminationFitness);
if (goodRun) {
//break if terminating fitness found
goodRuns++;
break;
}
}
//read time for generation rate
long timeGenStop = System.currentTimeMillis();
//report on final generation
showFinalGeneration(curGen, goodRun);
//compute and display run timing
long timeStop = System.currentTimeMillis();
double secsTotal = (timeStop-timeStart)/1000.0;
double secsPerGen;
if (gens > 0)
secsPerGen = (timeGenStop-timeGenStart)/(1000.0*gens);
else
secsPerGen = 0.0;
showTiming(secsTotal, secsPerGen);
//erase final stream file of run
if (cfg.CheckpointGens > 0)
(new File(getCheckpointName())).delete();
//update counters for next run
curRun++;
curGen = 0;
cntGen = cfg.CheckpointGens;
} while (goodRuns < cfg.GoodRuns);
//close output files
sout.close();
if (cfg.PrintDetails)
dout.close();
} catch (Exception e) {
System.err.println();
System.err.println();
e.printStackTrace();
System.exit(1);
}
}
/**
* Returns a valid instance of GPVariables. Override to create
* an instance of a subclass of GPVariables that contains
* problem-specific variables as well.
*/
protected GPVariables createVariables() {
return new GPVariables();
}
/**
* Returns a valid instance of Random used to generate
* all random numbers throughout the package. The default
* implementation uses the current time to seed the
* generator.
*/
protected Random createRandomGenerator() {
return new Random();
}
/**
* Reads the specified file to get run configuration variables.
* Calls GPProperties.load() to interpret the file. If the
* file is not found and createDefaultIni is true, readIni()
* creates a new file and writes the current values of cfg
* to this file using GPVariables.printOn.
*
* @see gpjpp.GPProperties#load
* @see gpjpp.GPVariables#printOn
*/
protected void readIni(String iniName, boolean createDefaultIni)
throws IOException {
try {
FileInputStream propf = new FileInputStream(iniName);
GPProperties prop = new GPProperties();
prop.load(propf);
propf.close();
cfg.load(prop);
} catch (FileNotFoundException e) {
//.ini file not found, use defaults
if (createDefaultIni)
try {
//create ini file for next time
dout = new GPPrintStream(
new FileOutputStream(iniName), true);
cfg.printOn(dout, cfg);
dout.close();
} catch (Exception f) {
throw new Error("Can't create "+iniName);
}
}
}
/**
* Creates or appends to a specified file and returns a valid
* reference to a GPPrintStream for that file. If append is true and
* fname exists, createOrAppend() renames fname to "tmp.tmp",
* opens tmp.tmp for reading, creates fname anew, copies tmp.tmp
* to fname, deletes tmp.tmp, and leaves fname open for writing.
* Otherwise, createOrAppend() creates fname, overwriting any
* existing file of that name without warning.
*/
protected GPPrintStream createOrAppend(String fname, boolean append)
throws IOException {
FileOutputStream os = null;
if (append) {
File f = new File(fname);
if (f.exists()) {
//delete temporary file if it exists
File nf = new File("tmp.tmp");
if (nf.exists())
nf.delete();
//rename fname to temp name
f.renameTo(nf);
//open old file for input
FileInputStream is = new FileInputStream(nf);
//create output file
os = new FileOutputStream(fname);
//copy input to output
byte[] buf = new byte[4096];
int len;
while ((len = is.read(buf)) != -1)
os.write(buf, 0, len);
//close and delete old file
is.close();
nf.delete();
}
}
if (os == null)
//create new file
os = new FileOutputStream(fname);
return new GPPrintStream(
new BufferedOutputStream(os, outBufSize), true);
}
/**
* Prints a string to System.out and also to sout.
*/
protected void echoPrint(String dispStr) {
System.out.println(dispStr);
sout.println(dispStr);
}
/**
* Prints the configuration variables and the node definitions
* to sout.
*/
protected void showConfiguration() {
//print configuration parameters
cfg.printOn(sout, cfg);
sout.println();
//print tree descriptions
adfNs.printOn(sout, cfg);
sout.println();
}
/**
* Prints the current run number and number of good runs
* so far to System.out, sout, and dout.
*/
protected void showRunNumber(int curRun, int goodRuns) {
echoPrint("");
String dispStr =
"Run number "+curRun+" (good runs "+goodRuns+")";
echoPrint(dispStr);
if (cfg.PrintDetails)
dout.println(dispStr);
}
/**
* Prints a status message to System.out while the initial
* population is being created. When the population is done,
* finishes the status message and writes to System.out and
* sout the number of individuals that were rejected
* because they were too complex or were duplicates.
*/
protected void showCreation(boolean preCreation) {
if (preCreation) {
System.out.print("Creating initial population... ");
} else {
System.out.println("Ok");
echoPrint("Too complex "+pop.attemptedComplexCount);
if (cfg.TestDiversity)
echoPrint("Duplicate "+pop.attemptedDupCount);
sout.println();
}
}
/**
* Returns the symbols displayed in the statistical display
* when a checkpoint is finished or skipped. The default
* implementation returns 'c' for a checkpoint and ' ' for
* no checkpoint.
*/
protected char checkChar(boolean savedCheckpoint) {
return savedCheckpoint? 'c' : ' ';
}
/**
* Prints information to System.out and to sout about the
* generation just completed. GPPopulation.printStatisticsLegend()
* is called if showLegend is true. GPPopulation.printStatistics()
* is always called. GPPopulation.printDetails() is called only
* if cfg.PrintDetails is true and it prints to dout.
*/
protected void showGeneration(boolean showLegend,
int curGen, boolean savedCheckpoint) {
if (showLegend) {
pop.printStatisticsLegend(System.out);
pop.printStatisticsLegend(sout);
}
pop.printStatistics(curGen, checkChar(savedCheckpoint), System.out);
pop.printStatistics(curGen, checkChar(savedCheckpoint), sout);
if (cfg.PrintDetails) {
//print details about this generation
pop.printDetails(curGen,
cfg.PrintPopulation, //showAll
true, //showBest
true, //showWorst
cfg.PrintExpression, //showExpression
false, //showTree
dout);
}
}
/**
* Prints information about the final generation of a run.
* Calls GPPopulation.printDetails to write information about the
* run's best individual to sout. If cfg.PrintTree is true,
* a GPDrawing drawing surface is created and GP.drawOn is
* called to draw the best individual's trees to gif files.
* These files are named as follows:
* baseName+curRun+branchName+".gif"
* where branchName is "RPB" for the result-producing branch
* and "ADFn" for the ADF branches, or "" for single-branch trees.
* * For some Java implementations, Microsoft J++ in particular, * the console window loses focus temporarily while the * off-screen drawing window is active. Focus is returned to * the previous window once drawing is complete. The same * behavior is not seen for the Sun virtual machine running * under Windows 95. * * @param curGen the final generation number, which * can be cfg.NumberOfGenerations or less. * @param goodrun true if the best individual's fitness was less * than cfg.TerminationFitness. * * @exception java.io.IOException * if an I/O error occurs while writing gif files. */ protected void showFinalGeneration(int curGen, boolean goodRun) throws IOException { //print details about best individual of run sout.println(); pop.printDetails(curGen, false, //showAll true, //showBest false, //showWorst cfg.PrintExpression, //showExpression cfg.PrintTree, //showTree sout); if (cfg.PrintTree) { System.out.print("Drawing best individual... "); //get a drawing surface (may grab focus from console window) GPDrawing ods = new GPDrawing(); //make gif files of the best individual found //user can override GP.drawOn to print a trail or // other problem-specific graphic too ((GP)pop.get(pop.bestOfPopulation)).drawOn( ods, baseName+curRun, cfg); //return system resources (return focus to console window) ods.dispose(); System.out.println("Ok"); } } /** * Print to System.out and to sout the total elapsed seconds for * a run and also the number of seconds to process each generation. * The latter figure does not include time spent creating the * initial population or printing details about the final * generation. */ protected void showTiming(double elapsedSecs, double secsPerGen) { echoPrint("Run time "+ GPPopulation.trimFormatDouble(elapsedSecs, 9, 2)+" seconds, "+ GPPopulation.trimFormatDouble(secsPerGen, 9, 2)+" seconds/generation"); sout.println(); } /** * Registers with the GPObject stream manager all classes * needed for checkpointing. Does nothing if cfg.CheckpointGens * is 0 or less. Also creates the node index used to store the * multitudinous genes efficiently on the stream. * * @exception java.lang.IllegalAccessException * if any registered class or null constructor is * not public. * * @see gpjpp.GPGene#createNodeIndex */ protected void registerAllClasses() throws IllegalAccessException { if (cfg.CheckpointGens > 0) { //create the list of all node types used to stream genes GPGene.createNodeIndex(adfNs); //register user variable class and its superclasses GPObject.registerClass(cfg); //register overall ADF node set, a branch node set, and a node GPObject.registerClass(adfNs); GPNodeSet tmpNs = (GPNodeSet)adfNs.get(0); GPObject.registerClass(tmpNs); GPNode tmpN = (GPNode)tmpNs.get(0); GPObject.registerClass(tmpN); //create a temporary GP of user type and register it GP tmpGP = pop.createGP(adfNs.containerSize()); GPObject.registerClass(tmpGP); //create a temporary gene of user type and register it GPObject.registerClass(tmpGP.createGene(tmpN)); //register user population class and its superclasses GPObject.registerClass(pop); } } /** * Returns the checkpoint file name, baseName+".stm" by default. */ protected String getCheckpointName() { return baseName+".stm"; } /** * Returns the statistics file name, baseName+".stc" by default. */ protected String getStatisticsName() { return baseName+".stc"; } /** * Returns the detail file name, baseName+".det" by default. */ protected String getDetailName() { return baseName+".det"; } /** * Returns an instantiated File of the stream file if * checkpointing is enabled and the stream file exists. Otherwise * returns null. */ protected File getCheckpointFile() { if (cfg.CheckpointGens > 0) { File f = new File(getCheckpointName()); if (f.exists()) return f; } return null; } /** * Loads a checkpoint if cfg.CheckpointGens is greater than * zero and the checkpoint file is found. For a successful * load, the configuration variables and node definitions * in this run must exactly match those in force when the * checkpoint file was created. loadCheckpoint() generates * a RuntimeException with an informative message if this * is not the case. You can either bring the current configuration * in line with the original run or delete the stream file * to start over.
* * After the checkpoint is loaded, the run picks up exactly * where it left off when the checkpoint was stored. The only * difference is that the random number sequence used in the new * run won't match any results obtained after the original * checkpoint was stored. (The random number seed is not stored * on the stream.) * * @return true if a checkpoint was loaded; otherwise false. * * @exception java.io.FileNotFoundException * if the stream file is not found (shouldn't happen). * @exception java.io.IOException * if an I/O error occurs while reading the stream. * @exception java.lang.RuntimeException * if the current configuration doesn't match the * checkpoint's. */ protected boolean loadCheckpoint() throws FileNotFoundException, IOException { File f = getCheckpointFile(); if (f != null) { //open stream file for reading DataInputStream is = new DataInputStream( new BufferedInputStream( new FileInputStream(f), stmBufSize)); System.out.println(); System.out.print("Loading checkpoint population... "); //try to load the stream boolean streamOk = true; String msg = ""; try { load(is); } catch (ClassNotFoundException e) { streamOk = false; msg = e.getMessage(); } catch (InstantiationException e) { streamOk = false; msg = e.getMessage(); } catch (IllegalAccessException e) { streamOk = false; msg = e.getMessage(); } catch (IOException e) { streamOk = false; msg = e.getMessage(); } is.close(); if (streamOk) { System.out.println("Ok"); //put a comment in the statistics file sout.println(); sout.println("Restarted from checkpoint"); return true; } else { System.out.println("Error"); System.out.println(msg); System.out.print("Erase stream file or correct configuration"); throw new RuntimeException("Stream loading error"); } } return false; } /** * Saves a checkpoint to disk if cfg.CheckpointGens is greater than * zero and that many generations has passed since the last * checkpoint. Returns true if a checkpoint was saved. */ protected boolean saveCheckpoint() throws IOException { if (cfg.CheckpointGens > 0) { cntGen--; if (cntGen <= 0) { //create or overwrite stream file DataOutputStream os = new DataOutputStream( new BufferedOutputStream( new FileOutputStream(getCheckpointName()), stmBufSize)); save(os); os.close(); cntGen = cfg.CheckpointGens; //flush statistics file too //sout.flush(); //sout.close(); //sout = createOrAppend(getStatisticsName(), true); //data file often so big it's a waste of time to flush return true; } } return false; } /** * Loads a checkpoint file from the specified stream. The stream * contains an image of the configuration variables, the node * set, the current run and generation numbers, the population * of individuals, and a terminator code. If the configuration * variables or node set don't match those of the current run, * load() throws an InstantiationException which is caught by * loadCheckpoint(). * * @exception java.lang.ClassNotFoundException * if the class indicated by the stream's ID code * is not registered with GPObject. * @exception java.lang.InstantiationException * if an error occurs while calling new or the null * constructor of the specified class. * @exception java.lang.IllegalAccessException * if a class or its null constructor is not public. * @exception java.io.IOException * if an error occurs while reading the stream. */ protected void load(DataInputStream is) throws ClassNotFoundException, IOException, InstantiationException, IllegalAccessException { //load configuration variables stored on stream GPVariables tmpCfg = (GPVariables)GPObject.createRegisteredClassObject(cfg.isA()); tmpCfg.load(is); //confirm it matches current configuration if (!tmpCfg.equals(cfg)) throw new InstantiationException( "Checkpoint configuration doesn't match current ini file"); //load node set stored on stream GPAdfNodeSet tmpAdfNs = (GPAdfNodeSet)GPObject.createRegisteredClassObject(adfNs.isA()); tmpAdfNs.load(is); //confirm it matches current node set if (!tmpAdfNs.equals(adfNs)) throw new InstantiationException( "Checkpoint node set doesn't match program node set"); //load run state curRun = is.readInt(); goodRuns = is.readInt(); curGen = is.readInt(); //load population pop.load(is); //check terminator ID if (is.readInt() != RUNENDID) throw new InstantiationException("Stream file is corrupt"); } /** * Saves a checkpoint to the specified stream. * * @exception java.io.IOException * if an error occurs while writing the stream. * * @see gpjpp.GPRun#load */ protected void save(DataOutputStream os) throws IOException { //save configuration variables cfg.save(os); //save node set adfNs.save(os); //save run state os.writeInt(curRun); os.writeInt(goodRuns); os.writeInt(curGen); //save population pop.save(os); //write terminator ID // (mostly used for visual inspection of stream file // to confirm that whole stream was flushed) os.writeInt(RUNENDID); } } OthelloProj/GP/gpjpp/GPPrintStream.java 100644 5763 134 4501 6506556654 17062 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; /** * Extends the standard PrintStream class to output a * platform-specific line separator. This is not needed for JDK 1.1, * which outputs the System property line.separator automatically * at the end of each line. GPPrintStream does not interfere with * the operation of PrintStream under JDK 1.1 (which deprecates * PrintStream and completely changes its implementation). * * @version 1.0 */ public class GPPrintStream extends PrintStream { /** * The line separator string obtained by calling * System.getProperty("line.separator"). */ protected String lineSeparator = System.getProperty("line.separator", "\r\n"); /** * Creates a GPPrintStream filter over an OutputStream. */ public GPPrintStream(OutputStream out) { super(out); } /** * Creates a GPPrintStream filter over an OutputStream. */ public GPPrintStream(OutputStream out, boolean autoflush) { super(out, autoflush); } /** * Writes the line separator string to the PrintStream. */ public void writeEol() { for (int i = 0; i < lineSeparator.length(); i++) super.write(lineSeparator.charAt(i)); } /** * Detects '\n' and expands it to a full line separator string. * All other characters are passed on to the superclass. */ public void write(int b) { if (b == '\n') writeEol(); else super.write(b); } } OthelloProj/GP/gpjpp/GPDrawing.java 100644 5763 134 20762 6506556655 16235 0 ustar evs faculty // gpjpp (genetic programming package for Java) // Copyright (c) 1997, Kim Kokkonen // // This program is free software; you can redistribute it and/or // modify it under the terms of version 2 of the GNU General Public // License as published by the Free Software Foundation. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. // // Send comments, suggestions, problems to kimk@turbopower.com package gpjpp; import java.io.*; import java.awt.*; //Frame, Canvas, Graphics, Image, Font, FontMetrics import Acme.JPM.Encoders.*; /** * Used to draw graphic images of the results of the genetic * algorithm. Most commonly, it is used to draw a graphic rendition * of genetic program trees. It can also be used to draw other * images such as the path followed by a mower in the lawnmower * problem. * * Because the rest of gpjpp is designed without any user interface, * this class attempts to shoehorn graphics into the library with * minimal side effects, which turned out to be surprisingly * difficult. The technique chosen was to create a subclass * of Java's standard AWT Frame class, to add a single Canvas to * this frame, and to create an off-screen Image where the drawing * is performed relative to the Canvas. Then the freeware class * Acme.JPM.Encoders.GifEncoder is used to write the graphic image to * a gif file for viewing in a web browser, drawing program, or * word processor.
* * In my experience using Java console applications running under * the Microsoft J++ 1.1 VM in Windows 95, creating a GPDrawing * object causes the console window to temporarily lose focus until * the GPDrawing.dispose() method (inherited from Frame) is called. * See * GPRun.showFinalGeneration for an example. Although the effect * can be disconcerting, a mouse click returns focus to any * window you desire without disturbing the drawing process. * Numerous experiments have not uncovered a solution. The same effect * does not occur under the Sun VM.
*
* The GPGenePrint and
* LawnGP classes show examples of drawing images with GPDrawing.
* If you just want to create gif files of the genetic trees,
* set PrintTree
* to true in your configuration file and don't worry about the rest.
*
* @version 1.0
*/
public class GPDrawing extends Frame {
/**
* The typeface used to display text in genetic trees. This
* should be a monospace font. Courier was chosen as a default
* because it is a standard Java font that should be available
* on all platforms. There's nothing that limits you to just one
* font for other applications, but GPDrawing enables this
* one and gets various font metrics that are useful
* while drawing.
*/
public static String fontName = "Courier";
/**
* The default font size used for the font. This can be changed
* while constructing the object or by calling
* setFontSize.
* Default value 12.
*/
public static int defFontSize = 12;
/**
* The canvas on which the image is drawn.
*/
protected Canvas cvs;
/**
* The active font for the image.
*/
protected Font fnt;
/**
* Font metrics for the active font.
*/
protected FontMetrics fm;
/**
* An off-screen image associated with the canvas on which
* the drawing is created.
*/
protected Image img;
/**
* A graphics context whose methods are called to produce the
* off-screen image.
*
* @see gpjpp.GPDrawing#getGra
*/
protected Graphics gra;
/**
* The current font size.
*/
protected int fontSize;
/**
* The width of the widest character in the current font.
* It's public so that users of the class can get the value
* efficiently.
*/
public int cw;
/**
* The height of the current font.
* It's public so that users of the class can get the value
* efficiently.
*/
public int ch;
/**
* The maximum ascent of any character in the current font.
* It's public so that users of the class can get the value
* efficiently.
*/
public int as;
/**
* Public null constructor for this class. It creates
* a Frame with the title "gif drawing", adds a Canvas
* to it, creates the peer components, creates the
* default font at default size, and gets the
* cw,
* ch, and
* as
* font metrics. The frame remains hidden and
* disabled.
*/
public GPDrawing() {
super("gif drawing");
//create a canvas to draw on
cvs = new Canvas();
//add canvas to frame
add(cvs);
//create peer components
addNotify();
//create a default font
setFontSize(defFontSize);
}
/**
* Changes the font size. The typeface is specified by the
* fontName
* field of the class. Updates the
* fm,
* cw,
* ch, and
* as
* fields of the class.
*/
public void setFontSize(int fontSize) {
if (fontSize != this.fontSize) {
this.fontSize = fontSize;
fnt = new Font(fontName, Font.PLAIN, fontSize);
if (fnt == null)
throw new RuntimeException("Courier font not available");
//get font metrics needed by gif tree
fm = getFontMetrics(fnt);
cw = fm.getMaxAdvance();
ch = fm.getHeight();
as = fm.getMaxAscent();
}
}
/**
* Prepares an off-screen drawing image of the specified
* pixel width and height. The image is cleared to a white
* background, the default font is enabled, and the foreground
* color is set to black.
*/
public void prepImage(int w, int h) {
prepImage(w, h, this.fontSize);
}
/**
* Sets a new font size and prepares an off-screen drawing
* image.
*
* @see gpjpp.GPDrawing#prepImage(int, int)
*/
public void prepImage(int w, int h, int fontSize) {
//create properly sized font if needed
setFontSize(fontSize);
//create image of desired size
img = cvs.createImage(w, h);
if (img == null)
throw new RuntimeException("Unable to create image");
if (gra != null)
gra.dispose();
gra = img.getGraphics();
//clear the image and set default colors and font
gra.setColor(Color.white);
gra.fillRect(0, 0, w, h);
gra.setColor(Color.black);
gra.setFont(fnt);
}
/**
* Returns the pixel width of a text string when displayed
* in the default font.
*/
public int stringWidth(String s) { return fm.stringWidth(s); }
/**
* Returns the graphics context on which drawing is done.
* See java.awt.Graphics for a complete list of available
* drawing methods.
* prepImage()
* must be called first.
*/
public Graphics getGra() { return gra; }
/**
* Writes the current off-screen image to a gif file.
*
* @param fname the name of the gif file to create.
* @exception IOException
* if an error occurs while writing the file.
*/
public void writeGif(String fname) throws IOException {
OutputStream os = new BufferedOutputStream(
new FileOutputStream(fname), 1024);
(new GifEncoder(img, os)).encode();
os.close();
}
}
OthelloProj/GP/Acme/ 40755 5763 134 0 6506556656 13152 5 ustar evs faculty OthelloProj/GP/Acme/JPM/ 40755 5763 134 0 6506556655 13577 5 ustar evs faculty OthelloProj/GP/Acme/JPM/Encoders/ 40755 5763 134 0 6506556656 15342 5 ustar evs faculty OthelloProj/GP/Acme/JPM/Encoders/GifEncoder.java 100644 5763 134 44073 6506556655 20336 0 ustar evs faculty // GifEncoder - write out an image as a GIF
//
// Transparency handling and variable bit size courtesy of Jack Palevich.
//
// Copyright (C) 1996 by Jef Poskanzer
// Fetch the software.
// @see ToGif
public class GifEncoder extends ImageEncoder
{
private boolean interlace = false;
/// Constructor from Image.
// @param img The image to encode.
// @param out The stream to write the GIF to.
public GifEncoder( Image img, OutputStream out ) throws IOException
{
super( img, out );
}
/// Constructor from Image with interlace setting.
// @param img The image to encode.
// @param out The stream to write the GIF to.
// @param interlace Whether to interlace.
public GifEncoder( Image img, OutputStream out, boolean interlace ) throws IOException
{
super( img, out );
this.interlace = interlace;
}
/// Constructor from ImageProducer.
// @param prod The ImageProducer to encode.
// @param out The stream to write the GIF to.
public GifEncoder( ImageProducer prod, OutputStream out ) throws IOException
{
super( prod, out );
}
/// Constructor from ImageProducer with interlace setting.
// @param prod The ImageProducer to encode.
// @param out The stream to write the GIF to.
public GifEncoder( ImageProducer prod, OutputStream out, boolean interlace ) throws IOException
{
super( prod, out );
this.interlace = interlace;
}
int width, height;
int[][] rgbPixels;
void encodeStart( int width, int height ) throws IOException
{
this.width = width;
this.height = height;
rgbPixels = new int[height][width];
}
void encodePixels(
int x, int y, int w, int h, int[] rgbPixels, int off, int scansize )
throws IOException
{
// Save the pixels.
for ( int row = 0; row < h; ++row )
System.arraycopy(
rgbPixels, row * scansize + off,
this.rgbPixels[y + row], x, w );
}
Acme.IntHashtable colorHash;
void encodeDone() throws IOException
{
int transparentIndex = -1;
int transparentRgb = -1;
// Put all the pixels into a hash table.
colorHash = new Acme.IntHashtable();
int index = 0;
for ( int row = 0; row < height; ++row )
{
int rowOffset = row * width;
for ( int col = 0; col < width; ++col )
{
int rgb = rgbPixels[row][col];
boolean isTransparent = ( ( rgb >>> 24 ) < 0x80 );
if ( isTransparent )
{
if ( transparentIndex < 0 )
{
// First transparent color; remember it.
transparentIndex = index;
transparentRgb = rgb;
}
else if ( rgb != transparentRgb )
{
// A second transparent color; replace it with
// the first one.
rgbPixels[row][col] = rgb = transparentRgb;
}
}
GifEncoderHashitem item =
(GifEncoderHashitem) colorHash.get( rgb );
if ( item == null )
{
if ( index >= 256 )
throw new IOException( "too many colors for a GIF" );
item = new GifEncoderHashitem(
rgb, 1, index, isTransparent );
++index;
colorHash.put( rgb, item );
}
else
++item.count;
}
}
// Figure out how many bits to use.
int logColors;
if ( index <= 2 )
logColors = 1;
else if ( index <= 4 )
logColors = 2;
else if ( index <= 16 )
logColors = 4;
else
logColors = 8;
// Turn colors into colormap entries.
int mapSize = 1 << logColors;
byte[] reds = new byte[mapSize];
byte[] grns = new byte[mapSize];
byte[] blus = new byte[mapSize];
for ( Enumeration e = colorHash.elements(); e.hasMoreElements(); )
{
GifEncoderHashitem item = (GifEncoderHashitem) e.nextElement();
reds[item.index] = (byte) ( ( item.rgb >> 16 ) & 0xff );
grns[item.index] = (byte) ( ( item.rgb >> 8 ) & 0xff );
blus[item.index] = (byte) ( item.rgb & 0xff );
}
GIFEncode(
out, width, height, interlace, (byte) 0, transparentIndex,
logColors, reds, grns, blus );
}
byte GetPixel( int x, int y ) throws IOException
{
GifEncoderHashitem item =
(GifEncoderHashitem) colorHash.get( rgbPixels[y][x] );
if ( item == null )
throw new IOException( "color not found" );
return (byte) item.index;
}
static void writeString( OutputStream out, String str ) throws IOException
{
int len = str.length();
byte[] buf = new byte[len];
str.getBytes( 0, len, buf, 0 );
out.write( buf );
}
// Adapted from ppmtogif, which is based on GIFENCOD by David
// Rowley
// A framework for classes that encode and write out an image in
// a particular file format.
//
// This provides a simplified rendition of the ImageConsumer interface.
// It always delivers the pixels as ints in the RGBdefault color model.
// It always provides them in top-down left-right order.
// If you want more flexibility you can always implement ImageConsumer
// directly.
//
// Fetch the software.
// @see GifEncoder
// @see PpmEncoder
// @see Acme.JPM.Decoders.ImageDecoder
public abstract class ImageEncoder implements ImageConsumer
{
protected OutputStream out;
private ImageProducer producer;
private int width = -1;
private int height = -1;
private int hintflags = 0;
private boolean started = false;
private boolean encoding;
private IOException iox;
private static final ColorModel rgbModel = ColorModel.getRGBdefault();
private Hashtable props = null;
/// Constructor.
// @param img The image to encode.
// @param out The stream to write the bytes to.
public ImageEncoder( Image img, OutputStream out ) throws IOException
{
this( img.getSource(), out );
}
/// Constructor.
// @param producer The ImageProducer to encode.
// @param out The stream to write the bytes to.
public ImageEncoder( ImageProducer producer, OutputStream out ) throws IOException
{
this.producer = producer;
this.out = out;
}
// Methods that subclasses implement.
/// Subclasses implement this to initialize an encoding.
abstract void encodeStart( int w, int h ) throws IOException;
/// Subclasses implement this to actually write out some bits. They
// are guaranteed to be delivered in top-down-left-right order.
// One int per pixel, index is row * scansize + off + col,
// RGBdefault (AARRGGBB) color model.
abstract void encodePixels(
int x, int y, int w, int h, int[] rgbPixels, int off, int scansize )
throws IOException;
/// Subclasses implement this to finish an encoding.
abstract void encodeDone() throws IOException;
// Our own methods.
/// Call this after initialization to get things going.
public synchronized void encode() throws IOException
{
encoding = true;
iox = null;
producer.startProduction( this );
while ( encoding )
try
{
wait();
}
catch ( InterruptedException e ) {}
if ( iox != null )
throw iox;
}
private boolean accumulate = false;
private int[] accumulator;
private void encodePixelsWrapper(
int x, int y, int w, int h, int[] rgbPixels, int off, int scansize )
throws IOException
{
if ( ! started )
{
started = true;
encodeStart( width, height );
if ( ( hintflags & TOPDOWNLEFTRIGHT ) == 0 )
{
accumulate = true;
accumulator = new int[width * height];
}
}
if ( accumulate )
for ( int row = 0; row < h; ++row )
System.arraycopy(
rgbPixels, row * scansize + off,
accumulator, ( y + row ) * width + x,
w );
else
encodePixels( x, y, w, h, rgbPixels, off, scansize );
}
private void encodeFinish() throws IOException
{
if ( accumulate )
{
encodePixels( 0, 0, width, height, accumulator, 0, width );
accumulator = null;
accumulate = false;
}
}
private synchronized void stop()
{
encoding = false;
notifyAll();
}
// Methods from ImageConsumer.
public void setDimensions( int width, int height )
{
this.width = width;
this.height = height;
}
public void setProperties( Hashtable props )
{
this.props = props;
}
public void setColorModel( ColorModel model )
{
// Ignore.
}
public void setHints( int hintflags )
{
this.hintflags = hintflags;
}
public void setPixels(
int x, int y, int w, int h, ColorModel model, byte[] pixels,
int off, int scansize )
{
int[] rgbPixels = new int[w];
for ( int row = 0; row < h; ++row )
{
int rowOff = off + row * scansize;
for ( int col = 0; col < w; ++col )
rgbPixels[col] = model.getRGB( pixels[rowOff + col] & 0xff );
try
{
encodePixelsWrapper( x, y + row, w, 1, rgbPixels, 0, w );
}
catch ( IOException e )
{
iox = e;
stop();
return;
}
}
}
public void setPixels(
int x, int y, int w, int h, ColorModel model, int[] pixels,
int off, int scansize )
{
if ( model == rgbModel )
{
try
{
encodePixelsWrapper( x, y, w, h, pixels, off, scansize );
}
catch ( IOException e )
{
iox = e;
stop();
return;
}
}
else
{
int[] rgbPixels = new int[w];
for ( int row = 0; row < h; ++row )
{
int rowOff = off + row * scansize;
for ( int col = 0; col < w; ++col )
rgbPixels[col] = model.getRGB( pixels[rowOff + col] );
try
{
encodePixelsWrapper( x, y + row, w, 1, rgbPixels, 0, w );
}
catch ( IOException e )
{
iox = e;
stop();
return;
}
}
}
}
public void imageComplete( int status )
{
producer.removeConsumer( this );
if ( status == ImageConsumer.IMAGEABORTED )
iox = new IOException( "image aborted" );
else
{
try
{
encodeFinish();
encodeDone();
}
catch ( IOException e )
{
iox = e;
}
}
stop();
}
}
OthelloProj/GP/Acme/JPM/Encoders/GifEncoderHashitem.class 100644 5763 134 725 6506556655 22141 0 ustar evs faculty Êþº¾ - !
rgb Z
ConstantValue Acme/JPM/Encoders/GifEncoder
Exceptions (IIIZ)V LineNumberTable I
SourceFile GifEncoder.java LocalVariables Code java/lang/Object index
isTransparent
// Fetch the entire Acme package.
//
// Fetch the entire Acme package.
//