001/*
002 * Java Genetic Algorithm Library (jenetics-7.2.0).
003 * Copyright (c) 2007-2023 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 */
020package io.jenetics.ext.moea;
021
022import static java.lang.String.format;
023import static java.util.Objects.requireNonNull;
024import static io.jenetics.ext.moea.Pareto.front;
025
026import java.util.Comparator;
027import java.util.Objects;
028import java.util.function.ToIntFunction;
029import java.util.stream.Collector;
030
031import io.jenetics.Gene;
032import io.jenetics.Optimize;
033import io.jenetics.Phenotype;
034import io.jenetics.engine.EvolutionResult;
035import io.jenetics.util.ISeq;
036import 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 */
069public 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 first.
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 first.
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}