001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 * Copyright (c) 2007-2024 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.engine;
021
022import static java.util.Objects.requireNonNull;
023
024import java.util.function.BiFunction;
025import java.util.function.Function;
026import java.util.function.Predicate;
027
028import io.jenetics.Gene;
029import io.jenetics.Genotype;
030import io.jenetics.Phenotype;
031import io.jenetics.util.Factory;
032
033/**
034 * This interface allows you to define constraints on single phenotypes. It is a
035 * more advanced version of the {@link Phenotype#isValid()} method, which checks
036 * the validity of the underlying genotypes and/or chromosomes. Additionally, it
037 * is possible to <em>repair</em> invalid individuals. The evolution
038 * {@link Engine} is using the constraint in the following way: check the validity
039 * and repair invalid individuals.
040 * {@snippet lang="java":
041 * for (int i = 0; i < population.size(); ++i) {
042 *     final Phenotype<G, C> individual = population.get(i);
043 *     if (!constraint.test(individual)) {
044 *         population.set(i, constraint.repair(individual, generation));
045 *     }
046 * }
047 * }
048 *
049 * <b>Note</b><br>
050 * Keep in mind, that this interface only repairs invalid individuals, which
051 * has been destroyed by the <em>evolution</em> process. Individuals, created
052 * by the given {@code Factory<Genotype<G>>}, are not validated and repaired.
053 * This means that it is still possible to have invalid individuals, created
054 * by the genotype factory. The {@link #constrain(Factory)} will wrap the given
055 * factory which obeys {@code this} constraint. The following code will show
056 * how to create such a <em>constrained</em> genotype factory and use it for
057 * creating an evolution engine.
058 * {@snippet lang="java":
059 * final Constraint<DoubleGene, Double> constraint = null; // @replace substring='null' replacement="..."
060 * final Factory<Genotype<DoubleGene>> gtf = null; // @replace substring='null' replacement="..."
061 * final Engine<DoubleGene, Double> engine = Engine
062 *     .builder(fitness, constraint.constrain(gtf))
063 *     .constraint(constraint)
064 *     .build();
065 * }
066 *
067 * The following example illustrates how a constraint which its repair function
068 * can look like. Imagine that your problem domain consists of double values
069 * between <em>[0, 2)</em> and <em>[8, 10)</em>. Since it is not possible
070 * <pre>{@code
071 *   +--+--+--+--+--+--+--+--+--+--+
072 *   |  |  |  |  |  |  |  |  |  |  |
073 *   0  1  2  3  4  5  6  7  8  9  10
074 *   |-----|xxxxxxxxxxxxxxxxx|-----|
075 *      ^  |llllllll|rrrrrrrr|  ^
076 *      |       |        |      |
077 *      +-------+        +------+
078 * }</pre>
079 * The invalid range is marked with {@code x}. Repairing an invalid value will
080 * map values in the {@code l} range on the valid range <em>[0, 2)</em>, and
081 * value in the {@code r} range on the valid range <em>[8, 10)</em>. This mapping
082 * guarantees an even distribution of the values in the valid ranges, which is
083 * an important characteristic of the repair function.
084 *
085 * {@snippet lang="java":
086 * final InvertibleCodec<Double, DoubleGene> codec = Codecs.ofScalar(DoubleRange.of(0, 10));
087 * final Constraint<DoubleGene, Double> constraint = Constraint.of(
088 *     codec,
089 *     v -> v < 2 || v >= 8,
090 *     v -> {
091 *         if (v >= 2 && v < 8) {
092 *             return v < 5 ? ((v - 2)/3)*2 : ((8 - v)/3)*2 + 8;
093 *         }
094 *         return v;
095 *     }
096 * );
097 * }
098 *
099 * <b>Alternative solution</b><br>
100 * Instead of repairing individuals, it is better to not create invalid one in
101 * the first place. Once you have a proper <em>repair</em> strategy, you can use
102 * it to create a {@link Codec} which only creates valid individuals, using your
103 * repair method.
104 * {@snippet lang="java":
105 * final Codec<Double, DoubleGene> codec = Codecs
106 *     .ofScalar(DoubleRange.of(0, 10))
107 *     .map(v -> {
108 *             if (v >= 2 && v < 8) {
109 *                 return v < 5 ? ((v - 2)/3)*2 : ((8 - v)/3)*2 + 8;
110 *             }
111 *             return v;
112 *         });
113 * }
114 * The same example with an {@link InvertibleCodec} will look like this:
115 * {@snippet lang="java":
116 * final InvertibleCodec<Double, DoubleGene> codec = Codecs
117 *     .ofScalar(DoubleRange.of(0, 10))
118 *     .map(v -> {
119 *             if (v >= 2 && v < 8) {
120 *                 return v < 5 ? ((v - 2)/3)*2 : ((8 - v)/3)*2 + 8;
121 *             }
122 *             return v;
123 *         },
124 *         Function.identity());
125 * }
126 *
127 * @see Engine.Builder#constraint(Constraint)
128 * @see RetryConstraint
129 * @see #constrain(Factory)
130 *
131 * @apiNote
132 * This class is part of the more advanced API and is unnecessary for default use
133 * cases. If the {@link Engine} is created with an explicit constraint
134 * ({@link Engine.Builder#constraint(Constraint)}), the <em>default</em>
135 * validation mechanism via {@link Phenotype#isValid()} is overridden. Also keep
136 * in mind that a defined constraint doesn't protect the fitness function from
137 * <em>invalid</em> values. It is still necessary that the fitness function must
138 * handle invalid values accordingly. The constraint <em>only</em> filters
139 * invalid individuals after the selection and altering step.
140 *
141 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
142 * @version 6.1
143 * @since 5.0
144 */
145public interface Constraint<
146        G extends Gene<?, G>,
147        C extends Comparable<? super C>
148> {
149
150        /**
151         * Checks the validity of the given {@code individual}.
152         *
153         * @param individual the phenotype to check
154         * @return {@code true} if the given {@code individual} is valid,
155         *         {@code false} otherwise
156         * @throws NullPointerException if the given {@code individual} is
157         *         {@code null}
158         */
159        boolean test(final Phenotype<G, C> individual);
160
161        /**
162         * Tries to repair the given phenotype. This method is called by the
163         * evolution {@link Engine} if the {@link #test(Phenotype)} method returned
164         * {@code false}.
165         *
166         * @param individual the phenotype to repair
167         * @param generation the actual generation, where this method is called by
168         *        the evolution engine
169         * @return a newly created, valid phenotype. The implementation is free to
170         *         use the given invalid {@code individual} as a starting point for
171         *         the created phenotype.
172         * @throws NullPointerException if the given {@code individual} is
173         *         {@code null}
174         */
175        Phenotype<G, C> repair(
176                final Phenotype<G, C> individual,
177                final long generation
178        );
179
180        /**
181         * Wraps the given genotype factory into a factory, which only creates
182         * individuals obeying {@code this} constraint. The following code will
183         * create an evolution engine, where also the genotype factory will only
184         * create valid individuals.
185         *
186         * {@snippet lang="java":
187         * final Constraint<DoubleGene, Double> constraint = null; // @replace substring='null' replacement="..."
188         * final Factory<Genotype<DoubleGene>> gtf = null; // @replace substring='null' replacement="..."
189         * final Engine<DoubleGene, Double> engine = Engine
190         *     .builder(fitness, constraint.constrain(gtf))
191         *     .constraint(constraint)
192         *     .build();
193         * }
194         *
195         * @since 6.1
196         *
197         * @see #constrain(Codec)
198         * @see #constrain(InvertibleCodec)
199         *
200         * @param gtf the genotype factory to wrap
201         * @return a new constrained genotype factory.
202         * @throws NullPointerException if the given genotype factory is {@code null}
203         */
204        default Factory<Genotype<G>> constrain(final Factory<Genotype<G>> gtf) {
205                requireNonNull(gtf);
206                return () -> {
207                        final Phenotype<G, C> result = Phenotype.of(gtf.newInstance(), 1);
208                        return (test(result) ? result : repair(result, 1)).genotype();
209                };
210        }
211
212        /**
213         * Wraps the given codec into a codec, which obeys {@code this} constraint.
214         *
215         * @since 6.1
216         *
217         * @see #constrain(Factory)
218         * @see #constrain(InvertibleCodec)
219         *
220         * @param codec the codec to wrap
221         * @param <T> the argument type of given problem
222         * @return the wrapped codec, which obeys {@code this} constraint
223         * @throws NullPointerException if the given {@code codec} is {@code null}
224         */
225        default <T> Codec<T, G> constrain(final Codec<T, G> codec) {
226                return Codec.of(constrain(codec.encoding()), codec.decoder());
227        }
228
229        /**
230         * Wraps the given codec into a codec, which obeys {@code this} constraint.
231         *
232         * @since 6.1
233         *
234         * @see #constrain(Factory)
235         * @see #constrain(Codec)
236         *
237         * @param codec the codec to wrap
238         * @param <T> the argument type of given problem
239         * @return the wrapped codec, which obeys {@code this} constraint
240         * @throws NullPointerException if the given {@code codec} is {@code null}
241         */
242        default <T> InvertibleCodec<T, G> constrain(final InvertibleCodec<T, G> codec) {
243                return InvertibleCodec.of(
244                        constrain(codec.encoding()),
245                        codec.decoder(),
246                        codec.encoder()
247                );
248        }
249
250        /**
251         * Return a new constraint object with the given {@code validator} and
252         * {@code repairer}.
253         *
254         * @param validator the phenotype validator used by the constraint
255         * @param repairer the phenotype repairer used by the constraint
256         * @param <G> the gene type
257         * @param <C> the fitness value type
258         * @return a new constraint strategy
259         * @throws NullPointerException if one of the arguments is {@code null}
260         */
261        static <G extends Gene<?, G>, C extends Comparable<? super C>>
262        Constraint<G, C> of(
263                final Predicate<? super Phenotype<G, C>> validator,
264                final BiFunction<? super Phenotype<G, C>, Long, Phenotype<G, C>> repairer
265        ) {
266                requireNonNull(validator);
267                requireNonNull(repairer);
268
269                return new Constraint<>() {
270                        @Override
271                        public boolean test(final Phenotype<G, C> individual) {
272                                return validator.test(individual);
273                        }
274
275                        @Override
276                        public Phenotype<G, C> repair(
277                                final Phenotype<G, C> individual,
278                                final long generation
279                        ) {
280                                return repairer.apply(individual, generation);
281                        }
282                };
283        }
284
285        /**
286         * Return a new constraint object with the given {@code validator}. The used
287         * repairer just creates a new phenotype by using the phenotype to be
288         * repaired as a template. The <em>repaired</em> phenotype might still be
289         * invalid.
290         *
291         * @see RetryConstraint#of(Predicate)
292         *
293         * @param validator the phenotype validator used by the constraint
294         * @param <G> the gene type
295         * @param <C> the fitness value type
296         * @return a new constraint strategy
297         * @throws NullPointerException if one of the arguments is {@code null}
298         */
299        static <G extends Gene<?, G>, C extends Comparable<? super C>>
300        Constraint<G, C> of(final Predicate<? super Phenotype<G, C>> validator) {
301                return RetryConstraint.of(validator);
302        }
303
304        /**
305         * Return a new constraint object with the given {@code validator} and
306         * {@code repairer}. The given invertible codec allows simplifying the
307         * necessary validator and repairer.
308         *
309         * @since 5.2
310         *
311         * @param codec the invertible codec used for simplify the necessary
312         *        validator and repairer
313         * @param validator the phenotype validator used by the constraint
314         * @param repairer the phenotype repairer used by the constraint
315         * @param <T> the type of the <em>native</em> problem domain
316         * @param <G> the gene type
317         * @param <C> the fitness value type
318         * @return a new constraint strategy
319         * @throws NullPointerException if one of the arguments is {@code null}
320         */
321        static <T, G extends Gene<?, G>, C extends Comparable<? super C>>
322        Constraint<G, C> of(
323                final InvertibleCodec<T, G> codec,
324                final Predicate<? super T> validator,
325                final Function<? super T, ? extends T> repairer
326        ) {
327                requireNonNull(codec);
328                requireNonNull(validator);
329                requireNonNull(repairer);
330
331                return of(
332                        pt -> validator.test(codec.decode(pt.genotype())),
333                        (pt, gen) -> Phenotype.of(
334                                codec.encode(repairer.apply(codec.decode(pt.genotype()))),
335                                gen
336                        )
337                );
338        }
339
340}