TribesPSO continued...

Dec 19, 2011 at 5:42 PM

Thank you very much for your immediate answer. Your comments were very helpful to me. Now, I would like to ask you another last question: in order to calculate the expected number of function evaluations, I think that the following formula should be used:

Expected number of function evaluations = (number of particles)*(average convergence generations among all trials) / success rate

I would be grateful If you could confirm the validity of the above formula. If this formula is valid, I would also need to know which is the number of used particles. I admit that despite my efforts I was unable to find out the number of particles used in your implementation of TribesPSO. So, if possible, I would like you to provide the relevant information.

Once again, congratulations for your fine work. You are very helpful to young researchers. It is no need to mention that your work will be cited in my planned papers that are relevant to unconstrained optimization, and that are going to be published very soon.

Best regards and many thanks for your time

John Tassopoulos, PhD Student

Coordinator
Dec 20, 2011 at 5:17 AM

John,

The number of particles in TribesPSO is variable.  That's what makes it a parameter-free particle swarm optimization technique.  This implementation is entirely based on a paper by Maurice Clerc.  You should check out his page here.  Specifically, this paper has some extremely good information.  Check out figure 5 on page 10.  It shows how the swarm size changes over time.  (As a side note, if you're going to cite anyone, it should probably be him!).

Back on topic, though,  because the swarm size is variable, it's not so simple to determine the number of function evaluations.  Before I go into more detail, I'd like to define a few terms:

An "Evaluation" happens when the objective function is solved for a specific point in hyperspace

A "Move" refers to one iteration for the entire swarm.  Every call to SearchSpace.MoveThanAdapt() is a "Move".  Depending on the number of particles in the swarm, this may cause one or more "Evaluations"

Now for an example.

When you first create a SearchSpace object, it contains zero particles.  Upon the first call to SearchSpace.MoveThanAdapt() a single particle will be added.  This particle will be placed at a random location in hyperspace and will evaluate its objective function.  At this point, we've got one move and one evaluation.  The next time you call SearchSpace.MoveThanAdapt() you'll get another move and another evaluation (we're up to 2 and 2).  This time, however, the search space will determine that it needs to adapt (because things probably haven't improved very much) and it will add a new particle to the swarm.  The next time you call SearchSpace.MoveThanAdapt() both particles are going to evaluate the objective function at their respective locations.  Now we're up to 3 moves and 5 evaluations.  Another particle may be added at this point (for a total of 3 particles) so the next call to MoveThanAdapt() will cause 3 evaluations (now we're up to 4 moves and 9 evaluations) etc.

Things get even more complicated down the road because particles can be removed from the swarm too.

Therefore, if you want the total number of evaluations, it's better to just count them directly.  Simply modify your IObjectiveFunction.Evaluate(EuclidianVector position) function to increment a value every time it's called.  For the tripod example, you'll need to make the following modifications:

  • Add a parameterless constructor to initialize your count variable to 0
  • Add a public property so Program.cs can read the count variable when you're done
  • Add a private backing field that gets incremented on every call to Evaluate

The additions to the code would look something like this:

using System.Threading; //Necessary for Interlocked.Increment

class Tripod : IObjectiveFunction
{
    private int evaluationCount; //Private backing field
    public int EvaluationCount{ get{ return this.evaluationCount; } } //Public read-only property that exposes private backing field

    /* Parameterless constructor to initialize evaluationCount
     * to zero.  This is not strictly necessary because
     * integer fields get initialized to zero anyway, but it never
     * hurts to be verbose
     */
    public Tripod()
    {
        this.evaluationCount = 0;
    }

    public double Evaluate(EuclidianVector position)
    {
         Interlocked.Increment(ref this.evaluationCount); //Interlocked.Increment instead of this.evaluationCount++ in case we're ever in a multi-threaded environment

        //. . .
        //the rest of the Evaluate function
        //. . .
    }
}

If you check out the bottom of the tripod example you'll see a histogram of the number of evaluations that it took to solve the tripod problem.  The optimization was run 10,000 times.  Each time the optimization was run, I recorded the number of evaluations and plotted the results as a histogram.

You may also find it interesting to measure the following statistics:

  • The swarm size vs the number of moves (see SearchSpace.SwarmSize)
  • The number of tribes in the swarm vs the number of moves (see SearchSpace.TribeCount)
  • The amount of potential energy in the swarm vs the number of moves (see SearchSpace.ParticlePositions)
Dec 22, 2011 at 7:16 AM
Edited Dec 22, 2011 at 7:40 AM

Good day to anyone who may attend this discussion,

First of all, I would like to thank Mr. Baugham for his accurate remarks and his immediate responces.

I have been implementing his code and during this proccess I found out some points that I think they should be posted.

First at the "public  static int OptimizeTripod",

the "Tripod functionToSolve = " should be substituded by "ConsoleApplication1.Tripod  functionToSolve = "

 

The second point is that in order to get access to the incremented variable "private int evaluationCount",

I added the following property:

 

