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