population.java

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

  public Chromosome nextGeneration() throws Exception
  {

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "Entered Population.nextGeneration()"
      );
    }

/*
** KPD Modified Scott's single elitism to improve the entire population,
** instead of focusing only on a single elite member.  This is a pretty
** ugly and simple minded improvement, but I'd only read about 1% of the
** applet code when I did it, since the poor performance due to throwing
** away almost all improved genomes each generation was the single most
** annoying misfeature of the original applet.  Now, instead of just
** carrying forward the best genome of the prior generation, slots in
** the population vector are all competitive, and a new genome must beat
** out the previous genome at the same index/slot to be part of the new
** population, otherwise the old genome at the index/slot is copied
** forward instead.
** 
** A better implementation of the same idea would hold a tournament to
** select the member to be replaced, worst of some "m" samples, and
** implement continuous evolution instead of generations, perhaps still
** counting generations each time a population size of replacement
** attempts occurred.
** 
** It is yet to be decided whether mutation should occur before or after
** the replacement/copy-forward decision is made.  Right now it occurs
** before, but that may crush population diversity too thoroughly; the
** last half of a run seems to be being made with a very homogeneous
** population based on the limited amount of visible change per improved
** new elite genome.
** 
** With these changes, the applet is now easily capable of solving
** cities=100, pop=250, mutation=1% in a handful of minutes, and
** cities=250, pop=500, mutation=1% took less than 30 minutes, in both
** cases using the circular layout so that visual feedback and the known
** final length of the path made convergence on a perfect solution
** obvious.
*/

/*
**  Create a place to duplicate the best chromosome, so we can return a
**  copy to the caller which is unattached to the population.
*/

    Chromosome result = null;

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "in Population.nextGeneration(), about to create a new population"
      );
    }

    // create a new population
    Chromosome [] new_pop = new Chromosome [m_population.length];

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "in Population.nextGeneration(), doing single elitism"
      );
    }

/*
** Copy the best genome found in the evaluateGenomes() method, into the
** new population [at the same slot, for simplicity], if we are doing
** single elitism.
*/

    if
    (
      CheckBoxControls.getState
      (
        CheckBoxControls.CBC_METAHEURISTIC_SINGLE_ELITISM
      )
    )
    {
       new_pop[m_bestGenomeIndex] = m_population[m_bestGenomeIndex].cloneThis();
    }

