001 /*
002 * Java Genetic Algorithm Library (jenetics-5.2.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.Phenotype;
030
031 /**
032 * This interface allows you to define constraints on single phenotypes. It is a
033 * more advanced version of the {@link Phenotype#isValid()} method, which checks
034 * the validity of the underlying genotypes and/or chromosomes. Additionally it
035 * is possible to <em>repair</em> invalid individuals. The evolution
036 * {@link Engine} is using the constraint in the following way: check the validity
037 * and repair invalid individuals.
038 * <pre>{@code
039 * for (int i = 0; i < population.size(); ++i) {
040 * final Phenotype<G, C> individual = population.get(i);
041 * if (!constraint.test(individual)) {
042 * population.set(i, constraint.repair(individual, generation));
043 * }
044 * }
045 * }</pre>
046 *
047 * The following example illustrates how a constraint which its repair function
048 * can be look like. Imagine that your problem domain consists of double values
049 * between <em>[0, 2)</em> and <em>[8, 10)</em>. Since it is not possible
050 * <pre>{@code
051 * +--+--+--+--+--+--+--+--+--+--+
052 * | | | | | | | | | | |
053 * 0 1 2 3 4 5 6 7 8 9 10
054 * |-----|xxxxxxxxxxxxxxxxx|-----|
055 * ^ |llllllll|rrrrrrrr| ^
056 * | | | |
057 * +-------+ +------+
058 * }</pre>
059 * The invalid range is marked with {@code x}. Repairing an invalid value will
060 * map values in the {@code l} range on the valid range <em>[0, 2)</em>, and
061 * value in the {@code r} range on the valid range <em>[8, 10)</em>. This mapping
062 * guarantees an evenly distribution of the values in the valid ranges, which is
063 * an important characteristic of the repair function.
064 *
065 * <pre>{@code
066 * final InvertibleCodec<Double, DoubleGene> codec = Codecs.ofScalar(DoubleRange.of(0, 10));
067 * final Constraint<DoubleGene, Double> constraint = Constraint.of(
068 * codec,
069 * v -> v < 2 || v >= 8,
070 * v -> {
071 * if (v >= 2 && v < 8) {
072 * return v < 5 ? ((v - 2)/3)*2 : ((8 - v)/3)*2 + 8;
073 * }
074 * return v;
075 * }
076 * );
077 * }</pre>
078 *
079 * <b>Alternative solution</b><br>
080 * Instead of repairing individuals, it is better to not create invalid one in
081 * the first place. Once you have a proper <em>repair</em> strategy, you can use
082 * it to create a {@link Codec} which only creates valid individuals, using your
083 * repair method.
084 * <pre>{@code
085 * final Codec<Double, DoubleGene> codec = Codecs
086 * .ofScalar(DoubleRange.of(0, 10))
087 * .map(v -> {
088 * if (v >= 2 && v < 8) {
089 * return v < 5 ? ((v - 2)/3)*2 : ((8 - v)/3)*2 + 8;
090 * }
091 * return v;
092 * });
093 * }</pre>
094 * The same example with an {@link InvertibleCodec} will look like this:
095 * <pre>{@code
096 * final InvertibleCodec<Double, DoubleGene> codec = Codecs
097 * .ofScalar(DoubleRange.of(0, 10))
098 * .map(v -> {
099 * if (v >= 2 && v < 8) {
100 * return v < 5 ? ((v - 2)/3)*2 : ((8 - v)/3)*2 + 8;
101 * }
102 * return v;
103 * },
104 * Function.identity());
105 * }</pre>
106 *
107 * @see Engine.Builder#constraint(Constraint)
108 * @see RetryConstraint
109 *
110 * @apiNote
111 * This class is part of the more advanced API and is not needed for default use
112 * cases. If the {@link Engine} is created with an explicit constraint
113 * ({@link Engine.Builder#constraint(Constraint)}), the <em>default</em>
114 * validation mechanism via {@link Phenotype#isValid()} is overridden. Also keep
115 * in mind, that a defined constraint doesn't protect the fitness function from
116 * <em>invalid</em> values. It is still necessary that the fitness function must
117 * handle invalid values accordingly. The constraint <em>only</em> filters
118 * invalid individuals after the selection and altering step.
119 *
120 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
121 * @version 5.2
122 * @since 5.0
123 */
124 public interface Constraint<
125 G extends Gene<?, G>,
126 C extends Comparable<? super C>
127 > {
128
129 /**
130 * Checks the validity of the given {@code individual}.
131 *
132 * @param individual the phenotype to check
133 * @return {@code true} if the given {@code individual} is valid,
134 * {@code false} otherwise
135 * @throws NullPointerException if the given {@code individual} is
136 * {@code null}
137 */
138 boolean test(final Phenotype<G, C> individual);
139
140 /**
141 * Tries to repair the given phenotype. This method is called by the
142 * evolution {@link Engine} if the {@link #test(Phenotype)} method returned
143 * {@code false}.
144 *
145 * @param individual the phenotype to repair
146 * @param generation the actual generation used for the repaired phenotype
147 * @return a newly created, valid phenotype. The implementation is free to
148 * use the given invalid {@code individual} as a starting point for
149 * the created phenotype.
150 * @throws NullPointerException if the given {@code individual} is
151 * {@code null}
152 */
153 Phenotype<G, C> repair(
154 final Phenotype<G, C> individual,
155 final long generation
156 );
157
158
159 /**
160 * Return a new constraint object with the given {@code validator} and
161 * {@code repairer}.
162 *
163 * @param validator the phenotype validator used by the constraint
164 * @param repairer the phenotype repairer used by the constraint
165 * @param <G> the gene type
166 * @param <C> the fitness value type
167 * @return a new constraint strategy
168 * @throws NullPointerException if one of the arguments is {@code null}
169 */
170 static <G extends Gene<?, G>, C extends Comparable<? super C>>
171 Constraint<G, C> of(
172 final Predicate<? super Phenotype<G, C>> validator,
173 final BiFunction<? super Phenotype<G, C>, Long, Phenotype<G, C>> repairer
174 ) {
175 requireNonNull(validator);
176 requireNonNull(repairer);
177
178 return new Constraint<G, C>() {
179 @Override
180 public boolean test(final Phenotype<G, C> individual) {
181 return validator.test(individual);
182 }
183
184 @Override
185 public Phenotype<G, C> repair(
186 final Phenotype<G, C> individual,
187 final long generation
188 ) {
189 return repairer.apply(individual, generation);
190 }
191 };
192 }
193
194 /**
195 * Return a new constraint object with the given {@code validator}. The used
196 * repairer just creates a new phenotype by using the phenotype to be
197 * repaired as template. The <em>repaired</em> phenotype might still be
198 * invalid.
199 *
200 * @param validator the phenotype validator used by the constraint
201 * @param <G> the gene type
202 * @param <C> the fitness value type
203 * @return a new constraint strategy
204 * @throws NullPointerException if one of the arguments is {@code null}
205 */
206 static <G extends Gene<?, G>, C extends Comparable<? super C>>
207 Constraint<G, C> of(final Predicate<? super Phenotype<G, C>> validator) {
208 return of(
209 validator,
210 (pt, gen) -> Phenotype.of(pt.genotype().newInstance(), gen)
211 );
212 }
213
214 /**
215 * Return a new constraint object with the given {@code validator} and
216 * {@code repairer}. The given invertible codec allows to simplify the
217 * needed validator and repairer.
218 *
219 * @since 5.2
220 *
221 * @param codec the invertible codec used for simplify the needed
222 * validator and repairer
223 * @param validator the phenotype validator used by the constraint
224 * @param repairer the phenotype repairer used by the constraint
225 * @param <T> the type of the <em>native</em> problem domain
226 * @param <G> the gene type
227 * @param <C> the fitness value type
228 * @return a new constraint strategy
229 * @throws NullPointerException if one of the arguments is {@code null}
230 */
231 static <T, G extends Gene<?, G>, C extends Comparable<? super C>>
232 Constraint<G, C> of(
233 final InvertibleCodec<T, G> codec,
234 final Predicate<? super T> validator,
235 final Function<? super T, ? extends T> repairer
236 ) {
237 requireNonNull(codec);
238 requireNonNull(validator);
239 requireNonNull(repairer);
240
241 return of(
242 pt -> validator.test(codec.decode(pt.genotype())),
243 (pt, gen) -> Phenotype.of(
244 codec.encode(repairer.apply(codec.decode(pt.genotype()))),
245 gen
246 )
247 );
248 }
249
250 }
|