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