geneticalgorithm.java

遗传算法源代码,实现了选择操作、交叉操作和变异操作

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

/**
 * GeneticAlgorithm
 *
 * location: net.openai.ai.ga.GenteticAlgorithm
 *
 */
package net.openai.ai.ga;

import net.openai.ai.ga.world.*;
import java.util.Collection;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * GeneticAlgorithm is the top-level class for the Genetic Algorithm Java
 * implementation of the OpenAI Toolkit. It provides the handling
 * of multiple worlds (isolated genetic algorithm implementations) and making
 * the algorithms run.
 *
 * @author	Jared Grubb
 * @version	%I%, %G%
 * @since	JDK1.3
 */
public class GeneticAlgorithm {
    /**
     * Controls whether
     */
    private static boolean debug = true;

    /**
     * The collection of all the World objects in this GeneticAlgorithm.
     * Since World's are stored as Object's, it is important to keep this
     * list private to avoid adding non-World objects to this list
     */
    private Collection worlds;

    /**
     * Initializes the GeneticAlgorithm with an <code>ArrayList</code>
     */
    public GeneticAlgorithm() {
	this(new ArrayList());
    }

    /**
     * Initializes the GeneticAlgorithm with the specified <code>
     * Collection</code>
     */
    public GeneticAlgorithm(Collection initialCollection) {
	worlds = initialCollection;
    }

    /**
     * Adds a given World onto the end of all the worlds in this
     * Genetic Algorithm.
     *
     * @param toAdd a World to be added into this GeneticAlgorithm
     */
    public void addWorld(World toAdd) {
	worlds.add(toAdd);
    }

    /**
     * Removes a given World out of this GeneticAlgorithm. Returns true
     * when it can successfully remove the given World. When multiple copies
     * of the given World exist, only the first instance is deleted. This
     * method does not throw an IndexOutOfBoundsException.
     *
     * @param toRemove	a World to be deleted from this GeneticAlgorithm
     * @return 		<code>true</code> if the World has been found and
     *                  deleted<br>
     *                  <code>false</code> otherwise
     */
    public boolean removeWorld(World toRemove) {
	return worlds.remove(toRemove);
    }

    /**
     * Removes a World with the given name out of this GeneticAlgorithm.
     * Returns true when it can successfully remove the given World. When
     * multiple copies of the given World exist, only the first instance is
     * deleted. This method does not throw an IndexOutOfBoundsException. This
     * method uses getWorld(String) to find the given World.
     *
     * @param name	a String specifying the name of the world to be deleted
     * @return 		<code>true</code> if the World has been found and
     *                  deleted<br>
     *                  <code>false</code> otherwise
     */
    public boolean removeWorld(String name) {
	return removeWorld(getWorld(name));
    }

    /**
     * Removes all World's with the given name out of this GeneticAlgorithm.
     * This method does not throw an IndexOutOfBoundsException. This
     * method uses removeWorld(String) to delete all World's with the given
     * name and keeps calling until removeWorld(String) returns false. Does
     * not return a value.
     *
     * @param name	a String specifying the name of the world to be deleted
     */
    public void removeAllWorlds(String name) {
	while (removeWorld(name));
    }

    /**
     * Retrieves a World from the list with a given name. Iterates through
     * all the World's in this GeneticAlgorithm until one is found that has
     * the given name. Returns the World when one is found; returns null when
     * the search is unsuccessful.
     *
     * @param name	a String specifying the name of the world to be returned
     * @return		<code>Object</code> when a match is found<br>
     *                  <code>null</code> when no match can be found
     */
    public World getWorld(String name) {
	World w;

	for (Iterator i = getWorldIterator(); i.hasNext(); ) {
	    w = (World) i.next();

	    if (name.equals(w.getName())) {
		return w;
	    }
	}

	return null;
    }

    /**
     * Retrieves a World from the list with a given name. Iterates through
     * all the World's in this GeneticAlgorithm until one is found that has
     * the given name. Returns the World when one is found; returns null when
     * the search is unsuccessful.
     *
     * @param name	a String specifying the name of the world to be returned
     * @return		<code>Object</code> when a match is found<br>
     *                  <code>null</code> when no match can be found
     */
    public String[] getWorldNames() {
	String[] names = new String[worlds.size()];
	int      ctr = 0;

	for (Iterator i = getWorldIterator(); i.hasNext(); ) {
	    names[ctr++] = ((World) (i.next())).getName();
	}

	return names;
    }

    /**
     * Retrieves a World[] copy of all the World's in this GeneticAlgorithm.
     * The order is not guaranteed to be consistant on every call.
     *
     * @return		<code>World[]</code> of all the World objects
     */
    public World[] getWorldArray() {
	return (World[]) (worlds.toArray(new World[0]));
    }

    /**
     * Retrieves the <code>Collection</code> that holds this collection's
     * <code>World</code> objects
     *
     * @return		<code>Collection</code> of all the World objects
     */
    public Collection getWorlds() {
	return worlds;
    }

