001 /*
002 * Java Genetic Algorithm Library (jenetics-6.3.0).
003 * Copyright (c) 2007-2021 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.util.Objects.requireNonNull;
023
024 import java.util.ArrayList;
025 import java.util.Comparator;
026 import java.util.List;
027 import java.util.function.ToIntFunction;
028 import java.util.stream.IntStream;
029
030 import io.jenetics.Gene;
031 import io.jenetics.Optimize;
032 import io.jenetics.Phenotype;
033 import io.jenetics.Selector;
034 import io.jenetics.util.ISeq;
035 import io.jenetics.util.ProxySorter;
036 import 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 */
054 public 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 * <pre>{@code
071 * new NSGA2Selector<>(
072 * Vec<T>::dominance,
073 * Vec<T>::compare,
074 * Vec<T>::distance,
075 * Vec<T>::length
076 * );
077 * }</pre>
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 * <pre>{@code
144 * new NSGA2Selector<>(
145 * Vec<T>::dominance,
146 * Vec<T>::compare,
147 * Vec<T>::distance,
148 * Vec<T>::length
149 * );
150 * }</pre>
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 }
|