001 /*
002 * Java Genetic Algorithm Library (jenetics-4.1.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 MOEA() {
071 }
072
073 /**
074 * Collector of {@link Phenotype} objects, who's (multi-objective) fitness
075 * value is part of the <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">
076 * pareto front</a>.
077 *
078 * @param <G> the gene type
079 * @param <T> the array type, e.g. {@code double[]}
080 * @param <V> the multi object result type vector
081 * @return the pareto set collector
082 * @throws IllegalArgumentException if the minimal pareto set {@code size}
083 * is smaller than one
084 */
085 public static <G extends Gene<?, G>, T, V extends Vec<T>>
086 Collector<EvolutionResult<G, V>, ?, ISeq<Phenotype<G, V>>>
087 toParetoSet() {
088 return toParetoSet(IntRange.of(75, 100));
089 }
090
091 /**
092 * Collector of {@link Phenotype} objects, who's (multi-objective) fitness
093 * value is part of the <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">
094 * pareto front</a>.
095 *
096 * @param size the allowed size range of the returned pareto set. If the
097 * size of the pareto set is bigger than {@code size.getMax()},
098 * during the collection, it is reduced to {@code size.getMin()}.
099 * Pareto set elements which are close to each other are removed firsts.
100 * @param <G> the gene type
101 * @param <T> the array type, e.g. {@code double[]}
102 * @param <V> the multi object result type vector
103 * @return the pareto set collector
104 * @throws NullPointerException if one the {@code size} is {@code null}
105 * @throws IllegalArgumentException if the minimal pareto set {@code size}
106 * is smaller than one
107 */
108 public static <G extends Gene<?, G>, T, V extends Vec<T>>
109 Collector<EvolutionResult<G, V>, ?, ISeq<Phenotype<G, V>>>
110 toParetoSet(final IntRange size) {
111 return toParetoSet(
112 size,
113 Vec<T>::dominance,
114 Vec<T>::compare,
115 Vec<T>::distance,
116 Vec<T>::length
117 );
118 }
119
120 /**
121 * Collector of {@link Phenotype} objects, who's (multi-objective) fitness
122 * value is part of the <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">
123 * pareto front</a>.
124 *
125 * @see #toParetoSet(IntRange)
126 *
127 * @param size the allowed size range of the returned pareto set. If the
128 * size of the pareto set is bigger than {@code size.getMax()},
129 * during the collection, it is reduced to {@code size.getMin()}.
130 * Pareto set elements which are close to each other are removed firsts.
131 * @param dominance the pareto dominance measure of the fitness result type
132 * {@code C}
133 * @param comparator the comparator of the elements of the vector type
134 * {@code C}
135 * @param distance the distance function of two elements of the vector
136 * type {@code C}
137 * @param dimension the dimensionality of the result vector {@code C}.
138 * Usually {@code Vec::length}.
139 * @param <G> the gene type
140 * @param <C> the multi object result vector. E.g. {@code Vec<double[]>}
141 * @return the pareto set collector
142 * @throws NullPointerException if one the arguments is {@code null}
143 * @throws IllegalArgumentException if the minimal pareto set {@code size}
144 * is smaller than one
145 */
146 public static <G extends Gene<?, G>, C extends Comparable<? super C>>
147 Collector<EvolutionResult<G, C>, ?, ISeq<Phenotype<G, C>>>
148 toParetoSet(
149 final IntRange size,
150 final Comparator<? super C> dominance,
151 final ElementComparator<? super C> comparator,
152 final ElementDistance<? super C> distance,
153 final ToIntFunction<? super C> dimension
154 ) {
155 requireNonNull(size);
156 requireNonNull(dominance);
157 requireNonNull(distance);
158
159 if (size.getMin() < 1) {
160 throw new IllegalArgumentException(format(
161 "Minimal pareto set size must be greater than zero: %d",
162 size.getMin()
163 ));
164 }
165
166 return Collector.of(
167 () -> new Front<G, C>(
168 size, dominance, comparator, distance, dimension),
169 Front::add,
170 Front::merge,
171 Front::toISeq
172 );
173 }
174
175 private static final class Front<
176 G extends Gene<?, G>,
177 C extends Comparable<? super C>
178 > {
179
180 final IntRange _size;
181 final Comparator<? super C> _dominance;
182 final ElementComparator<? super C> _comparator;
183 final ElementDistance<? super C> _distance;
184 final ToIntFunction<? super C> _dimension;
185
186 private Optimize _optimize;
187 private ParetoFront<Phenotype<G, C>> _front;
188
189 Front(
190 final IntRange size,
191 final Comparator<? super C> dominance,
192 final ElementComparator<? super C> comparator,
193 final ElementDistance<? super C> distance,
194 final ToIntFunction<? super C> dimension
195 ) {
196 _size = size;
197 _dominance = dominance;
198 _comparator = comparator;
199 _distance = distance;
200 _dimension = dimension;
201 }
202
203 void add(final EvolutionResult<G, C> result) {
204 if (_front == null) {
205 _optimize = result.getOptimize();
206 _front = new ParetoFront<>(this::dominance);
207 }
208
209 final ISeq<Phenotype<G, C>> front = front(
210 result.getPopulation(),
211 this::dominance
212 );
213 _front.addAll(front.asList());
214 trim();
215 }
216
217 private int dominance(final Phenotype<G, C> a, final Phenotype<G, C> b) {
218 return _optimize == Optimize.MAXIMUM
219 ? _dominance.compare(a.getFitness(), b.getFitness())
220 : _dominance.compare(b.getFitness(), a.getFitness());
221 }
222
223 private void trim() {
224 assert _front != null;
225 assert _optimize != null;
226
227 if (_front.size() > _size.getMax() - 1) {
228 _front.trim(
229 _size.getMin(),
230 this::compare,
231 _distance.map(Phenotype::getFitness),
232 v -> _dimension.applyAsInt(v.getFitness())
233 );
234 }
235 }
236
237 private int compare(
238 final Phenotype<G, C> a,
239 final Phenotype<G, C> b,
240 final int i
241 ) {
242 return _optimize == Optimize.MAXIMUM
243 ? _comparator.compare(a.getFitness(), b.getFitness(), i)
244 : _comparator.compare(b.getFitness(), a.getFitness(), i);
245 }
246
247 Front<G, C> merge(final Front<G, C> front) {
248 _front.merge(front._front);
249 trim();
250 return this;
251 }
252
253 ISeq<Phenotype<G, C>> toISeq() {
254 return _front != null ? _front.toISeq() : ISeq.empty();
255 }
256
257 }
258
259 }
|