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