Bug in the PSO toroidal topology

[xoanpardo]

I've noticed a minor bug in the createToroidalPattern method of the Particle class in the PSO implementation. The condition of the second for loop should be:

i < myindex + (neighborhoodSize / 2) + 1

instead of:

i < neighborhoodSize - (neighborhoodSize / 2) + 1

🐛

[SeanLuke]

Thanks. You say you've "noticed" it. I think you're right, but were you able to verify the error and the correction?

[xoanpardo]

Hi. Let me say that I'm using your PSO implementation to validate the results of my own implementation by running some tests and comparing the results with a two-sample Kolmogorov-Smirnov test. That's how I "noticed" the bug 😄.

After your comment, I did some more testing and I´ve realised that my correction does not work for odd neighborhood sizes. The right condition should be: i < myindex + (neighborhoodSize/2) + 1 + neighborhoodSize%2

For debugging I've added the following line to print the neighborhood after initializing it in the update method of the Particle class: state.output.message("Neighborhood[" + myindex + "]: " + Arrays.toString(neighborhood));

For example, the original output for a toroidal topology of 4 neighbors in a population of size 10 without including the particle in the neighborhood was:

Neighborhood[0]: [8, 9, 1, 2]
Neighborhood[1]: [9, 0, 2, 0]
Neighborhood[2]: [0, 1, 0, 0]
Neighborhood[3]: [1, 2, 0, 0]
Neighborhood[4]: [2, 3, 0, 0]
Neighborhood[5]: [3, 4, 0, 0]
Neighborhood[6]: [4, 5, 0, 0]
Neighborhood[7]: [5, 6, 0, 0]
Neighborhood[8]: [6, 7, 0, 0]
Neighborhood[9]: [7, 8, 0, 0]

and after the correction is:

Neighborhood[0]: [8, 9, 1, 2]
Neighborhood[1]: [9, 0, 2, 3]
Neighborhood[2]: [0, 1, 3, 4]
Neighborhood[3]: [1, 2, 4, 5]
Neighborhood[4]: [2, 3, 5, 6]
Neighborhood[5]: [3, 4, 6, 7]
Neighborhood[6]: [4, 5, 7, 8]
Neighborhood[7]: [5, 6, 8, 9]
Neighborhood[8]: [6, 7, 9, 0]
Neighborhood[9]: [7, 8, 0, 1]

After repeating my KS tests, which include both even and odd neighborhood sizes, with the corrected condition, some of the differences in the results have gone away, but other remain. I'm still in the process of thorougly reviewing both PSO implementations and until now, I've already found another two bugs in your Particle class, one in the createRandomPattern method and another in the updating of the neighborhood best in the update method. Both have to do with the special case the particle is not part of the neighborhood (i.e. breed.include-self = false).

Please, let me know how do you prefer to proceed. Should I open a new issue for each bug or maybe it would be better to change the title of this issue to something more general (e.g. bugs in the PSO implementation) and discuss all of them here.

[SeanLuke]

Either way is fine, but you might as well keep it all in the same thread. Just post new bugs here as you find them and I'll make the necessary changes.

[xoanpardo]

About the bug in createRandomPattern. The neighborhood for a population of size 5 with the following configuration:

breed.include-self = false
breed.neighborhood-style = random
breed.neighborhood-size = 4

is

Neighborhood[0]: [0, 1, 2, 4]
Neighborhood[1]: [3, 1, 0, 2]
Neighborhood[2]: [3, 0, 1, 2]
Neighborhood[3]: [0, 1, 3, 2]
Neighborhood[4]: [2, 3, 4, 1]

which includes the particle in the neighborhood contrary to what was configured. The bug is in the following if-else:

if (includeSelf)
    {
    neighbors = new int[neighborhoodSize + 1];
    neighbors[neighborhoodSize] = myIndex;  // put me at the top
    already.add(Integer.valueOf(myIndex));
    }
else
    neighbors = new int[neighborhoodSize];

