edgepreservingcycliccrossover.java

经典的货郎担问题解决办法

/*
** 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.
*/

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

import java.util.*;

import com.coyotegulch.tools.*;
import com.coyotegulch.genetic.*;

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

public class EdgePreservingCyclicCrossover
    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 EdgePreservingCyclicCrossover.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( "EdgePreservingCyclicCrossover" );
        child.checkValidity();
        return child;
      }
      else
      {
        throw m_errIncompatible;
      }

    }
    catch (Exception e)
    {
      System.err.println
      (
        "EdgePreservingCyclicCrossover.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( "EdgePreservingCyclicCrossover" );
      }
    }
    else
    {
      if ( m_vdb != null )
      {
        m_vdb.closeWindow();
        m_vdb = null;
      }
    }

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

/*
** 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();

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

    MersenneTwister mt    = MersenneTwister.getTwister();

/*
** We like to keep the genomes in some known order, so assure that they
** are there (this is cheap enough to do, since it is just a couple of
** comparisons if the genome is already in canonical order, which is:
** the genome ring rotated if necessary to put the minimun named codon
** (city zero) in array slot zero, and the genome ring is reversed if
** needed so that the smaller numbered neighbor of codon zero is in
** array slot one, and thus the larger numbered neighbor of codon zero
** is in the last array slot.  Since the "tour" which we are trying to
** minimize is invariant in fitness and contained edges, with respect to
** genome ring rotation or reversal, this canonical form is equivalent
** to the general form in which the genome might be left by various
** heuristics or other operations.
*/

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

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

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

    int genomeLength = ValuatorControls.getNumberOfCities();

/*
** Arbitrarily copy each parent just to make the skeleton of a genome, we
** will completely replace the contents of the copy.  Because we are
** doing a cyclic crossover, we need two such places to work
*/

    TravellerChromosome s = new TravellerChromosome(f);
    TravellerChromosome d = new TravellerChromosome(m);

    TravellerWorld world = f.getWorld();

/*
** Do an edge preserving cyclic  crossover.
*/

/*
** Put input genomes in canonical order so that edgelists to be created
** will have some expected ordering.
*/

    s.canonicalize();
    d.canonicalize();

    if (DB)
    {
      dbb
        .append( "\r\n" + s.toString() + " son in EPCXO")
        .append( "\r\n" + d.toString() + " daughter in EPCXO");
    }

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

/*
** We need two edgelists in original order, from which to create our bin
** contents, later, and two edgelists in sorted order, with which to
** detect matching edges between the two genomes.  Create all four.
*/

    EdgeList sel = null;
    EdgeList del = null;
    try
    {
      sel = new EdgeList( s );
      del = new EdgeList( d );
    }
    catch (Exception e)
    {
      System.out.println( "EPCXO caught from EdgeList constructors" );
    }
    finally
    {
      // System.out.println( "EPCXO EdgeList constructors ran" );
    }

    if (DB)
    {
      dbb
        .append( "\r\n" + sel.toString() + " sel edgelist" )
        .append( "\r\n" + del.toString() + " del edgelist" );
    }

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

/*
** Notice that we are using our edgelist cloning constructor, rather
** than the one that builds directly from a genome, here (for no
** particular reason).
** 
** Create the edgelists to be sorted.
*/

    EdgeList selSorted = new EdgeList( sel );
    EdgeList delSorted = new EdgeList( del );

    if (DB)
    {
      dbb
        .append
        ( "\r\n" + selSorted.toString() + "selSorted edgelist pre-sort" )
        .append
        ( "\r\n" + delSorted.toString() + "delSorted edgelist pre-sort" );
    }

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

/*
** Sorting edge lists is complex enough to be abstracted as an EdgeList
** class service, so sort them using that service.
*/

    selSorted.sort();
    delSorted.sort();

    if (DB)
    {
      dbb
        .append
        ( "\r\n" + selSorted.toString() + "selSorted edgelist post-sort" )
        .append
        ( "\r\n" + delSorted.toString() + "delSorted edgelist post-sort" );
    }

    if (DB)
    {
      System.out.println( dbb.toString() );
      System.out.println();
      dbb = new StringBuffer();
    }

