rollingcrossover.java

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

    int motherCurrentCity =
      m.getCity( motherOffset + ( motherStep * genomeIndex ) );

    blendedSprog.setCity( 0, fatherCurrentCity );
    fatherEncounters[ fatherCurrentCity ] = true;
    motherEncounters[ motherCurrentCity ] = true;

    genomeIndex++;

    while ( genomeIndex < genomeLength )
    {

      int fatherPreviousCity = fatherCurrentCity;
      int motherPreviousCity = motherCurrentCity;

      fatherCurrentCity =
        f.getCity( fatherOffset + ( fatherStep * genomeIndex ) );
      motherCurrentCity =
        m.getCity( motherOffset + ( motherStep * genomeIndex ) );

      if ( fatherCurrentCity != motherCurrentCity )
      {
        if ( motherEncounters[ fatherCurrentCity ] )
        {
          mismatchCount--;
        }
        else
        {
          mismatchCount++;
        }

        if ( fatherEncounters[ motherCurrentCity ] )
        {
          mismatchCount--;
        }
        else
        {
          mismatchCount++;
        }
      }

      fatherEncounters[ fatherCurrentCity ] = true;
      motherEncounters[ motherCurrentCity ] = true;

      fatherFitnessIncrement +=
        world.getDistance( fatherPreviousCity, fatherCurrentCity );

      motherFitnessIncrement +=
        world.getDistance( motherPreviousCity, motherCurrentCity );

      if ( ( genomeIndex + 1 ) == genomeLength )
      {

/*
** The "getCity( 0 )" is redundant here, we know this is city zero, but
** doing it this way allows for a new city naming scheme to be slid into
** place without breaking this code, or at least quite as severely so.
** FIXME A better, less fragile design would have getDistance() take a
** Codon pair instead of an int pair, and similarly for many, many other
** cases where city names are used in Traveller.
*/

        fatherFitnessIncrement +=
          world.getDistance( fatherCurrentCity, f.getCity( fatherOffset ) );

        motherFitnessIncrement +=
          world.getDistance( motherCurrentCity, m.getCity( motherOffset ) );

      }

      if ( mismatchCount == 0 )
      {
        TravellerChromosome currentSourceGenome = null;
        int currentSourceOffset = 0;
        int currentSourceStep   = 0;

        if ( fatherFitnessIncrement < motherFitnessIncrement )
        {
          currentSourceGenome = f;
          currentSourceOffset = fatherOffset;
          currentSourceStep   = fatherStep;

/*
** Whomever wins, the other must carry on as if that were his or her
** last city!
*/

          motherCurrentCity = fatherCurrentCity;

          if (DB)
          {
            dbb
            .append
            (
              "\r\n"
              + "fFI/mFI: "
              + fatherFitnessIncrement
              + "/"
              + motherFitnessIncrement
              + " father wins! At benchmark point "
              + genomeIndex
            );
          }

        }
        else
        {
          currentSourceGenome = m;
          currentSourceOffset = motherOffset;
          currentSourceStep   = motherStep;

/*
** Whomever wins, the other must carry on as if that were his or her
** last city!
*/

          fatherCurrentCity = motherCurrentCity;

          if (DB)
          {
            dbb.append
            (
              "\r\n"
              + "fFI/mFI: "
              + fatherFitnessIncrement
              + "/"
              + motherFitnessIncrement
              + " mother wins! At benchmark point "
              + genomeIndex
            );
          }

        }

/*
** Copy the more fit Codon substring from the winning parent to the
** offspring.  We already copied the Codon at the last match point,
** either initially or as the last Codon of the previous substring copy,
** so copy on from the next Codon.
*/

        for ( int j = ( lastMatchPoint + 1 ); j <= genomeIndex; j++ )
        {
          blendedSprog.setCity
          (
            j,
            currentSourceGenome.getCity
            (
              currentSourceOffset + ( currentSourceStep * j )
            )
          );
          copiedUpto = j;
        }

        if (DB)
        {
          dbb.append
          ( "\r\n" + blendedSprog.toString() + " bS in RXO" );
        }

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

/*
** Reset the gates and race again.
*/

        lastMatchPoint = genomeIndex;
        fatherFitnessIncrement = 0.0D;
        motherFitnessIncrement = 0.0D;

      }

      genomeIndex++;
    }

