population.java

来自「遗传算法源代码,实现了选择操作、交叉操作和变异操作」· Java 代码 · 共 432 行

/*--- formatted by Jindent 2.1, (www.c-lab.de/~jindent) ---*/

/**
 * Population Class
 *
 * location: net.openai.ai.ga.population.Population
 *
 */
package net.openai.ai.ga.population;

import net.openai.ai.ga.*;
import net.openai.ai.ga.cell.*;
import net.openai.ai.ga.environment.*;
import net.openai.ai.ga.selection.*;

import java.util.Collection;
import java.util.ArrayList;
import java.util.Iterator;

/**
 * The Population is the encapsulation of the individual solutions (<code>
 * Cell</code>s that are used to solve the problem. <code>Cell</code>s may
 * be added and deleted from this collection. This also implements the
 * following functions, which are passed on to the appropriate targets:
 * <ul>
 *   <li>Mature (or age)
 *   <li>Evaluate
 *   <li>Combine (or reproduce)
 *   <li>Mutate
 * </ul>
 * @author	Jared Grubb
 * @version	%I%, %G%
 * @since	JDK1.3
 */
public class Population implements java.io.Serializable {

    /**
     * The collection of cells that are in this <code>Population</code>
     */
    protected Collection cells;

    /**
     * Creates a population using an <code>ArrayList</code>
     */
    public Population() {
	this(new ArrayList(0));
    }

    /**
     * Creates a population using a given <code>Collection</code>
     *
     * @param initialCollection a <code>Collection</code> to initialize
     * 		with
     */
    public Population(Collection initialCollection) {
	cells = initialCollection;
    }

    /**
     * Creates a partial clone of this <code>Population</code>. This
     * is not a complete clone, in which each of the <code>Cell</code>s would
     * also be cloned; this instead creates a copy of the collection of
     * <code>Cell</code>s to which additions and removals do not affect the
     * original population. Equilivant to <code>Population(toClone,false)
     * </code>.
     */
    public Population(Population toClone) {
        this(toClone,false);
    }

    /**
     * Creates a partial clone of this <code>Population</code>. This
     * is not a complete clone, in which each of the <code>Cell</code>s would
     * also be cloned; this instead creates a copy of the collection of
     * <code>Cell</code>s to which additions and removals do not affect the
     * original population.
     */
    public Population(Population toClone, boolean makeEmpty) {
	try {
	    this.cells =
	        (Collection) toClone.cells.getClass().newInstance();
	} catch (InstantiationException e) {
	    db("Cannot instantiate new clone!");
	    throw new RuntimeException(
	        "Cannot clone population's collection: InstantiationException");
	} catch (IllegalAccessException e) {
	    db("Cannot access ojbect!");
	    throw new RuntimeException(
	        "Cannot clone population's collection: IllegalAccessException");
	}
	if (makeEmpty==false)
	    this.addCells(toClone);
    }

    /**
     * Matures the population. Calls the mature() method of each of the
     * <code>Cell</code>s contained in this <code>Population</code>.
     */
    public void mature() {
	for (Iterator i = cells.iterator(); i.hasNext(); ) {
	    ((Cell) i.next()).mature();
	}
    }

    /**
     * Tells each <code>Cell</code> in this <code>Population</code> to
     * evaluate its fitness based upon the <code>Environment</code> given to
     * it.
     *
     * @param env	<code>Environment</code> to evaluate against
     */
    public void evaluate(Environment env) {
	for (Iterator i = cells.iterator(); i.hasNext(); ) {
	    ((Cell) i.next()).evaluateFitness(env);
	}
    }

    /**
     * Creates new <code>Cell</code>s to add into the <code>Population</code>.
     * The groups of cells to combine are passed as a <code>PopulationArray
     * </code>. The first <code>Cell</code> in each <code>Population</code> in
     * the group is issued the combine method to return a new <code>Cell</code>
     * which is then added into this <code>Population</code>.
     *
     * @param parents	a <code>PopulationArray</code> containing sets of
     *                  parents
     */
    public void combine(PopulationArray parents) {
	Population p;
	Cell c;

	for (Iterator i = parents.getPopulationIterator(); i.hasNext(); ) {
	    p = (Population) (i.next());

	    try {
	    	c = (Cell) p.getCellIterator().next();
	    } catch (java.util.NoSuchElementException e) {
	    	// Do nothing on empty population sets:
	    	continue;
	    }

	    // This is done outside of the catch in order to throw the
	    // exception if the Cell itself does something funny, but keeps
	    // an exception from happening on simply empty parent lists
	    this.addCells(c.combine(p));
	}
    }

