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.util.Objects.requireNonNull;
023
024import java.util.ArrayList;
025import java.util.Comparator;
026import java.util.List;
027import java.util.function.ToIntFunction;
028import java.util.stream.IntStream;
029
030import io.jenetics.Gene;
031import io.jenetics.Optimize;
032import io.jenetics.Phenotype;
033import io.jenetics.Selector;
034import io.jenetics.util.ISeq;
035import io.jenetics.util.ProxySorter;
036import io.jenetics.util.Seq;
037
038/**
039 * This selector selects the first {@code count} elements of the population,
040 * which has been sorted by the <em>Crowded-Comparison Operator</em>, as
041 * described in <a href="http://ieeexplore.ieee.org/document/996017/">
042 *     A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II</a>
043 * <p>
044 *  <b>Reference:</b><em>
045 *      K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist
046 *      multiobjective genetic algorithm: NSGA-II. Trans. Evol. Comp 6, 2
047 *      (April 2002), 182-197. DOI=<a href="http://dx.doi.org/10.1109/4235.996017">
048 *          10.1109/4235.996017</a></em>
049 *
050 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
051 * @version 4.1
052 * @since 4.1
053 */
054public class NSGA2Selector<
055        G extends Gene<?, G>,
056        C extends Comparable<? super C>
057>
058        implements Selector<G, C>
059{
060
061        private final Comparator<Phenotype<G, C>> _dominance;
062        private final ElementComparator<Phenotype<G, C>> _comparator;
063        private final ElementDistance<Phenotype<G, C>> _distance;
064        private final ToIntFunction<Phenotype<G, C>> _dimension;
065
066        /**
067         * Creates a new {@code NSGA2Selector} with the functions needed for
068         * handling the multi-objective result type {@code C}. For the {@link Vec}
069         * classes, a selector is created like in the following example:
070         * {@snippet lang="java":
071         * new NSGA2Selector<>(
072         *     Vec<T>::dominance,
073         *     Vec<T>::compare,
074         *     Vec<T>::distance,
075         *     Vec<T>::length
076         * );
077         * }
078         *
079         * @see #ofVec()
080         *
081         * @param dominance the pareto dominance comparator
082         * @param comparator the vector element comparator
083         * @param distance the vector element distance
084         * @param dimension the dimensionality of vector type {@code C}
085         */
086        public NSGA2Selector(
087                final Comparator<? super C> dominance,
088                final ElementComparator<? super C> comparator,
089                final ElementDistance<? super C> distance,
090                final ToIntFunction<? super C> dimension
091        ) {
092                requireNonNull(dominance);
093                requireNonNull(comparator);
094                requireNonNull(distance);
095                requireNonNull(dimension);
096
097                _dominance = (a, b) -> dominance.compare(a.fitness(), b.fitness());
098                _comparator = comparator.map(Phenotype::fitness);
099                _distance = distance.map(Phenotype::fitness);
100                _dimension = v -> dimension.applyAsInt(v.fitness());
101        }
102
103        @Override
104        public ISeq<Phenotype<G, C>> select(
105                final Seq<Phenotype<G, C>> population,
106                final int count,
107                final Optimize opt
108        ) {
109                final CrowdedComparator<Phenotype<G, C>> cc = new CrowdedComparator<>(
110                        population,
111                        opt,
112                        _dominance,
113                        _comparator,
114                        _distance,
115                        _dimension
116                );
117
118                final int[] idx = ProxySorter.sort(
119                        init(new int[population.size()]),
120                        population.size(),
121                        (a, i, j) -> cc.compare(a[j], a[i])
122                );
123
124                final List<Phenotype<G, C>> result = new ArrayList<>();
125                while (result.size() < count) {
126                        IntStream.of(idx)
127                                .limit(count - result.size())
128                                .mapToObj(population)
129                                .forEach(result::add);
130                }
131
132                return ISeq.of(result);
133        }
134
135        private static int[] init(final int[] indexes) {
136                for (int i = 0; i < indexes.length; ++i) indexes[i] = i;
137                return indexes;
138        }
139
140        /**
141         * Return a new selector for the given result type {@code V}. This method is
142         * a shortcut for
143         * {@snippet lang="java":
144         * new NSGA2Selector<>(
145         *     Vec<T>::dominance,
146         *     Vec<T>::compare,
147         *     Vec<T>::distance,
148         *     Vec<T>::length
149         * );
150         * }
151         *
152         * @param <G> the gene type
153         * @param <T> the array type, e.g. {@code double[]}
154         * @param <V> the multi object result type vector
155         * @return a new selector for the given result type {@code V}
156         */
157        public static <G extends Gene<?, G>, T, V extends Vec<T>>
158        NSGA2Selector<G, V> ofVec() {
159                return new NSGA2Selector<>(
160                        Vec::dominance,
161                        Vec::compare,
162                        Vec::distance,
163                        Vec::length
164                );
165        }
166
167}