Closed riven521 closed 2 years ago
Remember that i
here iterates through the sorted decreasing ranking
so it represents the ith
largest distance individual. ranking[i].second
represents the pos of that same individual in the fitness sorted population.
Thanks a lot, @TheIronBorn for following up and providing a very concise explanation.
The code in the current form is indeed correct: the individuals in pop
are kept sorted by increasing penalized objective, therefore ranking[i].second
provides the rank of the considered individual in terms of objective (fitRank). Moreover, since we perform a sort by diversity contribution in ranking, ranking[i] will correspond to the i^th best individual in terms of diversity contribution.
Thanks for your reply~ @vidalt @TheIronBorn
As mentioned in the paper "Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood.", the fitness in HGS is based on objective value and diversity considerations with formula (1).
The diversity is measured as its average broken-pairs distance; We found the calculation of diversity rank in the function updateBiasedFitnesses() is as follows:
double divRank = (double)i / (double)(pop.size() - 1);
while the solution quality isdouble fitRank = (double)ranking[i].second / (double)(pop.size() - 1);
Are these two calculations reversed? Maybe it should be:
double divRank = (double)ranking[i].second / (double)(pop.size() - 1);
double fitRank = (double)i / (double)(pop.size() - 1);
since the ranking store the averageBrokenPairsDistance
ranking.push_back({-pop[i]->averageBrokenPairsDistanceClosest(params->nbClose),i});