    /**
     * Issues a mutate command to each cell in the passed <code>Population
     * </code>.
     *
     * @param toMutate the target <code>Population</code> for the mutation
     */
    static public void mutate(Population toMutate) {
	for (Iterator i = toMutate.getCellIterator(); i.hasNext(); ) {
	    ((Cell) i.next()).mutate();
	}
    }

    /**
     * Returns an Iterator to be used to iterate through all the <Code>
     * Cell</code> in this <code>Population</code>.
     *
     * @return	an <code>Iterator</code> on the <code>Cell</code> collection
     */
    public Iterator getCellIterator() {
	return this.cells.iterator();
    }

    /**
     * Adds a <code>Cell</code> to this <code>Population</code>. Does nothing
     * when given <code>null</code>.
     *
     * @param toAdd	the <code>Cell</code> to add
     */
    public void addCell(Cell toAdd) {
	if (toAdd != null) {
	    this.cells.add(toAdd);
	}
    }

    /**
     * Adds all the <code>Cell</code>s in the given <code>Population</code>.
     * Does nothing on <code>null</code> or an empty <code>Population</code>.
     *
     * @param p	the <code>Population</code> to add
     */
    public void addCells(Population toAdd) {
	if (toAdd != null) {
	    this.cells.addAll(toAdd.cells);
	}
    }

    /**
     * Removes a <code>Cell</code> from this <code>Population</code>. Returns
     * whether the removal was successful or not. Does nothing when given a
     * <code>null</code>.
     *
     * @param toRemove	the <code>Cell</code> to remove
     * @return <code>true</code> on success;
     * <code>false</code> otherwise;
     */
    public boolean removeCell(Cell toRemove) {
	return (toRemove==null) ? true : this.cells.remove(toRemove);
    }

    /**
     * Removes a group of <code>Cell</code>s from this <code>Population
     * </code>. Does not indicate whether the removal was successful or not.
     * Does nothing when given a <code>null</code> or an empty <code>
     * Population</code>.
     *
     * @param p	the <code>Population</code> to remove
     */
    public void removeCells(Population toRemove) {
	if (toRemove != null) {
	    this.cells.removeAll(toRemove.cells);
	}
    }

    /**
     * Removes all the <code>Cell</code>s from this <code>Population</code>
     * except those specified in the passed <code>Population</code>. Does not
     * indicate whether the removal was successful or not. Does nothing when
     * given a <code>null</code> or an empty <code>Population</code>.
     *
     * @param p	the <code>Population</code> to keep
     */
    public void removeAllCellsBut(Population toKeep) {
	if (toKeep != null) {
	    this.cells.retainAll(toKeep.cells);
	}
    }

    /**
     * Removes all instances of <code>Cell</code> from this <code>
     * Population</code>. Does not indicate whether any removal took place.
     * Does nothing when given a <code>null</code> or a non-existant <code>
     * Cell</code>.
     *
     * @param toRemove	the <code>Cell</code> to remove
     */
    public void removeAllSameAs(Cell toRemove) {
	while (removeCell(toRemove));
    }

    /**
     * Returns a <code>Cell</code> from this <code>Population</code> with the
     * given index.
     *
     * <p>This method is not recommended since access to the collection
     * via an index is highly unreliable. This method is provided only to
     * provide a way for mutation selection algorithm to access random
     * elements of the <code>Cell</code> array without having to do constant
     * array conversions.
     *
     * @param index	the index of the <code>Cell</code> to return
     * @return <code>Cell</code> at the given index
     * @throws IndexOutOfBoundsException
     */
    public Cell getCell(int index) {
	Iterator iter = getCellIterator();
	Object o = null;

	if (index<0 || index>=this.getSize())
	    throw new IndexOutOfBoundsException(
	        "No such element in Population: index "+index+" of "+
	        this.getSize());

	for(int i = 0; i<=index; i++)
	    o = iter.next();

	return (Cell) o;
    }

