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.lang.Math.min;
023 import static java.util.Objects.requireNonNull;
024 import static io.jenetics.internal.math.comb.subset;
025
026 import java.util.ArrayList;
027 import java.util.Comparator;
028 import java.util.List;
029 import java.util.Random;
030 import java.util.function.ToIntFunction;
031 import java.util.stream.Collectors;
032
033 import io.jenetics.Gene;
034 import io.jenetics.Optimize;
035 import io.jenetics.Phenotype;
036 import io.jenetics.Selector;
037 import io.jenetics.util.ISeq;
038 import io.jenetics.util.RandomRegistry;
039 import io.jenetics.util.Seq;
040
041 /**
042 * Unique fitness based tournament selection.
043 * <p>
044 * <em>The selection of unique fitnesses lifts the selection bias towards
045 * over-represented fitnesses by reducing multiple solutions sharing the same
046 * fitness to a single point in the objective space. It is therefore no longer
047 * required to assign a crowding distance of zero to individual of equal fitness
048 * as the selection operator correctly enforces diversity preservation by
049 * picking unique points in the objective space.</em>
050 * <p>
051 * <b>Reference:</b><em>
052 * Félix-Antoine Fortin and Marc Parizeau. 2013. Revisiting the NSGA-II
053 * crowding-distance computation. In Proceedings of the 15th annual
054 * conference on Genetic and evolutionary computation (GECCO '13),
055 * Christian Blum (Ed.). ACM, New York, NY, USA, 623-630.
056 * DOI=<a href="http://dx.doi.org/10.1145/2463372.2463456">
057 * 10.1145/2463372.2463456</a></em>
058 *
059 *
060 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
061 * @version 4.1
062 * @since 4.1
063 */
064 public class UFTournamentSelector<
065 G extends Gene<?, G>,
066 C extends Comparable<? super C>
067 >
068 implements Selector<G, C>
069 {
070 private final Comparator<Phenotype<G, C>> _dominance;
071 private final ElementComparator<Phenotype<G, C>> _comparator;
072 private final ElementDistance<Phenotype<G, C>> _distance;
073 private final ToIntFunction<Phenotype<G, C>> _dimension;
074
075 /**
076 * Creates a new {@code UFTournamentSelector} with the functions needed for
077 * handling the multi-objective result type {@code C}. For the {@link Vec}
078 * classes, a selector is created like in the following example:
079 * <pre>{@code
080 * new UFTournamentSelector<>(
081 * Vec<T>::dominance,
082 * Vec<T>::compare,
083 * Vec<T>::distance,
084 * Vec<T>::length
085 * );
086 * }</pre>
087 *
088 * @see #ofVec()
089 *
090 * @param dominance the pareto dominance comparator
091 * @param comparator the vector element comparator
092 * @param distance the vector element distance
093 * @param dimension the dimensionality of vector type {@code C}
094 */
095 public UFTournamentSelector(
096 final Comparator<? super C> dominance,
097 final ElementComparator<? super C> comparator,
098 final ElementDistance<? super C> distance,
099 final ToIntFunction<? super C> dimension
100 ) {
101 requireNonNull(dominance);
102 requireNonNull(comparator);
103 requireNonNull(distance);
104 requireNonNull(dimension);
105
106 _dominance = (a, b) -> dominance.compare(a.getFitness(), b.getFitness());
107 _comparator = comparator.map(Phenotype::getFitness);
108 _distance = distance.map(Phenotype::getFitness);
109 _dimension = v -> dimension.applyAsInt(v.getFitness());
110 }
111
112 @Override
113 public ISeq<Phenotype<G, C>> select(
114 final Seq<Phenotype<G, C>> population,
115 final int count,
116 final Optimize opt
117 ) {
118 final Random random = RandomRegistry.getRandom();
119
120 final CrowdedComparator<Phenotype<G, C>> cc = new CrowdedComparator<>(
121 population,
122 opt,
123 _dominance,
124 _comparator,
125 _distance,
126 _dimension
127 );
128
129 final List<Phenotype<G, C>> S = new ArrayList<>();
130 while (S.size() < count) {
131 final int k = min(2*count - S.size(), population.size());
132 final int[] G = subset(population.size(), k, random);
133
134 for (int j = 0; j < G.length - 1 && S.size() < count; j += 2) {
135 final int cmp = cc.compare(G[j], G[j + 1]);
136 final int p;
137 if (cmp > 0) {
138 p = G[j];
139 } else if (cmp < 0) {
140 p = G[j + 1];
141 } else {
142 p = random.nextBoolean() ? G[j] : G[j + 1];
143 }
144
145 final C fitness = population.get(p).getFitness();
146 final List<Phenotype<G, C>> list = population.stream()
147 .filter(pt -> pt.getFitness().equals(fitness))
148 .collect(Collectors.toList());
149
150 S.add(list.get(random.nextInt(list.size())));
151 }
152 }
153
154 return ISeq.of(S);
155 }
156
157 /**
158 * Return a new selector for the given result type {@code V}. This method is
159 * a shortcut for
160 * <pre>{@code
161 * new UFTournamentSelector<>(
162 * Vec<T>::dominance,
163 * Vec<T>::compare,
164 * Vec<T>::distance,
165 * Vec<T>::length
166 * );
167 * }</pre>
168 *
169 * @param <G> the gene type
170 * @param <T> the array type, e.g. {@code double[]}
171 * @param <V> the multi object result type vector
172 * @return a new selector for the given result type {@code V}
173 */
174 public static <G extends Gene<?, G>, T, V extends Vec<T>>
175 UFTournamentSelector<G, V> ofVec() {
176 return new UFTournamentSelector<>(
177 Vec<T>::dominance,
178 Vec<T>::compare,
179 Vec<T>::distance,
180 Vec<T>::length
181 );
182 }
183
184 }
|