001 /*
002 * Java Genetic Algorithm Library (jenetics-5.1.0).
003 * Copyright (c) 2007-2019 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<T>::dominance,
117 Vec<T>::compare,
118 Vec<T>::distance,
119 Vec<T>::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.getMin() < 1) {
163 throw new IllegalArgumentException(format(
164 "Minimal pareto set size must be greater than zero: %d",
165 size.getMin()
166 ));
167 }
168
169 return Collector.of(
170 () -> new Front<G, C>(
171 size, dominance, comparator, distance, dimension),
172 Front::add,
173 Front::merge,
174 Front::toISeq
175 );
176 }
177
178 private static final class Front<
179 G extends Gene<?, G>,
180 C extends Comparable<? super C>
181 > {
182
183 final IntRange _size;
184 final Comparator<? super C> _dominance;
185 final ElementComparator<? super C> _comparator;
186 final ElementDistance<? super C> _distance;
187 final ToIntFunction<? super C> _dimension;
188
189 private Optimize _optimize;
190 private ParetoFront<Phenotype<G, C>> _front;
191
192 Front(
193 final IntRange size,
194 final Comparator<? super C> dominance,
195 final ElementComparator<? super C> comparator,
196 final ElementDistance<? super C> distance,
197 final ToIntFunction<? super C> dimension
198 ) {
199 _size = size;
200 _dominance = dominance;
201 _comparator = comparator;
202 _distance = distance;
203 _dimension = dimension;
204 }
205
206 void add(final EvolutionResult<G, C> result) {
207 if (_front == null) {
208 _optimize = result.getOptimize();
209 _front = new ParetoFront<>(this::dominance, this::equals);
210 }
211
212 final ISeq<Phenotype<G, C>> front = front(
213 result.getPopulation(),
214 this::dominance
215 );
216 _front.addAll(front.asList());
217 trim();
218 }
219
220 private int dominance(final Phenotype<G, C> a, final Phenotype<G, C> b) {
221 return _optimize == Optimize.MAXIMUM
222 ? _dominance.compare(a.getFitness(), b.getFitness())
223 : _dominance.compare(b.getFitness(), a.getFitness());
224 }
225
226 private boolean equals(final Phenotype<?, ?> a, final Phenotype<?, ?> b) {
227 return Objects.equals(a.getGenotype(), b.getGenotype());
228 }
229
230 private void trim() {
231 assert _front != null;
232 assert _optimize != null;
233
234 if (_front.size() > _size.getMax() - 1) {
235 _front.trim(
236 _size.getMin(),
237 this::compare,
238 _distance.map(Phenotype::getFitness),
239 v -> _dimension.applyAsInt(v.getFitness())
240 );
241 }
242 }
243
244 private int compare(
245 final Phenotype<G, C> a,
246 final Phenotype<G, C> b,
247 final int i
248 ) {
249 return _optimize == Optimize.MAXIMUM
250 ? _comparator.compare(a.getFitness(), b.getFitness(), i)
251 : _comparator.compare(b.getFitness(), a.getFitness(), i);
252 }
253
254 Front<G, C> merge(final Front<G, C> front) {
255 _front.merge(front._front);
256 trim();
257 return this;
258 }
259
260 ISeq<Phenotype<G, C>> toISeq() {
261 return _front != null ? _front.toISeq() : ISeq.empty();
262 }
263
264 }
265
266 }
|