How convert the Traveling Salesperson JS to Object-oriented Programming style Java Processing

[psamead]

please format code with </> button * homework policy * asking questions

Dear friends,
I am learning the Processing and trying to convert Daniel’s ‘Traveling Sales Person’ JavaScript to the Java Processing in the Object Oriented style using the genetic algorithm method. But it seems my code is not actually calculating. I wonder ifsomeone can help me to find out the problem and teach me how to fix it.

Here is the code:

int totalCities = 12;
int popSize = 500;

Population population;

void setup()
{
size(800, 800);
population = new Population();
}

void draw()
{
background(0);

population.run();
population.show();
}

class City
{
// PVector as the location of city on the screen
PVector loc; // psotion
float r; // circles radius

City(PVector p)
{
loc = p.copy();

r = 16;

}
}

class Order
{
IntList index;
int shuffleTimes = 10;

Order()
{

index = new IntList();
for(int i = 0; i < totalCities; i++)
{
  index.append(i);
}    

}

void shuffleOrder()
{
for(int i = 0; i < shuffleTimes; i++)
{
int numA = floor(random(index.size()));
int numB = floor(random(index.size()));
swap(index, numA, numB);
}
}

void swap(IntList list, int i, int j)
{
int tempA = list.get(i);
int tempB = list.get(j);
list.set(i, tempB);
list.set(j, tempA);
}

}

class Population
{
IntList population;
Order seqList;
City cities;

float fitness;

float recordDistance = Float.POSITIVE_INFINITY;

IntList bestEver;
IntList currentBest;

//PVector points;

Population()
{
fitness = new float[popSize];

cities = new City[totalCities];
for(int i = 0; i < totalCities; i++)
{
  PVector v = new PVector(random(width), random(height/2));

  cities[i] = new City(v);
  //cities[i] = new City();
}

population = new IntList[popSize];
seqList = new Order();


for(int i = 0; i < popSize; i++)
{
  seqList.shuffleOrder();
  population[i] = seqList.index.copy();    
} 

}

float calcDistance(City cities, IntList list)
{
float sum = 0;
for(int i = 0; i < list.size()- 1; i++)
{
int cityAIndex = list.get(i);
City cityA = cities[cityAIndex];
int cityBIndex = list.get(i+1);
City cityB = cities[cityBIndex];
float d = dist(cityA.loc.x, cityA.loc.y, cityB.loc.x, cityB.loc.y);
sum += d;
}
return sum;
}

void calculateFitness()
{
float currentRecord = Float.POSITIVE_INFINITY;
for(int i = 0; i < population.length; i++)
{
float d = calcDistance(cities, population[i]);
if(d < recordDistance)
{
recordDistance = d;
bestEver = population[i];
}
if(d < currentRecord)
{
currentRecord = d;
currentBest = population[i];
}

  fitness[i] = 1/(pow(d, 8)+1);
}

}

void normalizeFitness()
{
float sum = 0;
for(int i = 0; i < fitness.length; i++)
{
sum += fitness[i];
}
for(int i = 0; i < fitness.length; i++)
{
fitness[i] = fitness[i]/sum;
}
}

void nextGeneration()
{
IntList newPopulation = new IntList[popSize];
for(int i = 0; i < population.length; i++)
{
IntList orderA = pickOne(population, fitness);
IntList orderB = pickOne(population, fitness);
IntList order = crossOver(orderA, orderB);
mutate(order, 0.01);
newPopulation[i] = order;

}

}

IntList pickOne(IntList list, float prob)
{
int index = 0;
float r = random(1);

while(r > 0)
{
  r = r - prob[index];
  index++;
}
index--;


return list[index].copy();

}

IntList crossOver(IntList orderA, IntList orderB)
{
int start = floor(random(orderA.size()));
int end = floor(random(start+1, orderA.size()));
IntList neworder = new IntList();
for(int i = start; i < end; i++)
{
neworder.append(orderA.get(i));
}

for(int i = 0; i < orderB.size(); i++)
{
  int city = orderB.get(i);
  if(!neworder.hasValue(city))
  {
    neworder.append(city);
  }
}
return neworder;

}

void mutate(IntList order, float mutationRate)
{
for(int i = 0; i < totalCities; i++)
{
if(random(1) < mutationRate)
{
int indexA = floor(random(order.size()));
int indexB = (indexA + 1) % totalCities;
swap(order, indexA, indexB);
}
}
}

void swap(IntList a, int i, int j)
{
int temp1 = a.get(i);
int temp2 = a.get(j);
a.set(i, temp2);
a.set(j, temp1);
}

void run()
{
calculateFitness();
normalizeFitness();
nextGeneration();

}

void show()
{
stroke(250, 160, 0);
strokeWeight(4);
noFill();
beginShape();
for(int i = 0; i < bestEver.size(); i++)
{
int n = bestEver.get(i);
vertex(cities[n].loc.x, cities[n].loc.y);
ellipse(cities[n].loc.x, cities[n].loc.y, 16, 16);
}
endShape();

translate(0, height/2);

stroke(250, 0, 160);
strokeWeight(4);
noFill();
beginShape();
for(int i = 0; i < currentBest.size(); i++)
{
  int n = currentBest.get(i);
  vertex(cities[n].loc.x, cities[n].loc.y);
  ellipse(cities[n].loc.x, cities[n].loc.y, 16, 16);
}
endShape();

}

}

