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.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 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 * <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 }
|