Quantcast

Problem with TSP output

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Problem with TSP output

Pratyush Chandra-2
Hi,

I am trying to run a TSP code as given in example. My problem is slight variation of TSP, in the sense I don't want to return back to starting point. To do this, I am adding dummy starting point and all nodes are at 0 distance from this dummy starting node. After running I find score to be correct as 8, but gene path seems to be incorrect.
Output should be 0->1->2->3->4->5->0
Can somebody help me with that. Adding the source code below :

import org.jgap.*;
import org.jgap.impl.*;
import org.jgap.impl.salesman.*;

public class TravellingSalesman
    extends Salesman {

  /** The number of cities to visit*/
  public static final int CITIES = 6;

 
  public static final int[][] CITYARRAY = new int[][] { {0,0 }, {28, 1}, {28, 6}, {28, 7},
      {28, 8}, {28, 9}
  };
  public IChromosome createSampleChromosome(Object a_initial_data) {
    try {
      Gene[] genes = new Gene[CITIES];
      for (int i = 0; i < genes.length; i++) {
        genes[i] = new IntegerGene(getConfiguration()
, 0, CITIES - 1 );
        genes[i].setAllele(new Integer(i));
      }
      IChromosome sample = new Chromosome(getConfiguration(), genes);
      return sample;
    }
    catch (InvalidConfigurationException iex) {
      throw new IllegalStateException(iex.getMessage());
    }
  }

  public double distance(Gene a_from, Gene a_to) {
    IntegerGene geneA = (IntegerGene) a_from;
    IntegerGene geneB = (IntegerGene) a_to;
    int a = geneA.intValue();
    int b = geneB.intValue();
   
    if(a==0 || b==0) {
        return 0;
    }
    int x1 = CITYARRAY[a][0];
    int y1 = CITYARRAY[a][1];
    int x2 = CITYARRAY[b][0];
    int y2 = CITYARRAY[b][1];
    double ret = 0;
    if(x1==x2) ret =  Math.abs(y1-y2)*1;
    else ret = Math.abs(x1 - x2)*5 + (Math.abs(y1)+Math.abs(y2))*1;
 
    return ret;
   
  }

  public static void main(String[] args) {
    try {
      TravellingSalesman t = new TravellingSalesman();
      IChromosome optimal = t.findOptimalPath(null);
      System.out.println("Solution: ");
      System.out.println(optimal);
      System.out.println("Score " +
                         (Integer.MAX_VALUE / 2 - optimal.getFitnessValue()));
     
      for(int i=1;i<optimal.getGenes().length;i++) {
          Gene p = optimal.getGene(i-1);
          Gene n = optimal.getGene(i);
          System.out.println(p.getAllele()+"->"+n.getAllele()+":"+t.distance(p, n));
      }
      Gene p = optimal.getGene(optimal.getGenes().length-1);
      Gene n = optimal.getGene(0);
      System.out.println(p.getAllele()+"->"+n.getAllele()+":"+t.distance(p, n));
    }
    catch (Exception ex) {
      ex.printStackTrace();
    }
  }
}


--
Pratyush Chandra


------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Loading...