The line already.add(Integer.valueOf(myIndex)); used to exclude the particle's id from the random selection is only executed when breed.include-self = true. The solution is to move it out of the if-else. The neighborhood after the correction is:

Neighborhood[0]: [4, 2, 3, 1]
Neighborhood[1]: [0, 2, 3, 4]
Neighborhood[2]: [1, 4, 3, 0]
Neighborhood[3]: [2, 0, 1, 4]
Neighborhood[4]: [3, 2, 1, 0]

[xoanpardo]

With regard to the bug related to the updating of the neighborhood best in the update method of the Particle class.

For debugging, I've added the following code at the end of the method:

double []fitnesses = new double[neighborhood.length];
for(int i = 0 ; i < neighborhood.length ; i++)
  fitnesses[i] = state.population.subpops.get(subpop).individuals.get(neighborhood[i]).fitness.fitness();
state.output.message("Fitnesses[" + fitness.fitness() + "]: " + Arrays.toString(fitnesses) + "-> " + neighborhoodBestFitness.fitness() + " (best: " + Arrays.stream(fitnesses).max().getAsDouble() + ")");

The following is the output of one iteration for a population of size 5 with random neighborhood of size 4 and breed.include-self = true:

Fitnesses[-4330.356132136232]: [-12085.426949919698, -22516.19764513911, -12172.016403418853, -72494.81758336417, -4330.356132136232]-> -4330.356132136232 (best: -4330.356132136232)
Fitnesses[-72494.81758336417]: [-12172.016403418853, -22516.19764513911, -4330.356132136232, -12085.426949919698, -72494.81758336417]-> -12085.426949919698 (best: -4330.356132136232)
Fitnesses[-12085.426949919698]: [-4330.356132136232, -72494.81758336417, -12172.016403418853, -22516.19764513911, -12085.426949919698]-> -4330.356132136232 (best: -4330.356132136232)
Fitnesses[-22516.19764513911]: [-12085.426949919698, -4330.356132136232, -12172.016403418853, -72494.81758336417, -22516.19764513911]-> -12172.016403418853 (best: -4330.356132136232)
Fitnesses[-12172.016403418853]: [-4330.356132136232, -12085.426949919698, -22516.19764513911, -72494.81758336417, -12172.016403418853]-> -12085.426949919698 (best: -4330.356132136232)

For three of the particles, the neighborhoodBestFitness (the value after the arrow) is different from the best (the maximum of the neighborhood). The bug is in the condition:

if (state.population.subpops.get(subpop).individuals.get(ind).fitness.betterThan(fitness))

that should be:

if (state.population.subpops.get(subpop).individuals.get(ind).fitness.betterThan(neighborhoodBestFitness))

In all the test I did after the correction, I got the right value.

[xoanpardo]

There is another (more subtle) bug in the the updating of the neighborhood best that only happens with breed.include-self = false. The following is the output for a particle in a population of size 5 with random neighborhood of size 4:

Fitnesses[-11553.072159344178]: [-15002.85670269305, -19417.964153984507, -14426.265734398221, -25498.27168064804]-> -11553.072159344178 (best: -14426.265734398221)

In this case, the neighborhoodBestFitness takes the value of the particle's fitness instead of the best in the neighborhood. The bug is in the initialization of neighborhoodBestFitness:

neighborhoodBestFitness = fitness;  // initially me
neighborhoodBestGenome = genome;

that will cause a wrong result if the particle is not in the neighborhood and its fitness is better than the best in the neighborhood. The solution could be to initialize neighborhoodBestFitness to the first neighbor (assuming the neighborhood is not empty) and starting the for loop from 1 instead of 0.

neighborhoodBestFitness = state.population.subpops.get(subpop).individuals.get(neighborhood[0]).fitness;  // initially the first neighbor
neighborhoodBestGenome = ((DoubleVectorIndividual)(state.population.subpops.get(subpop).individuals.get(neighborhood[0]))).genome;
for(int i = 1 ; i < neighborhood.length ; i++) { ... }

[SeanLuke]

