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