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