    /**
     * Returns a <code>Cell[]</code> array representing all the <code>Cell
     * </code>s in this population. Returns an empty array when empty.
     *
     * @return <code>Cell[]</code> of all <code>Cell</code>s
     */
    public Cell[] getCellArray() {
	return (Cell[]) (this.cells.toArray(new Cell[0]));
    }

    /**
     * Returns the <code>Collection</code> used internally to represent the
     * members of the population
     *
     * @return <code>Collection</code> of all <code>Cell</code>s
     */
    public Collection getCells() {
	return this.cells;
    }

    /**
     * Condemns all the <code>Cell</code>s in the given <code>Population
     * </code>. Each <code>Cell</code> in the <code>Population</code> has
     * its <code>condemn()</code> called. A <code>null</code> passed
     * returns immediately.
     *
     * @param toCondemn the <code>Population</code> to condemn
     */
    public static void condemnPopulation(Population toCondemn) {
	if (toCondemn==null) return;

	for(Iterator i=toCondemn.getCellIterator(); i.hasNext(); ) {
	    ((Cell) i.next()).condemn();
	}
    }

    /**
     * Returns the number of <code>Cell</code>s in this <code>Population
     * </code>.
     *
     * @return the number of <code>Cell</code>s
     */
    public int getSize() {
	return this.cells.size();
    }

    /**
     * Removes non-<code>Cell</code> objects from the <code>Collection
     * </code>
     */
    public void cleanse() {
	Cell c;
	for (Iterator i = this.getCellIterator(); i.hasNext(); ) {
	    try {
	    	c = (Cell) i.next();
	    } catch (ClassCastException e) {
	    	i.remove();
	    }
	}
    }

    /**
     * Determines whether to display anything on a <code>toString()</code>
     * call.
     */
    public boolean toStringQuiet = false;

    /**
     * Determines whether to display the size of the <code>Population</code>
     */
    public boolean toStringUsesSize = true;

    /**
     * Determines whether to call all the <code>Cell</code>s to return
     * something as well.
     */
    public boolean toStringUsesCells = true;

    /**
     * Determines whether the <code>Cell</code> with the highest fitness
     * is displayed.
     */
    public boolean toStringUsesTopCell = true;

    /**
     * Returns a <code>String</code> representation of this <code>
     * Population</code>. Uses the following <code>boolean</code> values to
     * create the return <code>String</code>:
     * <ul>
     *   <li>toStringQuiet
     *   <li>toStringUsesSize
     *   <li>toStringUsesCells
     *   <li>toStringUsesTopCell
     * </ul>
     *
     * @return a <code>String</code> representation of the status
     */
    public String toString() {
	StringBuffer ret = new StringBuffer();

	if (toStringQuiet) {
	    return "";
	}

	if (toStringUsesSize) {
	    ret.append("{size:")
	       .append(this.getSize())
	       .append("}");
	}

	if (toStringUsesCells) {
	    ret.append("\n{population: ");

	    for (Iterator i = cells.iterator(); i.hasNext(); ) {
		ret.append("\n   [" )
		   .append(((Cell) i.next()).toString())
		   .append("]");
	    }

	    ret.append("\n}");
	}

	if (toStringUsesTopCell) {
	    double  highest = Double.NEGATIVE_INFINITY;
	    Cell c, best = null;

	    for (Iterator i = cells.iterator(); i.hasNext(); ) {
		c = (Cell) i.next();

		if (c.getFitness() > highest) {
		    highest = c.getFitness();
		    best = c;
		}
	    }

	    if (best!=null)
	        ret.append("{top: [")
	           .append(best.toString())
	           .append("]}");
	}

	return ret.append("\n").toString();
    }

    private static void db(String message) {
    	if (GeneticAlgorithm.getDebug()) {
    	    System.err.println("Population: " + message);
    	}
    }
}



/*--- formatting done in "Sun Java Convention" style on 12-28-2000 ---*/