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 import static io.jenetics.internal.util.Arrays.revert;
024
025 import java.util.AbstractSet;
026 import java.util.ArrayList;
027 import java.util.Collection;
028 import java.util.Comparator;
029 import java.util.Iterator;
030 import java.util.List;
031 import java.util.Objects;
032 import java.util.Set;
033 import java.util.function.BiPredicate;
034 import java.util.function.ToIntFunction;
035 import java.util.stream.Collector;
036 import java.util.stream.Collectors;
037 import java.util.stream.IntStream;
038
039 import io.jenetics.util.ISeq;
040 import io.jenetics.util.ProxySorter;
041 import io.jenetics.util.Seq;
042
043 /**
044 * This class only contains non-dominate (Pareto-optimal) elements according to
045 * a given <em>dominance</em> measure. Like a {@link Set}, it only contains no
046 * duplicate entries. Unlike the usual set implementation, the iteration order
047 * is deterministic.
048 * <p>
049 * You can create a new {@code ParetoFront} for {@link Vec} objects
050 * <pre>{@code
051 * final ParetoFront<Vec<double[]>> front = new ParetoFront<>(Vec::dominance);
052 * front.add(Vec.of(1.0, 2.0));
053 * front.add(Vec.of(1.1, 2.5));
054 * front.add(Vec.of(0.9, 2.1));
055 * front.add(Vec.of(0.0, 2.9));
056 * }</pre>
057 *
058 * or directly for {@code double[]} array objects
059 * <pre>{@code
060 * final ParetoFront<double[]> front = new ParetoFront<>(Pareto::dominance);
061 * front.add(new double[]{1.0, 2.0});
062 * front.add(new double[]{1.1, 2.5});
063 * front.add(new double[]{0.9, 2.1});
064 * front.add(new double[]{0.0, 2.9});
065 * }</pre>
066 *
067 * You only have to specify the <a href="https://en.wikipedia.org/wiki/Pareto_efficiency">
068 * Pareto dominance/efficiency</a> measure.
069 *
070 * @see Pareto
071 *
072 * @apiNote
073 * Inserting a new element has a time complexity of {@code O(n)}.
074 *
075 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
076 * @version 5.1
077 * @since 4.1
078 */
079 public final class ParetoFront<T> extends AbstractSet<T> {
080
081 private final List<T> _population = new ArrayList<>();
082
083 private final Comparator<? super T> _dominance;
084 private final BiPredicate<? super T, ? super T> _equals;
085
086 /**
087 * Create a new {@code ParetoSet} with the given {@code dominance} measure.
088 *
089 * @since 5.1
090 *
091 * @param dominance the <em>Pareto</em> dominance measure
092 * @param equals the equals predicate used for keeping the set distinct
093 * @throws NullPointerException if the given {@code dominance} measure is
094 * {@code null}
095 */
096 public ParetoFront(
097 final Comparator<? super T> dominance,
098 final BiPredicate<? super T, ? super T> equals
099 ) {
100 _dominance = requireNonNull(dominance);
101 _equals = requireNonNull(equals);
102 }
103
104 /**
105 * Create a new {@code ParetoSet} with the given {@code dominance} measure.
106 *
107 * @param dominance the <em>Pareto</em> dominance measure
108 * @throws NullPointerException if the given {@code dominance} measure is
109 * {@code null}
110 */
111 public ParetoFront(final Comparator<? super T> dominance) {
112 this(dominance, Objects::equals);
113 }
114
115 /**
116 * Inserts an {@code element} to this pareto front.
117 *
118 * @implNote
119 * Inserting a new element has a time complexity of {@code O(this.size())},
120 * where <em>n</em> is the number of elements of {@code this} pareto-front.
121 *
122 * @param element the element to add
123 * @return {@code true} if this set did not already contain the specified
124 * element
125 */
126 @Override
127 public boolean add(final T element) {
128 requireNonNull(element);
129
130 boolean updated = false;
131 final Iterator<T> iterator = _population.iterator();
132 while (iterator.hasNext()) {
133 final T existing = iterator.next();
134
135 int cmp = _dominance.compare(element, existing);
136 if (cmp > 0) {
137 iterator.remove();
138 updated = true;
139 } else if (cmp < 0 || _equals.test(element, existing)) {
140 return updated;
141 }
142 }
143
144 _population.add(element);
145 return true;
146 }
147
148 /**
149 * Adds all elements of the given collection to {@code this} pareto front.
150 *
151 * @implNote
152 * The runtime complexity of this operation is
153 * {@code O(elements.size()*this.size())}.
154 *
155 * @param elements the elements to add to {@code this} pareto front
156 * @return {@code true} if {@code this} pareto front has been changed,
157 * {@code false} otherwise
158 */
159 @Override
160 public boolean addAll(final Collection<? extends T> elements) {
161 final int sum = elements.stream()
162 .mapToInt(e -> add(e) ? 1 : 0)
163 .sum();
164 return sum > 0;
165 }
166
167 /**
168 * Add the all {@code elements} to {@code this} pareto-set.
169 *
170 * @implNote
171 * Merging two pareto fronts has a time complexity of
172 * {@code O(elements.size()*this.size())}.
173 *
174 * @param elements the elements to add
175 * @return {@code this} pareto-set
176 * @throws NullPointerException if the given parameter is {@code null}
177 */
178 public ParetoFront<T> merge(final ParetoFront<? extends T> elements) {
179 addAll(elements);
180 return this;
181 }
182
183 /**
184 * Trims {@code this} pareto front to the given size. The front elements are
185 * sorted according its crowding distance and the elements which have smaller
186 * distance to its neighbors are removed first.
187 *
188 * <pre>{@code
189 * final ParetoFront<Vec<double[]>> front = new ParetoFront<>(Vec::dominance);
190 * front.trim(10, Vec::compare, Vec::distance, Vec::length);
191 * }</pre>
192 * The example above reduces the given front to 10 elements.
193 *
194 * @param size the number of front elements after the trim. If
195 * {@code size() <= size}, nothing is trimmed.
196 * @param comparator the element comparator used for calculating the
197 * crowded distance
198 * @param distance the element distance measure
199 * @param dimension the number of vector elements of {@code T}
200 * @return {@code this} trimmed pareto front
201 * @throws NullPointerException if one of the objects is {@code null}
202 */
203 public ParetoFront<T> trim(
204 final int size,
205 final ElementComparator<? super T> comparator,
206 final ElementDistance<? super T> distance,
207 final ToIntFunction<? super T> dimension
208 ) {
209 requireNonNull(comparator);
210 requireNonNull(distance);
211 requireNonNull(dimension);
212
213 if (size() > size) {
214 final double[] distances = Pareto.crowdingDistance(
215 Seq.viewOf(_population),
216 comparator,
217 distance,
218 dimension
219 );
220 final int[] indexes = ProxySorter.sort(distances);
221 revert(indexes);
222
223 final List<T> list = IntStream.of(indexes)
224 .limit(size)
225 .mapToObj(_population::get)
226 .collect(Collectors.toList());
227
228 _population.clear();
229 _population.addAll(list);
230 }
231
232 return this;
233 }
234
235 @Override
236 public Iterator<T> iterator() {
237 return _population.iterator();
238 }
239
240 @Override
241 public int size() {
242 return _population.size();
243 }
244
245 @Override
246 public boolean isEmpty() {
247 return _population.isEmpty();
248 }
249
250 /**
251 * Return the elements of {@code this} pareto-front as {@link ISeq}.
252 *
253 * @return the elements of {@code this} pareto-front as {@link ISeq}
254 */
255 public ISeq<T> toISeq() {
256 return ISeq.of(_population);
257 }
258
259 /**
260 * Return a pareto-front collector. The natural order of the elements is
261 * used as pareto-dominance order.
262 *
263 * @param <C> the element type
264 * @return a new pareto-front collector
265 */
266 public static <C extends Comparable<? super C>>
267 Collector<C, ?, ParetoFront<C>> toParetoFront() {
268 return toParetoFront(Comparator.naturalOrder());
269 }
270
271 /**
272 * Return a pareto-front collector with the given pareto {@code dominance}
273 * measure.
274 *
275 * @param dominance the pareto dominance comparator
276 * @param <T> the element type
277 * @return a new pareto-front collector
278 * @throws NullPointerException if the given {@code dominance} collector is
279 * {@code null}
280 */
281 public static <T> Collector<T, ?, ParetoFront<T>>
282 toParetoFront(final Comparator<? super T> dominance) {
283 requireNonNull(dominance);
284
285 return Collector.of(
286 () -> new ParetoFront<>(dominance),
287 ParetoFront::add,
288 ParetoFront::merge
289 );
290 }
291
292 }
|