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