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 java.util.Random;
023
024 import org.jenetics.ext.util.TreeNode;
025 import org.jenetics.util.ISeq;
026 import org.jenetics.util.RandomRegistry;
027
028 /**
029 * Swaps two, randomly chosen, nodes (sub-trees) from two given trees.
030 * <pre> {@code
031 * Tree A Tree B
032 * 0 a
033 * ├── 1 ├── b
034 * │ ├── 4 │ ├── e
035 * │ └── 5 │ └── f
036 * ├── 2 ├── c
037 * │ └── 6 │ └── g
038 * └── 3 └── d
039 * ├── 7 ├── h
040 * │ ├── 10 │ ├── k
041 * │ └── 11 │ └── l
042 * ├── 8 ├── i
043 * └── 9 └── j
044 *
045 * Swap node "3" of A with node "c" of B
046 *
047 * 0 a
048 * ├── 1 ├── b
049 * │ ├── 4 │ ├── e
050 * │ └── 5 │ └── f
051 * ├── 2 ├── 3
052 * │ └── 6 │ ├── 7
053 * └── c │ │ ├── 10
054 * └── g │ │ └── 11
055 * │ ├── 8
056 * │ └── 9
057 * └── d
058 * ├── h
059 * │ ├── k
060 * │ └── l
061 * ├── i
062 * └── j
063 * }</pre>
064 *
065 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
066 * @version 3.9
067 * @since 3.9
068 */
069 public class SingleNodeCrossover<
070 G extends TreeGene<?, G>,
071 C extends Comparable<? super C>
072 >
073 extends TreeCrossover<G, C>
074 {
075
076 public SingleNodeCrossover(double probability) {
077 super(probability);
078 }
079
080 public SingleNodeCrossover() {
081 this(DEFAULT_ALTER_PROBABILITY);
082 }
083
084 @Override
085 protected <A> int crossover(final TreeNode<A> that, final TreeNode<A> other) {
086 return swap(that, other);
087 }
088
089 // The static method makes it easier to test.
090 static <A> int swap(final TreeNode<A> that, final TreeNode<A> other) {
091 assert that != null;
092 assert other != null;
093
094 final Random random = RandomRegistry.getRandom();
095
096 final ISeq<TreeNode<A>> seq1 = that.breadthFirstStream()
097 .collect(ISeq.toISeq());
098
099 final ISeq<TreeNode<A>> seq2 = other.breadthFirstStream()
100 .collect(ISeq.toISeq());
101
102 final int changed;
103 if (seq1.length() > 1 && seq2.length() > 1) {
104 final TreeNode<A> n1 = seq1.get(random.nextInt(seq1.length() - 1) + 1);
105 final TreeNode<A> p1 = n1.getParent().orElseThrow(AssertionError::new);
106
107 final TreeNode<A> n2 = seq2.get(random.nextInt(seq2.length() - 1) + 1);
108 final TreeNode<A> p2 = n2.getParent().orElseThrow(AssertionError::new);
109
110 final int i1 = p1.getIndex(n1);
111 final int i2 = p2.getIndex(n2);
112
113 p1.insert(i1, n2.detach());
114 p2.insert(i2, n1.detach());
115
116 changed = 2;
117 } else {
118 changed = 0;
119 }
120
121 return changed;
122 }
123 }
|