001 /*
002 * Java Genetic Algorithm Library (jenetics-1.5.0).
003 * Copyright (c) 2007-2013 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@gmx.at)
019 */
020 package org.jenetics;
021
022 import static java.util.Objects.requireNonNull;
023 import static org.jenetics.util.object.eq;
024 import static org.jenetics.util.object.hashCodeOf;
025
026 import java.util.ArrayList;
027 import java.util.Collection;
028 import java.util.Collections;
029 import java.util.Comparator;
030 import java.util.Iterator;
031 import java.util.List;
032 import java.util.ListIterator;
033 import java.util.RandomAccess;
034
035 import javolution.xml.XMLFormat;
036 import javolution.xml.XMLSerializable;
037 import javolution.xml.stream.XMLStreamException;
038
039 import org.jenetics.util.Copyable;
040 import org.jenetics.util.Factory;
041
042 /**
043 * A population is a collection of Phenotypes.
044 *
045 * <p/>
046 * <strong>This class is not synchronized.</strong> If multiple threads access
047 * a {@code Population} concurrently, and at least one of the threads modifies
048 * it, it <strong>must</strong> be synchronized externally.
049 *
050 * @author <a href="mailto:franz.wilhelmstoetter@gmx.at">Franz Wilhelmstötter</a>
051 * @since 1.0
052 * @version 1.5 — <em>$Date: 2013-12-06 $</em>
053 */
054 public class Population<G extends Gene<?, G>, C extends Comparable<? super C>>
055 implements
056 List<Phenotype<G, C>>,
057 Copyable<Population<G, C>>,
058 RandomAccess,
059 XMLSerializable
060 {
061 private static final long serialVersionUID = 1L;
062
063 private final List<Phenotype<G, C>> _population;
064
065 private Population(final List<Phenotype<G, C>> population) {
066 _population = population;
067 }
068
069 /**
070 * Constructs a population containing the elements of the specified collection,
071 * in the order they are returned by the collection's iterator.
072 *
073 * @param population the collection whose elements are to be placed into
074 * this list.
075 * @throws NullPointerException if the specified population is {@code null}.
076 */
077 public Population(final Collection<Phenotype<G, C>> population) {
078 this(new ArrayList<>(population));
079 }
080
081 /**
082 * Creating a new {@code Population} with the pre-allocated population
083 * size.
084 *
085 * @param size Pre-allocated population size.
086 * @throws IllegalArgumentException if the specified initial capacity is
087 * negative
088 */
089 public Population(final int size) {
090 this(new ArrayList<Phenotype<G, C>>(size + 1));
091 }
092
093 /**
094 * Creating a new {@code Population}.
095 */
096 public Population() {
097 this(new ArrayList<Phenotype<G, C>>());
098 }
099
100 /**
101 * Fills the population with individuals created by the given factory.
102 *
103 * @param factory the {@code Phenotype} factory.
104 * @param count the number of individuals to add to this population.
105 * @return return this population, for command chaining.
106 */
107 public Population<G, C> fill(
108 final Factory<Phenotype<G, C>> factory,
109 final int count
110 ) {
111 for (int i = count; --i >= 0;) {
112 _population.add(factory.newInstance());
113 }
114 //lists.fill(_population, factory, count);
115 return this;
116 }
117
118 /**
119 * Add {@code Phenotype} to the {@code Population}.
120 *
121 * @param phenotype {@code Phenotype} to be add.
122 * @throws NullPointerException if the given {@code phenotype} is
123 * {@code null}.
124 */
125 @Override
126 public boolean add(final Phenotype<G, C> phenotype) {
127 requireNonNull(phenotype, "Phenotype");
128 return _population.add(phenotype);
129 }
130
131 /**
132 * Add {@code Phenotype} to the {@code Population}.
133 *
134 * @param index Index of the
135 * @param phenotype {@code Phenotype} to be add.
136 * @throws NullPointerException if the given {@code phenotype} is
137 * {@code null}.
138 */
139 @Override
140 public void add(final int index, final Phenotype<G, C> phenotype) {
141 requireNonNull(phenotype, "Phenotype");
142 _population.add(index, phenotype);
143 }
144
145 @Override
146 public boolean addAll(final Collection<? extends Phenotype<G, C>> c) {
147 return _population.addAll(c);
148 }
149
150 @Override
151 public boolean addAll(int index, Collection<? extends Phenotype<G, C>> c) {
152 return _population.addAll(index, c);
153 }
154
155 @Override
156 public Phenotype<G, C> get(final int index) {
157 return _population.get(index);
158 }
159
160 @Override
161 public Phenotype<G, C> set(final int index, final Phenotype<G, C> pt) {
162 requireNonNull(pt, "Phenotype");
163 return _population.set(index, pt);
164 }
165
166 public void remove(final Phenotype<G, C> phenotype) {
167 requireNonNull(phenotype, "Phenotype");
168 _population.remove(phenotype);
169 }
170
171 @Override
172 public boolean remove(final Object o) {
173 return _population.remove(o);
174 }
175
176 @Override
177 public boolean removeAll(final Collection<?> c) {
178 return _population.removeAll(c);
179 }
180
181 @Override
182 public Phenotype<G, C> remove(final int index) {
183 return _population.remove(index);
184 }
185
186 @Override
187 public void clear() {
188 _population.clear();
189 }
190
191 /**
192 * Sorting the phenotypes in this population according to its fitness
193 * value in descending order.
194 */
195 public void sort() {
196 sortWith(Optimize.MAXIMUM.<C>descending());
197 }
198
199 /**
200 * Sort this population according the order defined by the given
201 * {@code comparator}.
202 *
203 * @param comparator the comparator which defines the sorting order.
204 * @throws java.lang.NullPointerException if the {@code comparator} is
205 * {@code null}.
206 *
207 * @deprecated This method conflicts with the default method of the
208 * {@link java.util.List} interface introduced in Java 8. Use
209 * {@link #sortWith(java.util.Comparator)} instead.
210 */
211 @Deprecated
212 public void sort(final Comparator<? super C> comparator) {
213 sortWith(comparator);
214 }
215
216 /**
217 * Sort this population according the order defined by the given
218 * {@code comparator}.
219 *
220 * @param comparator the comparator which defines the sorting order.
221 * @throws java.lang.NullPointerException if the {@code comparator} is
222 * {@code null}.
223 */
224 public void sortWith(final Comparator<? super C> comparator) {
225 quickSort(0, size() - 1, comparator);
226 }
227
228
229 private void quickSort(
230 final int left, final int right,
231 final Comparator<? super C> comparator
232 ) {
233 if (right > left) {
234 final int j = partition(left, right, comparator);
235 quickSort(left, j - 1, comparator);
236 quickSort(j + 1, right, comparator);
237 }
238 }
239
240 private int partition(
241 final int left, final int right,
242 final Comparator<? super C> comparator
243 ) {
244 final C pivot = _population.get(left).getFitness();
245 int i = left;
246 int j = right + 1;
247 while (true) {
248 do {
249 ++i;
250 } while (
251 i < right &&
252 comparator.compare(_population.get(i).getFitness(), pivot) < 0
253 );
254
255 do {
256 --j;
257 } while (
258 j > left &&
259 comparator.compare(_population.get(j).getFitness(), pivot) > 0
260 );
261 if (j <= i) {
262 break;
263 }
264 swap(i, j);
265 }
266 swap(left, j);
267
268 return j;
269 }
270
271 private void swap(final int i, final int j) {
272 _population.set(i, _population.set(j, _population.get(i)));
273 }
274
275 /**
276 * Reverse the order of the population.
277 */
278 public void reverse() {
279 Collections.reverse(_population);
280 }
281
282 @Override
283 public Iterator<Phenotype<G, C>> iterator() {
284 return _population.iterator();
285 }
286
287 @Override
288 public ListIterator<Phenotype<G, C>> listIterator() {
289 return _population.listIterator();
290 }
291
292 @Override
293 public ListIterator<Phenotype<G, C>> listIterator(final int index) {
294 return _population.listIterator(index);
295 }
296
297 @Override
298 public int size() {
299 return _population.size();
300 }
301
302 @Override
303 public boolean isEmpty() {
304 return _population.isEmpty();
305 }
306
307 @Override
308 public boolean contains(final Object o) {
309 return _population.contains(o);
310 }
311
312 @Override
313 public boolean containsAll(final Collection<?> c) {
314 return _population.containsAll(c);
315 }
316
317 @Override
318 public int indexOf(final Object o) {
319 return _population.indexOf(o);
320 }
321
322 @Override
323 public int lastIndexOf(final Object o) {
324 return _population.lastIndexOf(o);
325 }
326
327 @Override
328 public boolean retainAll(final Collection<?> c) {
329 return _population.retainAll(c);
330 }
331
332 @Override
333 public List<Phenotype<G, C>> subList(final int fromIndex, final int toIndex) {
334 return _population.subList(fromIndex, toIndex);
335 }
336
337 @Override
338 public Object[] toArray() {
339 return _population.toArray();
340 }
341
342 @Override
343 public <A> A[] toArray(final A[] a) {
344 return _population.toArray(a);
345 }
346
347 public List<Genotype<G>> getGenotypes() {
348 final List<Genotype<G>> genotypes = new ArrayList<>(_population.size());
349 for (Phenotype<G, C> phenotype : _population) {
350 genotypes.add(phenotype.getGenotype());
351 }
352 return genotypes;
353 }
354
355 @Override
356 public Population<G, C> copy() {
357 return new Population<>(new ArrayList<>(_population));
358 }
359
360 @Override
361 public int hashCode() {
362 return hashCodeOf(getClass()).and(_population).value();
363 }
364
365 @Override
366 public boolean equals(final Object object) {
367 if (object == this) {
368 return true;
369 }
370 if (!(object instanceof Population<?, ?>)) {
371 return false;
372 }
373
374 final Population<?, ?> population = (Population<?, ?>)object;
375 return eq(_population, population._population);
376 }
377
378 @Override
379 public String toString() {
380 StringBuilder out = new StringBuilder();
381
382 for (Phenotype<?, ?> pt : this) {
383 out.append(pt).append("\n");
384 }
385
386 return out.toString();
387 }
388
389
390 @SuppressWarnings({ "unchecked", "rawtypes" })
391 static final XMLFormat<Population>
392 XML = new XMLFormat<Population>(Population.class)
393 {
394 private static final String SIZE = "size";
395
396 @Override
397 public Population newInstance(
398 final Class<Population> cls, final InputElement xml
399 )
400 throws XMLStreamException
401 {
402 final int size = xml.getAttribute(SIZE, 10);
403 final Population p = new Population(size);
404 for (int i = 0; i < size; ++i) {
405 p.add(xml.<Phenotype>getNext());
406 }
407 return p;
408 }
409 @Override
410 public void write(final Population p, final OutputElement xml)
411 throws XMLStreamException
412 {
413 xml.setAttribute(SIZE, p.size());
414 for (Object phenotype : p) {
415 xml.add(phenotype);
416 }
417 }
418 @Override
419 public void read(final InputElement xml, final Population p) {
420 }
421 };
422
423 }
424
425
426
|