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

Processing Coding Questions
4

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:

1 Like