painteddesertproblem.java

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

   *
   * @author Scott Mueller
   */
  public static void main(String[] args) {
    try {
      System.out.println("Painted Desert Problem");
      GPConfiguration config = new GPConfiguration();
      config.setSelectionMethod(new TournamentSelector(3));
      config.setGPFitnessEvaluator(new DeltaGPFitnessEvaluator());
      int popSize = 300;
      String filename;
      if (args.length == 1) {
        filename = args[0];
      }
      else {
        filename = "standard.desert";
      }
      System.out.println("Using population size of " + popSize);
      System.out.println("Using map " + filename);
      config.setMaxInitDepth(10);
      config.setPopulationSize(popSize);
      final PaintedDesertProblem problem = new PaintedDesertProblem(config);
      GPFitnessFunction func = problem.createFitFunc();
      config.setFitnessFunction(func);
      config.setCrossoverProb(0.4f);
      config.setReproductionProb(0.6f);
      config.setFunctionProb(0.6f);
      config.setNewChromsPercent(0.3f);
      config.setStrictProgramCreation(true);
      config.setUseProgramCache(false);
      GPGenotype gp = problem.create();
      gp.setVerboseOutput(true);
      // Read the map from file.
      problem.m_map = problem.readMap(filename);
      problem.displaySolution(problem.m_map, problem.m_map);
      m_antMap = new AntMap(problem.m_map, problem.m_ants);
      // Simple implementation of running evolution in a thread.

      final Thread t = new Thread(gp);
      IEventManager eventManager = config.getEventManager();
      eventManager.addEventListener(GeneticEvent.
                                    GPGENOTYPE_EVOLVED_EVENT,
                                    new GeneticEventListener() {
        public void geneticEventFired(GeneticEvent a_firedEvent) {
          GPGenotype genotype = (GPGenotype) a_firedEvent.getSource();
          int evno = genotype.getGPConfiguration().getGenerationNr();
          double freeMem = SystemKit.getFreeMemoryMB();
          if (evno % 10 == 0) {
            double bestFitness = genotype.getFittestProgram().
                getFitnessValue();
            System.out.println("Evolving generation " + evno
                               + ", best fitness: " + bestFitness
                               + ", memory free: " + freeMem + " MB");
          }
          if (evno > 500000) {
            t.stop();
          }
          else {
            try {
              // Collect garbage if memory low.
              if (freeMem < 50) {
                System.gc();
                t.sleep(500);
              }
              else {
                // Avoid 100% CPU load.
                t.sleep(30);
              }
            } catch (InterruptedException iex) {
              iex.printStackTrace();
              System.exit(1);
            }
          }
        }
      });
      eventManager.addEventListener(GeneticEvent.
                                    GPGENOTYPE_NEW_BEST_SOLUTION,
                                    new GeneticEventListener() {
        public void geneticEventFired(GeneticEvent a_firedEvent) {
          GPGenotype genotype = (GPGenotype) a_firedEvent.getSource();
          int evno = genotype.getGPConfiguration().getGenerationNr();
          String indexString = "" + evno;
          while (indexString.length() < 5) {
            indexString = "0" + indexString;
          }
//          String filename = "painteddesert_best" + indexString + ".png";
          IGPProgram best = genotype.getAllTimeBest();
          // Display solution's final map.
          // -----------------------------
          AntMap antmap = (AntMap) best.getApplicationData();
          problem.displaySolution(antmap.getMap(), antmap.getInitialMap());
          java.text.DateFormat df = java.text.DateFormat.getTimeInstance(java.
              text.DateFormat.SHORT);
          String time = df.format(new java.util.Date());
          System.out.println(time + " Number of moves: " + antmap.getMoveCount());
          double bestFitness = genotype.getFittestProgram().
              getFitnessValue();
          if (bestFitness < 0.001) {
            genotype.outputSolution(best);
            t.stop();
            System.exit(0);
          }
        }
      });
      //
//      eventManager.addEventListener(GeneticEvent.
//                                    GPGENOTYPE_NEW_BEST_SOLUTION,
//                                    new MyGeneticEventListener(problem, t));
      t.start();
    } catch (Exception ex) {
      ex.printStackTrace();
      System.exit(1);
    }
  }

  /**
   * Display ant map as found by GP.
   *
   * @param a_antmap the map containing the ants and grains of sand
   */
  private static void displaySolution(int[][] a_antmap, int[][] origMap) {
    for (int y = 0; y < m_maxy; y++) {
      for (int x = 0; x < m_maxx; x++) {
        char toPrint = '?';
        int c = a_antmap[x][y];
        switch (c) {
          case AntMap.ANT_AT_POSITION:
            toPrint = 'A';
            break;
          case AntMap.BLACK:
            toPrint = 'b';
            break;
          case AntMap.GRAY:
            toPrint = 'g';
            break;
          case AntMap.EMPTY:
            toPrint = ' ';
            break;
          case AntMap.STRIPED:
            toPrint = 's';
            break;
        }
        System.out.print(toPrint);
      }
      System.out.print("  ");
      for (int x = 0; x < m_maxx; x++) {
        char toPrint = '?';
        int c = origMap[x][y];
        switch (c) {
          case AntMap.ANT_AT_POSITION:
            toPrint = 'A';
            break;
          case AntMap.BLACK:
            toPrint = 'b';
            break;
          case AntMap.GRAY:
            toPrint = 'g';
            break;
          case AntMap.EMPTY:
            toPrint = ' ';
            break;
          case AntMap.STRIPED:
            toPrint = 's';
            break;
        }
        System.out.print(toPrint);
      }
      System.out.println();
    }
    System.out.println();
  }

  private GPFitnessFunction createFitFunc() {
    return new AntFitnessFunction();
  }

  /**
   * Represents the fitness funtion.  Counts the grains of sand to that are not in the
   * correct column.  This varies from the measurement used by Koza and tries to penalize
   * the ants that are further from the proper location.
   *
   * @author Scott Mueller
   *
   */
  class AntFitnessFunction
      extends GPFitnessFunction {
    private static final int VALUE1 = 100;

    protected double evaluate(final IGPProgram a_subject) {
      return computeRawFitness(a_subject);
    }

    public double computeRawFitness(final IGPProgram a_program) {
      double error = 0.0f;
      Object[] noargs = new Object[0];
      // Initialize local stores.
      a_program.getGPConfiguration().clearStack();
      a_program.getGPConfiguration().clearMemory();
      a_program.setApplicationData(m_antMap);
      try {
        m_antMap.init();
        // Execute the program for each ant in turn.
        for (int antIndex = 0; antIndex < m_popSize; antIndex++) {
          m_antMap.nextAnt();
          a_program.execute_void(0, noargs);
        }
        // Determine success of individual.
        // --------------------------------
        error = (double) m_antMap.fitness();
      } catch (IllegalStateException iex) {
        error = GPFitnessFunction.MAX_FITNESS_VALUE;
      }
      return error;
    }
  }
  /**
   * Resets the ants to initial positions. So they can be run with the next version
   * of the program.
   */
  public void resetAnts() {
    for (int antIndex = 0; antIndex < m_popSize; antIndex++) {
      m_antMap.getAnts()[antIndex].reset();
    }
  }

}