001 /*
002 * Java Genetic Algorithm Library (jenetics-4.4.0).
003 * Copyright (c) 2007-2019 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@gmail.com)
019 */
020 package io.jenetics.ext;
021
022 import static java.lang.String.format;
023 import static io.jenetics.internal.util.Hashes.hash;
024
025 import java.util.Random;
026
027 import io.jenetics.util.ISeq;
028 import io.jenetics.util.RandomRegistry;
029
030 import io.jenetics.ext.util.TreeNode;
031
032 /**
033 * Swaps two, randomly chosen, nodes (sub-trees) from two given trees.
034 * <pre> {@code
035 * Tree A Tree B
036 * 0 a
037 * ├── 1 ├── b
038 * │ ├── 4 │ ├── e
039 * │ └── 5 │ └── f
040 * ├── 2 ├── c
041 * │ └── 6 │ └── g
042 * └── 3 └── d
043 * ├── 7 ├── h
044 * │ ├── 10 │ ├── k
045 * │ └── 11 │ └── l
046 * ├── 8 ├── i
047 * └── 9 └── j
048 *
049 * Swap node "3" of A with node "c" of B
050 *
051 * 0 a
052 * ├── 1 ├── b
053 * │ ├── 4 │ ├── e
054 * │ └── 5 │ └── f
055 * ├── 2 ├── 3
056 * │ └── 6 │ ├── 7
057 * └── c │ │ ├── 10
058 * └── g │ │ └── 11
059 * │ ├── 8
060 * │ └── 9
061 * └── d
062 * ├── h
063 * │ ├── k
064 * │ └── l
065 * ├── i
066 * └── j
067 * }</pre>
068 *
069 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
070 * @version 3.9
071 * @since 3.9
072 */
073 public class SingleNodeCrossover<
074 G extends TreeGene<?, G>,
075 C extends Comparable<? super C>
076 >
077 extends TreeCrossover<G, C>
078 {
079
080 public SingleNodeCrossover(double probability) {
081 super(probability);
082 }
083
084 public SingleNodeCrossover() {
085 this(DEFAULT_ALTER_PROBABILITY);
086 }
087
088 @Override
089 protected <A> int crossover(final TreeNode<A> that, final TreeNode<A> other) {
090 return swap(that, other);
091 }
092
093 // The static method makes it easier to test.
094 static <A> int swap(final TreeNode<A> that, final TreeNode<A> other) {
095 assert that != null;
096 assert other != null;
097
098 final Random random = RandomRegistry.getRandom();
099
100 final ISeq<TreeNode<A>> seq1 = that.breadthFirstStream()
101 .collect(ISeq.toISeq());
102
103 final ISeq<TreeNode<A>> seq2 = other.breadthFirstStream()
104 .collect(ISeq.toISeq());
105
106 final int changed;
107 if (seq1.length() > 1 && seq2.length() > 1) {
108 final TreeNode<A> n1 = seq1.get(random.nextInt(seq1.length() - 1) + 1);
109 final TreeNode<A> p1 = n1.getParent().orElseThrow(AssertionError::new);
110
111 final TreeNode<A> n2 = seq2.get(random.nextInt(seq2.length() - 1) + 1);
112 final TreeNode<A> p2 = n2.getParent().orElseThrow(AssertionError::new);
113
114 final int i1 = p1.getIndex(n1);
115 final int i2 = p2.getIndex(n2);
116
117 p1.insert(i1, n2.detach());
118 p2.insert(i2, n1.detach());
119
120 changed = 2;
121 } else {
122 changed = 0;
123 }
124
125 return changed;
126 }
127
128 @Override
129 public int hashCode() {
130 return hash(_probability);
131 }
132
133 @Override
134 public boolean equals(final Object obj) {
135 return obj == this ||
136 obj instanceof SingleNodeCrossover &&
137 Double.compare(((SingleNodeCrossover)obj)._probability, _probability) == 0;
138 }
139
140 @Override
141 public String toString() {
142 return format("SingleNodeCrossover[%f]", _probability);
143 }
144
145 }
|