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