public  int  publish_incremented_value

{
 

   get  
  { 
       return evaluationCount;

   } 
  set
 
   { 
       evaluationCount = zzz; 

 }
 where "zzz" is a variable declared as "static int zzz;" at "public class Tripod: IObjectiveFunction". 

 

 

In addition, I substituded

"Interlocked.Increment(ref evaluationCount);" by "zzz = Interlocked.Increment(refevaluationCount);" at "public uble Evaluate(EuclidianVector position)

Then, at "Program.cs" I created an istance (tripod22) of Tripod by using :

"ConsoleApplication1.Tripod tripod22 = new ConsoleApplication1.Tripod();"

Afterwards, I initialized the "publish_incremernted_value" by using :

"tripod22.publish_incremented_value = 0;" at

"static void Main(string[] args)"

where the statistics analysis is taking place.

Then, when I needed to get the function evaluations, I simply use "tripod22.publish_incremented_value".

One final point: the "public int EvaluationCount { get { return evaluationCount; } } " does not seem to do anything, at least in my code, since when I comment it the results are the same.

As I  am a beginner to C#, I would be greatful if Mr. Baugham or someone else could verify my points of code.

Note that the  number of function evaluations I get range between  90000 and 120000 or so, when the goal is set to 10e-5. Is it expected?

Thank you very much for your time,

John Tassopoulos, Ph.D student

 

  

 

 

 

 

 

 

 

 

 

 

 

 

Coordinator
Dec 23, 2011 at 3:51 PM

The EvaluationCount property that you said doesn't do anything is a read-only property that you use to get the number of times that Evaluate was called.  Your publish_incremented_value property does almost the same thing, but it contains a deeply unintuative setter that you should probably eliminate.  Normally, the setter uses a value that's passed in, but in your code it uses the value zzz.  That means that someone could write the following code:

functionToSolve.publish_incremented_value = 0;

Then, inside your setter, instead of setting evaluationCount to 0, it will get set to whatever the value of zzz is.  That is extremely unintuative behavior and will probably cause your statistics to be wrong at some point.  In fact, this is probably causing a pretty serious error in your code.  See my last paragraph for more information.

Instead, initialize evaluationCount (notice the lower-case e) to zero in the Tripod constructor, and return the value of evaluationCount using the EvaluationCount (note the upper-case E) read-only property.  You can eliminiate your "zzz" variable (which should really have a more meaningful name) as well.  It's also extremely risky to declare zzz as static, becuase its value will be shared by all Tripod objects.  The Tripod code that I posed above is correct.  You shouldn't need to modify it.

Also, the reason you had to use ConsoleApplication1.Tripod instead of just Tripod is because you put Tripod in a different namespace than your program.cs.  If you put them in the same namespace, you won't have to qualify Tripod with ConsoleApplication1.

As for the expected results: they seem a bit high  If you look at the graph at the end of the Tripod Example, you'll see that my results were quite a bit lower.  I would guess that because your zzz variable is declared as "static" it's counting the number of evaluations for all of the optimizations combined rather than counting the number of evaluations for each optimization.  I would eliminiate zzz and publish_incremented_value because they have almost the exact same meaning as evaluationCount and EvaluationCount.  In the future, you should also give properties names that start with capital letters.  Names with lowercase letters are normally used for fields

Dec 25, 2011 at 5:48 PM

Good day and merry Christmas to anybody,

All that Mr. Baughman refers to are correct. The reason that forced me to alter his code  was that the incrementing value "evaluationCount" I was getting was always 0. For that reason I used the "puplish_incremented_value" and I used badly the variable "zzz". On the other hand, the reason that caused the return value to be always 0 was the initialization of the instance of Tripod "Tripod22" that I  used. That was the problem. Any time I had to get the " evaluationCount", having first creating the new instance, set the value of " evaluationCount" to 0 and that was what I was getting. But following the instructions of Mr. Baughman I fixed up my code and now everything is fine.

Nevertheless, I have one comment to make concerning the number of calls of "MoveThenAdapt" which is set to 10000. A lot of paper that refer to variations of PSO and that use a fixed particle number, run the algorithm for about 2000 generations. That means that if the success rate is in the range [0.95, 1] or so and the number of particles is in the range [15, 50] which is quite common, then the number of function evaluations is almost in the range [30000, 100000]. In order to have a fair comparison of TribesPSO with the other algorithms the same number of function evaluations should be used, i.e. not larger than 100000. Thus, the average number of calls of MoveThen Adapt is about 1834 , if max number of function evaluations is 100000, and about 887 if the maximum number of function evaluations is 30000, as experimentally I found out by performing 100 experiments.

Besides, if we allow 10000 calls to MoveThenAdapt then the number of function evaluations is an enormous number. Note that with the restriction of function evaluations that I suggest the success rate is in the range [0.87, 0.96] , the best fitness value is in the range [4.3e-77, 3.7e-35] and the mean is in the range [0.04, 0.07].

John Tassopoulos, PhD student