ProgramChromosome.java
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 }