edgepreservingcycliccrossover.java

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

                  d.getCity(dIndex)
                )
              )
            )
            .getMatched()
          )
          {
            dv.add(new Integer(d.getCity(dIndex)));
            dUsed++;
            dIndex = ( dIndex + 1 ) % genomeLength;
          }

/*
** Okay, we dropped through, so we have a binful, do something useful
** with it -- put it into an array to be a bin.
*/

          int mTemp[] = new int[dv.size()];
          int dTemp[] = new int[dv.size()];
          for ( int i = 0; i < dTemp.length; i++ )
          {
            mTemp[i] = (int) ((Integer)dv.get(i)).intValue();
            dTemp[i] = (int) ((Integer)dv.get(i)).intValue();
          }

/*
** Hang the bins into our bin array; we only need one on the distaff
** side, since only the father bin list duplicate is needed to verify
** termination of our permutation cycle between the son and daughter
** bin arrays.
*/

          dBins[dBinCount] = dTemp;

          if (DB)
          {
            dbb
              .append
              (
                "\r\n"
                + Debugging.dump(dBins[dBinCount])
                + "/"
                + dBinCount
                + " next daughter bin found / dBinCount"
              );
          }

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

          dBinCount++;
        }
      }

/*
** Okay, we bail to here when both input genomes have been used up in
** the process of creating bins.  Put one bin list pair in general
** orientation, the other will be fine as is; for a cyclic crossover,
** that is "good enough".
*/

      int dOffset = mt.nextInt(dBinCount);
      int dStep   = mt.nextBoolean() ? 1 : -1;

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


/*
** Do a bin-wise cycle crossover.
** 
** Pick a random starting bin in the first sibling genome; this will be
** our first bin to copy down into the second sibling genome.
*/

      int sonIndex = mt.nextInt(sBinCount);

/*
** Copy the pointer to that bin into a temporary variable.
*/

      int tempBin[] = sBins[sonIndex];

/*
** Copy a pointer to this same starting bin, but in the (read-only)
** father bin list.  We will use this bin as part of our test for when
** the cycle is finished, which is when a bin with these same contents,
** though possibly in the opposite order, is moved from the second
** sibling back up into the first sibling, completing the cycle by
** restoring the permutation-genome precondition for the travelling
** salesman problem.
*/

      int fKeep[] = fBins[sonIndex];

      if (DB)
      {
        dbb
          .append
          (
            "\r\n"
            + sonIndex
            + "/"
            + dOffset
            + "/"
            + dStep
            + " fStart, dOffset/dStep in EPCXO"
          )
          .append
          (
            "\r\n"
            + Debugging.dump(sBins)
            + " son bins before crossover"
          )
          .append
          (
            "\r\n"
            + Debugging.dump(dBins)
            + " daughter bins before crossover"
          );
      }

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


/*
** POLICY We include (above) an offset and direction reversal for the
** mother to put one genome in general position, removing artifacts
** caused by using arrays instead of rings to hold permutation genomes,
** and by keeping genomes in canonical form for other reasons.
*/

      while (true)
      {

/*
** Figure out the bin which corresponds in the second sibling genome to
** our bin in the first sibling genome, taking into account that we have
** put the second sibling genome in general orientation (in fact, this
** statement is where we accomplish that generalization).
*/

        int dGPIndex =
          ( dOffset + ( dStep * sonIndex ) + 2 * dBinCount ) % dBinCount;

/*
** Continue our (pointer oriented) swap by replacing the pointer in the
** first sibling bin list slot with a pointer to the corresponding bin
** in the second sibling bin list.  This all works because arrays, our
** bins, have independent existence in Java's managed memory, and just
** moving pointers (references) to them suffices to hook them to their
** new locations.
*/

        sBins[sonIndex] = dBins[dGPIndex];

/*
** Finish the pointer oriented swap by copying the pointer from the temp
** variable to the second sibling genome's bin list slot.
*/

        dBins[dGPIndex] = tempBin;

        if (DB)
        {
          dbb
            .append
            (
              "\r\n"
              + Debugging.dump(sBins)
              + " son bins during crossover"
            )
            .append
            (
              "\r\n"
              + Debugging.dump(dBins)
              + " daughter bins during crossover"
            );
        }

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

/*
** Did we just move up the bin corresponding to the one we first moved
** down?  If so, we are done with the cycle.
** 
** To determine this, we check, does the beginning of the current bin
** match the beginning or end of the first bin we moved? They might have
** their codons in opposite orders, so we have to check both ends, but
** since codons are unique within a permutation genome, that also is a
** sufficient test to check for a match.
*/

        if
        (
          ( sBins[sonIndex][0] == fKeep[0])
          ||
          ( sBins[sonIndex][0] == fKeep[fKeep.length - 1] )
        )
        {
          break;  // This is how we get out of the "while (true)", above.
        }

/*
** If we get here, then we guess not, so we'd better go find the
** original of the bin we just copied up [we have to find the original,
** because right now there are _two_ of them in this genome, (which
** means that it is in an incosistent state), so checking here might
** find the wrong one, which is the whole reason for keeping a
** redundant, read-only copy of the bin list as "fBins"],  and cycle it
** down next, it is redundant where it sits.  Having no better recourse,
** we do a linear search of the read-only copy of the original first
** sibling bin list.
*/

        for ( int fatherIndex = 0; fatherIndex < sBinCount; fatherIndex++ )
        {
          if
          (
            ( fBins[fatherIndex][0] == sBins[sonIndex][0])
            ||
            (
              fBins[fatherIndex][0]
              ==
              sBins[sonIndex][sBins[sonIndex].length - 1]
            )
          )
          {

/*
** Okay, found it, so save the first sibling index, for use in computing
** the secnd sibling (daughter general position) index, and also start
** our bin pointer swaps again by saving the pointer to the current
** first sibling genome bin into our temp variable.
*/

            sonIndex = fatherIndex;
            tempBin = sBins[sonIndex];
            break;
          }
        }

      }

      if (DB)
      {
        dbb
          .append
          (
            "\r\n"
            + Debugging.dump(sBins)
            + " son bins after crossover"
          )
          .append
          (
            "\r\n"
            + Debugging.dump(dBins)
            + " daughter bins after crossover"
          );
      }

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

