001 package org.jaga.reproduction.booleanFormulas;
002
003 import org.jaga.reproduction.XOver;
004 import org.jaga.individualRepresentation.booleanFormulas.*;
005 import org.jaga.reproduction.booleanFormulas.nodes.BooleanFormulaTreeNode;
006 import org.jaga.definitions.*;
007
008 /**
009 * TODO: Complete these comments.
010 *
011 * <p><u>Project:</u> JAGA - Java API for Genetic Algorithms.</p>
012 *
013 * <p><u>Company:</u> University College London and JAGA.Org
014 * (<a href="http://www.jaga.org" target="_blank">http://www.jaga.org</a>).
015 * </p>
016 *
017 * <p><u>Copyright:</u> (c) 2004 by G. Paperin.<br/>
018 * This program is free software; you can redistribute it and/or modify
019 * it under the terms of the GNU General Public License as published by
020 * the Free Software Foundation, ONLY if you include a note of the original
021 * author(s) in any redistributed/modified copy.<br/>
022 * This program is distributed in the hope that it will be useful,
023 * but WITHOUT ANY WARRANTY; without even the implied warranty of
024 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
025 * GNU General Public License for more details.<br/>
026 * You should have received a copy of the GNU General Public License
027 * along with this program; if not, write to the Free Software
028 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
029 * or see http://www.gnu.org/licenses/gpl.html</p>
030 *
031 * @author Greg Paperin (greg@jaga.org)
032 *
033 * @version JAGA public release 1.0 beta
034 */
035
036 public class FunctionTreeXOver extends XOver {
037
038 private static final Class applicableClass = BooleanFormulaTree.class;
039
040 public FunctionTreeXOver() {
041 super();
042 }
043
044 public FunctionTreeXOver(double xOverProb) {
045 super(xOverProb);
046 }
047
048 public Class getApplicableClass() {
049 return applicableClass;
050 }
051
052 public Individual[] reproduce(Individual[] parents, GAParameterSet params) {
053
054 if (null == parents || parents.length != getRequiredNumberOfParents())
055 throw new IllegalArgumentException("Must have " + getRequiredNumberOfParents()
056 + " parents");
057
058 RandomGenerator rand = params.getRandomGenerator();
059 Individual [] kids = copyParents(parents, params);
060
061 if (getXOverProbability() > rand.nextDouble())
062 return kids;
063
064 BooleanFormulaTree mum = (BooleanFormulaTree) kids[0];
065 BooleanFormulaTree dad = (BooleanFormulaTree) kids[1];
066
067 int maxDepth = ((BooleanFormulaTreeFactory) params.getIndividualsFactory()).getMaxTreeDepth();
068 int attempts = 0;
069 boolean kidsAreValid = false;
070 while (!kidsAreValid && attempts <= params.getMaxBadReproductionAttempts()) {
071
072 Long mumHandle = mum.selectRandomNode(params);
073 Long dadHandle = dad.selectRandomNode(params);
074
075 int mumHeight = mum.getNodeHeight(mumHandle);
076 int dadHeight = dad.getNodeHeight(dadHandle);
077 int mumDepth = mum.getNodeDepth(mumHandle);
078 int dadDepth = dad.getNodeDepth(dadHandle);
079
080 if (mumDepth + dadHeight <= maxDepth || dadDepth + mumHeight <= maxDepth) {
081
082 BooleanFormulaTreeNode mumNode = mum.exportNode(mumHandle);
083 BooleanFormulaTreeNode dadNode = dad.exportNode(dadHandle);
084
085 mum.replaceNode(mumHandle, dadNode);
086 dad.replaceNode(dadHandle, mumNode);
087
088 kidsAreValid = true;
089 mum.setFitness(null);
090 dad.setFitness(null);
091
092 } else { // i.e. if mum + dad > maxDepth
093 ++attempts;
094 }
095
096 }
097
098 return kids;
099 }
100
101 private Individual [] copyParents(Individual[] parents, GAParameterSet params) {
102 BooleanFormulaTreeFactory factory = (BooleanFormulaTreeFactory) params.getIndividualsFactory();
103 Individual [] clones = new Individual[parents.length];
104 for (int i = 0; i < clones.length; i++) {
105 clones[i] = factory.createSpecificIndividual(parents[i], params);
106 }
107 return clones;
108 }
109
110 }