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.prog;
021
022 import static java.lang.String.format;
023 import static java.util.Objects.requireNonNull;
024
025 import java.util.function.Predicate;
026
027 import org.jenetics.ext.AbstractTreeChromosome;
028 import org.jenetics.ext.util.FlatTreeNode;
029 import org.jenetics.ext.util.Tree;
030 import org.jenetics.ext.util.TreeNode;
031 import org.jenetics.prog.op.Op;
032 import org.jenetics.prog.op.Program;
033 import org.jenetics.util.ISeq;
034
035 /**
036 * Holds the nodes of the operation tree.
037 *
038 * <pre>{@code
039 * final int depth = 6;
040 * final ISeq<Op<Double>> operations = ISeq.of(...);
041 * final ISeq<Op<Double>> terminals = ISeq.of(...);
042 * final ProgramChromosome<Double> ch = ProgramChromosome.of(
043 * depth,
044 * // If the program has more that 200 nodes, it is marked as "invalid".
045 * ch -> ch.length() <= 200,
046 * operations,
047 * terminals
048 * );
049 * }</pre>
050 *
051 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
052 * @version 3.9
053 * @since 3.9
054 */
055 public class ProgramChromosome<A>
056 extends AbstractTreeChromosome<Op<A>, ProgramGene<A>>
057 {
058
059 private final Predicate<? super ProgramChromosome<A>> _validator;
060 private final ISeq<? extends Op<A>> _operations;
061 private final ISeq<? extends Op<A>> _terminals;
062
063 /**
064 * Create a new program chromosome from the given program genes. This
065 * constructor assumes that the given {@code program} is valid. Since the
066 * program validation is quite expensive, the validity check is skipped in
067 * this constructor.
068 *
069 * @param program the program. During the program evolution, newly created
070 * program trees has the same <em>depth</em> than this tree.
071 * @param validator the chromosome validator. A typical validator would
072 * check the size of the tree and if the tree is too large, mark it
073 * at <em>invalid</em>. The <em>validator</em> may be {@code null}.
074 * @param operations the allowed non-terminal operations
075 * @param terminals the allowed terminal operations
076 * @throws NullPointerException if one of the given arguments is {@code null}
077 * @throws IllegalArgumentException if either the {@code operations} or
078 * {@code terminals} sequence is empty
079 */
080 protected ProgramChromosome(
081 final ISeq<ProgramGene<A>> program,
082 final Predicate<? super ProgramChromosome<A>> validator,
083 final ISeq<? extends Op<A>> operations,
084 final ISeq<? extends Op<A>> terminals
085 ) {
086 super(program);
087 _validator = requireNonNull(validator);
088 _operations = requireNonNull(operations);
089 _terminals = requireNonNull(terminals);
090
091 if (operations.isEmpty()) {
092 throw new IllegalArgumentException("No operations given.");
093 }
094 if (terminals.isEmpty()) {
095 throw new IllegalArgumentException("No terminals given");
096 }
097 }
098
099 /**
100 * Return the allowed operations.
101 *
102 * @return the allowed operations
103 */
104 public ISeq<? extends Op<A>> getOperations() {
105 return _operations;
106 }
107
108 /**
109 * Return the allowed terminal operations.
110 *
111 * @return the allowed terminal operations
112 */
113 public ISeq<? extends Op<A>> getTerminals() {
114 return _terminals;
115 }
116
117 @Override
118 public boolean isValid() {
119 if (_valid == null) {
120 _valid = _validator.test(this);
121 }
122
123 return _valid;
124 }
125
126 private boolean isSuperValid() {
127 return ProgramChromosome.super.isValid();
128 }
129
130 /**
131 * Evaluates the root node of this chromosome.
132 *
133 * @see ProgramGene#apply(Object[])
134 * @see ProgramChromosome#eval(Object[])
135 *
136 * @param args the input variables
137 * @return the evaluated value
138 * @throws NullPointerException if the given variable array is {@code null}
139 */
140 public A apply(final A[] args) {
141 return getRoot().apply(args);
142 }
143
144 /**
145 * Evaluates the root node of this chromosome.
146 *
147 * @see ProgramGene#eval(Object[])
148 * @see ProgramChromosome#apply(Object[])
149 *
150 * @param args the function arguments
151 * @return the evaluated value
152 * @throws NullPointerException if the given variable array is {@code null}
153 */
154 @SafeVarargs
155 public final A eval(final A... args) {
156 return getRoot().eval(args);
157 }
158
159 @Override
160 public ProgramChromosome<A> newInstance(final ISeq<ProgramGene<A>> genes) {
161 return create(genes, _validator, _operations, _terminals);
162 }
163
164 @Override
165 public ProgramChromosome<A> newInstance() {
166 return create(getRoot().depth(), _validator, _operations, _terminals);
167 }
168
169 /**
170 * Create a new chromosome from the given operation tree (program).
171 *
172 * @param program the operation tree
173 * @param validator the chromosome validator. A typical validator would
174 * check the size of the tree and if the tree is too large, mark it
175 * at <em>invalid</em>. The <em>validator</em> may be {@code null}.
176 * @param operations the allowed non-terminal operations
177 * @param terminals the allowed terminal operations
178 * @param <A> the operation type
179 * @return a new chromosome from the given operation tree
180 * @throws NullPointerException if one of the given arguments is {@code null}
181 * @throws IllegalArgumentException if the given operation tree is invalid,
182 * which means there is at least one node where the operation arity
183 * and the node child count differ.
184 */
185 public static <A> ProgramChromosome<A> of(
186 final Tree<? extends Op<A>, ?> program,
187 final Predicate<? super ProgramChromosome<A>> validator,
188 final ISeq<? extends Op<A>> operations,
189 final ISeq<? extends Op<A>> terminals
190 ) {
191 Program.check(program);
192 checkOperations(operations);
193 checkTerminals(terminals);
194
195 return create(program, validator, operations, terminals);
196 }
197
198 // Create the chromosomes without checks.
199 private static <A> ProgramChromosome<A> create(
200 final Tree<? extends Op<A>, ?> program,
201 final Predicate<? super ProgramChromosome<A>> validator,
202 final ISeq<? extends Op<A>> operations,
203 final ISeq<? extends Op<A>> terminals
204 ) {
205 final ISeq<ProgramGene<A>> genes = FlatTreeNode.of(program).stream()
206 .map(n -> new ProgramGene<>(
207 n.getValue(), n.childOffset(), operations, terminals))
208 .collect(ISeq.toISeq());
209
210 return new ProgramChromosome<>(genes, validator, operations, terminals);
211 }
212
213 private static void checkOperations(final ISeq<? extends Op<?>> operations) {
214 final ISeq<?> terminals = operations.stream()
215 .filter(op -> op.isTerminal())
216 .map(op -> (Op<?>)op)
217 .collect(ISeq.toISeq());
218
219 if (!terminals.isEmpty()) {
220 throw new IllegalArgumentException(format(
221 "Operations must not contain terminals: %s",
222 terminals.toString(",")
223 ));
224 }
225 }
226
227 private static void checkTerminals(final ISeq<? extends Op<?>> terminals) {
228 final ISeq<?> operations = terminals.stream()
229 .filter(op -> !op.isTerminal())
230 .map(op -> (Op<?>)op)
231 .collect(ISeq.toISeq());
232
233 if (!operations.isEmpty()) {
234 throw new IllegalArgumentException(format(
235 "Terminals must not contain operations: %s",
236 operations.toString(",")
237 ));
238 }
239 }
240
241 /**
242 * Create a new chromosome from the given operation tree (program).
243 *
244 * @param program the operation tree
245 * @param operations the allowed non-terminal operations
246 * @param terminals the allowed terminal operations
247 * @param <A> the operation type
248 * @return a new chromosome from the given operation tree
249 * @throws NullPointerException if one of the given arguments is {@code null}
250 * @throws IllegalArgumentException if the given operation tree is invalid,
251 * which means there is at least one node where the operation arity
252 * and the node child count differ.
253 */
254 public static <A> ProgramChromosome<A> of(
255 final Tree<? extends Op<A>, ?> program,
256 final ISeq<? extends Op<A>> operations,
257 final ISeq<? extends Op<A>> terminals
258 ) {
259 return of(program, ProgramChromosome::isSuperValid, operations, terminals);
260 }
261
262 /**
263 * Create a new program chromosome with the defined depth. This method will
264 * create a <em>full</em> program tree.
265 *
266 * @param depth the depth of the created program tree
267 * @param validator the chromosome validator. A typical validator would
268 * check the size of the tree and if the tree is too large, mark it
269 * at <em>invalid</em>. The <em>validator</em> may be {@code null}.
270 * @param operations the allowed non-terminal operations
271 * @param terminals the allowed terminal operations
272 * @param <A> the operation type
273 * @return a new program chromosome from the given (flattened) program tree
274 * @throws NullPointerException if one of the parameters is {@code null}
275 * @throws IllegalArgumentException if the {@code depth} is smaller than zero
276 */
277 public static <A> ProgramChromosome<A> of(
278 final int depth,
279 final Predicate<? super ProgramChromosome<A>> validator,
280 final ISeq<? extends Op<A>> operations,
281 final ISeq<? extends Op<A>> terminals
282 ) {
283 checkOperations(operations);
284 checkTerminals(terminals);
285
286 return create(depth, validator, operations, terminals);
287 }
288
289 private static <A> ProgramChromosome<A> create(
290 final int depth,
291 final Predicate<? super ProgramChromosome<A>> validator,
292 final ISeq<? extends Op<A>> operations,
293 final ISeq<? extends Op<A>> terminals
294 ) {
295 return create(
296 Program.of(depth, operations, terminals),
297 validator,
298 operations,
299 terminals
300 );
301 }
302
303 /**
304 * Create a new program chromosome with the defined depth. This method will
305 * create a <em>full</em> program tree.
306 *
307 * @param depth the depth of the created (full) program tree
308 * @param operations the allowed non-terminal operations
309 * @param terminals the allowed terminal operations
310 * @param <A> the operation type
311 * @return a new program chromosome from the given (flattened) program tree
312 * @throws NullPointerException if one of the parameters is {@code null}
313 * @throws IllegalArgumentException if the {@code depth} is smaller than zero
314 */
315 public static <A> ProgramChromosome<A> of(
316 final int depth,
317 final ISeq<? extends Op<A>> operations,
318 final ISeq<? extends Op<A>> terminals
319 ) {
320 return of(depth, ProgramChromosome::isSuperValid, operations, terminals);
321 }
322
323 /**
324 * Create a new program chromosome from the given (flattened) program tree.
325 * This method doesn't make any assumption about the validity of the given
326 * operation tree. If the tree is not valid, it will repair it. This
327 * behaviour allows the <em>safe</em> usage of all existing alterer.
328 *
329 * <pre>{@code
330 * final ProgramChromosome<Double> ch = ProgramChromosome.of(
331 * genes,
332 * // If the program has more that 200 nodes, it is marked as "invalid".
333 * ch -> ch.length() <= 200,
334 * operations,
335 * terminals
336 * );
337 * }</pre>
338 *
339 * @param genes the program genes
340 * @param validator the chromosome validator to use
341 * @param operations the allowed non-terminal operations
342 * @param terminals the allowed terminal operations
343 * @param <A> the operation type
344 * @return a new program chromosome from the given (flattened) program tree
345 * @throws NullPointerException if one of the parameters is {@code null}
346 */
347 public static <A> ProgramChromosome<A> of(
348 final ISeq<ProgramGene<A>> genes,
349 final Predicate<? super ProgramChromosome<A>> validator,
350 final ISeq<? extends Op<A>> operations,
351 final ISeq<? extends Op<A>> terminals
352 ) {
353 final TreeNode<Op<A>> program = Program.toTree(genes, terminals);
354 return of(program, validator, operations, terminals);
355 }
356
357 private static <A> ProgramChromosome<A> create(
358 final ISeq<ProgramGene<A>> genes,
359 final Predicate<? super ProgramChromosome<A>> validator,
360 final ISeq<? extends Op<A>> operations,
361 final ISeq<? extends Op<A>> terminals
362 ) {
363 final TreeNode<Op<A>> program = Program.toTree(genes, terminals);
364 return create(program, validator, operations, terminals);
365 }
366
367 public static <A> ProgramChromosome<A> of(
368 final ISeq<ProgramGene<A>> genes,
369 final ISeq<? extends Op<A>> operations,
370 final ISeq<? extends Op<A>> terminals
371 ) {
372 return of(genes, ProgramChromosome::isSuperValid, operations, terminals);
373 }
374
375 }
|