gpgenotype.java

基于JAVA开发的遗传算法程序。功能很强大

    System.gc();
    if (a_verboseOutput) {
      LOGGER.info("Creating initial population");
      LOGGER.info("Mem free: "
                  + SystemKit.niceMemory(SystemKit.getTotalMemoryMB()) + " MB");
    }
    // Create initial population.
    // --------------------------
    GPPopulation pop = new GPPopulation(a_conf, a_conf.getPopulationSize());
    try {
      a_popCreator.initialize(pop, a_types, a_argTypes, a_nodeSets, a_minDepths,
                              a_maxDepths, a_maxNodes, a_fullModeAllowed);
    } catch (Exception ex) {
      throw new InvalidConfigurationException(ex);
    }
    System.gc();
    if (a_verboseOutput) {
      LOGGER.info("Mem free after creating population: "
                  + SystemKit.niceMemory(SystemKit.getTotalMemoryMB()) + " MB");
    }
    GPGenotype gp = new GPGenotype(a_conf, pop, a_types, a_argTypes, a_nodeSets,
                                   a_minDepths, a_maxDepths, a_maxNodes);
    gp.m_fullModeAllowed = a_fullModeAllowed;
    // Publish GP variables to configuration to make them accessible globally.
    // -----------------------------------------------------------------------
    Iterator it = gp.m_variables.keySet().iterator();
    while (it.hasNext()) {
      /**@todo optimize access to map*/
      String varName = (String) it.next();
      Variable var = (Variable) gp.m_variables.get(varName);
      a_conf.putVariable(var);
    }
    return gp;
  }

  public GPConfiguration getGPConfiguration() {
    return m_configuration;
  }

  /**
   * @return the static configuration to use with the Genetic Programming
   *
   * @author Klaus Meffert
   * @since 3.2
   */
  public static GPConfiguration getStaticGPConfiguration() {
    return m_staticConfiguration;
  }

  /**
   * Sets the static configuration to use with the Genetic Programming.
   *
   * @param a_configuration the static configuration to use
   *
   * @author Klaus Meffert
   * @since 3.2
   */
  public static void setStaticGPConfiguration(GPConfiguration a_configuration) {
    m_staticConfiguration = a_configuration;
  }

  static class GPFitnessComparator
      implements Comparator {
    public int compare(Object o1, Object o2) {
      if (! (o1 instanceof IGPProgram) ||
          ! (o2 instanceof IGPProgram))
        throw new ClassCastException(
            "FitnessComparator must operate on IGPProgram instances");
      double f1 = ( (IGPProgram) o1).getFitnessValue();
      double f2 = ( (IGPProgram) o2).getFitnessValue();
      if (f1 > f2) {
        return 1;
      }
      else if (Math.abs(f1 - f2) < 0.000001) {
        return 0;
      }
      else {
        return -1;
      }
    }
  }

  /**
   * Evolves the population n times.
   *
   * @param a_evolutions number of evolution
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void evolve(int a_evolutions) {
    int offset = getGPConfiguration().getGenerationNr();
    int evolutions;
    if (a_evolutions < 0) {
      evolutions = Integer.MAX_VALUE;
    }
    else {
      evolutions = a_evolutions;
    }
//    getGPPopulation().sort(new GPFitnessComparator());
    for (int i = 0; i < evolutions; i++) {
//      if (m_bestFitness < 0.000001) {
//        // Optimal solution found, quit.
//        // -----------------------------
//        return;
//      }
      if (m_verbose) {
        if (i % 25 == 0) {
          String freeMB = SystemKit.niceMemory(SystemKit.getFreeMemoryMB());
          LOGGER.info("Evolving generation "
                      + (i + offset)
                      + ", memory free: "
                      +  freeMB
                      + " MB");
        }
      }
      evolve();
      calcFitness();
    }
  }

  /**
   * Calculates the fitness value of all programs, of the best solution as well
   * as the total fitness (sum of all fitness values).
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void calcFitness() {
    double totalFitness = 0.0d;
    GPPopulation pop = getGPPopulation();
    IGPProgram best = null;
    IGPFitnessEvaluator evaluator = getGPConfiguration().getGPFitnessEvaluator();
    m_bestFitness = FitnessFunction.NO_FITNESS_VALUE;
    for (int i = 0; i < pop.size() && pop.getGPProgram(i) != null; i++) {
      IGPProgram program = pop.getGPProgram(i);
      /**@todo get information from fitness function how calculation happened.
       * In case of Robocode: Return the robot competed against, in case the
       * -enemies option was used without -battleAll
       */
      double fitness;
      try {
        fitness = program.getFitnessValue();
      }
      catch (IllegalStateException iex) {
        fitness = Double.NaN;
      }
      // Don't acceppt Infinity as a result.
      // -----------------------------------
      if (Double.isInfinite(fitness) || Double.isNaN(fitness)) {
        continue;
      }
      if (best == null || evaluator.isFitter(fitness, m_bestFitness)) {
        best = program;
        m_bestFitness = fitness;
      }
      // Problem with totalFitness: what about fitness being NaN?
      totalFitness += fitness;
    }
    m_totalFitness = totalFitness;