[Chrisir]

What do you see now and what do you want to see instead?

[psamead]

Hi Chrisir,
Thanks for your kindly reply. I know there are problem here in framing this question. I am quite a newbie and don’t really know the exact question is. But basically my code results in a static image.

The functions doesn’t seem to generate new order objects to mark the cities. In the example provided by Dantiel CC_035_4_TSP_GA, the functions constantly provide orders in comparision.

what kind of mistake do I make here that the code does not work in that way?

[Chrisir]

I see

Error was that this line was missing
population = newPopulation;

at the end of nextGeneration()

Chrisir

//
int totalCities = 12;
int popSize = 500;

Population population;

void setup()
{
  size(800, 800);
  population = new Population();

  frameRate(1);
}

void draw()
{
  background(0);

  population.run();
  population.show();

  print(".");
}

// ==================================================================================================

class City
{
  // PVector as the location of city on the screen
  PVector loc; // position
  float r;     // circles radius

  City(PVector p)
  {
    loc = p.copy();
    r = 16;
  }
}

// ==================================================================================================

class Order
{
  IntList index;
  int shuffleTimes = 10;

  Order()
  {
    index = new IntList();
    for (int i = 0; i < totalCities; i++)
    {
      index.append(i);
    }
  }

  void shuffleOrder()
  {
    for (int i = 0; i < shuffleTimes; i++)
    {
      int numA = floor(random(index.size()));
      int numB = floor(random(numA, index.size())); // Added numA here !!!
      swap(index, numA, numB);
    }
  }

  void swap(IntList list, int i, int j)
  {
    int tempA = list.get(i);
    int tempB = list.get(j);
    list.set(i, tempB);
    list.set(j, tempA);
  }
}

// ==================================================================================================

class Population
{
  IntList[] population;
  Order seqList;
  City[] cities;

  float[] fitness;

  float recordDistance = Float.POSITIVE_INFINITY;

  IntList bestEver;
  IntList currentBest;

  //PVector points;

  Population()
  {
    fitness = new float[popSize];

    cities = new City[totalCities];
    for (int i = 0; i < totalCities; i++)
    {
      PVector v = new PVector(random(width), random(height/2));

      cities[i] = new City(v);
      //cities[i] = new City();
    }

    population = new IntList[popSize];
    seqList = new Order();

    for (int i = 0; i < popSize; i++)
    {
      seqList.shuffleOrder();
      population[i] = seqList.index.copy();
    }
  }

  float calcDistance(City[] cities, IntList list)
  {
    float sum = 0;
    for (int i = 0; i < list.size()- 1; i++)
    {
      int cityAIndex = list.get(i);
      City cityA = cities[cityAIndex];

      int cityBIndex = list.get(i+1);
      City cityB = cities[cityBIndex];

      float d = dist(cityA.loc.x, cityA.loc.y, 
        cityB.loc.x, cityB.loc.y);
      sum += d;
    }
    return sum;
  }

  void calculateFitness()
  {
    float currentRecord = Float.POSITIVE_INFINITY;
    for (int i = 0; i < population.length; i++)
    {
      float d = calcDistance(cities, population[i]);
      if (d < recordDistance)
      {
        recordDistance = d;
        bestEver = population[i].copy();
      }
      if (d < currentRecord)
      {
        currentRecord = d;
        currentBest = population[i].copy();
      }

      fitness[i] = 1/(pow(d, 8)+1);
    }
  }

  void normalizeFitness()
  {
    float sum = 0;
    for (int i = 0; i < fitness.length; i++)
    {
      sum += fitness[i];
    }
    for (int i = 0; i < fitness.length; i++)
    {
      fitness[i] = fitness[i]/sum;
    }
  }

