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.ext.moea;
021
022 import static java.lang.String.format;
023 import static java.util.Objects.requireNonNull;
024 import static io.jenetics.ext.moea.Pareto.front;
025
026 import java.util.Comparator;
027 import java.util.Objects;
028 import java.util.function.ToIntFunction;
029 import java.util.stream.Collector;
030
031 import io.jenetics.Gene;
032 import io.jenetics.Optimize;
033 import io.jenetics.Phenotype;
034 import io.jenetics.engine.EvolutionResult;
035 import io.jenetics.util.ISeq;
036 import io.jenetics.util.IntRange;
037
038 /**
039 * Collectors for collecting final <em>pareto-set</em> for multi-objective
040 * optimization.
041 *
042 * <pre>{@code
043 * final Problem<double[], DoubleGene, Vec<double[]>> problem = Problem.of(
044 * v -> Vec.of(v[0]*cos(v[1]), v[0]*sin(v[1])),
045 * Codecs.ofVector(
046 * DoubleRange.of(0, 1),
047 * DoubleRange.of(0, 2*PI)
048 * )
049 * );
050 *
051 * final Engine<DoubleGene, Vec<double[]>> engine = Engine.builder(problem)
052 * .alterers(
053 * new Mutator<>(0.1),
054 * new MeanAlterer<>())
055 * .offspringSelector(new TournamentSelector<>(2))
056 * .survivorsSelector(UFTournamentSelector.ofVec())
057 * .build();
058 *
059 * final ISeq<Phenotype<DoubleGene, Vec<double[]>>> result = engine.stream()
060 * .limit(Limits.byFixedGeneration(50))
061 * .collect(MOEA.toParetoSet());
062 * }</pre>
063 *
064 *
065 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
066 * @version 5.1
067 * @since 4.1
068 */
069 public final class MOEA {
070
071 private static final IntRange DEFAULT_SET_RANGE = IntRange.of(75, 100);
072
073 private MOEA() {
074 }
075
076 /**
077 * Collector of {@link Phenotype} objects, who's (multi-objective) fitness
078 * value is part of the <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">
079 * pareto front</a>.
080 *
081 * @param <G> the gene type
082 * @param <T> the array type, e.g. {@code double[]}
083 * @param <V> the multi object result type vector
084 * @return the pareto set collector
085 * @throws IllegalArgumentException if the minimal pareto set {@code size}
086 * is smaller than one
087 */
088 public static <G extends Gene<?, G>, T, V extends Vec<T>>
089 Collector<EvolutionResult<G, V>, ?, ISeq<Phenotype<G, V>>>
090 toParetoSet() {
091 return toParetoSet(DEFAULT_SET_RANGE);
092 }
093
094 /**
095 * Collector of {@link Phenotype} objects, who's (multi-objective) fitness
096 * value is part of the <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">
097 * pareto front</a>.
098 *
099 * @param size the allowed size range of the returned pareto set. If the
100 * size of the pareto set is bigger than {@code size.getMax()},
101 * during the collection, it is reduced to {@code size.getMin()}.
102 * Pareto set elements which are close to each other are removed firsts.
103 * @param <G> the gene type
104 * @param <T> the array type, e.g. {@code double[]}
105 * @param <V> the multi object result type vector
106 * @return the pareto set collector
107 * @throws NullPointerException if one the {@code size} is {@code null}
108 * @throws IllegalArgumentException if the minimal pareto set {@code size}
109 * is smaller than one
110 */
111 public static <G extends Gene<?, G>, T, V extends Vec<T>>
112 Collector<EvolutionResult<G, V>, ?, ISeq<Phenotype<G, V>>>
113 toParetoSet(final IntRange size) {
114 return toParetoSet(
115 size,
116 Vec::dominance,
117 Vec::compare,
118 Vec::distance,
119 Vec::length
120 );
121 }
122
123 /**
124 * Collector of {@link Phenotype} objects, who's (multi-objective) fitness
125 * value is part of the <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">
126 * pareto front</a>.
127 *
128 * @see #toParetoSet(IntRange)
129 *
130 * @param size the allowed size range of the returned pareto set. If the
131 * size of the pareto set is bigger than {@code size.getMax()},
132 * during the collection, it is reduced to {@code size.getMin()}.
133 * Pareto set elements which are close to each other are removed firsts.
134 * @param dominance the pareto dominance measure of the fitness result type
135 * {@code C}
136 * @param comparator the comparator of the elements of the vector type
137 * {@code C}
138 * @param distance the distance function of two elements of the vector
139 * type {@code C}
140 * @param dimension the dimensionality of the result vector {@code C}.
141 * Usually {@code Vec::length}.
142 * @param <G> the gene type
143 * @param <C> the multi object result vector. E.g. {@code Vec<double[]>}
144 * @return the pareto set collector
145 * @throws NullPointerException if one the arguments is {@code null}
146 * @throws IllegalArgumentException if the minimal pareto set {@code size}
147 * is smaller than one
148 */
149 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
150 Collector<EvolutionResult<G, C>, ?, ISeq<Phenotype<G, C>>>
151 toParetoSet(
152 final IntRange size,
153 final Comparator<? super C> dominance,
154 final ElementComparator<? super C> comparator,
155 final ElementDistance<? super C> distance,
156 final ToIntFunction<? super C> dimension
157 ) {
158 requireNonNull(size);
159 requireNonNull(dominance);
160 requireNonNull(distance);
161
162 if (size.min() < 1) {
163 throw new IllegalArgumentException(format(
164 "Minimal pareto set size must be greater than zero: %d",
165 size.min()
166 ));
167 }
168
169 return Collector.of(
170 () -> new Front<G, C>(
171 size, dominance, comparator, distance, dimension
172 ),
173 Front::add,
174 Front::merge,
175 Front::toISeq
176 );
177 }
178
179 private static final class Front<
180 G extends Gene<?, G>,
181 C extends Comparable<? super C>
182 > {
183
184 final IntRange _size;
185 final Comparator<? super C> _dominance;
186 final ElementComparator<? super C> _comparator;
187 final ElementDistance<? super C> _distance;
188 final ToIntFunction<? super C> _dimension;
189
190 private Optimize _optimize;
191 private ParetoFront<Phenotype<G, C>> _front;
192
193 Front(
194 final IntRange size,
195 final Comparator<? super C> dominance,
196 final ElementComparator<? super C> comparator,
197 final ElementDistance<? super C> distance,
198 final ToIntFunction<? super C> dimension
199 ) {
200 _size = size;
201 _dominance = dominance;
202 _comparator = comparator;
203 _distance = distance;
204 _dimension = dimension;
205 }
206
207 void add(final EvolutionResult<G, C> result) {
208 if (_front == null) {
209 _optimize = result.optimize();
210 _front = new ParetoFront<>(this::dominance, this::equals);
211 }
212
213 final ISeq<Phenotype<G, C>> front = front(
214 result.population(),
215 this::dominance
216 );
217 _front.addAll(front.asList());
218 trim();
219 }
220
221 private int dominance(final Phenotype<G, C> a, final Phenotype<G, C> b) {
222 return _optimize == Optimize.MAXIMUM
223 ? _dominance.compare(a.fitness(), b.fitness())
224 : _dominance.compare(b.fitness(), a.fitness());
225 }
226
227 private boolean equals(final Phenotype<?, ?> a, final Phenotype<?, ?> b) {
228 return Objects.equals(a.genotype(), b.genotype());
229 }
230
231 private void trim() {
232 assert _front != null;
233 assert _optimize != null;
234
235 if (_front.size() > _size.max() - 1) {
236 _front.trim(
237 _size.min(),
238 this::compare,
239 _distance.map(Phenotype::fitness),
240 v -> _dimension.applyAsInt(v.fitness())
241 );
242 }
243 }
244
245 private int compare(
246 final Phenotype<G, C> a,
247 final Phenotype<G, C> b,
248 final int i
249 ) {
250 return _optimize == Optimize.MAXIMUM
251 ? _comparator.compare(a.fitness(), b.fitness(), i)
252 : _comparator.compare(b.fitness(), a.fitness(), i);
253 }
254
255 Front<G, C> merge(final Front<G, C> front) {
256 _front.merge(front._front);
257 trim();
258 return this;
259 }
260
261 ISeq<Phenotype<G, C>> toISeq() {
262 return _front != null ? _front.toISeq() : ISeq.empty();
263 }
264
265 }
266
267 }
|