I could tweak the pso code as necessary to make these fixes: or when you're ready you are welcome to submit a pull request.

[xoanpardo]

OK. I will submit a PR as soon as I finish debugging. I still get some different results in the KS tests.

[xoanpardo]

Finally I found the reason of the difference in the results of the KS tests. It is again related to the updating of the neighborhood best. In ECJ only the fitnesses of the current generation are considered in the updating:

if (state.population.subpops.get(subpop).individuals.get(ind).fitness.betterThan(fitness)) {
  neighborhoodBestFitness = state.population.subpops.get(subpop).individuals.get(ind).fitness;
  ...
}

whilst in my implementation the historical best is used (i.e. what in ECJ would be personalBestFitness instead of fitness). After changing the ECJ implementation to use the historical best, the KS tests are successful. Whether to consider this a bug or not depends on the interpretation of "best in the neighborhood". As far as I know, the interpretation I'm using is the most usual in the literature about PSO. Changing the ECJ implementation to use the historical best requires to update the personal best of all the particles before updating the neighborhood best. I implemented it by splitting the update method in two, one for the personal best and another for the neighborhood best (which I named updateNeighborhood), and adding a new loop to the breedPopulation method of PSOBreeder to update the neighborhood best :

 // update global best and personal best
for(int ind = 0; ind < state.population.subpops.get(subpop).individuals.size() ; ind++) { ... }
// update neighborhood best
for(int ind = 0; ind < state.population.subpops.get(subpop).individuals.size() ; ind++)
  ((Particle) state.population.subpops.get(subpop).individuals.get(ind)).updateNeighborhood(state, subpop, ind, 0);

I'm now ready to submit the PR, but first I would like to know if you agree with this "change in interpretation" or if you would prefer not to include it in the PR.

[eclab]

In this case it would be probably best to specify which approach to take using an ECJ parameter. I can get that arranged, all you need to do for now is add a boolean to PSOBreeder.java. For now you can hard-code the boolean to your preference. I can add the logic in setup() to set it from a parameter file.

Sean

On Apr 1, 2023, at 11:27 AM, xoanpardo @.***> wrote:

Finally I found the reason of the difference in the results of the KS tests. It is again related to the updating of the neighborhood best. In ECJ only the fitnesses of the current generation are considered in the updating:

if (state.population.subpops.get(subpop).individuals.get(ind).fitness.betterThan(fitness)) { neighborhoodBestFitness = state.population.subpops.get(subpop).individuals.get(ind).fitness; ... } whilst in my implementation the historical best is used (i.e. what in ECJ would be personalBestFitness instead of fitness). After changing the ECJ implementation to use the historical best, the KS tests are successful. Whether to consider this a bug or not depends on the interpretation of "best in the neighborhood". As far as I know, the interpretation I'm using is the most usual in the literature about PSO. Changing the ECJ implementation to use the historical best requires to update the personal best of all the particles before updating the neighborhood best. I implemented it by splitting the update method in two, one for the personal best and another for the neighborhood best (which I named updateNeighborhood), and adding a new loop to the breedPopulation method of PSOBreeder to update the neighborhood best :

// update global best and personal best for(int ind = 0; ind < state.population.subpops.get(subpop).individuals.size() ; ind++) { ... } // update neighborhood best for(int ind = 0; ind < state.population.subpops.get(subpop).individuals.size() ; ind++) ((Particle) state.population.subpops.get(subpop).individuals.get(ind)).updateNeighborhood(state, subpop, ind, 0); I'm now ready to submit the PR, but first I would like to know if you agree with this "change in interpretation" or if you would prefer not to include it in the PR.

— Reply to this email directly, view it on GitHub https://github.com/GMUEClab/ecj/issues/82#issuecomment-1493005285, or unsubscribe https://github.com/notifications/unsubscribe-auth/ADAZDVHCSL3BOOSO6GM6WSLW7BCMTANCNFSM6AAAAAAWMMO6UE. You are receiving this because you are subscribed to this thread.