rollingcrossover.java

来自「经典的货郎担问题解决办法」· Java 代码 · 共 603 行 · 第 1/2 页

/*
** This code was written from scratch by Kent Paul Dolan, and may
** represent an algorithm which is a "new invention".  See accompanying
** file TravellerDoc.html for status for your use.
*/

/*
** Motivation: unlike the partial match, cyclic, or ordered crossovers,
** which are _blind_ to possible improvements until the overall genome
** fitness is computed, this rolling crossover attempts to do an
** intelligent crossover.  Wherever it can match subsequences of the
** parent genomes whose crossing over would preserve the "permutation
** genome" character of the traveling salesman tour, it choses for the
** child genome the subsequence of the two offered by parent genomes
** which would extend the partially built child genome with the better
** incremental fitness.  This will never produce a genome worse-fit than
** both parents, it may produce a genome with fitness intermediate
** between the fitnesses of the parents and therefore suitable to
** replace the worse-fit parent, or it may, and often does, produce a
** genome with fitness superior to both parents.
** 
** The impulse for this design was noticing how often new, more fit
** genomes reintroduced old, less fit subsequences, and a resulting goal
** to combine as far as possible superior subsequences of genomes into
** new genomes containing multiple simultaneous improvements, to hasten
** the spread of superior subsequences through the genome population.
** 
** Because this technique depends on there being matchable subsequences
** of genomes containing the same total set of codons, of length less
** than the total length of the genome, it is expected that this
** heuristic will exhibit superior improvement power in a population
** most of whose genomes are fairly well organized already.  Rolling
** crossover is thus a helper, not a wonderfully useful final solution
** run on its own, or with only mutation to assist it.
*/

package com.well.www.user.xanthian.java.genetic.reproducers.sexual;

import com.coyotegulch.genetic.*;
import com.well.www.user.xanthian.java.genetic.*;
import com.well.www.user.xanthian.java.tools.*;
import com.well.www.user.xanthian.java.ui.*;

public class RollingCrossover
    implements SexualReproducer
{

  private static boolean DB = false;
  private static boolean VDB = false;
  private static VisualDebugger m_vdb = null;

  public Chromosome reproduce(Chromosome father, Chromosome mother)
  {

    try
    {

/*
** Debugging hook abbreviation.  During development, turn on debugging
** just for this class by setting this variable to true, here.  When the
** code is stable, set it to false here, and control debugging from the
** checkbox controls panel, instead.  This variable is global to this
** class, so it controls debugging thoughout the class when set here at
** the top of the entry method for the class.
*/

      DB = false;

      if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
      {
        DB = true;
        System.out.println
        (
          "Entering RollingCrossover.reproduce()"
        );
      }

      if
      (
        (father instanceof TravellerChromosome)
        &&
        (mother instanceof TravellerChromosome)
      )
      {

/*
** Give local names with extended types to the two parent genome handles
** passed in as parameters of unextended types.
*/

        TravellerChromosome f = (TravellerChromosome)father;
        TravellerChromosome m = (TravellerChromosome)mother;

        Chromosome child = (Chromosome) algorithm( f, m );

        child.setOriginator( "RollingCrossover" );
        child.checkValidity();
        return child;
      }
      else
      {
        throw m_errIncompatible;
      }

    }
    catch (Exception e)
    {
      System.err.println
      (
        "RollingCrossover.reproduce() threw!"
      );
    }

/*
** This code should never be reached, it is just here to pacify javac
** about the return statement being stuck in a try context above.
*/

    return father; 
  }

  private TravellerChromosome algorithm
  (
    TravellerChromosome f,
    TravellerChromosome m
  )
  {

    VDB = false;
    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_VISUAL_WINDOWS))
    {
      VDB = true;
    }

    if (VDB)
    {
      if ( m_vdb == null )
      {
        m_vdb = new VisualDebugger( "RollingCrossover" );
      }
    }
    else
    {
      if ( m_vdb != null )
      {
        m_vdb.closeWindow();
        m_vdb = null;
      }
    }

    if (VDB) { m_vdb.toFront(); }

