Checklist
Bug Description
When the archieve size is too small to store the non-dominated solutions, the truncation operator is supposed to remove solution one by one based on the distances of between those solutions in the lexicographical order (the smallest first), see the second paragraph of Section 3.2 of the orignal paper.
In the current SPEA2Survival._do method, the blob around lines 104-106 is:
while len(survivors) > n_survive:
i = dists[survivors][:, survivors].min(axis=1).argmin()
survivors = [survivors[j] for j in range(len(survivors)) if j != i]This only removes an arbitrary individual (the argmin part) with the smallest distance to its nearest neighbours (the min part), thus the tie-breaking based on the second, third, etc smallest distances are not applied. The correct code should be more like this:
while len(survivors) > n_survive:
survdists = np.sort(dists[survivors][:,survivors], axis=1).tolist()
i = min(range(len(survdists)), key=survdists.__getitem__)
survivors = [survivors[j] for j in range(len(survivors)) if j != i]Here we first sort the distances between the non-dominated solutions row by row, and convert this matrix to a list of lists in Python. This allows Python's min() function in the next line to directly locate the minimum in the lexicographical order.
A minor comment (this is not a bug fix but a simplification): Non-dominated solutions are those with raw fitness of 0, thus line 82 can be simplified to:
survivors = np.where(R==0)[0].tolist()
Minimal Code to Reproduce
import numpy as np
from pymoo.util.dominator import Dominator
from pymoo.util.misc import vectorized_cdist
F = np.array([[2,0],[1,1],[0,2]])
n_survive = 2 # expect SPEA2 to keep the two extreme solutions indexed 0 and 2 in F
M = Dominator().calc_domination_matrix(F)
dists = vectorized_cdist(F, F, fill_diag_with_inf=True)
survivors = list(np.where(np.all(M >= 0, axis=1))[0])
# the buggy part
while len(survivors) > n_survive:
i = dists[survivors][:, survivors].min(axis=1).argmin()
survivors = [survivors[j] for j in range(len(survivors)) if j != i]
print(F[survivors])Error Message
The output is [[1 1] [0 2]], in other words we lose the extreme solution with fitness [2,0] as it is the first one appears in F. Consequently, extreme non-dominated solutions are not guaranteed to be kept as originally designed. I guess this is the reason that some forcing was put in lines 85-87 but only when the normalize option is turned on...
Replacing the buggy part with the suggested fix should indeed keep the extreme solutions.
PyMoo & Python Version
Python 3.10.12 and PyMOO 0.6.1.6
Checklist
Bug Description
When the archieve size is too small to store the non-dominated solutions, the truncation operator is supposed to remove solution one by one based on the distances of between those solutions in the lexicographical order (the smallest first), see the second paragraph of Section 3.2 of the orignal paper.
In the current SPEA2Survival._do method, the blob around lines 104-106 is:
This only removes an arbitrary individual (the argmin part) with the smallest distance to its nearest neighbours (the min part), thus the tie-breaking based on the second, third, etc smallest distances are not applied. The correct code should be more like this:
Here we first sort the distances between the non-dominated solutions row by row, and convert this matrix to a list of lists in Python. This allows Python's min() function in the next line to directly locate the minimum in the lexicographical order.
A minor comment (this is not a bug fix but a simplification): Non-dominated solutions are those with raw fitness of 0, thus line 82 can be simplified to:
Minimal Code to Reproduce
Error Message
The output is
[[1 1] [0 2]], in other words we lose the extreme solution with fitness[2,0]as it is the first one appears in F. Consequently, extreme non-dominated solutions are not guaranteed to be kept as originally designed. I guess this is the reason that some forcing was put in lines 85-87 but only when thenormalizeoption is turned on...Replacing the buggy part with the suggested fix should indeed keep the extreme solutions.
PyMoo & Python Version
Python 3.10.12 and PyMOO 0.6.1.6