KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgap > gp > impl > BranchTypingCross


1 /*
2  * This file is part of JGAP.
3  *
4  * JGAP offers a dual license model containing the LGPL as well as the MPL.
5  *
6  * For licencing information please see the file license.txt included with JGAP
7  * or have a look at the top of class org.jgap.Chromosome which representatively
8  * includes the JGAP license policy applicable for any file delivered with JGAP.
9  */

10 package org.jgap.gp.impl;
11
12 import java.io.*;
13 import org.jgap.*;
14 import org.jgap.gp.*;
15
16 /**
17  * Crossing over for GP ProgramChromosomes.
18  *
19  * @author Klaus Meffert
20  * @since 3.0
21  */

22 public class BranchTypingCross
23     extends CrossMethod implements Serializable, Comparable JavaDoc {
24   /** String containing the CVS revision. Read out via reflection!*/
25   private final static String JavaDoc CVS_REVISION = "$Revision: 1.11 $";
26
27   public BranchTypingCross(GPConfiguration a_config) {
28     super(a_config);
29   }
30
31   /**
32    * Crosses two individuals. A random chromosome is chosen for crossing based
33    * probabilistically on the proportion of nodes in each chromosome in the
34    * first individual.
35    *
36    * @param i1 the first individual to cross
37    * @param i2 the second individual to cross
38    * @return an array of the two resulting individuals
39    *
40    * @author Klaus Meffert
41    * @since 3.0
42    */

43   public IGPProgram[] operate(final IGPProgram i1,
44                               final IGPProgram i2) {
45     try {
46       // Determine which chromosome we'll cross, probabilistically determined
47
// by the sizes of the chromosomes of the first individual --
48
// equivalent to Koza's branch typing.
49

50       int[] sizes = new int[i1.size()];
51       int totalSize = 0;
52       for (int i = 0; i < i1.size(); i++) {
53         // Size of a chromosome = number of nodes.
54
// ---------------------------------------
55
sizes[i] = i1.getChromosome(i).getSize(0);
56         totalSize += sizes[i];
57       }
58       /**@todo we could also select a chromosome directly!*/
59       int nodeNum = getConfiguration().getRandomGenerator().nextInt(
60           totalSize);
61       // Select the chromosome in which node "nodeNum" resides.
62
// ------------------------------------------------------
63
int chromosomeNum;
64       for (chromosomeNum = 0; chromosomeNum < i1.size(); chromosomeNum++) {
65         nodeNum -= sizes[chromosomeNum];
66         if (nodeNum < 0)
67           break;
68       }
69       // Cross the selected chromosomes.
70
// -------------------------------
71
ProgramChromosome[] newChromosomes = doCross(
72           i1.getChromosome(chromosomeNum),
73           i2.getChromosome(chromosomeNum));
74       // Create the new individuals by copying the uncrossed chromosomes
75
// and setting the crossed chromosome. There's no need to deep-copy
76
// the uncrossed chromosomes because they don't change. That is,
77
// even if two individuals' chromosomes point to the same chromosome,
78
// the only change in a chromosome is crossing, which generates
79
// deep-copied chromosomes anyway.
80

81       IGPProgram[] newIndividuals = {
82           new GPProgram(i1), //getConfiguration(), i1.size()),
83
new GPProgram(i1)}; //getConfiguration(), i1.size())};
84
for (int i = 0; i < i1.size(); i++)
85         if (i != chromosomeNum) {
86           newIndividuals[0].setChromosome(i, i1.getChromosome(i));
87           newIndividuals[1].setChromosome(i, i2.getChromosome(i));
88         }
89         else {
90           newIndividuals[0].setChromosome(i, newChromosomes[0]);
91           newIndividuals[1].setChromosome(i, newChromosomes[1]);
92         }
93       return newIndividuals;
94     } catch (InvalidConfigurationException iex) {
95       return null;
96     }
97   }
98
99   /**
100    * Crosses two chromsomes using branch-typing.
101    * A random point in the first chromosome is chosen, with 90% probability it
102    * will be a function and 10% probability it will be a terminal. A random
103    * point in the second chromosome is chosen using the same probability
104    * distribution, but the node chosen must be of the same type as the chosen
105    * node in the first chromosome.<p>
106    * If a suitable point in the second chromosome couldn't be found then the
107    * chromosomes are not crossed.<p>
108    * If a resulting chromosome's depth is larger than the World's maximum
109    * crossover depth then that chromosome is simply copied from the original
110    * rather than crossed.
111    *
112    * @param c0 the first chromosome to cross
113    * @param c1 the second chromosome to cross
114    * @return an array of the two resulting chromosomes
115    * @throws InvalidConfigurationException
116    *
117    * @author Klaus Meffert
118    * @since 3.0
119    */

120   protected ProgramChromosome[] doCross(ProgramChromosome c0,
121                                         ProgramChromosome c1)
122       throws InvalidConfigurationException {
123     ProgramChromosome[] c = {
124         c0, c1};
125     // Choose a point in c1.
126
// ---------------------
127
int p0;
128     RandomGenerator random = getConfiguration().getRandomGenerator();
129     if (random.nextFloat() < getConfiguration().getFunctionProb()) {
130       // choose a function
131
int nf = c0.numFunctions();
132       if (nf == 0) {
133         // no functions
134
return c;
135       }
136       p0 = c0.getFunction(random.nextInt(nf));
137     }
138     else {
139       // Choose a terminal.
140
// ------------------
141
p0 = c0.getTerminal(random.nextInt(c0.numTerminals()));
142       // Mutate the terminal's value.
143
// ----------------------------
144
/**@todo make this random and configurable*/
145       CommandGene command = c0.getNode(p0);
146       if (IMutateable.class.isInstance(command)) {
147         IMutateable term = (IMutateable) command;
148         command = term.applyMutation(0, 0.5d);
149         if (command != null) {
150           // Check if mutant's function is allowed.
151
// --------------------------------------
152
if (c0.getCommandOfClass(0, command.getClass()) >=0) {
153             c0.setGene(p0, command);
154           }
155         }
156       }
157     }
158     // Choose a point in c2 matching the type and subtype of p0.
159
// ---------------------------------------------------------
160
int p1;
161     CommandGene nodeP0 = c0.getNode(p0);
162     Class JavaDoc type_ = nodeP0.getReturnType();
163     int subType = nodeP0.getSubReturnType();
164     if (random.nextFloat() < getConfiguration().getFunctionProb()) {
165       // choose a function
166
int nf = c1.numFunctions(type_, subType);
167       if (nf == 0) {
168         // No functions of that type.
169
// --------------------------
170
return c;
171       }
172       p1 = c1.getFunction(random.nextInt(nf), type_, subType);
173     }
174     else {
175       // Choose a terminal.
176
// ------------------
177
int nt = c1.numTerminals(type_, subType);
178       if (nt == 0) {
179         // No terminals of that type.
180
// --------------------------
181
return c;
182       }
183       p1 = c1.getTerminal(random.nextInt(c1.numTerminals(type_, subType)), type_, subType);
184       // Mutate the terminal's value.
185
// ----------------------------
186
/**@todo make this random and configurable*/
187       CommandGene command = c1.getNode(p1);
188       if (IMutateable.class.isInstance(command)) {
189         IMutateable term = (IMutateable) command;
190         command = term.applyMutation(0, 0.5d);
191         if (command != null) {
192           // Check if mutant's function is allowed.
193
// --------------------------------------
194
if (c0.getCommandOfClass(0, command.getClass()) >=0) {
195             c1.setGene(p1, command);
196           }
197         }
198       }
199     }
200     int s0 = c0.getSize(p0); //Number of nodes in c0 from index p0
201
int s1 = c1.getSize(p1); //Number of nodes in c1 from index p1
202
int d0 = c0.getDepth(p0); //Depth of c0 from index p0
203
int d1 = c1.getDepth(p1); //Depth of c1 from index p1
204
int c0s = c0.getSize(0); //Number of nodes in c0
205
int c1s = c1.getSize(0); //Number of nodes in c1
206

207     // Check for depth constraint for p1 inserted into c0.
208
// ---------------------------------------------------
209
if (d0 - 1 + s1 > getConfiguration().getMaxCrossoverDepth()
210         || c0s - p0 - s0 < 0
211         || p0 + s1 + c0s - p0 - s0>= c0.getFunctions().length) {
212       // Choose the other parent.
213
// ------------------------
214
c[0] = c1;
215     }
216     else {
217       c[0] = new ProgramChromosome(getConfiguration(), c0.getFunctions().length, // c0s - s0 + s1,
218
c[0].getFunctionSet(),
219                                    c[0].getArgTypes(),
220                                    c0.getIndividual());
221       System.arraycopy(c0.getFunctions(), 0, c[0].getFunctions(), 0, p0);
222       System.arraycopy(c1.getFunctions(), p1, c[0].getFunctions(), p0, s1);
223       System.arraycopy(c0.getFunctions(), p0 + s0, c[0].getFunctions(),
224                        p0 + s1, c0s - p0 - s0);
225       c[0].redepth();
226     }
227     // Check for depth constraint for p0 inserted into c1.
228
// ---------------------------------------------------
229
if (d1 - 1 + s0 > getConfiguration().getMaxCrossoverDepth()
230         || c1s - p1 - s1 < 0
231         || p1 + s0 + c1s - p1 - s1 >= c1.getFunctions().length) {
232       // Choose the other parent.
233
// ------------------------
234
c[1] = c0;
235     }
236     else {
237       c[1] = new ProgramChromosome(getConfiguration(), c1.getFunctions().length, // c1s - s1 + s0,
238
c[1].getFunctionSet(),
239                                    c[1].getArgTypes(),
240                                    c1.getIndividual());
241       System.arraycopy(c1.getFunctions(), 0, c[1].getFunctions(), 0, p1);
242       System.arraycopy(c0.getFunctions(), p0, c[1].getFunctions(), p1, s0);
243       System.arraycopy(c1.getFunctions(), p1 + s1, c[1].getFunctions(),
244                        p1 + s0, c1s - p1 - s1);
245       c[1].redepth();
246     }
247     return c;
248   }
249
250   /**
251    * The compareTo-method.
252    *
253    * @param a_other the other object to compare
254    * @return 0 or 1 in this case, as BranchTypingCross objects keep no state
255    *
256    * @author Klaus Meffert
257    * @since 3.0
258    */

259   public int compareTo(Object JavaDoc a_other) {
260     BranchTypingCross other = (BranchTypingCross) a_other;
261     if (other == null) {
262       return 1;
263     }
264     return 0;
265   }
266
267   /**
268    * The equals-method.
269    *
270    * @param a_other the other object to compare
271    * @return always true for non-null BranchTypingCross objects because they
272    * keep no state
273    *
274    * @author Klaus Meffert
275    * @since 3.0
276    */

277   public boolean equals(Object JavaDoc a_other) {
278     try {
279       BranchTypingCross other = (BranchTypingCross) a_other;
280       if (other == null) {
281         return false;
282       }
283       else {
284         return true;
285       }
286     } catch (ClassCastException JavaDoc cex) {
287       return false;
288     }
289   }
290 }
291
Popular Tags