travellerchromosome.java

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

      int targetSlot = offset + ((reversed) ? ( 0 - n ) : n);
      while ( targetSlot < 0 )
      {
        targetSlot += ValuatorControls.getNumberOfCities();
      }
      targetSlot = targetSlot % ValuatorControls.getNumberOfCities();
      return this.getCodon( targetSlot );
    }

    // for someone outside who wants to work with the city list
    // (a reproducer, for example)
    public int getCity(int n)
    {

        if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
        {
          System.out.println
          (
            "Entered TravellerChromosome.getCity(int n) = "
            + n
          );
        }

        // KPD Make chromosomes rings instead of vectors to simplify
        // KPD many reproduction algorithms.
        // KPD return m_cityList[n];
        // return m_cityList[n % m_cityList.length].get();
        // KPD Unbelievable; the java2sdk "%" function is broken, it
        // KPD returns (-1) from ((-1) % 10).

        int j = n;

        while ( j < 0 )
        {
          j += this.getNumCities();
        }

        j = j % this.getNumCities();

        return m_cityList[j].get();
    }

    // enable arithmetic for matching genomes in general position before
    // doing crossovers.

    public int getCity(int n, int offset, boolean reversed)
    {
      int targetSlot = offset + ((reversed) ? ( 0 - n ) : n);
      while ( targetSlot < 0 )
      {
        targetSlot += ValuatorControls.getNumberOfCities();
      }
      targetSlot = targetSlot % ValuatorControls.getNumberOfCities();
      return this.getCity( targetSlot );
    }

    public void setCity( int n, int city, int offset, boolean reversed)
    {
      int targetSlot = offset + ((reversed) ? ( 0 - n ) : n);
      while ( targetSlot < 0 )
      {
        targetSlot += ValuatorControls.getNumberOfCities();
      }
      targetSlot = targetSlot % ValuatorControls.getNumberOfCities();
      this.setCity(targetSlot, city);
      m_fitnessValid = false;
    }

    public void setCity(int n, int city)
    {

        if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
        {
          System.out.println
          (
            "Entered TravellerChromosome.setCity(int n, int city) = "
            + n
            + ", "
            + city
          );
        }

        // *** This method is dangerous!
        //     It does not ensure that the change results in a valid
        //     permutation!
        //     I did this for speed; only reproducive operators should
        //     use this method.
        // KPD Make chromosomes rings instead of vectors to simplify
        // KPD many reproduction algorithms.
        // KPD m_cityList[n] = city;
        // KPD Unbelievable; the java2sdk "%" function is broken, it
        // KPD returns (-1) from ((-1) % 10).

        int j = n;

        while ( j < 0 )
        {
          j += this.getNumCities();
        }

        j = j % this.getNumCities();

        m_cityList[j].set( city );

        m_fitnessValid = false;
    }

    public int findCity(int city)
    {

        if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
        {
          System.out.println
          (
            "Entered TravellerChromosome.findCity( int city) = "
            + city
          );
        }

        int i = 0;

        while (true)
        {
            if (city == m_cityList[i].get())
                return i;

            ++i;

            if (i == m_world.getNumberOfCities())
                return -1;
        }
    }

    // Be careful with this!  The index returned only works
    // in the longer parameter list versions of getCity and setCity.
    public int findCity(int city, int offset, boolean reverse)
    {

        int i = 0;

        while (true)
        {
            if ( city == this.getCity(i, offset, reverse) )
                return i;

            ++i;

            if (i == m_world.getNumberOfCities())
                return -1;
        }
    }

    // Utility arithmetic done once here to put the quite complicated
    // logic in just one place; seems natural to keep it with other stuff
    // about having the ring in general position for crossovers.
    // This became needed as soon as segments were allowed to wrap the
    // ends of arrays to implement the "ring essense" of Traveller
    // permutation chromosomes properly to avoid artifacts that lock out
    // possible paths to solutions.

    public boolean indexIsInSegment
    (
      int     index,                         // 8
      int     segStart,                      // 10
      int     segLength,                     // 13
      int     offset,                        // false
      boolean reverse
    )
    {
      int ringLength = this.getNumCities();  // 16
      int virtualIndex = ((reverse) ? (offset - index) : (offset + index));
      int indexStart = segStart + offset;    // 18
      int indexEnd =                         // 30
        indexStart + ((reverse) ? (1 - segLength) : (segLength - 1));

      // Move all indices back to the 0 to ringLength - 1 indexing range.

      // Compensate for Sun's buggy Java 1.4 modulus function by doing
      // everything twice to avoid its incorrect negative results when
      // taking the positive modulus of a negative number.
      // FIXME when Sun's bug is fixed.

      virtualIndex =
        ((( virtualIndex % ringLength) + ringLength ) % ringLength);
      // 0
      indexStart = ((( indexStart % ringLength ) + ringLength ) % ringLength);
      // 2
      indexEnd = ((( indexEnd % ringLength ) + ringLength ) % ringLength);
      // 14

      return
      (
        (
          (           // case (nnnSyyyEnnn)
            (!reverse)
            &&
            (indexEnd > indexStart)
            &&
            (virtualIndex >= indexStart)
            &&
            (virtualIndex <= indexEnd)
          )
          ||
          (           // case (nnnEyyySnnn)
            reverse
            &&
            (indexEnd < indexStart)
            &&
            (virtualIndex <= indexStart)
            &&
            (virtualIndex >= indexEnd)
          )
          ||
          (           // case (yyyEnnnSyyy)
            (!reverse)
            &&
            (indexEnd < indexStart)
            &&
            (
              (virtualIndex <= indexEnd)
              ||
              (virtualIndex >= indexStart)
            )
          )
          ||
          (           // case (yyySnnnEyyy)
            (reverse)
            &&
            (indexStart < indexEnd)
            &&
            (
              (virtualIndex <= indexStart)
              ||
              (virtualIndex >= indexEnd)
            )
          )

        )
      );

    }

    public int getNumCities()
    {
        return m_world.getNumberOfCities();
    }

    // duplicate a chromosome
    public Chromosome cloneThis()
    {
        return new TravellerChromosome(this);
    }

    public String getOriginator()
    {
      return m_originator;
    }

    public void setOriginator( String originatorName )
    {
      m_originator = new String( originatorName );
    }

    public TravellerWorld getWorld()
    {
      return m_world;
    }

    // test and report genome validity
    public void checkValidity()
    {
      try
      {
        int genomeLength = ValuatorControls.getNumberOfCities();
        boolean isIn[] = new boolean[genomeLength];

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

        for ( int i =0; i < genomeLength; i++ )
        {
          int codonName = m_cityList[i].get();
          if ( ( codonName < 0 ) || ( codonName > ( genomeLength - 1 ) ) )
          {
            System.out.println
            (
              "\r\n"
              + "TravellerChromosome.isValid(); invalid Codon in genome: "
              + m_cityList[i].toString()
            );
            complain();
            return;
          }
          else
          {
            isIn[i] = true;
          }
        }
        for ( int i =0; i < genomeLength; i++ )
        {
          if ( isIn[i] == false )
          {
            System.out.println
            (
              "\r\n"
              + "TravellerChromosome.isValid(); city "
              + i
              + " missing in genome."
            );
            complain();
            return;
          }
        }
      }
      catch (Exception e)
      {
        System.out.println
        (
          "TravellerChromosome.isValid() threw!"
        );
        System.out.println
        (
          "And did it for a chromosome created by "
          + m_originator
        );
      }
    }

    private void complain()
    {
      try
      {
        System.out.println
        (
          "\r\n"
          + "isValid() failed for genome created by "
          + this.getOriginator()
        );
      }
      catch (Exception e)
      {
        System.out.println
        (
          "TravellerChromosome.complain() threw!"
        );
        System.out.println
        (
          "And did it for a chromosome created by "
          + m_originator
        );
      }
    }

    // compute fitness
    public double testFitness()
    {

        if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
        {
          System.out.println
          (
            "Entered TravellerChromosome.testFitness()"
          );
        }

        if ( m_fitnessValid ) { return m_fitness; }

        // calculate round-trip distance
//        if (m_closedPath)
            m_fitness =
              m_world.getDistance
              (
                m_cityList[0].get(),
                m_cityList[m_world.getNumberOfCities() - 1].get()
              );
//        else
//            m_fitness = 0;

        for (int n = 1; n < m_world.getNumberOfCities(); ++n)
            m_fitness +=
              m_world.getDistance(m_cityList[n-1].get(),m_cityList[n].get());

        m_fitnessValid = true;

        return m_fitness;
    }

    public void canonicalize()
    {

      if (CheckBoxControls.getState(CheckBoxControls.CBC_DEBUG_PRINTOUTS))
      {
        System.out.println
        (
          "Entered TravellerChromosome.canonicalize()"
        );
      }

      // For safety, check that we _have_ a city list.
      if ( m_cityList == null ) { return; }

      // Distinguish a starting city.  Canonical form has this city in slot
      // zero, and the city in slot one lexicographically less than the city
      // in slot minus one (since we are working in a ring, this makes sense).

      int hometown = 0;

      // For efficiency, check whether we are already _in_ canonical form,
      // and so need do nothing.
      if
      (
        ( m_cityList[0].get() == hometown )
        &&
        ( m_cityList[1].get() < m_cityList[getNumCities() - 1].get() )
      )
      { return; }

      // No joy, we must work for a living.

      int [] tempCityList = null;
      tempCityList        = new int [this.getNumCities()];
      int startAt = findCity( hometown );
      int stepBy = 1;
      if (getCity( startAt + 1 ) > getCity( startAt - 1 ) )
      {
        stepBy = ( -1 );
      }

/*
      System.out.println
      (
        "in canonicalize getNumCities() gives "
        + this.getNumCities()
        + ", startAt is "
        + startAt
      );
*/

      for
      (
        int i = 0, j = startAt ;
        i < this.getNumCities() ;
        i++ , j += stepBy
      )
      {

/*
        System.out.println
        (
          "in canonicalize for loop, i is "
          + i
          + ", and j is "
          + j
        );
*/

        tempCityList[i] = this.getCity(j);
      }

      for ( int i = 0 ; i < this.getNumCities() ; i++ )
      {
        setCity(i , tempCityList[i]);
      }

      return;
    }
}