    /**
     * Tells a World with a given name to iterate through one generation. Uses
     * getWorld(String) to find the World with the given name and calls that
     * World's iterate() function.
     *
     * @param name	a String specifying the name of the world to iterate()
     */
    public void iterateWorld(String name) {
	iterateWorld(getWorld(name));
    }

    /**
     * Tells a World to iterate through one generation. Equilivant to calling
     * the iterate() function of the given World. Throws an exception when
     * the World does not belong to its collection.
     *
     * @param toIterate		a World to iterate
     * @throws NoSuchElementException thrown if the specified <code>World</code>
     *          does not belong to this <code>GeneticAlgorithm</code>
     */
    public void iterateWorld(World toIterate) {
	if (worlds.contains(toIterate)) {
	    iterate_Unconditional(toIterate);
	} else {
	    throw new NoSuchElementException(
	        "World does not exist in GeneticAlgorithm");
	}
    }

    /**
     * Tells a World to iterate through multiple generations. Calls
     * getWorld(name) to retrieve the World from the collection and then
     * calls the iterate() function on it a given number of times. Does not
     * iterate when called with a non-positive number. Does no iterations
     * when no world with the given name can be found.
     *
     * @param name	a String specifying a world to iterate
     * @param reps	the number of times to iterate
     */
    public void iterateWorld(String name, int reps) {
	World w = getWorld(name);
	if (w==null) return;

	for (int i = 0; i < reps; i++) {
	    iterate_Unconditional(w);
	}
    }

    /**
     * Tells a World to iterate through multiple generations. Calls
     * getWorld(name) to retrieve the World from the collection and then
     * calls the iterate() function on it a given number of times. Does not
     * iterate when called with a non-positive number. Throws an exception
     * when the World does not belong to its collection.
     *
     * @param toIterate	the <code>World</code> to iterate
     * @param reps	the number of times to iterate
     * @throws NoSuchElementException thrown if the specified <code>World</code>
     *          does not belong to this <code>GeneticAlgorithm</code>
     */
    public void iterateWorld(World toIterate, int reps) {
	if (worlds.contains(toIterate)==false) {
	    throw new NoSuchElementException(
	        "World does not exist in GeneticAlgorithm");
	}

	for (int i = 0; i < reps; i++) {
	    iterate_Unconditional(toIterate);
	}
    }

    /**
     * Tells all World's in this GeneticAlgorithm to iterate through one
     * generation. Uses getWorldIterator() to iterate through each call,
     * and therefore does not guarantee any order of execution.
     */
    public void iterateAllWorlds() {
	for (Iterator i = getWorldIterator(); i.hasNext(); ) {
	    iterate_Unconditional((World) (i.next()));
	}
    }

    /**
     * Tells all World's in this GeneticAlgorithm to iterate through multiple
     * generations. There are two methods of iteration:
     * <ul>
     *   <li>Serially - Each world is iterated the complete number of times
     *          before the next world is iterated even once.
     *   <li>Parallelly - Each world is iterated once before any other world
     *          gets to iterate again.
     * </ul>
     * @param reps		the number of times to iterate each world
     * @param iterateParallel <code>false</code> specifies serial iteration
     *                          (all iterations on each world)<br>
     *                         <code>true</code> specifies parallel iteration
     *                          (each iteration simultaneously on all worlds)
     */
    public void iterateAllWorlds(int reps, boolean iterateParallel) {
	if (iterateParallel == true) {
	    for (int i = 0; i < reps; i++) {
		iterateAllWorlds();
	    }
	} else {
	    for (Iterator i = getWorldIterator(); i.hasNext(); ) {
		iterateWorld((World) (i.next()), reps);
	    }
	}
    }

    /**
     * Internal. Iterates the World without checking whether it's part of the
     * collection. Called from all public iterate methods.
     *
     * @param toIterate	the World to iterate once
     */
    private void iterate_Unconditional(World toIterate) {
	toIterate.iterate();
    }

    /**
     * Returns the number of <code>World</code>s stored in this <code>
     * GeneticAlgorithm</code>.
     *
     * @return	the number of <code>World</code>s
     */
    public int getNumberOfWorlds() {
	return worlds.size();
    }

    /**
     * Calls every <code>World<code>'s <code>toString()</code> method and
     * returns a concatenation of all the <code>String</code>s returned.
     *
     * @return a concatenated <code>String</code> of all the <code>World</code>s'
     *           <code>toString()</code> methods
     */
    public String toString() {
	StringBuffer sb = new StringBuffer("");

	for (Iterator i = getWorldIterator(); i.hasNext(); ) {
	    sb.append((World) (i.next())).append(";");
	}

	return sb.toString();
    }

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

    /**
     * Return an <code>Iterator</code> to use to go through all the <code>
     * World</code>s in this <code>GeneticAlgorithm</code>.
     *
     * @return an <code>Iterator</code> for the collection of <code>World</code>s
     */
    public Iterator getWorldIterator() {
	return worlds.iterator();
    }

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

    public static boolean getDebug() {return debug;}
}



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