/*
** Check our work.
*/

    if ( mismatchCount != 0 )
    {
      System.out.println
      (
        "mismatch counting failed in Rolling Crossover: "
        + mismatchCount
      );
    }

    if ( copiedUpto !=  ( genomeLength - 1 ) )
    {
      System.out.println
      (
        "copying whole genome failed in Rolling Crossover: "
        + copiedUpto
        + "; "
        + blendedSprog.toString()
      );
    }

    blendedSprog.canonicalize();
    double bsf = blendedSprog.testFitness();

/*
** [Very successful change added in Traveller release "epsilon".]
** Prevent catastrophic population diversity collapse.  If the offspring
** is identical to the genome selected biased on fitness (the secondary
** parent genome), return instead the genome selected sequentially from
** the population (the primary parent genome).  While the secondary
** parent genome in this case is the more fit one, it contributes no new
** partial solutions to the population, and letting it replace the
** primary parent genome removes from the population any partial
** solutions the primary parent genome might have that didn't get
** captured by this heuristic into a child genome, a negative result
** overall despite the ephemeral improvement in average population
** fitness.
*/

    if ( m.looksLikeMe( blendedSprog ) )
    {
      blendedSprog = new TravellerChromosome( f );
    }

/*
** Feed the new kid back into the population in the standard manner.
*/

    if (DB)
    {
      dbb.append
      ( "\r\n" + blendedSprog.toString() + " final bS in RXO" );
    }

    if
    (

/*
** This printout was used to help me understand why I wasn't always
** getting back improved solutions more fit than _both_ parents when any
** change at all was made.  The reason, once seen, was blindingly
** obvious, the kind that makes you want to kick yourself.  Joining an
** internally very fit segment from one genome to an internally very fit
** segment from the other genome may very well improve fitness overall,
** but lose part of its gains at the point where the two segments join,
** and thus not end up as fit as the more fit genome, while still
** succeeding in rolling crossover's primary goal of combining excellent
** edge sequences from both genomes into one genome.  Fixing up the
** lossage at the joins can then be deferred to other heuristics.
*/

      DB
      &&
      ( !( m.looksLikeMe( blendedSprog ) || f.looksLikeMe( blendedSprog) ) )
      &&
      (
        bsf > f.testFitness()
        ||
        bsf > m.testFitness()
      )
    )
    {
      System.out.println( dbb.toString() );
      System.out.println( f.testFitness() + " father in RXO " );
      System.out.println( m.testFitness() + " mother in RXO" );
      System.out.println( bsf + " blendedSprog  in RXO" );
      System.out.println();
    }

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

    return blendedSprog;
  }

}

/*
** The original design for this heuristic, from my "to do" list.
** 
** Create a "rolling join" crossover.  Put two genomes in canonical
** form, and associate a boolean "encountered" array with each, marking
** cities in the genome which have been encountered in each in the
** process of marching along the genome.  Starting at the beginning,
** mark cities encountered in each, incrementing a mismatch counter for
** each city encounterd that matches a city not marked encountered in
** the other encountered array, and decrementing the mismatch counter
** each time a city is encountered that matches one already encountered
** in the other genome.  Keep a rolling fitness increment while
** progressing, for each genome.  Whenever the mismatches count falls to
** zero, benchmark the fitness increments to that point.  Check which
** genome since the last benchmark point has been more fit, and copy the
** intervening sublist to a child genome.  At the end of the march, of
** necessity the mismatch counter will have fallen to zero, and the
** child genome will be comprised of the superior parts between
** benchmark points of either parent genome.  In the case that one
** parent is superior at all benchmark points, or the mismatch counters
** never fall to zero until the end, the child will just be a clone of
** one parent, which is fine.  This should be simple to implement, with
** time complexity of order N, which is very nice, and behave like
** inver-over in consolidating gains made across the population into
** compromise genomes.
*/