Stochastic Universal Sampling

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

Stochastic Universal Sampling

martin martinez
Hi,

My name is Martin Martinez and i'm a student from Computer Engineering University, Montevideo Uruguay. Currently i'm working on my final dissertation with two classmates, and it's about the Bin Packing Problem in 3D. We are working with your framework in order to use the GA implementation, we have used the roulette wheel as for the selection, we also have extended the NaturalSelectorExt class in order to implement the Stochastic Universal Sampling(SUS from now on). We have done it, maybe not using the most appropriate structures but the algorithm idea remains the same.

The only issue we have found with our implementation is the difference between the execution times, while the roulette wheel takes no more than 25 seconds to execute, our SUS implementation takes up to 2-3 minutes keeping the rest of the configuration the same.

One thing that we have noticed is that if we remove the cloning section code from the roulette wheel implementation the execution time increase enormously (from 25 seconds to 120), therefore we try to use this section in our implementation (copy/paste pretty much) without seeing a significant decrease in the execution time.

Any ideas? Thoughts?

I've enclosed the class file in fact. Any hints or suggestions are welcome :)

Best Regards

Martin Martinez


------------------------------------------------------------------------------
Lotusphere 2011
Register now for Lotusphere 2011 and learn how
to connect the dots, take your collaborative environment
to the next level, and enter the era of Social Business.
http://p.sf.net/sfu/lotusphere-d2d
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users

