TreeCrossover.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-3.9.0).
003  * Copyright (c) 2007-2017 Franz Wilhelmstötter
004  *
005  * Licensed under the Apache License, Version 2.0 (the "License");
006  * you may not use this file except in compliance with the License.
007  * You may obtain a copy of the License at
008  *
009  *      http://www.apache.org/licenses/LICENSE-2.0
010  *
011  * Unless required by applicable law or agreed to in writing, software
012  * distributed under the License is distributed on an "AS IS" BASIS,
013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014  * See the License for the specific language governing permissions and
015  * limitations under the License.
016  *
017  * Author:
018  *    Franz Wilhelmstötter (franz.wilhelmstoetter@gmx.at)
019  */
020 package org.jenetics.ext;
021 
022 import static java.lang.Math.min;
023 
024 import java.util.Random;
025 
026 import org.jenetics.Chromosome;
027 import org.jenetics.Genotype;
028 import org.jenetics.Phenotype;
029 import org.jenetics.Population;
030 import org.jenetics.Recombinator;
031 import org.jenetics.ext.util.FlatTree;
032 import org.jenetics.ext.util.FlatTreeNode;
033 import org.jenetics.ext.util.TreeNode;
034 import org.jenetics.util.ISeq;
035 import org.jenetics.util.MSeq;
036 import org.jenetics.util.RandomRegistry;
037 
038 /**
039  * Abstract implementation of tree base crossover recombinator. This class
040  * simplifies the implementation of tree base crossover implementation, by doing
041  * the transformation of the flattened tree genes to actual trees and vice versa.
042  * Only the {@link #crossover(TreeNode, TreeNode)} method must be implemented.
043  *
044  @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
045  @version 3.9
046  @since 3.9
047  */
048 public abstract class TreeCrossover<
049     extends TreeGene<?, G>,
050     extends Comparable<? super C>
051 >
052     extends Recombinator<G, C>
053 {
054 
055     /**
056      * Constructs an tree crossover with a given recombination probability.
057      *
058      @param probability the recombination probability
059      @throws IllegalArgumentException if the {@code probability} is not in the
060      *          valid range of {@code [0, 1]}
061      */
062     protected TreeCrossover(final double probability) {
063         super(probability, 2);
064     }
065 
066     @Override
067     protected int recombine(
068         final Population<G, C> population,
069         final int[] individuals,
070         final long generation
071     ) {
072         assert individuals.length == "Required order of 2";
073         final Random random = RandomRegistry.getRandom();
074 
075         final Phenotype<G, C> pt1 = population.get(individuals[0]);
076         final Phenotype<G, C> pt2 = population.get(individuals[1]);
077         final Genotype<G> gt1 = pt1.getGenotype();
078         final Genotype<G> gt2 = pt2.getGenotype();
079 
080         //Choosing the Chromosome index for crossover.
081         final int chIndex = random.nextInt(min(gt1.length(), gt2.length()));
082 
083         final MSeq<Chromosome<G>> c1 = gt1.toSeq().copy();
084         final MSeq<Chromosome<G>> c2 = gt2.toSeq().copy();
085 
086         crossover(c1, c2, chIndex);
087 
088         //Creating two new Phenotypes and exchanging it with the old.
089         population.set(
090             individuals[0],
091             pt1.newInstance(Genotype.of(c1.toISeq()), generation)
092         );
093         population.set(
094             individuals[1],
095             pt2.newInstance(Genotype.of(c2.toISeq()), generation)
096         );
097 
098         return getOrder();
099     }
100 
101     // Since the allele type "A" is not part of the type signature, we have to
102     // do some unchecked casts to make it "visible" again. The implementor of
103     // the abstract "crossover" method usually don't have to do additional casts.
104     private <A> void crossover(
105         final MSeq<Chromosome<G>> c1,
106         final MSeq<Chromosome<G>> c2,
107         final int index
108     ) {
109         @SuppressWarnings("unchecked")
110         final TreeNode<A> tree1 = (TreeNode<A>)TreeNode.ofTree(c1.get(index).getGene());
111         @SuppressWarnings("unchecked")
112         final TreeNode<A> tree2 = (TreeNode<A>)TreeNode.ofTree(c2.get(index).getGene());
113 
114         crossover(tree1, tree2);
115 
116         final FlatTreeNode<A> flat1 = FlatTreeNode.of(tree1);
117         final FlatTreeNode<A> flat2 = FlatTreeNode.of(tree2);
118 
119         @SuppressWarnings("unchecked")
120         final TreeGene<A, ?> template = (TreeGene<A, ?>)c1.get(0).getGene();
121 
122         final ISeq<G> genes1 = flat1.map(tree -> gene(template, tree));
123         final ISeq<G> genes2 = flat2.map(tree -> gene(template, tree));
124 
125         c1.set(index, c1.get(index).newInstance(genes1));
126         c2.set(index, c2.get(index).newInstance(genes2));
127     }
128 
129     @SuppressWarnings("unchecked")
130     private <A> G gene(
131         final TreeGene<A, ?> template,
132         final FlatTree<? extends A, ?> tree
133     ) {
134         return (G)template.newInstance(
135             tree.getValue(),
136             tree.childOffset(),
137             tree.childCount()
138         );
139     }
140 
141     /**
142      * Template method which performs the crossover. The arguments given are
143      * mutable non null trees.
144      *
145      @param <A> the <em>existential</em> allele type
146      @param that the first (chromosome) tree
147      @param other he second (chromosome) tree
148      @return the number of altered genes
149      */
150     protected abstract <A> int crossover(
151         final TreeNode<A> that,
152         final TreeNode<A> other
153     );
154 
155 }