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