//    best = pop.determineFittestProgram();
//    m_bestFitness = best.getFitnessValue();
    /**@todo do something similar here as with Genotype.preserveFittestChromosome*/
    if (m_allTimeBest == null
        || evaluator.isFitter(m_bestFitness, m_allTimeBestFitness)) {
      pop.setChanged(true);
      try {
        ICloneHandler cloner = getGPConfiguration().getJGAPFactory().
            getCloneHandlerFor(best, null);
        if (cloner == null) {
          m_allTimeBest = best;
          if (!m_cloneWarningGPProgramShown) {
            LOGGER.info("Warning: cannot clone instance of "
                        + best.getClass());
            m_cloneWarningGPProgramShown = true;
          }
        }
        else {
          m_allTimeBest = (IGPProgram) cloner.perform(best, null, null);
        }
      }
      catch (Exception ex) {
        m_allTimeBest = best;
        ex.printStackTrace();
      }
      m_allTimeBestFitness = m_bestFitness;
      // Fire an event to indicate a new best solution.
      // ----------------------------------------------
      /**@todo introduce global value object to be passed to the listener*/
      try {
        getGPConfiguration().getEventManager().fireGeneticEvent(
            new GeneticEvent(GeneticEvent.GPGENOTYPE_NEW_BEST_SOLUTION, this));
      } catch (IllegalArgumentException iex) {
        /**@todo should not happen but does with ensureUniqueness(..)*/
      }
      if (m_verbose) {
        // Output the new best solution found.
        // -----------------------------------
        outputSolution(m_allTimeBest);
      }
    }
  }

  /**
   * @return the all-time best solution found
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public IGPProgram getAllTimeBest() {
    return m_allTimeBest;
  }

  /**
   * Outputs the best solution until now.
   *
   * @param a_best the fittest ProgramChromosome
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void outputSolution(IGPProgram a_best) {
    if (a_best == null) {
      LOGGER.info("No best solution (null");
      return;
    }
    double bestValue = a_best.getFitnessValue();
    if (Double.isInfinite(bestValue)) {
      LOGGER.info("No best solution (infinite)");
      return;
    }
    LOGGER.info("Best solution fitness: " + bestValue);
    LOGGER.info("Best solution: " + a_best.toStringNorm(0));
    String depths = "";
    int size = a_best.size();
    for (int i = 0; i < size; i++) {
      if (i > 0) {
        depths += " / ";
      }
      depths += a_best.getChromosome(i).getDepth(0);
    }
    if (size == 1) {
      LOGGER.info("Depth of chrom: " + depths);
    }
    else {
      LOGGER.info("Depths of chroms: " + depths);
    }
  }

  /**
   * Evolve the population by one generation. Probabilistically reproduces
   * and crosses individuals into a new population which then overwrites the
   * original population.
   *
   * @author Klaus Meffert
   * @since 3.0
   */
  public void evolve() {
    try {
      int popSize = getGPConfiguration().getPopulationSize();
      GPPopulation oldPop = getGPPopulation();
      GPPopulation newPopulation = new GPPopulation(oldPop, false);
      if (m_fittestToAdd != null) {
        newPopulation.addFittestProgram(m_fittestToAdd);
        m_fittestToAdd = null;
      }
      float val;
      RandomGenerator random = getGPConfiguration().getRandomGenerator();
      GPConfiguration conf = getGPConfiguration();
      // Determine how many new individuals will be added to the new generation.
      // -----------------------------------------------------------------------
      int popSize1 = (int) Math.round(popSize * (1 - conf.getNewChromsPercent()));
      double crossProb = conf.getCrossoverProb()
          / (conf.getCrossoverProb() + conf.getReproductionProb());
      int crossover = 0;
      int reproduction = 0;
      int creation = 0;
      for (int i = 0; i < popSize1; i++) {
        // Clear the stack for each GP program (=ProgramChromosome).
        // ---------------------------------------------------------
        getGPConfiguration().clearStack();
        val = random.nextFloat();
        // Note that if we only have one slot left to fill, we don't do
        // crossover, but fall through to reproduction.
        // ------------------------------------------------------------
        if (i < popSize - 1 && val < crossProb) {
          crossover++;
          // Do crossover.
          // -------------
          IGPProgram i1 = conf.getSelectionMethod().select(this);
//          newPopulation.checkIfFittest(i1);
          IGPProgram i2 = conf.getSelectionMethod().select(this);
//          newPopulation.checkIfFittest(i2);
          int tries = 0;
          do {
            try {
              IGPProgram[] newIndividuals = conf.getCrossMethod().operate(i1,
                  i2);
              newPopulation.setGPProgram(i, newIndividuals[0]);
              newPopulation.setGPProgram(i + 1, newIndividuals[1]);
              i++;
              break;
            }
            catch (IllegalStateException iex) {
              tries++;
              if (tries >= getGPConfiguration().getProgramCreationMaxtries()) {
                if (!getGPConfiguration().isMaxNodeWarningPrinted()) {
                  LOGGER.error(
                      "Warning: Maximum number of nodes allowed may be too small");
                  getGPConfiguration().flagMaxNodeWarningPrinted();
                  // Try cloning a previously generated valid program.
                  // -------------------------------------------------
                  IGPProgram program = cloneProgram(getGPConfiguration().
                      getPrototypeProgram());
                  if (program != null) {
                    newPopulation.setGPProgram(i++, program);
                    program = cloneProgram(getGPConfiguration().
                                           getPrototypeProgram());
                    newPopulation.setGPProgram(i, program);
                    break;
                  }
                  else {
                    throw new IllegalStateException(iex.getMessage());
                  }
                }
              }
            }
          }
          while (true);
        }
        else {//if (val < conf.getCrossoverProb() + conf.getReproductionProb()) {
          // Reproduction only.
          // ------------------
          reproduction++;
          newPopulation.setGPProgram(i, conf.getSelectionMethod().select(this));
        }
      }
      // Add new chromosomes randomly.
      // -----------------------------
      for (int i = popSize1; i < popSize; i++) {
        creation++;
        // Determine depth randomly and between minInitDepth and maxInitDepth.
        // -------------------------------------------------------------------
        int depth = conf.getMinInitDepth()
            + random.nextInt(conf.getMaxInitDepth() - conf.getMinInitDepth()
                             + 1);
        int tries = 0;
        do {
          try {
            /**@todo use program creator in case such is registered and returns
             * a non-null program
             */
            IGPProgram program = newPopulation.create(i, m_types, m_argTypes,
                m_nodeSets, m_minDepths, m_maxDepths, depth, (i % 2) == 0,
                m_maxNodes, m_fullModeAllowed, tries);
            newPopulation.setGPProgram(i, program);
            LOGGER.debug("Added new GP program (depth "
                         + depth
                         + ", "
                         + tries
                         + " tries)");
            break;
          }
          catch (IllegalStateException iex) {
            /**@todo instead of re-using prototype, create a program anyway
             * (ignoring the validator) in case it is the last try.
             * Or even better: Make the validator return a defect rate!
             */
            tries++;
            if (tries > getGPConfiguration().getProgramCreationMaxtries()) {
              LOGGER.debug(
                  "Creating random GP program failed (depth "
                  + depth
                  + ", "
                  + tries
                  + " tries), will use prototype");
              // Try cloning a previously generated valid program.
              // -------------------------------------------------
              IGPProgram program = cloneProgram(getGPConfiguration().
                                                getPrototypeProgram());