Constraint.java
001 /*
002  * Java Genetic Algorithm Library (jenetics-6.3.0).
003  * Copyright (c) 2007-2021 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.engine;
021 
022 import static java.util.Objects.requireNonNull;
023 
024 import java.util.function.BiFunction;
025 import java.util.function.Function;
026 import java.util.function.Predicate;
027 
028 import io.jenetics.Gene;
029 import io.jenetics.Genotype;
030 import io.jenetics.Phenotype;
031 import 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  <pre>{@code
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  * }</pre>
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  <pre>{@code
059  * final Constraint<DoubleGene, Double> constraint = ...;
060  * final Factory<Genotype<DoubleGene>> gtf = ...;
061  * final Engine<DoubleGene, Double> engine = Engine
062  *     .builder(fitness, constraint.constrain(gtf))
063  *     .constraint(constraint)
064  *     .build();
065  * }</pre>
066  *
067  * The following example illustrates how a constraint which its repair function
068  * can be 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 evenly distribution of the values in the valid ranges, which is
083  * an important characteristic of the repair function.
084  *
085  <pre>{@code
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  * }</pre>
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  <pre>{@code
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  * }</pre>
114  * The same example with an {@link InvertibleCodec} will look like this:
115  <pre>{@code
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  * }</pre>
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 not needed 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  */
145 public interface Constraint<
146     extends Gene<?, G>,
147     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      <pre>{@code
187      * final Constraint<DoubleGene, Double> constraint = ...;
188      * final Factory<Genotype<DoubleGene>> gtf = ...;
189      * final Engine<DoubleGene, Double> engine = Engine
190      *     .builder(fitness, constraint.constrain(gtf))
191      *     .constraint(constraint)
192      *     .build();
193      * }</pre>
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 a 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 a 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 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 to simplify the
307      * needed validator and repairer.
308      *
309      @since 5.2
310      *
311      @param codec the invertible codec used for simplify the needed
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 }