/*
** Flip bin substrings for better fitness here.  This is _not_, per se,
** a part of the edge preserving cyclic crossover, which up to now has
** been a _blind_ heuristic, ignoring detailed fitness considerations.
** Omit these two calls to perserve that characteristic.  What these
** calls accomplish is to led power to the heuristic, by trying the bins
** in a (large subset of) all possible orientations in each sibling
** genome, to (over-)compensate for the fact that our crossover may put
** bins (edge lists) back into the sibling genome in orientations
** opposite to the more fit ones.
*/

      flipBins( sBins, sBinCount, world, DB );
      flipBins( dBins, sBinCount, world, DB );

/*
** Okay, we've cycled the son and daughter bin lists, now to reconstruct
** some genomes from them.
*/
      binListToGenome( sBins, sBinCount, s, DB );
      binListToGenome( dBins, dBinCount, d, DB );

/*
** Convert the just built genomes to canonical form, so that we don't
** have to worry about order of evaluation roundoff artifacts when
** computing fitnesses.
*/

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

/*
** Figure out the genome fitnesses, so that we can pick a single most
** fit genome to present as our output.
*/

      double sf = s.testFitness();
      double df = d.testFitness();

      if (DB)
      {
        dbb
        .append
        (
          "\r\n"
          + s.toString()
          + " / "
          + sf
          + " canonical son after build from bins"
        )
        .append
        (
          "\r\n"
          + d.toString()
          + " / "
          + df
          + " canonical daughter after build from bins"
        );
      }

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

      if ( sf < df )
      {
        luckySprog = new TravellerChromosome( s );
      }
      else
      {
        luckySprog = new TravellerChromosome( d );
      }

    }
    else
    {
      if (DB)
      {
        dbb.append( "\r\n" + "matched all edges, cloning one parent" );
      }
      luckySprog = new TravellerChromosome( f );
    }

/*
** Canonicalize and calculate fitness for output genome, though both are
** normally a bit redundant; if created from one of teh siblings, the
** genome should already be in canonical form, and we know its fitness
** from the fitness of the propagated sibling.
*/

    luckySprog.canonicalize();

    double lsf = luckySprog.testFitness();

