001 /*
002 * Java Genetic Algorithm Library (jenetics-4.3.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 {@code true} 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 < 0 || 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(e) ? 1 : 0)
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 }
|