/*
** I thought at first that this technique would always produce a genome
** superior to both the parents, but that is not the case.  It very
** frequently does, but sometimes the genome produced is of a fitness
** intermediate between that of the parents.  The problem is where the
** copied segments join, that one parent may have to carry on from the
** end of a segment copied from the other parent, at a cost of reduced
** fitness at the juncture.  Nevertheless, the fitness produced is never
** larger than both parents, is most of the time a big win, and the
** genome produced always contains segments of superior fitness from the
** parents when possible, even when the overall fitness may not be the
** best of the three, so it does its job of blending better ideas from
** parent genomes.
*/

/*
** Make a place to store potentially useful debugging text until we find
** out if it is in fact worth writing to the output file handle.
*/

    StringBuffer dbb = new StringBuffer();

    if (DB)
    {
      dbb
        .append( "\r\n" + f.toString() + " father in RXO")
        .append( "\r\n" + m.toString() + " mother in RXO");
    }

/*
** Hook a handle to the soliton randomizer instance.
*/

    MersenneTwister mt    = MersenneTwister.getTwister();

/*
** POLICY Walk the genomes matched in general orientation, with just the
** limitation that we start at a matched codon.
*/

    f.canonicalize();
    m.canonicalize();
    if (VDB) { m_vdb.setup( f, m ); }


    int genomeLength = ValuatorControls.getNumberOfCities();

/*
** Pick a random starting place in one parent, a starting place at the
** matching city in the other parent.
*/

    int fatherOffset = mt.nextInt(genomeLength);
    int motherOffset = m.findCity( f.getCity( fatherOffset ) );

/*
** We want to walk in the direction of the "smaller in numerical value"
** city adjacent to each parent's starting city, to somewhat improve the
** odds that we are proceeding in a compatible direction between the two
** parents.
*/

    int fatherStep   = 1;
    int motherStep   = 1;

    if
    (
      f.getCity(fatherOffset - 1) < f.getCity(fatherOffset + 1)
    )
    {
      fatherStep = -1;
    }

    if
    (
      m.getCity(motherOffset - 1) < m.getCity(motherOffset + 1)
    )
    {
      motherStep = -1;
    }

/*
** Okay, we are ready to do this crossover in general position, now to
** fix all the calculations that follow to reflect that desire.
*/

/*
** Arbitrarily copy one parent just to make the skeleton of a genome, we
** will completely replace the contents of the copy.
*/

    TravellerChromosome blendedSprog = ( TravellerChromosome) m.cloneThis();

/*
** Copy the parent from the starting offset point and in the chosen
** travel direction so that visual debugger display will make sense
** (what a shame, it was prettier with the Blind Stupid Johnson thinko
** bug in place, it actually "rolled" on the screen).
*/

    for ( int i = 0; i < genomeLength; i++ )
    {
    //  blendedSprog.setCity( i, m.getCity( motherOffset + ( i * motherStep ) ) );
      // OK, do it wrong, it's more fun.
      blendedSprog.setCity( i, f.getCity( fatherOffset ) );
    }

/*
** Fill offspring with invalid city markers when debugging.
*/

    if (DB)
    {
      for ( int i = 0; i < genomeLength; i++ )
      {
        blendedSprog.setCity( i, -1 );
      }
    }

    TravellerWorld world = blendedSprog.getWorld();

/*
** Do a rolling crossover.
*/

    boolean fatherEncounters[] = new boolean[ genomeLength ];
    boolean motherEncounters[] = new boolean[ genomeLength ];

    for ( int i = 0; i < genomeLength; i++ )
    {
      fatherEncounters[i] = false;
      motherEncounters[i] = false;
    }

    double fatherFitnessIncrement = 0.0D;
    double motherFitnessIncrement = 0.0D;

    int mismatchCount = 0;
    int lastMatchPoint = 0;
    int genomeIndex = 0;

/*
** Start by seeding in the first city.
*/

    int copiedUpto = 0;

    int fatherCurrentCity =
      f.getCity( fatherOffset + ( fatherStep * genomeIndex ) );