001: /*
002: * This file is part of JGAP.
003: *
004: * JGAP offers a dual license model containing the LGPL as well as the MPL.
005: *
006: * For licensing information please see the file license.txt included with JGAP
007: * or have a look at the top of class org.jgap.Chromosome which representatively
008: * includes the JGAP license policy applicable for any file delivered with JGAP.
009: */
010: package org.jgap.gp.impl;
011:
012: import java.io.*;
013: import org.jgap.*;
014: import org.jgap.gp.*;
015:
016: /**
017: * Crossing over for GP ProgramChromosomes.
018: *
019: * @author Klaus Meffert
020: * @since 3.0
021: */
022: public class BranchTypingCross extends CrossMethod implements
023: Serializable, Comparable, Cloneable {
024: /** String containing the CVS revision. Read out via reflection!*/
025: private final static String CVS_REVISION = "$Revision: 1.15 $";
026:
027: public BranchTypingCross(GPConfiguration a_config) {
028: super (a_config);
029: }
030:
031: /**
032: * Crosses two individuals. A random chromosome is chosen for crossing based
033: * probabilistically on the proportion of nodes in each chromosome in the
034: * first individual.
035: *
036: * @param i1 the first individual to cross
037: * @param i2 the second individual to cross
038: * @return an array of the two resulting individuals
039: *
040: * @author Klaus Meffert
041: * @since 3.0
042: */
043: public IGPProgram[] operate(final IGPProgram i1, final IGPProgram i2) {
044: try {
045: // Determine which chromosome we'll cross, probabilistically determined
046: // by the sizes of the chromosomes of the first individual --
047: // equivalent to Koza's branch typing.
048: int[] sizes = new int[i1.size()];
049: int totalSize = 0;
050: for (int i = 0; i < i1.size(); i++) {
051: // Size of a chromosome = number of nodes.
052: // ---------------------------------------
053: sizes[i] = i1.getChromosome(i).getSize(0);
054: totalSize += sizes[i];
055: }
056: /**@todo we could also select a chromosome directly!*/
057: int nodeNum = getConfiguration().getRandomGenerator()
058: .nextInt(totalSize);
059: // Select the chromosome in which node "nodeNum" resides.
060: // ------------------------------------------------------
061: int chromosomeNum;
062: for (chromosomeNum = 0; chromosomeNum < i1.size(); chromosomeNum++) {
063: nodeNum -= sizes[chromosomeNum];
064: if (nodeNum < 0)
065: break;
066: }
067: // Cross the selected chromosomes.
068: // -------------------------------
069: ProgramChromosome[] newChromosomes = doCross(i1
070: .getChromosome(chromosomeNum), i2
071: .getChromosome(chromosomeNum));
072: // Create the new individuals by copying the uncrossed chromosomes
073: // and setting the crossed chromosome. There's no need to deep-copy
074: // the uncrossed chromosomes because they don't change. That is,
075: // even if two individuals' chromosomes point to the same chromosome,
076: // the only change in a chromosome is crossing, which generates
077: // deep-copied chromosomes anyway.
078: // ------------------------------------------------------------------
079: IGPProgram[] newIndividuals = { new GPProgram(i1), //getConfiguration(), i1.size()),
080: new GPProgram(i1) }; //getConfiguration(), i1.size())};
081: for (int i = 0; i < i1.size(); i++)
082: if (i != chromosomeNum) {
083: newIndividuals[0].setChromosome(i, i1
084: .getChromosome(i));
085: newIndividuals[1].setChromosome(i, i2
086: .getChromosome(i));
087: } else {
088: newIndividuals[0].setChromosome(i,
089: newChromosomes[0]);
090: newIndividuals[1].setChromosome(i,
091: newChromosomes[1]);
092: }
093: return newIndividuals;
094: } catch (InvalidConfigurationException iex) {
095: return null;
096: }
097: }
098:
099: /**
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) throws InvalidConfigurationException {
122: ProgramChromosome[] c = { c0, c1 };
123: // Choose a point in c1.
124: // ---------------------
125: int p0;
126: RandomGenerator random = getConfiguration()
127: .getRandomGenerator();
128: if (random.nextFloat() < getConfiguration().getFunctionProb()) {
129: // choose a function
130: int nf = c0.numFunctions();
131: if (nf == 0) {
132: // no functions
133: return c;
134: }
135: int fctIndex = random.nextInt(nf);
136: p0 = c0.getFunction(fctIndex);
137: } else {
138: // Choose a terminal.
139: // ------------------
140: p0 = c0.getTerminal(random.nextInt(c0.numTerminals()));
141: }
142: // Mutate the command'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 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: } else {
174: // Choose a terminal.
175: // ------------------
176: int nt = c1.numTerminals(type_, subType);
177: if (nt == 0) {
178: // No terminals of that type.
179: // --------------------------
180: return c;
181: }
182: p1 = c1.getTerminal(random.nextInt(c1.numTerminals(type_,
183: subType)), type_, subType);
184: }
185: // Mutate the command's value.
186: // ----------------------------
187: /**@todo make this random and configurable*/
188: /*CommandGene */command = c1.getNode(p1);
189: if (IMutateable.class.isInstance(command)) {
190: IMutateable term = (IMutateable) command;
191: command = term.applyMutation(0, 0.5d);
192: if (command != null) {
193: // Check if mutant's function is allowed.
194: // --------------------------------------
195: if (c0.getCommandOfClass(0, command.getClass()) >= 0) {
196: c1.setGene(p1, command);
197: }
198: }
199: }
200:
201: int s0 = c0.getSize(p0); //Number of nodes in c0 from index p0
202: int s1 = c1.getSize(p1); //Number of nodes in c1 from index p1
203: int d0 = c0.getDepth(p0); //Depth of c0 from index p0
204: int d1 = c1.getDepth(p1); //Depth of c1 from index p1
205: int c0s = c0.getSize(0); //Number of nodes in c0
206: int c1s = c1.getSize(0); //Number of nodes in c1
207:
208: // Check for depth constraint for p1 inserted into c0.
209: // ---------------------------------------------------
210: if (d0 - 1 + s1 > getConfiguration().getMaxCrossoverDepth()
211: || c0s - p0 - s0 < 0
212: || p0 + s1 + c0s - p0 - s0 >= c0.getFunctions().length) {
213: // Choose the other parent.
214: // ------------------------
215: c[0] = c1;
216: } else {
217: c[0] = new ProgramChromosome(getConfiguration(), c0
218: .getFunctions().length, // c0s - s0 + s1,
219: c[0].getFunctionSet(), c[0].getArgTypes(), c0
220: .getIndividual());
221: System.arraycopy(c0.getFunctions(), 0, c[0].getFunctions(),
222: 0, p0);
223: System.arraycopy(c1.getFunctions(), p1,
224: c[0].getFunctions(), p0, s1);
225: System.arraycopy(c0.getFunctions(), p0 + s0, c[0]
226: .getFunctions(), p0 + s1, c0s - p0 - s0);
227: c[0].redepth();
228: }
229: // Check for depth constraint for p0 inserted into c1.
230: // ---------------------------------------------------
231: if (d1 - 1 + s0 > getConfiguration().getMaxCrossoverDepth()
232: || c1s - p1 - s1 < 0
233: || p1 + s0 + c1s - p1 - s1 >= c1.getFunctions().length) {
234: // Choose the other parent.
235: // ------------------------
236: c[1] = c0;
237: } else {
238: c[1] = new ProgramChromosome(getConfiguration(), c1
239: .getFunctions().length, // c1s - s1 + s0,
240: c[1].getFunctionSet(), c[1].getArgTypes(), c1
241: .getIndividual());
242: System.arraycopy(c1.getFunctions(), 0, c[1].getFunctions(),
243: 0, p1);
244: System.arraycopy(c0.getFunctions(), p0,
245: c[1].getFunctions(), p1, s0);
246: System.arraycopy(c1.getFunctions(), p1 + s1, c[1]
247: .getFunctions(), p1 + s0, c1s - p1 - s1);
248: c[1].redepth();
249: }
250: return c;
251: }
252:
253: /**
254: * The compareTo-method.
255: *
256: * @param a_other the other object to compare
257: * @return 0 or 1 in this case, as BranchTypingCross objects keep no state
258: *
259: * @author Klaus Meffert
260: * @since 3.0
261: */
262: public int compareTo(Object a_other) {
263: BranchTypingCross other = (BranchTypingCross) a_other;
264: if (other == null) {
265: return 1;
266: }
267: return 0;
268: }
269:
270: /**
271: * The equals-method.
272: *
273: * @param a_other the other object to compare
274: * @return always true for non-null BranchTypingCross objects because they
275: * keep no state
276: *
277: * @author Klaus Meffert
278: * @since 3.0
279: */
280: public boolean equals(Object a_other) {
281: try {
282: BranchTypingCross other = (BranchTypingCross) a_other;
283: if (other == null) {
284: return false;
285: } else {
286: return true;
287: }
288: } catch (ClassCastException cex) {
289: return false;
290: }
291: }
292:
293: /**
294: * @return deep clone of this instance
295: *
296: * @author Klaus Meffert
297: * @since 3.2
298: */
299: public Object clone() {
300: BranchTypingCross result = new BranchTypingCross(
301: getConfiguration());
302: return result;
303: }
304: }
|