/*
** Do a complicated set of checks for debugging, so that our debugging
** trace accurately represents our degree of success.
*/

    if (DB)
    {
      if
      (
        ( ( m.looksLikeMe( luckySprog ) || f.looksLikeMe( luckySprog) ) )
      )
      {
        dbb.append
        (
          "\r\n"
          + "offspring replicates one parent"
        );
      }
      else if
      (
        (
          lsf > f.testFitness()
          &&
          lsf > m.testFitness()
        )
      )
      {
        dbb.append
        (
          "\r\n"
          + "offspring changed, is worse-fit than both parents"
        );
      }
      else if
      (
        (
          lsf < f.testFitness()
          &&
          lsf < m.testFitness()
        )
      )
      {
        dbb.append
        (
          "\r\n"
          + "offspring changed, is better-fit than both parents"
        );
      }
      else if
      (
        (
          lsf == f.testFitness()
          ||
          lsf == m.testFitness()
        )
      )
      {
        dbb.append
        (
          "\r\n"
          + "offspring changed, is equally-fit to at least one parent"
        );
      }
      else if
      (
        (
          lsf > f.testFitness()
          &&
          lsf < m.testFitness()
        )
        ||
        (
          lsf < f.testFitness()
          &&
          lsf > m.testFitness()
        )
      )
      {
        dbb.append
        (
          "\r\n"
          + "offspring changed, has fitness intermediate between parents"
        );
      }
      else
      {
        dbb.append
        (
          "\r\n"
          + "offspring changed, had other outcome"
        );
      }
      System.out.println( dbb.toString() );
      System.out.println( f.testFitness() + " father in EPCXO " );
      System.out.println( m.testFitness() + " mother in EPCXO" );
      System.out.println( lsf + " luckySprog  in EPCXO" );
      System.out.println();
    }

    if (VDB) { m_vdb.step( luckySprog ); }

    if (VDB) { m_vdb.done( f, m, luckySprog ); }

    return luckySprog;

  }

  private int matchEdgesAndMarkMatches
  (
    TravellerChromosome s,
    TravellerChromosome d,
    EdgeList            sel,
    EdgeList            del,
    EdgeList            selSorted,
    EdgeList            delSorted,
    boolean             sMarks[],
    boolean             dMarks[],
    Edge                el[],
    boolean             DB
  )
  {

      StringBuffer dbb          = new StringBuffer();
      int          matchesCount = 0;
      int          si           = 0;
      int          di           = 0;
      int          genomeLength = ValuatorControls.getNumberOfCities();

      for ( int i = 0; i < genomeLength; i++ )
      {
        sMarks[i] = false;
        dMarks[i] = false;
        el[i]     = null;
      }

      while (true)
      {
        if
        (
          Sortable.THIS_EQUAL_TO
          ==
          selSorted.getEdge(si).compareTo(delSorted.getEdge(di))
        )
        {
          el[matchesCount] = (Edge) selSorted.getEdge(si).cloneThis();
          matchesCount++;

/*
** Flag matched edges as matched in orginal-ordering edge lists and
** per-Codon boolean arrays.
** 
** This is fairly complicated to make work correctly.  It is possible
** for consecutive codons in one genome to be flagged as participating
** in matched edges, and yet, in the other genome, for those same codons
** to be in matched edges which are not adjacent, so both matched edges,
** and codons in matched edges, must be both flagged when found and also
** both checked later, to discover when a string of codons in matched
** edges are part of a string of matched edges which constitute a
** matched substring of edges/codons in both genomes, in which case we
** want them put into a single bin, as opposed to accidentally adjacent
** edges not adjacent in the other genome, in which case they belong in
** separate bins.
*/

          int matchInSel =  sel.findEdge( selSorted.getEdge(si) );
          if ( matchInSel != -1 )
          {
            sel.setEdge
            (
              matchInSel,
              new Edge( sel.getEdge(matchInSel), true )
            );
          }

          int matchInDel =  del.findEdge( delSorted.getEdge(di) );
          if ( matchInDel != -1 )
          {
            del.setEdge
            (
              matchInDel,
              new Edge( del.getEdge(matchInDel), true )
            );
          }

/*
** Mark codons on both ends of the edge as participating in a matched edge.
*/

          sMarks[s.findCity( selSorted.getEdge(si).getStart().get() ) ] = true;
          sMarks[s.findCity( selSorted.getEdge(si).getEnd()  .get() ) ] = true;
          dMarks[d.findCity( delSorted.getEdge(di).getStart().get() ) ] = true;
          dMarks[d.findCity( delSorted.getEdge(di).getEnd()  .get() ) ] = true;

/*
** Since we found a match, we want to advance both edge indices, because
** neither could possibly participate in a different match.  If either
** won't advance, we have walked off the end of at least one genome, and
** so are done.
*/

          if ( si < ( genomeLength - 1 ) ) { si++; } else { break; }
          if ( di < ( genomeLength - 1 ) ) { di++; } else { break; }

        }
        else
        {
          if
          (
            Sortable.THIS_LESS_THAN
            ==
            selSorted.getEdge(si).compareTo(delSorted.getEdge(di))
          )
          {
            if ( si < ( genomeLength - 1 ) ) { si++; } else { break; }
          }
          else
          {
            if
            (
              Sortable.THIS_LESS_THAN
              ==
              delSorted.getEdge(di).compareTo(selSorted.getEdge(si))
            )
            {
              if ( di < ( genomeLength - 1 ) ) { di++; } else { break; }
            }
            else
            {

/*
** Drop-through to here should never happen. FIXME Complain if it does. 
*/

              break;
            }
          }