selectgreatestfitness.java

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

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

/**
 * SelectionAlgorithm Class
 *
 * location: net.openai.ai.ga.selection.SelectionAlgorithm
 *
 */
package net.openai.ai.ga.selection.common;

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

import java.util.Iterator;

/**
 * <code>SelectGreatestFitness</code> is a <code>SelectionAlgorithm</code>
 * that will return a portion of the passed <code>Population</code> that
 * have the greatest fitness. It will choose either a fixed number or a
 * percentage.
 *
 * @author	Jared Grubb
 * @version	%I%, %G%
 * @since	JDK1.3
 */
public class SelectGreatestFitness implements SelectionAlgorithm {
    private int goal;
    private double percent;
    private boolean isPercentage;

    /**
     * Creates a new <code>SelectGreatestFitness</code> object for choosing
     * the specified number of <code>Cell</code>s out of the specified <code>
     * Population</code> who have the greatest fitness.
     *
     * @param goalNumber the maximum number of <code>Cell</code>s to allow
     * @throws <code>ArithmeticException</code> on a negative goalNumber
     */
    public SelectGreatestFitness(int goalNumber) {
        if (goalNumber<0)
            throw new ArithmeticException(
                "SelectGreatestFitness: illegal goal number");
        this.goal = goalNumber;
        this.isPercentage = false;
    }

    /**
     * Creates a new <code>SelectGreatestFitness</code> object for choosing
     * the specified percentage of <code>Cell</code>s out of the specified <code>
     * Population</code> who have the greatest fitness. The percentage must be
     * between 0.0 and 1.0, inclusive.
     *
     * @param goalNumber the maximum number of <code>Cell</code>s to allow
     * @throws <code>ArithmeticException</code> on a negative percentage or on
     *          a percentage greater than 1.0
     */
    public SelectGreatestFitness(double goalPercentage) {
        if (goalPercentage<0.0 || goalPercentage>1.0)
            throw new ArithmeticException(
                "SelectGreatestFitness: illegal percentile");
        this.percent = goalPercentage;
        this.isPercentage = true;
    }

    /**
     * Chooses the <code>Cell</code>s in the specified <code>Population</code>
     * with the greatest fitness. For a fixed number, returns a maximum number
     * depending on the size of the population, but may return fewer if the
     * population if the population is not that large. For a percentage, returns
     * a percentage of the population, rounded down (i.e., percentage of 10%
     * (0.10) on a size of 25 {0.10 * 25 = 2.5} returns a maximum of 2, not
     * three; percentage of 10% on a size of 9 {0.10 * 9 = 0.9} will not return
     * any objects.)
     *
     * <p>The returned population is guaranteed to return the members of the
     * specified population such that there are no other members in that
     * population who are greater than those returned. This means that cells
     * who tie those already in the return population are ignored when their
     * addition would cause the size to exceed that specified. For example, if
     * the fitness of a population was {1,1,2,3,3,3,4,5,5} and the greatest 4
     * should be returned, then the returned population will be {3,4,5,5}.
     * The cells who have fitness 5 are kept since their addition will knock
     * less fit members out of the list. However, the other cells of fitness 3
     * are ignored since their addition could not knock any other cell out.
     *
     * @param pop  the <code>Population</code> to choose from
     * @return a selected <code>Population</code> in arbitrary order
     */
    public Population selectFromPopulation(Population pop) {
        if (isPercentage) {goal=(int)(percent*pop.getSize());}

        Population output = new Population();
        if (goal==0) return output;

        Cell tempCell;
        Cell lowestCellInOutput = null;
        double lowestFitnessInOutput = Double.POSITIVE_INFINITY;
            // That needs to be +Inf! Otherwise if(tF<lFIO) {} fails below
        double tempFitness;

        for(Iterator i=pop.getCellIterator(); i.hasNext(); ) {
            tempCell = (Cell) i.next();
            tempFitness = tempCell.getFitness();

            if (output.getSize()<goal) { // Add cells until the goal is reached
                output.addCell(tempCell);
                if (tempFitness<=lowestFitnessInOutput) {
                  // <= in case fitness==Double.POSITIVE_INFINITY
                  // side effect: does not guarantee any order to adding cells
                    lowestFitnessInOutput = tempFitness;
                    lowestCellInOutput = tempCell;
                }
            } else if (tempFitness>lowestFitnessInOutput) {
                // Then start trimming out cells in the output
                output.removeCell(lowestCellInOutput);
                output.addCell(tempCell);
                lowestFitnessInOutput = tempFitness;
                lowestCellInOutput = tempCell;
                for (Iterator j = output.getCellIterator(); j.hasNext(); ) {
                    tempCell = (Cell) j.next();
                    tempFitness = tempCell.getFitness();
                    if (tempFitness<lowestFitnessInOutput) {
                        lowestFitnessInOutput = tempFitness;
                        lowestCellInOutput = tempCell;
                    }
                 }
            }
        }
        return output;
    }
}



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