painteddesertproblem.java

JGAP是一种遗传算法和遗传规划的组成部分提供了一个Java框架。它提供了基本的遗传机制

/*
 * This file is part of JGAP.
 *
 * JGAP offers a dual license model containing the LGPL as well as the MPL.
 *
 * For licensing information please see the file license.txt included with JGAP
 * or have a look at the top of class org.jgap.Chromosome which representatively
 * includes the JGAP license policy applicable for any file delivered with JGAP.
 */
package examples.gp.paintedDesert;

import java.io.*;
import java.util.*;
import org.jgap.*;
import org.jgap.event.*;
import org.jgap.gp.*;
import org.jgap.gp.function.*;
import org.jgap.gp.impl.*;
import org.jgap.util.*;

/**
 * The Painted Desert problem from Koza's "Evolution of Emergent Cooperative Behavior
 * using Genetic Programming".  The problem is to create the same genetic program for
 * a group of ants that will move three colors of sand into columns of like sand.
 *
 * @author Scott Mueller
 * @since 3.2
 */
public class PaintedDesertProblem
    extends GPProblem {
  /** String containing the CVS revision. Read out via reflection!*/
  private final static String CVS_REVISION = "$Revision: 1.4 $";
  /**
   * Local copy of the map read into from the file.
   */
  private int[][] m_map;

  /**
   * Set by readMap and passed to the AntMap constructor
   */
  private Ant[] m_ants;

  /**
   * Holds the AntMap object used to hold the initial and current map of sand
   * and Ants.
   */
  private static AntMap m_antMap;

  /**
   * The maximum number of locations in the East or X direction.
   */
  private static int m_maxx;

  /**
   * The maximum number of locaitons in the North or Y direction.
   */
  private static int m_maxy;

  /**
   * The number of ants in the map.
   */
  private static int m_popSize;

  /**
   * Maximum number of moves allowed.
   */
  private static int m_maxMoves = 300;

  /**
   * Creates the Painted Desert Problem using the GPConfiguration.
   * @param a_conf
   * @throws InvalidConfigurationException
   */
  public PaintedDesertProblem(GPConfiguration a_conf)
      throws InvalidConfigurationException {
    super(a_conf);
  }

  /**
   * Sets up the functions to use and other parameters. Then creates the
   * initial genotype.
   *
   * @return the genotype created
   * @throws InvalidConfigurationException
   *
   * @author Scott Mueller
   */
  public GPGenotype create()
      throws InvalidConfigurationException {
    Class[] types = {CommandGene.VoidClass};
    Class[][] argTypes = { {}
    };
    int[] minDepths = new int[] {2};
    int[] maxDepths = new int[] {8};
    GPConfiguration conf = getGPConfiguration();
    CommandGene[][] nodeSets = { {
        new SubProgram(conf, new Class[] {CommandGene.VoidClass,
                       CommandGene.VoidClass, CommandGene.VoidClass}),
        new SubProgram(conf, new Class[] {CommandGene.VoidClass,
                       CommandGene.VoidClass}),
        new X(conf),
        new Y(conf),
        new Carrying(conf),
        new SandColor(conf),
        new GO_N(conf),
        new GO_E(conf),
        new GO_S(conf),
        new GO_W(conf),
        new MoveRandom(conf),
        new Pickup(conf),
        new IfDrop(conf, CommandGene.IntegerClass),
        new IfLessThanOrEqual(conf, CommandGene.IntegerClass),
        new IfLessThanZero(conf, CommandGene.IntegerClass),
        new IfDrop(conf, CommandGene.IntegerClass),
    }
    };
    // Create genotype with initial population.
    return GPGenotype.randomInitialGenotype(conf, types, argTypes, nodeSets,
        minDepths, maxDepths, 5000, new boolean[] {!true}, true);
  }

  /**
   * Reads the map from a file.  The first line contains the number of X and Y locations and
   * the number of Ants on the map. A 'b' at a location represents a Black grain of sand.
   * A 's' represents a striped grain of sands.  A 'g' represents a grey grain of sand.  An
   * 'A' represents an Ant.  A 'B' represents an Ant and a black grain of sand at the
   * same location.  A 'S' represents an Ant and a striped grain of sand at the same location.
   * A 'G' represents an Ant and a grey grain of sand at the same location.
   *
   * A side effect of this function is setting the m_ants member variable.
   *
   * @param a_filename The location of the file containing the map information.
   * @return An array of the sand locations read in from the map.
   * @throws Exception
   */
  private int[][] readMap(String a_filename)
      throws Exception {
    LineNumberReader lnr;
    try {
      lnr = new LineNumberReader(new FileReader(a_filename));
    } catch (FileNotFoundException fex) {
      throw new FileNotFoundException("File not found: " +
                                      new File(".").getAbsolutePath() +
                                      a_filename);
    }
    // Read dimensions of trail and the number of ants.
    try {
      StringTokenizer st = new StringTokenizer(lnr.readLine());
      m_maxx = Integer.parseInt(st.nextToken());
      m_maxy = Integer.parseInt(st.nextToken());
      m_popSize = Integer.parseInt(st.nextToken());
      int[][] result = new int[m_maxx][m_maxy];
      m_ants = new Ant[m_popSize];
      int y;
      int antIndex = 0;
      for (y = 0; y < m_maxy; y++) {
        String s = lnr.readLine();
        System.out.println(s);
        if (s == null) {
          throw new RuntimeException("Ant map file ended prematurely");
        }
        int x;
        for (x = 0; x < s.length() & x < m_maxx; x++) {
          if (s.charAt(x) == ' ') {
            result[x][y] = AntMap.EMPTY;
          }
          else if (s.charAt(x) == 'b') {
            result[x][y] = AntMap.BLACK;
          }
          else if (s.charAt(x) == 'g') {
            result[x][y] = AntMap.GRAY;
          }
          else if (s.charAt(x) == 's') {
            result[x][y] = AntMap.STRIPED;
          }
          else if (s.charAt(x) == 'A') {
            result[x][y] = AntMap.EMPTY;
            m_ants[antIndex] = new Ant(x, y);
            antIndex++;
          }
          else if (s.charAt(x) == 'S') {
            result[x][y] = AntMap.STRIPED;
            m_ants[antIndex] = new Ant(x, y);
            antIndex++;
          }
          else if (s.charAt(x) == 'G') {
            result[x][y] = AntMap.GRAY;
            m_ants[antIndex] = new Ant(x, y);
            antIndex++;
          }
          else if (s.charAt(x) == 'B') {
            result[x][y] = AntMap.BLACK;
            m_ants[antIndex] = new Ant(x, y);
            antIndex++;
          }
          else {
            throw new RuntimeException("Bad character '" + s.charAt(x) +
                                       "' on line number " + lnr.getLineNumber() +
                                       " of the Ant map file.");
          }
        }
        // fill out rest of X's
        for (int z = x; z < m_maxx; z++) {
          result[z][y] = AntMap.EMPTY;
        }
      }
      // fill out rest of Y's
      for (int z = y; z < m_maxy; z++) {
        for (int x = 0; x < m_maxx; x++) {
          result[x][z] = AntMap.EMPTY;
        }
      }
      return result;
    } catch (NumberFormatException e) {
      throw new RuntimeException(
          "The Ant map file does not begin with x and y and nbrOfAnts integer values.");
    } catch (IOException e) {
      throw new RuntimeException(
          "The Ant map file could not be read due to an IOException:\n" + e);
    }
  }

  /**
   * Runs the Painted Desert Problem
   *
   * @param args The location of the ant map file is optional
   * @throws Exception