001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 * Copyright (c) 2007-2024 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 * {@snippet lang="java":
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 * }
063 *
064 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
065 * @version 5.1
066 * @since 4.1
067 */
068public 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 first.
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::dominance,
116                        Vec::compare,
117                        Vec::distance,
118                        Vec::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 first.
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.min() < 1) {
162                        throw new IllegalArgumentException(format(
163                                "Minimal pareto set size must be greater than zero: %d",
164                                size.min()
165                        ));
166                }
167
168                return Collector.of(
169                        () -> new Front<G, C>(
170                                size, dominance, comparator, distance, dimension
171                        ),
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.optimize();
209                                _front = new ParetoFront<>(this::dominance, this::equals);
210                        }
211
212                        final ISeq<Phenotype<G, C>> front = front(
213                                result.population(),
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.fitness(), b.fitness())
223                                : _dominance.compare(b.fitness(), a.fitness());
224                }
225
226                private boolean equals(final Phenotype<?, ?> a, final Phenotype<?, ?> b) {
227                        return Objects.equals(a.genotype(), b.genotype());
228                }
229
230                private void trim() {
231                        assert _front != null;
232                        assert _optimize != null;
233
234                        if (_front.size() > _size.max() - 1) {
235                                _front.trim(
236                                        _size.min(),
237                                        this::compare,
238                                        _distance.map(Phenotype::fitness),
239                                        v -> _dimension.applyAsInt(v.fitness())
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.fitness(), b.fitness(), i)
251                                : _comparator.compare(b.fitness(), a.fitness(), 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}