abstractsupergene.java

java实现的遗传算法

/*
 * This file is part of JGAP.
 *
 * JGAP offers a dual license model containing the LGPL as well as the MPL.
 *
 * For licencing 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 org.jgap.supergenes;

import java.io.*;
import java.net.*;
import java.util.*;
import org.jgap.*;

/**
 * Combined implementation of both Supergene and SupergeneValidator.
 * A working supergene can be easily created from this class just by
 * adding genes and overriding
 * {@link org.jgap.supergenes.abstractSupergene#isValid(Gene [] a_case,
 *  Supergene a_forSupergene) isValid (Gene [], Supergene)}
 *  method. For more complex cases, you may need to set your own
 * {@link org.jgap.supergenes.Validator Validator}.
 *
 * @author Audrius Meskauskas
 * @since 2.0
 */
public abstract class abstractSupergene extends BaseGene
    implements Supergene, supergeneValidator, Serializable {
  /** String containing the CVS revision. Read out via reflection!*/
  private final static String CVS_REVISION = "$Revision: 1.15 $";

  /**
   * This field separates gene class name from
   * the gene persistent representation string.
   */
  public final static String GENE_DELIMITER = "#";

  /**
   * Represents the heading delimiter that is used to separate genes in the
   * persistent representation of CompositeGene instances.
   */
  public final static String GENE_DELIMITER_HEADING = "<";

  /**
   * Represents the closing delimiter that is used to separate genes in the
   * persistent representation of CompositeGene instances.
   */
  public final static String GENE_DELIMITER_CLOSING = ">";

  /** Holds the genes of this supergene. */
  private Gene[] m_genes;

  /**
   * @return the array of genes - components of this supergene. The supergene
   * components may be supergenes itself
   */
  public Gene[] getGenes() {
    return m_genes;
  }

  /**
   * Returns the Gene at the given index (locus) within the Chromosome. The
   * first gene is at index zero and the last gene is at the index equal to
   * the size of this Chromosome - 1.
   *
   * This seems to be one of the bottlenecks, so it is declared final.
   * I cannot imagine the reason for overriding this trivial single line
   * method.
   *
   * @param a_desiredLocus the index of the gene value to be returned.
   * @return The Gene at the given index
   */
  public final Gene getGene(int a_index) {
    return m_genes[a_index];
  };

  /** Constructs abstract supergene with the given gene list.
   * @param a_genes array of genes for this Supergene
   */
  public abstractSupergene(Gene[] a_genes) {
    m_genes = a_genes;
  }

  /**
   * <b>Always provide the parameterless
   * constructor</b> for the derived class. This is required to
   * create a new instance of supergene and should be used inside
   * <code>newGene</code> only. The parameterless
   * constructor need not (and cannot) assign the private
   * <code>genes</code> array.
   */
  public abstractSupergene() {
  }

  /**
   * Test the allele combination of this supergene for validity.
   * This method calls isValid for the current gene list.
   * @return true only if the supergene allele combination is valid
   * or the setValidator (<i>null</i>) has been previously called
   */
  public boolean isValid() {
    if (m_validator == null) {
      return true;
    }
    else {
      return m_validator.isValid(m_genes, this);
    }
  }

  /**
   * Test the given gene list for validity. The genes must exactly the same
   * as inside this supergene.
   * At <i>least about 5 % of the randomly
   * generated Supergene suparallele values should be valid.</i> If the valid
   * combinations represents too small part of all possible combinations,
   * it can take too long to find the suitable mutation that does not brake
   * a supergene. If you face this problem, try to split the supergene into
   * several sub-supergenes.
   *
   * This method is only called if you have not set any alternative
   * validator (including <i>null</i>.
   *
   * </p>
   * @param a_case ignored here
   * @param a_forSupergene ignored here
   *
   * @return true only if the supergene allele combination is valid
   * @throws Error by default. If you do not set external validator,
   * you should always override this method
   */
  public boolean isValid(Gene[] a_case, Supergene a_forSupergene) {
    throw new Error("For " + getClass().getName() + ", override " +
                    " isValid (Gene[], Supergene) or set an"
                    +" external validator.");
  }

  /** Creates a new instance of this Supergene class with the same number of
   * genes, calling newGene() for each subgene. The class, derived from this
   * abstract supergene will be instantiated
   * (not the instance of abstractSupergene itself). If the external
   * validator is set, the same validator will be set for the new gene.
   * @throws Error if the instance of <i>this</i> cannot be instantiated
   * (for example, if it is not public or  the parameterless constructor is
   * not provided).
   * */
  public Gene newGene() {
    Gene[] g = new Gene[m_genes.length];
    for (int i = 0; i < m_genes.length; i++) {
      g[i] = m_genes[i].newGene();
    }
    try {
      abstractSupergene age =
          (abstractSupergene) getClass().newInstance();
      if (m_validator != this)
        age.setValidator(m_validator);
      age.m_genes = g;
      return age;
    }
    catch (Exception ex) {
      ex.printStackTrace();
      throw new Error("This should not happen. Is the parameterless " +
                      "constructor provided fo " + getClass().getName() + "?");
    }
  }

  /** Maximal number of retries for applyMutation and setToRandomValue.
   * If the valid supergen cannot be created after this number of iterations,
   * the error message is printed and the unchanged instance is returned. */
  public static int MAX_RETRIES = 1000;

  /**
   * Applies a mutation of a given intensity (percentage) onto the gene
   * at the given index. Retries while isValid() returns true for the
   * supergene. The method is delegated to the first element [0] of the
   * gene, indexed by <code>index</code>.
   * @see org.jgap.supergenes.abstractSupergene.isValid()
   */
  /**
   * Applies a mutation of a given intensity (percentage) onto the gene
   * at the given index. Retries while isValid() returns true for the
   * supergene. The method is delegated to the first element [0] of the
   * gene, indexed by <code>index</code>.
   * @see org.jgap.supergenes.abstractSupergene.isValid()
   */
  public void applyMutation(int index, double a_percentage) {
    // Return immediately the current value is found in
    // the list of immutable alleles for this position.
    // ---------------------------------------------------
    if (index < m_immutable.length) {
      if (m_immutable[index] != null) {
        synchronized (m_immutable) {
          if (m_immutable[index].contains(this))
            return;
        }
      }
    }
    if (!isValid()) {
      throw new Error("Should be valid on entry");
    }
    Object backup = m_genes[index].getAllele();
    for (int i = 0; i < MAX_RETRIES; i++) {
      m_genes[index].applyMutation(0, a_percentage);
      if (isValid())return;
    }
    // restore the gene as it was
    m_genes[index].setAllele(backup);
    markImmutable(index);
  }

  /** Maximal number of notes about immutable genes per
   * single gene position */
  public static int MAX_IMMUTABLE_GENES = 100000;

  /** @todo: Implement protection against overgrowing of this
   * data block.
   */
  private void markImmutable(int a_index) {
    synchronized (m_immutable) {
      if (m_immutable.length <= a_index) {
        // Extend the array (double length).
        // ---------------------------------
        Set[] r = new Set[2 * m_immutable.length];
        System.arraycopy(m_immutable, 0, r, 0, m_immutable.length);
        m_immutable = r;
      }
      if (m_immutable[a_index] == null) {
        m_immutable[a_index] = new TreeSet();
      }
      if (m_immutable[a_index].size() < MAX_IMMUTABLE_GENES) {
        m_immutable[a_index].add(this);
      }
    }
    ;
  }

  /** Set of supergene allele values that cannot mutate. */
  private static Set[] m_immutable = new Set[1];

  /**
   * Discards all internal caches, ensuring correct repetetive tests
   * of performance. Differently from cleanup(), discards also static
   * references, that are assumed to be useful for the multiple instances
   * of the Supergene.
   * Clears the set of the alleles that are known to be immutable.
   */
  public static void reset() {
    m_immutable = new Set[1];
  }

  /**
   * Sets the value of this Gene to a random legal value for the
   * implementation. It calls setToRandomValue for all subgenes and
   * then validates. With a large number of subgenes and low percent of
   * valid combinations this may take too long to complete. We think,
   * at lease several % of the all possible combintations must be valid.
   *
   * @throws an error if unable to get a valid random instance in
   * the number of loops, defined by MAX_RETRIES.
   */
  public void setToRandomValue(RandomGenerator a_numberGenerator) {
    /** set all to random value first */
    for (int i = 0; i < m_genes.length; i++) {
      m_genes[i].setToRandomValue(a_numberGenerator);
    }
    if (isValid())return;
    for (int i = 0; i < MAX_RETRIES; i++) {
      for (int j = 0; j < m_genes.length; j++) {
        // Mutate only one gene at time.
        // -----------------------------
        m_genes[j].setToRandomValue(a_numberGenerator);
        if (isValid()) {
          return;
        }
      }
    }
  }

  /**
   * Sets the allele.
   * @param that must be an array of objects, size matching the
   * number of genes
   */
  public void setAllele(Object a_superAllele) {
    Object[] a = (Object[]) a_superAllele;
    if (a.length != m_genes.length) {
      throw new
          ClassCastException("Record length, " + a.length + " != " +
                             m_genes.length);
    }
    for (int i = 0; i < m_genes.length; i++) {
      m_genes[i].setAllele(a[i]);
    }
  }

  /**
   * Retrieves the allele value represented by this Supergene.
   * @return array of objects, each matching the subgene in this Supergene
   */
  public Object getAllele() {
    Object[] o = new Object[m_genes.length];
    for (int i = 0; i < m_genes.length; i++) {
      o[i] = m_genes[i].getAllele();
    }
    return o;
  }

  /**
   * @return a string representation of the value of this Supergene
   * instance, using calls to the Supergene components. Supports other
   * (nested) supergenes in this supergene
   */
  public String getPersistentRepresentation()
      throws UnsupportedOperationException {
    StringBuffer b = new StringBuffer();
    // Write validator: