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