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