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