StochasticUniversal.java (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Stochastic Universal Sampling

Klaus Meffert-5
Martin,
 
the first thing I can see after a quick snatch on your code:
There is one loop running inside another loop, where the inner loop potentially adds chromosomes to the list of candidates. The more candidates there are the slower evolution will be:
  for (int i = 0; i < ptrs.size(); i++) {
   double f = ptrs.get(i);
   double ptr = 0;
   for (int j = 0; j < cromosomes.size(); j++) {
    IChromosome cromosome = cromosomes.get(j);
    if (ptr < f && (ptr + cromosome.getFitnessValue()) > f){
              aFromPop.addChromosome(cromosome);
              break;
    }
          ptr += cromosome.getFitnessValue();
   }
  }
There is a break inside the inner loop, but as the outer loop runs farther, maybe this is one problem?
You could also try using a profiler to check out where the time is consumed most. Or maybe evaluate the number of chromosomes in the candidate's list and compare them to the number when using an original selector.
 
Best
 


From: martin martinez [mailto:[hidden email]]
Sent: Thursday, December 09, 2010 3:57 AM
To: [hidden email]
Cc: Gabriel López
Subject: [jgap-users] Stochastic Universal Sampling

Hi,

My name is Martin Martinez and i'm a student from Computer Engineering University, Montevideo Uruguay. Currently i'm working on my final dissertation with two classmates, and it's about the Bin Packing Problem in 3D. We are working with your framework in order to use the GA implementation, we have used the roulette wheel as for the selection, we also have extended the NaturalSelectorExt class in order to implement the Stochastic Universal Sampling(SUS from now on). We have done it, maybe not using the most appropriate structures but the algorithm idea remains the same.

The only issue we have found with our implementation is the difference between the execution times, while the roulette wheel takes no more than 25 seconds to execute, our SUS implementation takes up to 2-3 minutes keeping the rest of the configuration the same.

One thing that we have noticed is that if we remove the cloning section code from the roulette wheel implementation the execution time increase enormously (from 25 seconds to 120), therefore we try to use this section in our implementation (copy/paste pretty much) without seeing a significant decrease in the execution time.

Any ideas? Thoughts?

I've enclosed the class file in fact. Any hints or suggestions are welcome :)

Best Regards

Martin Martinez


------------------------------------------------------------------------------
Lotusphere 2011
Register now for Lotusphere 2011 and learn how
to connect the dots, take your collaborative environment
to the next level, and enter the era of Social Business.
http://p.sf.net/sfu/lotusphere-d2d
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Stochastic Universal Sampling

martin martinez
Klaus,

Actually I've found through debugging that the reason behind the difference in time is about how the roulette wheel structure works, after...lets say 30 generations, there are just 10 or less different chromosomes from the 100 originals. The roulette pretty much doesn't care about positions, actually it does, but what i'm trying to say is that is easier to use the advantage of the repeated chromosomes because of the nature of the algorithm, I've been thinking how to use it with SSUS but i'm sure if it's possible.

Does make any sense?

Martin


On Thu, Dec 16, 2010 at 11:49 AM, Klaus Meffert <[hidden email]> wrote:
Martin,
 
the first thing I can see after a quick snatch on your code:
There is one loop running inside another loop, where the inner loop potentially adds chromosomes to the list of candidates. The more candidates there are the slower evolution will be:
  for (int i = 0; i < ptrs.size(); i++) {
   double f = ptrs.get(i);
   double ptr = 0;
   for (int j = 0; j < cromosomes.size(); j++) {
    IChromosome cromosome = cromosomes.get(j);
    if (ptr < f && (ptr + cromosome.getFitnessValue()) > f){
              aFromPop.addChromosome(cromosome);
              break;
    }
          ptr += cromosome.getFitnessValue();
   }
  }
There is a break inside the inner loop, but as the outer loop runs farther, maybe this is one problem?
You could also try using a profiler to check out where the time is consumed most. Or maybe evaluate the number of chromosomes in the candidate's list and compare them to the number when using an original selector.
 
Best
 


From: martin martinez [mailto:[hidden email]]
Sent: Thursday, December 09, 2010 3:57 AM
To: [hidden email]
Cc: Gabriel López
Subject: [jgap-users] Stochastic Universal Sampling

Hi,

My name is Martin Martinez and i'm a student from Computer Engineering University, Montevideo Uruguay. Currently i'm working on my final dissertation with two classmates, and it's about the Bin Packing Problem in 3D. We are working with your framework in order to use the GA implementation, we have used the roulette wheel as for the selection, we also have extended the NaturalSelectorExt class in order to implement the Stochastic Universal Sampling(SUS from now on). We have done it, maybe not using the most appropriate structures but the algorithm idea remains the same.

The only issue we have found with our implementation is the difference between the execution times, while the roulette wheel takes no more than 25 seconds to execute, our SUS implementation takes up to 2-3 minutes keeping the rest of the configuration the same.

One thing that we have noticed is that if we remove the cloning section code from the roulette wheel implementation the execution time increase enormously (from 25 seconds to 120), therefore we try to use this section in our implementation (copy/paste pretty much) without seeing a significant decrease in the execution time.

Any ideas? Thoughts?

I've enclosed the class file in fact. Any hints or suggestions are welcome :)

Best Regards

Martin Martinez



------------------------------------------------------------------------------
Lotusphere 2011
Register now for Lotusphere 2011 and learn how
to connect the dots, take your collaborative environment
to the next level, and enter the era of Social Business.
http://p.sf.net/sfu/lotusphere-d2d
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Stochastic Universal Sampling

Klaus Meffert-5
Martin,
 
after evaluating a bit deeper, I probably found the solution:
 
Your implementation ignores the parameter aHowManyToSelect (type int), i.e. you always select as many chromosomes as your implementation "wants".
 
If you added something like the following to your code (forgive the naive implementation for reasons of brevity), see bold printed:
    int selected = 0;
    /*ahora selecciono la población*/
    for (int i = 0; i < ptrs.size(); i++) {
      if(selected>=aHowManyToSelect) {
        break;
      }
      double f = ptrs.get(i);
      double ptr = 0;
      for (int j = 0; j < cromosomes.size(); j++) {
        IChromosome cromosome = cromosomes.get(j);
        if (ptr < f && (ptr + cromosome.getFitnessValue()) > f){
          ICloneHandler cloner = getConfiguration().getJGAPFactory().
              getCloneHandlerFor(cromosome, null);
          if (cloner != null) {
            try {
              IChromosome cloned = (IChromosome) cloner.perform(
                  cromosome, null, null);
              aFromPop.addChromosome(cloned);
              selected++;
              if(selected>=aHowManyToSelect) {
                break;
              }
...
 
Then  your implementation gets an enormous speedup and is even faster than the roulette selection in some cases!
In the above code, I also added cloning (at least as a basic implementation), please use the cloning mechanism as WeightedRouletteSelector does.
 
You really should use cloning here, I suggest.
 
Best
 


From: martin martinez [mailto:[hidden email]]
Sent: Thursday, December 16, 2010 3:26 PM
To: Klaus Meffert
Cc: [hidden email]; Gabriel López
Subject: Re: [jgap-users] Stochastic Universal Sampling

Klaus,

Actually I've found through debugging that the reason behind the difference in time is about how the roulette wheel structure works, after...lets say 30 generations, there are just 10 or less different chromosomes from the 100 originals. The roulette pretty much doesn't care about positions, actually it does, but what i'm trying to say is that is easier to use the advantage of the repeated chromosomes because of the nature of the algorithm, I've been thinking how to use it with SSUS but i'm sure if it's possible.

Does make any sense?

Martin


On Thu, Dec 16, 2010 at 11:49 AM, Klaus Meffert <[hidden email]> wrote:
Martin,
 
the first thing I can see after a quick snatch on your code:
There is one loop running inside another loop, where the inner loop potentially adds chromosomes to the list of candidates. The more candidates there are the slower evolution will be:
  for (int i = 0; i < ptrs.size(); i++) {
   double f = ptrs.get(i);
   double ptr = 0;
   for (int j = 0; j < cromosomes.size(); j++) {
    IChromosome cromosome = cromosomes.get(j);
    if (ptr < f && (ptr + cromosome.getFitnessValue()) > f){
              aFromPop.addChromosome(cromosome);
              break;
    }
          ptr += cromosome.getFitnessValue();
   }
  }
There is a break inside the inner loop, but as the outer loop runs farther, maybe this is one problem?
You could also try using a profiler to check out where the time is consumed most. Or maybe evaluate the number of chromosomes in the candidate's list and compare them to the number when using an original selector.
 
Best
 


From: martin martinez [mailto:[hidden email]]
Sent: Thursday, December 09, 2010 3:57 AM
To: [hidden email]
Cc: Gabriel López
Subject: [jgap-users] Stochastic Universal Sampling

Hi,

My name is Martin Martinez and i'm a student from Computer Engineering University, Montevideo Uruguay. Currently i'm working on my final dissertation with two classmates, and it's about the Bin Packing Problem in 3D. We are working with your framework in order to use the GA implementation, we have used the roulette wheel as for the selection, we also have extended the NaturalSelectorExt class in order to implement the Stochastic Universal Sampling(SUS from now on). We have done it, maybe not using the most appropriate structures but the algorithm idea remains the same.

The only issue we have found with our implementation is the difference between the execution times, while the roulette wheel takes no more than 25 seconds to execute, our SUS implementation takes up to 2-3 minutes keeping the rest of the configuration the same.

One thing that we have noticed is that if we remove the cloning section code from the roulette wheel implementation the execution time increase enormously (from 25 seconds to 120), therefore we try to use this section in our implementation (copy/paste pretty much) without seeing a significant decrease in the execution time.

Any ideas? Thoughts?

I've enclosed the class file in fact. Any hints or suggestions are welcome :)

Best Regards

Martin Martinez



------------------------------------------------------------------------------
Lotusphere 2011
Register now for Lotusphere 2011 and learn how
to connect the dots, take your collaborative environment
to the next level, and enter the era of Social Business.
http://p.sf.net/sfu/lotusphere-d2d
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Loading...