/*
** Find and tag all matched edges between the two input genomes.  Record
** the matched edges in an auxiliary matched edges list, in case that
** proves useful later (it is, but only for debugging output.  Notice
** that by definition, we are creating that list in edge-sorted order,
** since we are walking the two sorted edge lists.
*/

    boolean sMarks[] = new boolean[genomeLength];
    boolean dMarks[] = new boolean[genomeLength];
    Edge el[]        = new Edge[genomeLength];

    int matchesCount =
      matchEdgesAndMarkMatches
      (
        s,
        d,
        sel,
        del,
        selSorted,
        delSorted,
        sMarks,
        dMarks,
        el,
        DB
      );

/*
** Build the binned edges structures we want to use in our cyclic crossover.
*/

    int fBins[][] = new int[genomeLength][];
    int sBins[][] = new int[genomeLength][];
    int dBins[][] = new int[genomeLength][];
    int sIndex = 0;
    int dIndex = 0;
    int sUsed = 0;
    int dUsed = 0;
    int sBinCount = 0;
    int dBinCount = 0;

/*
** It is easy to create bins once we get started, but how do we get
** started at the beginning of a bin-contents worth of codons?  Probably
** we are in good shape so long as it is not the case that every edge
** matched!  In that latter case, we might as well do nothing and just
** return one of the identical genomes as our answer, this heuristic has
** nothing to contribute to the overall problem solution when fed
** identical parent genomes.
*/

    TravellerChromosome luckySprog = null;

    if ( matchesCount < genomeLength )
    {

/*
** If we got this far, these two searches _must_ be able to succeed
** without walking off the respective genomes [but check anyway].
** 
** Sigh.  How seductive wrong answers are.  This doesn't work, in
** general.  It is quite possible to have an unmatched edge without ever
** having a Codon which isn't part of at least one matched edge.  Think
** of two cloned strings in which a substring of one is then inverted.
** That leaves two edges that don't match in each, but zero codons in
** each that are not part of some matched edge.  Rats, the other way of
** finding the starting point I want is much harder to code correctly
** because of the levels of indirection involved.
** 
**   while ( sMarks[sIndex] && ( sIndex < genomeLength) ) { sIndex++; }
** 
**   while ( dMarks[dIndex] && ( dIndex < genomeLength) ) { dIndex++; }
*/

/*
** Find an _edge_ which is not matched.  Its slot index is the slot of
** its _second_ codon, in the order in which we walk the genome.  We can
** start building our first bin with this second codon.  It may be a
** codon at the beginning of a chain of matched edges, or a codon not
** part of any matched edge, but it is _not_ a codon in the midst of a
** pair of matched edges, so it is a safe place to begin build a bin.
*/

      while
      (
        ( sel.getEdge(sIndex) ).getMatched()
        &&
        ( sIndex < genomeLength)
      )
      {
        sIndex++;
      }

      while
      (
        ( del.getEdge(dIndex) ).getMatched()
        &&
        ( dIndex < genomeLength)
      )
      {
        dIndex++;
      }

      if ( ( sIndex >= genomeLength ) || ( dIndex >= genomeLength ) )
      {
        System.out.println
        (
          "TravellerEdgePreservingCyclicCrossover unexpectedly walked sIndex or"
          + "\r\n"
          + "dIndex off the end of sMarks or dMarks when looking for a first"
          + "\r\n"
          + "unmarked codon not participating in a matched edge.  Bailing."
          + "\r\n"
          + s.toString()
          + " son genome"
          + "\r\n"
          + d.toString()
          + " daughter genome"
          + "\r\n"
          + Debugging.dump(sMarks)
          + " sMarks after matching markups"
          + "\r\n"
          + Debugging.dump(dMarks)
          + " dMarks after matching markups"
        );
        System.exit(1);
      }

      if (DB)
      {
        dbb
          .append
          (
            "\r\n"
            + sIndex
            + " index of first son codon after an unmatched edge"
          )
          .append
          (
            "\r\n"
            + dIndex
            + " index of first daughter codon after an unmatched edge"
          )
          ;
      }

      if (DB)
      {
        System.out.println( dbb.toString() );
        System.out.println();
        dbb = new StringBuffer();
      }

/*
** Okay, we have a starting point, _now_ we can build a first, and then
** subsequent, bins.
*/

      while ( true )
      {
        if ( ( sUsed == genomeLength ) && ( dUsed == genomeLength ) )
        {
          break;
        }

        if ( sUsed < genomeLength )
        {
          Vector sv = new Vector();
          sv.add(new Integer(s.getCity(sIndex)));
          sUsed++;
          sIndex = ( sIndex + 1 ) % genomeLength;

/*
** Continue copying so long as the just copied codon was part of a
** matched edge composed of it and its successor codon; this is the
** complicated, hard to get right part discussed earlier.
*/

          while
          (

            // while ...
            // the previous codon/node/city was marked as one end
            // of some matched edge ...
            sMarks[ ( sIndex - 1 + genomeLength ) % genomeLength ]
            // and ...
            &&
            // the current codon/node/city is marked as one end of
            // some matched edge ...
            sMarks[ sIndex ]
            // and ...
            &&

/*
** This check should be redundant, but it prevents a null pointer
** dereference so do it anyway.
*/

            // the edge between them exists (of course it does, we
            // just found it) ...
            (
              sel.findEdge
              (
                new Edge
                (
                  s.getCity( ( sIndex - 1 + genomeLength ) % genomeLength ),
                  s.getCity( sIndex )
                )
              )
              !=
              -1
            )
            // and ...
            &&
            // the edge between them is actually marked as a matched edge
            // (they weren't ends of other matched edges with their other
            // adjacent codons/nodes/cities but the edge that _they_ form
            // was _not_ a matched edge) ...
            sel.getEdge
            (
              sel.findEdge
              (
                new Edge
                (
                  s.getCity( ( sIndex - 1 + genomeLength ) % genomeLength ),
                  s.getCity( sIndex )
                )
              )
            )
            .getMatched()
          )
          // then do wonderful stuff.
          {
            sv.add(new Integer(s.getCity(sIndex)));
            sUsed++;
            sIndex = ( sIndex + 1 ) % genomeLength;
          }

/*
** Okay, we dropped through, so we have a binful, do something useful
** with it -- put it into an array, and also into a duplicate copy
** array.
*/

          int fTemp[] = new int[sv.size()];
          int sTemp[] = new int[sv.size()];
          for ( int i = 0; i < sTemp.length; i++ )
          {
            fTemp[i] = (int) ((Integer)sv.get(i)).intValue();
            sTemp[i] = (int) ((Integer)sv.get(i)).intValue();
          }

/*
** Hang the duplicate bins into our duplicate bin arrays.
*/

          fBins[sBinCount] = fTemp;
          sBins[sBinCount] = sTemp;

          if (DB)
          {
            dbb
              .append
              (
                "\r\n"
                + Debugging.dump(sBins[sBinCount])
                + "/"
                + sBinCount
                + " next son bin found / sBinCount"
              );
          }

          if (DB)
          {
            System.out.println( dbb.toString() );
            System.out.println();
            dbb = new StringBuffer();
          }

          sBinCount++;
        }

        if ( dUsed < genomeLength )
        {
          Vector dv = new Vector();
          dv.add(new Integer(d.getCity(dIndex)));
          dUsed++;
          dIndex = ( dIndex + 1 ) % genomeLength;

/*
** Continue copying so long as the just copied codon was part of a
** matched edge composed of it and its successor codon.  See detailed
** comments above in the sibling actions.
*/

          while
          (
            dMarks[ ( dIndex - 1 + genomeLength ) % genomeLength ]
            &&
            dMarks[ dIndex ]
            &&
            (
              del.findEdge
              (
                new Edge
                (
                  d.getCity( ( dIndex - 1 + genomeLength ) % genomeLength ),
                  d.getCity( dIndex )
                )
              )
              !=
              -1
            )
            &&
            del.getEdge
            (
              del.findEdge
              (
                new Edge
                (
                  d.getCity( ( dIndex - 1 + genomeLength ) % genomeLength),