  void nextGeneration()
  {
    IntList[] newPopulation = new IntList[popSize];
    for (int i = 0; i < population.length; i++)
    {
      IntList orderA = pickOne(population, fitness);
      IntList orderB = pickOne(population, fitness);
      IntList order = crossOver(orderA, orderB);
      mutate(order, 0.01); // was 0.01
      newPopulation[i] = order;
    }
    population = newPopulation;
  }

  IntList pickOne(IntList[] list, float[] prob)
  {
    int index = 0;
    float r = random(1);

    while (r > 0)
    {
      r = r - prob[index];
      index++;
    }
    index--;
    return list[index].copy();
  }

  IntList crossOver(IntList orderA, IntList orderB)
  {
    int start = floor(random(orderA.size()));
    int end = floor(random(start+1, orderA.size()));
    IntList neworder = new IntList();
    for (int i = start; i < end; i++)
    {
      neworder.append(orderA.get(i));
    }

    for (int i = 0; i < orderB.size(); i++)
    {
      int city = orderB.get(i);
      if (!neworder.hasValue(city))
      {
        neworder.append(city);
      }
    }
    return neworder;
  }

  void mutate(IntList order, float mutationRate)
  {
    for (int i = 0; i < totalCities; i++)
    {
      if (random(1) < mutationRate)
      {
        int indexA = floor(random(order.size()));
        int indexB = (indexA + 1) % totalCities;
        //print("before: " ); 
        //println(order);
        swap(order, indexA, indexB);
        //print("after: " );
        //println(order);
        //println("");
      }
    }
  }

  void swap(IntList a, int i, int j)
  {
    int temp1 = a.get(i);
    int temp2 = a.get(j);
    a.set(i, temp2);
    a.set(j, temp1);
  }

  void run()
  {
    calculateFitness();
    normalizeFitness();
    nextGeneration();
  }

  void show()
  {
    pushMatrix(); 

    stroke(250, 160, 0);
    strokeWeight(4);
    noFill();
    beginShape();
    for (int i = 0; i < bestEver.size(); i++)
    {
      int n = bestEver.get(i);
      vertex(cities[n].loc.x, cities[n].loc.y);
      ellipse(cities[n].loc.x, cities[n].loc.y, 16, 16);
    }
    endShape();
    popMatrix();

    pushMatrix(); 
    translate(0, height/2);

    stroke(250, 0, 160);
    strokeWeight(4);
    noFill();
    beginShape();
    for (int i = 0; i < currentBest.size(); i++)
    {
      int n = currentBest.get(i);
      vertex(cities[n].loc.x, cities[n].loc.y);
      ellipse(cities[n].loc.x, cities[n].loc.y, 16, 16);
    }
    endShape();
    popMatrix();
  }
  //
}//class Population
//

keywords:

• object-oriented programming,
• OOP,
• Traveling Salesman Problem, Traveling Salesperson Problem (TSP),
• Travelling Salesman Problem, Travelling Salesperson Problem (TSP),
• an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

[psamead]

Thanks for your kindly reply. This is very helpful and figuring out my mistake. The keywords are extremely useful to let me understand the topics behind. May I ask you a few more questions, if you have time to answer.

@Chrisir

int numB = floor(random(numA, index.size())); // Added numA here !!!

Is it to avoid the same number be picked here?

@Chrisir

if (random(1) < mutationRate)
      {
        int indexA = floor(random(order.size()));
        int indexB = (indexA + 1) % totalCities;
        //print("before: " ); 
        //println(order);
        swap(order, indexA, indexB);
        //print("after: " );
        //println(order);
        //println("");
      }

It seems there are difference generated even without ‘numA’ being added.

@Chrisir

(indexA + 1) % totalCities;

Is here using % to give a reverse series of number? But why + 1 ? Because the floor function is used?

Sorry for my English.
Very appreciate your time on my work befoe. Thank you again.

[Chrisir]

@psamead

Is it to avoid the same number be picked here?

This was an error by me

Please delete this numA!!!

[Chrisir]

@psamead

Is here using % to give a reverse series of number?

The % remainder is generally used to avoid that the value can get higher than this

When you say % totalCities the result is 0,1,2… up to totalCities-1

[psamead]

Thanks your explaination.

[Chrisir]

@psamead

But why + 1 ? Because the floor function is used?

That I don’t know

I am sorry

[psamead]

Thanks still