/*
** Fill remainder of new population by reproduction & mutation
*/


    Chromosome c = null;

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "in Population.nextGeneration(), "
        + "looping to create new pop by reproduction"
      );
    }

    for (int i = 0; i < m_population.length;)
    {

      updateProgressDisplay
      (
        "产生第"
        + i
        + " 个到第 "
        + ( m_population.length - 1 )
        + " 个基因组"
      );

/*
** KPD It isn't really necessary explicitly to retain the elite member,
** a genome at least that good would survive to the next generation,
** though mutation might nail it, but this doesn't cost a whole lot, and
** later changes might invalidate that lack of necessity, so do it
** anyway.  We kept track above of the location of the elite genome, and
** copied it to the new population's first slot, now do messy index
** calculations to avoid clobbering it, since its position is frozen in
** the roulette wheel already.
*/

      if
      (
        i == m_bestGenomeIndex
        &&
        CheckBoxControls.getState
        (
          CheckBoxControls.CBC_METAHEURISTIC_SINGLE_ELITISM
        )
      )  // leave elite one alone if requested.
      {
        i++;
      }
      else
      {
        if (m_reproducers == null)
        {
          c = m_population[m_rw.getIndex()].cloneThis();
        }
        else
        {

/*
**  KPD This could be producing more than one vector entry, since some
**  reproduction operators in some designs create two child genomes,
**  thus the array treatment, in the for loop just below.
*/

          Reproducer polymorphicReproducer = m_reproducers.select();

          if ( polymorphicReproducer instanceof AsexualReproducer )
          {
            c =
              ((AsexualReproducer)polymorphicReproducer).reproduce
              (

/*
** FIXME only for sexual reproduces, for now; depend on replacement
** policy for improvement, not parent quality.  A horrible parent will
** eventually be overwritten by a prior sexual reproducer's second
** child, anyway.  FIXME That last is no longer true!  A horrible parent
** will just have to find a way to improve, or it will be horrible, and
** thus receive few mating approaches, forever.
** 
**              m_population[m_rw.getIndex()]
*/

                m_population[i]
              );
          }
          else
          {
            if ( polymorphicReproducer instanceof SexualReproducer )
            {

/*
** Oops!  Another nasty bug.  Avoid mating sexually reproducing things
** with themselves!
*/

              int other = m_rw.getIndex();
              while (other == i) { other = m_rw.getIndex(); }

              c =
                ((SexualReproducer)polymorphicReproducer).reproduce
                (
                  // FIXME only bias one parent, for now
                  // m_population[m_rw.getIndex()],
                  m_population[i],
                  m_population[other]
                  // m_population[m_rw.getIndex()]
                );
            }
            else
            {
              if
              (
                polymorphicReproducer instanceof ConsultiveReproducer
              )
              {
                c =
                  ((ConsultiveReproducer)polymorphicReproducer).reproduce
                  (
                    // FIXME only for crossovers, for now
                    // m_population[m_rw.getIndex()],
                    m_population[i],  // self
                    m_population,     // consultants
                    m_rw
                  );
              }
              else
              {
                throw
                  polymorphicReproducer.m_errUnknownReproducerType;
              }
            }
          }
        }

/*
**  OK, one way or another we have a child genome c from the above
**  efforts.
*/

        if
        (

/*
** We may have more new kids than we have places to put them!  We
** callously discard surplus offspring.
*/
          ( i < m_population.length )
          &&
          (

/*
**  We have to defend against m_bestGenomeIndex again, because we may advance to it
**  while iterating on j.
*/
            ( 
              i != m_bestGenomeIndex
            )
              ||
            ( 
              CheckBoxControls.getState
              (
                CheckBoxControls.CBC_METAHEURISTIC_SINGLE_ELITISM
              ) == false
            )
          )
        )
        {

/*
** POLICY Here's the beef.  Instead of accepting whatever nearly random
** garbage reproduction gives us, make each child genome compete based
** on fitness for the next slot against the genome in that slot from the
** old population.  This forces a steadily improving population.  There
** are much smarter ways to do this, but this was easy to code just to
** prove how incredibly much difference it makes.
** 
** Here also is where the simulated annealer implementation's
** application is hidden, and the fitness check is now buried inside it.
*/

            new_pop[i] =
              ( m_annealer.anneal( m_population[i], c ) )
              .cloneThis();

/*
**  KPD Mutate _after_ competing for slot!!!  Otherwise, fitness can
**  squeeze out all change for thousands of generations.
** 
*/

            if (m_mutators != null)
            {

/*
** The original design here had the "mutate at all" rate and the "mutate
** how hard" rate coupled, which led to failures at high mutation rates;
** user choice of a 100% "mutate at all" rate created an infinite
** "mutate how hard" loop, yet might be a user-desired setting!
** 
** POLICY Decouple the "mutate at all" rate from the "how much mutation
** to do" rate.
** 
** Let the user choose the former rate, and the designer choose the
** latter rate by setting a depth of the mutation at some fixed
** probability.
*/

/*
** FIXME: A gaussian instead of a uniform probability might work better
** here for this latter part; I have something else on my mind just now,
** so do an easy one.  In any case, this needs tuning.
*/

              if (m_mt.nextDouble() < m_mutationRate)
              {

/*
** POLICY Pick _one_ mutator per entry here, don't mix and match.
*/

                Mutator someMutator = m_mutators.select();

/*
** Some mutators make sense to use multiple times, some would hash
** things too badly; check which we have, here, and do the Right Thing.
** Notice that the ability to perform this check is all that usefully
** distinguishes a Mutator from an AsexualReproducer.
*/

                boolean letLoop =
                  someMutator.isSuitableForMultipleMutationRuns();

/*
** Count mutation instances for the status displayer.
*/

                TravellerStatus.bumpCandidatesMutated();
                do
                {

/*
** We do a cloneThis rather than a mutate in place, because we don't
** want to get messed up using the wrong parent if we do in fact loop
** here, something that has burned me multiple times already.
*/

                  new_pop[i] = (someMutator.mutate(new_pop[i])).cloneThis();

/*
** Better do this here, just in case we find ourselves with a mutator
** that thinks canonical form is important, since we are messing it up
** with each mutation pass, and have no way to enforce a contract on
** subsequent programmers that any mutator must canonicalize before
** returning a genome.
*/

                  ((TravellerChromosome)(new_pop[i])).canonicalize();

/*
** We only loop the mutators who tell us they groove on that kind of
** thing.
*/

                } while ( letLoop && m_mt.nextBoolean() );
              }
            }
        }


/*
** Put in standard form as last hurrah of reproduction/mutation pass.
*/

        ((TravellerChromosome)(new_pop[i])).canonicalize();
        ++i;
      }
    }

    if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
    {
      System.out.println
      (
        "in Population.nextGeneration(), completed reproduction loop"
      );
    }

    // replace old population with new one
    m_population = new_pop;

/*
**  return best fitness
** 
** KPD BUG!  This is the best fitness of the _prior_ generation.
** 
** FIXED Refactored so that things could be computed in the correct
** order, which means that the population's genomes are evaluated once
** _before_ any GA heuristics are run, as the zeroth generation, then
** once _after_ any GA heuristics are run, for all subsequent
** generations.  That way our statistics displays are running on the
** results of the just completed generation consistently, rather than
** with a mix of current and prior generation statistics.
*/

    return evaluateGenomes();

  }

}